Al Zimmermann: non-coplanar points

[ctac]

Pavlovsky в сообщении #1117546 писал(а):

ctac в сообщении #1117540 писал(а):

Через центр проходит больше всего плоскостей.

Vovka17 приводит противоположные цифры.

Я искал все плоскости проходящие через каждую из точек (3 и более точек)

Vovka17 искал несколько иначе:

Цитата:

Вот мои значения количества значимых плоскостей (содержащих 4 и более точек), проходящих через точки куба

может так и правильнее

[Vovka17]

Я полагал, что если через точку проходит плоскость содержащая ровно 3 точки, то эту плоскость можно не учитывать, ведь присутствие точки на такой плоскости не может вызвать ошибку.
Однако, несмотря на такие мои рассуждения, ваши ctac результаты мне больше нравятся. Они совпадают с тем, что мы видим в решениях. Пока не могу объяснить для себя и понять почему так.

[Pavlovsky]

Все равно непонятно. Для N=7 и решения из 18 точек, надо чтобы через каждую точку решения проходило всего 136 плоскостей. А через любую точку куба (угловую, центральную и прочие) проходит тысячи плоскостей. Запас просто гигантский!

[dimkadimon]

Вот картинка моего решения для n=13, p=31:

[ctac]

Pavlovsky в сообщении #1117583 писал(а):

Для N=7 и решения из 18 точек, надо чтобы через каждую точку решения проходило всего 136 плоскостей.

Поясните, пожалуйста, как Вы пришли к этому.

[Pavlovsky]

Выберем точку. Каждая пара точек из оставшихся 17 точек образует с выбранной точкой 17*16/2=136 плоскостей.

[Pavlovsky]

Tim Foden
https://chessprogramming.wikispaces.com/Tim+Foden

Круто!

-- Ср апр 27, 2016 10:37:06 --

Если Tim Foden для текущей задачи применяет свой опыт написания шахматных программ, то вопрос о первом месте уже решен.

Современные шахматные программы, для оценки текущей позиции используют специальные таблицы. Эти таблицы формируются на основе статистики уже сыгранных партий или собственного анализа позиций. То есть таблицы постоянно совершенствуются в процессе анализа позиций. Идет процесс самообучения программы!!

-- Ср апр 27, 2016 10:42:20 --

Самообучающаяся программа за 72 часа освоила шахматы на уровне гроссмейстера
http://hitech.newsru.com/article/15sep2015/giraffe

Программа впервые обыграла человека в игру, которая считалась недоступной для компьютерного интеллекта
http://hitech.newsru.com/article/28jan2016/alphago

[Vovka17]

Если бы Tim Foden был автором приведенных примеров (Giraffe, AlphaGo), тогда да. А программа Тима - Green Light Chess, кажется ничем особенным не выделяется из сотен других шахматных программ. Хотя, само по себе написать хорошо играющую шахматную программу - не просто.

(Оффтоп)

Сам я несколько лет занимался написанием шашечной программы. (Я - шашист и мне это гораздо интереснее, чем шахматы). Времени на это надо много, очень много. А заниматься этим всегда некогда. Поэтому все мои наработки в области программирования шашек остались на уровне недоделанного кода и хобби отложенного "примерно до пенсии" .
В написании шахмат та же история, только теории разработано побольше. Хотя это быть может и мешает. Ведь создатель Giraffe создал совершенно новый тип программы, и понять как она у него работает - было бы очень интересно...

Я вижу лишь то, что его подход к решению текущей задачи оптимальный. И пока никто не додумался до того, что придумал он. Возможно и не додумается уже. Но такие же разговоры недавно были и о Tomas Rokicki ...

[dimkadimon]

Pavlovsky в сообщении #1118515 писал(а):

Tim Foden
https://chessprogramming.wikispaces.com/Tim+Foden

Круто!

Да круто. Хотя, если погуглить про других участников в топ-5 то убедитесь что они тоже "непростые" программисты. Единственное что я из это для себя понял это то что Тим очень хорошо умеет оптимизировать код и хорошо знаком с хэшами. Возможно это поможет.

(Оффтоп)

Для своей PhD я разрабатывал программу по игре в Го. Тогда (в 2008) она была в топ-5 по игре на маленькой доске 9х9. Игра на доске 19х19 казалась невозможной. Я думал что потребуются десятки лет чтобы сравниться с чемпионами мира. В то время я познакомился с David Silver. Он разрабатывал программу на основе Reinforcement Learning. Никто не верил что этот метод может дать тот нужный толчок на победу. В прошлом году David объединил свой метод с Deep Learning и все заработало. Он создал AlphaGo которая обыграла чемпиона мира. Просто сенсация!

[dimkadimon]

Что если взять решение и прокрутить его на несколько градусов вокруг всех трех осей? Мы должны получить эквивалентное решение по количеству ошибок*, но теперь наши точки не будут лежать на целых координатах. Теперь берем каждую точку и присваиваем ее к самой близкой целой координате. Что можно сказать про новое решение? Может ли оно быть лучше оригинального по количеству ошибок?

* Потому что отношения между точками не изменились, а значит плоскости тоже.

[ctac]

dimkadimon в сообщении #1118913 писал(а):

Мы должны получить эквивалентное решение по количеству ошибок

Вы имеете ввиду взять решение изначально содержащее ошибки?

Цитата:

наши точки не будут лежать на целых координатах

А также могут выйти вообще за пределы куба и вернуть их надо будет не к самой близкой целой координате а куда-нибудь в куб

[dimkadimon]

ctac в сообщении #1118923 писал(а):

Вы имеете ввиду взять решение изначально содержащее ошибки?

Да

ctac в сообщении #1118923 писал(а):

А также могут выйти вообще за пределы куба и вернуть их надо будет не к самой близкой целой координате а куда-нибудь в куб

Такие случаи можно просто исключить.

[Vovka17]

dimkadimon в сообщении #1118642 писал(а):

Единственное что я из это для себя понял это то что Тим очень хорошо умеет оптимизировать код и хорошо знаком с хэшами. Возможно это поможет.

Я принципиально не занимаюсь оптимизацией. Лишь иногда правлю что-то, если это вызовет рост скорости на порядки. И кодю на далеко не самом быстром C#. Всё лишь по той причине, что прирост скорости (даже в разы) никак не позволит мне догнать лидеров. А значит надо все усилия направлять на разработку новых алгоритмов, а не на оптимизацию посредственных старых.

dimkadimon в сообщении #1118913 писал(а):

Что если взять решение и прокрутить его на несколько градусов вокруг всех трех осей?

В вашем подходе есть один большой плюс - точки в решении переставляются все вместе, что очень хорошо учитывая "их связанность". Но подозреваю, что наш куб, при большом количестве точек, уж очень сильно пересечен плоскостями и любое "шаг влево шаг вправо" для точки вызовет всплеск ошибок. И после поворота её координаты просто некуда будет округлить. Кстати, почему вы хотите "крутить решение на несколько градусов"? Ничто не запрещает его крутить на сколько угодно градусов.

[dimkadimon]

Vovka17 в сообщении #1119205 писал(а):

Кстати, почему вы хотите "крутить решение на несколько градусов"? Ничто не запрещает его крутить на сколько угодно градусов.

Ну это я так для простоты сказал. На самом деле я пробовал поворачивать на все возможные градусы и не получил особо хороших результатов. Это обидно потому что идея в принципе неплохая. Надо найти такую мутацию которая меняет сразу много точек и не дает много новых ошибок.

Кстати вот вопрос: есть ли смысл находить решения для непростых N? Ведь из решения N можно найти решение N+2 передвинув все точки на один шаг.

[ctac]

dimkadimon в сообщении #1119240 писал(а):

Это обидно потому что идея в принципе неплохая. Надо найти такую мутацию которая меняет сразу много точек и не дает много новых ошибок.

А как насчет мутации типа "zoom" - т.е. все точки разбегаются от центра или может от угла куба (0,0,0)? А потом увеличить куб до ближайшего простого числа?