Типовой способ решения задач, на подобие поиска хорошего хода в логических играх, это метод полного перебора. Он гарантирует результат, однако быстро упирается в производительность компьютера и допустимое время ожидания.
При игре в шашки для поиска ответного хода отлично себя зарекомендовал метод минимакса. Суть его в том, что при анализе возможных ходов выбирается лучший ход для каждой из сторон.
Например, если у белых имеется три допустимых хода, то чтобы выбрать лучший, нужно сымитировать первый ход и оценить новую позицию (5). Затем определить ответы черных и оценить результаты каждого из них. Выбрать наибольшую (лучшую для черных) оценку (2) и вычесть ее из оценки предыдущего хода белых (5 - 2). Эти же действия повторить для второго и третьего ходов белых. В конце выбрать ход с наибольшей (лучшей для белых) оценкой (3).
Если поменять знак в оценочной функции, то бот станет играть в поддавки.
Алгоритм работает прекрасно, но быстро упирается в производительность. При глубине анализа в 8 - 9 полуходов (полуход - действие за одну из сторон) происходит более миллиона вычислений позиций. И с увеличением глубины на один шаг вычисления возрастают в 5 - 10 раз.
Здесь на помощь приходит оптимизация под названием альфа-бета отсечение.
Рассмотрим еще раз пример работы минимакса. Обратите внимание, что после оценки первого хода белых для всех последующих можно выбирать значения с уровня черных, не дожидаясь самого лучшего. Потому что как только оценка второго хода белых станет хуже первого, вычисления можно прекращать, так как все последующие ходы черных будут ее только уменьшать (помните, что минимакс выбирает наилучший ход на каждом уровне).
Альфа-бета отсечение чувствительно к начальному порядку ходов и в худшем случае вырождается в обычный перебор.
В шашках применение альфа-бета оптимизации в среднем уменьшает вычисления в 10 - 20 раз, что позволяет увеличить глубину анализа на 2 - 4 полухода при тех же затратах времени и процессора.
Пример практического решения в игре E-Champ Шашки.
Демонстрация игры доступна на сайте e-champ.