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

Question

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

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

Answer 1

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

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

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

Удачи.

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

, если вы заинтересованы в обучении, как написать C# движок Я приглашаю вас посетить Computer Chess Blog

В блоге описывает создание C# движка от первых шагов, обеспечивая C# примеры кода.

Страница, которую вы могли бы быть наиболее заинтересованы в том: Move Searching and Alpha Beta

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