Реализация минимаксного дерева C #

Question

Я пытаюсь написать C # Chess AI.

В этот момент мне нужно построить дерево минмакс. Я пытаюсь использовать рекурсию, но мои рекурсивные функции должны вызывать себя около 1 000 000 раз для каждого узла. Я получаю исключение переполнения стека после примерно ... 60 000 звонков.

Answer 1

Я полагаю, вы используете поиск в глубину. Это не слишком полезно, когда пространство поиска слишком велико. При реализации минимакса вы можете использовать поиск в ширину, реализованный как поиск в глубину с итеративным углублением .

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

Answer 2

Если вы заинтересованы в изучении написания шахматного движка на C #, я приглашаю вас посетить Компьютерный шахматный блог

Блог описывает создание C # Chess Engine с первых шагов, предоставляя примеры кода на C #.

Страница, которая может вас заинтересовать: Поиск по ходу и альфа-бета

В этой статье дается подробное объяснение алгоритмов поиска Min Max и Alpha Beta, включая примеры обоих кодов C #.

Answer 3

Большинство шахматных поисковых программ могут осуществлять поиск только до глубины 9 или 10. Этого недостаточно для переполнения стека.

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

После поиска до глубины 9 вам необходимо использовать функцию оценки статической доски для оценки и оценки позиции. Затем вы используете алгоритм mini-max для обрезки ветвей дерева поиска. Это все еще экспоненциальный поиск.

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

Answer 4

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

Как подтверждают другие, похоже, что у вас, вероятно, есть ошибка с учетом большого количества итераций.Может быть возможно сократить множество правил или выбрать другую стратегию поиска, чтобы уменьшить количество требуемых итераций, например итеративное углубление , A * или, возможно, Генетический алгоритм в шутку,

Было бы гораздо лучше вернуть результат, даже если он не идеален, а не потерпеть неудачу после слишком глубокого поиска в дереве.

Удачи.