Что представляет собой современное состояние поиска компьютерных шахмат?

Question

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

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

Спасибо.

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

Answer 1

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

Answer 2

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

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

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

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

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

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

Добавление Основная вариация поискового запроса h Техника для альфа-бета может дать вам дополнительный 10-процентный импульс.

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

Answer 3

Движения убийцы - хороший пример небольшого размера кода и большого улучшения в перемещении заказов.

Answer 4

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

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

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

Answer 5

MTD(f) или один из MTD variants является значительным улучшением по сравнению со стандартной alpha-beta, предоставляя вам не очень тонкие детали в вашей функции оценки и предполагая, что вы используете killer heuristic. Также полезен history heuristic.

Самая рейтинговая шахматная программа Rybka, по-видимому, оставила MDT (f) в пользу PVS с окном нулевой аспирации на не-PV узлах.

Extended futility pruning, который включает в себя как нормальную обрезку, так и глубокое разбрасывание, теоретически необоснован, но замечательно эффективен на практике.

Iterative deepening - еще одна полезная техника. И я перечислил много good chess programming links here.

Answer 6

Одна эвристика, о которой не упоминалось, является Null move pruning.

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

Answer 7

Я мог бы быть немного не по теме, но «состояние художественные "шахматные программы используют MPI, такие как Deep Blue для массивной параллельной власти.

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

Answer 8

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

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