Представление позиции

Интересно было посмотреть, что люди применяют для представления позиции. Судя по всему, сейчас два основных подхода: 0x88 и бинборды (имени Хьятта). А что еще эффективное придумано? Да и эти два подхода хочется обсудить не на уровне, как в статье Хьятта, а на уровне всех тонкостей именно приложений.

Я знаю, что NS работает с 0x88. На нем же написан Фрукт. Крафтя использует бинборды и не сильно вырвалась (хотя и прибавила) на Оптеронах. Я понял так, что оценочная функция считается все равно дольше (чем генерация ходов, которая впрямую связана с представлением позиции) и простота 0x88 дороже скорости бинбордов (которая к тому же сомнительна). Однако Хьятт уверяет, что ОФ лучше тоже на бинбордах... Так ли это?

Хочется почитать мнения!

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

Что действительно важно - это алгоритмы поиска, сортировка ходов. Уменьшение ветвистости дерева даёт выигрыш несравнимый с копейками, которые можно наскрести на оптимизации генератора ходов...

Ключевое слово в данной фразе предлагается найти в качестве самостоятельного упражнения

Не забудем также, что скорость программы не равна скорости генератора ходов, взятого в отдельности. Хьятт, например, приводил данные профилировки Крафти - там было примерно 50 на 50 времени CPU между поиском и оценкой.

Дано: медленный, но отлаженный генератор ходов - против быстрого, но с глюками.
Оценить возможный разброс рейтингов

Кстати, можно действительно интересный эксперимент поставить.
Запрещаем, скажем, генератору генерить ход Nf3-e5 - один-единственный. И смотрим, насколько в длинном матче с правильной версией это скажется.

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

так вот, идея - глупость, но есть рациональное зерно - рассматривть особо странные ходы в последнюю очередь. Ходы типа Кр гэ2 на аш1 без взятия и при отсутствии угрозы королю. правда, можно сконструировать позицию, где именно этот ход будет выигрывать.

ну как, глупая идея?

Идея вполне работоспособная. Примерно так и работает эвристика истории - только, вдобавок, "ненужность" ходов определяется динамически, по статистике, уже накопленной в поиске к данному моменту.

кстати, а когда вы в движках реализуете обучение? а то неприятно иногда смотреть, когда из 20 партий совпадают вдруг по дебюту партии, и, как следствие, и все остальное.

За себя отвечу - два года назад.

и по теме надо заметить, что существуют и другие способы представления позиции - 10*8, 12*12 и еще какие-то... то есть доска расширяется для того чтобы легче было генерировать ходы. типа.

Самое правильное представление позиции было в Deep Blue - аппаратное

Прошу вернуться в тему! Какие еще есть идеи представления позиции? Кроме битбордов (сорри за описку - я все же совсем чайник в этой области и путаю Архангельск с Астраханью).

Согласен, 0x88 - самое простое и лучшее для начала.
Насчёт битбордов - там тоже есть разные уровни сложности. В GNUChess и GreKo используются битборды в простом варианте - с массивом промежуточных полей для проверки заграждающих фигур. В Crafty - более сложный вариант, rotated bitboards. Они существенно быстрее для генерации ходов, но требуют больше предварительных вычислений.

Насколько больше памяти расходуют битборды?

Неужели никто не пробовал иные подходы? Мне в голову пришло по крайней мере пяток, как мне кажется, многообещающих вариантов. А все что я вижу это лишь 0x88 или битборды

Важно еще чтобы легко потом было писать ОФ. То есть легко просмотреть взаимодействие фигур, ведь иначе надо оценивать каждую поотдельности. А как анализировать взаимодействие?..

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

bankuss, спасибо!!! А какая сила твоей программы. Открыты ли исходники? На каком языке написана?

И почему ты не стал делать 0x88?

Если бы я когда-либо делал программу, то начал бы, скорее всего, с представления 4 бита на клетку (в С это не проблема). Есть еще одна идея, но, скорее всего, чайнико-безумная Но я бы и ее попробовал. Ради интереса