2010-05-27 2 views
6

Как часть домашнего задания, я должен запрограммировать простую шахматную игру на Java. Я собирался воспользоваться возможностью экспериментировать с рекурсией, и мне было интересно, есть ли очевидный кандидат в шахматы для рекурсивного кода?Хорошее использование рекурсии в шахматном программировании?

+1

Все, что связано с деревьями. – 2010-05-27 12:20:29

+0

Одна из моих первых программ Java (в 1998 году) была шахматной программой, использующей рекурсивный минимаксный алгоритм, о котором упоминает Лаплас ниже. Это, безусловно, интересный проект по изучению Java и рекурсии. – Jesper

+0

www.m-w.com говорит, что рекурсия не является верным английским словом. Отредактированное название. – 2010-05-28 04:05:48

ответ

7

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

Пример:

http://www.devshed.com/c/a/Practices/Solving-Problems-with-Recursion/6/

+0

Я даже думаю, что нет альтернативы рекурсивному minmax (если идея заключается в разработке KI) –

+0

Также полезна эта ссылка, объясняющая альфа-бета http://www.fierz.ch/strategy1.htm –

+0

Вау, это отличная статья. Похоже, что это метод, который будет использоваться по-разному на разных этапах. Возможно, будет одна версия для mate и одна версия для какой-то другой цели (например, захват части), каждая с разной глубиной. Хммм ... Весело. – JDelage

1

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

Будьте осторожны: вы можете быстро разрядиться. Вероятно, вы хотите ограничить количество движений, которые ИИ может посмотреть.

3

Да, есть. Если у вас есть функция, которая оценивает «силу» какой-либо позиции для белого игрока. Вы можете переместить кусок и называть его рекурсивно, чтобы оценить значение хода и выбрать лучший ход.

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

Затем снова для белых и т.д.

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

+0

Спасибо. Мне просто нужно найти хорошую логику для ценности каждого движения. – JDelage

1

Ум dynamic programming, так как у вас есть несколько комбинаций, которые приводят к одной и той же доске, вы должны помнить, чтобы кэшировать шаги для того, чтобы избежать повторения вычислений

Если вы обнаружили рекурсию только приведет вас к месту, где у вас есть был, просто сломал этот звонок. Это известно как backtracking