Каков современный уровень поиска компьютерных шахматных деревьев?

Question

Меня не интересуют крошечные оптимизации, дающие несколько процентов скорости. Мне интересны самые важные эвристики для альфа-бета-поиска. И самые важные компоненты для функции оценки.

Меня особенно интересуют алгоритмы, которые имеют наибольшее соотношение (улучшение / code_size). (НЕ (улучшение / сложность)).

Спасибо.

PS Эвристика Killer Move - прекрасный пример - простой в реализации и мощный. База данных эвристики слишком сложна.

Answer 1

Не уверен, если вы уже знаете об этом, но посмотрите Шахматное программирование Wiki - это отличный ресурс, который охватывает почти все аспекты современного шахматного ИИ. В частности, что касается вашего вопроса, см. Разделы «Поиск и оценка» (в разделе «Основные темы») на главной странице. Вы также можете обнаружить некоторые интересные приемы, используемые в некоторых из перечисленных программ здесь . Если на ваши вопросы по-прежнему нет ответов, я бы определенно рекомендовал вам задавать вопросы на Шахматных форумах по программированию , где, вероятно, будет гораздо больше специалистов, чтобы ответить. (Не то, чтобы вы не обязательно получили здесь хорошие ответы, просто это скорее на тематических форумах экспертов).

Answer 2

MTD (f) или один из вариантов MTD - это значительное улучшение по сравнению со стандартным альфа-бета , если у вас нет действительно мелких деталей в вашей функции оценки и при условии, что вы используете эвристический убийца . история эвристики также полезна.

Шахматная программа с самым высоким рейтингом Рыбка явно отказалась от MDT (f) в пользу PVS с окном с нулевой аспирацией на узлах без PV.

Расширенная обрезка бесполезности , которая включает в себя как обычную обрезку бесполезности, так и глубокую бритву, теоретически несостоятельна, но удивительно эффективна на практике.

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

Answer 3

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

Иногда эти эвристики могут возвращать плохой (я имею в виду не лучший) ход.

Люди, с которыми я говорил, всегда рекомендуют оптимизировать альфа-бета-поиск и реализовывать итеративное углубление в коде, а не пытаться добавить другие эвристики.

Основная причина в том, что вычислительная мощность компьютеров возрастает, и исследования [нуждаюсь в цитировании, я полагаю] показали, что программы, использующие свое полное время ЦП для грубой форсировки дерева альфа-бета до максимальной глубины, всегда опережали программы, которые делят свое время между определенными уровнями альфа-бета и некоторыми эвристиками.

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

Я уверен, что вы знаете, что для того, чтобы альфа-бета работала в точности так, как она должна работать, у вас должен быть механизм сортировки ходов ( итеративное углубление ). Итеративное углубление может дать вам около 10% прироста производительности.

Добавление Принципиальная вариация Searc ч техника альфа-бета может дать вам дополнительный 10% -ный прирост.

Попробуйте также алгоритм MTD (f ). Это также может повысить производительность вашего двигателя.

Answer 4

Использование таблицы транспонирования с хешем zobrist

Требуется очень мало кода, чтобы реализовать [один XOR на каждый ход или движение, и оператор if перед повторением в дереве игры], и преимущества довольно хороши, особенно если вы уже используете итеративное углубление, и это довольно настраиваемый (используйте больший стол, меньший стол, стратегии замены и т. д.)

Answer 5

Одна эвристика, которая не была упомянута, - Обрезка нулевого хода .

Кроме того, у Эд Шредера есть отличная страница, объясняющая ряд трюков, которые он использовал в своем движке Rebel, и насколько каждый из них улучшил скорость / производительность: Inside Rebel

Answer 6

Возможно, я немного не в теме, но в современных шахматных программах MPI, например Deep Blue, используется для массивной параллельной мощности.

Только подумайте, чем параллельная обработка играет большую роль в современных шахматах

Answer 7

Большинство алгоритмов ИИ настольной игры основаны на http://en.wikipedia.org/wiki/Minmax MinMax. Цель состоит в том, чтобы минимизировать их варианты, максимизируя ваши варианты. Хотя с шахматами это очень большая и дорогая проблема времени выполнения. Чтобы уменьшить это, вы можете объединить minmax с базой данных ранее сыгранных игр. Любая игра с похожей позицией на доске и с шаблоном, определяющим, как этот макет был выигран за ваш цвет, может использоваться для «анализа» того, куда двигаться дальше.

Я немного озадачен тем, что вы подразумеваете под улучшением / code_size. Вы действительно имеете в виду улучшение / анализ времени выполнения (большие O (n) против o (n))? Если это так, поговорите с IBM и Big Blue, или с командой Microsoft Parallels. В PDC я разговаривал с парнем (имя которого теперь ускользает от меня), который демонстрировал маджонг, используя по 8 ядер на противника, и они заняли первое место в конкурсе разработки алгоритмов игры (имя которого также ускользает от меня).

Я не думаю, что существуют какие-либо «законсервированные» алгоритмы, чтобы всегда выигрывать в шахматы и делать это очень быстро. Чтобы сделать это, нужно, чтобы КАЖДАЯ возможная ранее сыгранная игра была проиндексирована в очень большой базе данных на основе словаря и предварительно кэшировала анализ каждой игры. Это будет ОЧЕНЬ сложный алгоритм и, на мой взгляд, очень плохая проблема улучшения / сложности.

Answer 8

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