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

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

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

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

 

не бинборды а битборды от bitboard
на 64-битниках битборды однозначно быстрей работают. а в целом все зависит от общего устройства программы + квалификация программиста - битборды сложней программить, так что здесь 0х88 выигрывает.
я в своем движке не использую ни то ни другое у меня свое представление - код получился большой правда, но зато все просто и достаточно быстро.

 

Рыбка работает на bitboards

 

В 2 раза меньше быстродействие, при нормальных алгоритмах - это -70 пунктов силы...

 

Я могу проверить на Гаунлетах, но у меня близко к этой цифре. Так что ключевое слово вроде подходит
А +70 - Это достаточно много.

 

Если запретить за себя - то не очень сильно, а вот ежели запретить за соперника - то пойдут зевки...
У меня было хуже - были запрещены взятия, но повезло, что редко встречающиеся. Стоила эта ошибка в районе 30-50 пунктов. (то есть 60-100 пунктов при игре черными)

 

То есть наверно не так 10-20 при игре Белыми и 50-80 При игре черными. Но я проверял изменение силы только суммарно, то есть изменение рейтинга по моей базе движка с ошибкой и без.

 

У меня перед заполнением таблиц для Зобриста делается Randomize() - так что небольшое разнообразие есть Для обучения - можно использовать функцию обучения в оболочке.

 

Это всё модификации 0x88

 

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

 

Лучше начинать с простого. Самое простое и достаточно быстрое это 0x88. На порядок проще писать и оценку, и генератор, и проверку на шах.

 

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

 

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

 

Ни на сколько.... Память тратится на ХЕШ таблицы. Так что тратится её одинаково.
Единственное отличие в трате памяти - Под битБорды иногда (чаще?) используют ХЕШ пешечных структур, но на него нет смысла отводить много памяти (не так много различных расположений пешек случается в переборе)

 

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

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

 

Как это не пробовал? Пробовал конечно.
Но... Небитовые генераторы и т.д. упираются в КОЛИЧЕСТВО ОБРАЩЕНИЙ К ПАМЯТИ, а в 0x88 оно минимизировано

 

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

 

У всех процессоров разная Архитектура. Представление позиции всегда влезает в КЕШ, поэтому достаточно оптимизировать количество обращений к памяти, остальное процессор сделает сам.
Но Кеш - Это не регистровая переменная. Он всё-равно работает медленней.

 

atoku У меня иное предствление одномерный массив 0...63
так что ты не прав - не все держится на битбордах и 0х88
и все сделано через память (и вроде тормозов не видно) чистая скорость без make\unmake на P4-3000 в начальной позиции ~22 млн.ходов в секунду. но главное конечно в генераторе - это безглючность а не скорость.

 

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

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

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

 

atoru - сила небольшая... переборщик у меня простой, без наворотов. может на 1800 играет...не знаю, не мерял. написал на VB2005.Net, язык не очень шустрый (как и весь Net), но для экспериментов потянет Исходников не открывал, так как Net-exe можно глядеть одной программкой