Каково современное состояние поиска компьютерного шахматного дерева?

Ответ 1

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

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

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

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

Ответ 4

Одна эвристика, о которой не упоминалось, Нулевая обрезка.

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

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

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