Программирование шахамат
1. Постановка задачи
2. Основные компоненты шахматной программы
Сразу нужно определится с минимальными требованиями для шахматной программы. То есть, что необходимо любой из них, чтобы противостоять человеку. Среди них можно выделить нижеследующие:
То есть "объяснить" железному другу как в данной ситуации ходить можно, а как запрещено.
Цель - предоставить компьютеру средства для выбора из всевозможных доступных ходов одного.
Это необходимо для того, чтобы в результате анализа был выбран лучший в каком-то смысле ход.
Представление данных
Каждый из нас по-разному воспринимает входную информацию. На полотне Леонардо Да Винчи один человек может увидеть Джоконду, другой сто долларовую купюру, третий тещу (или зятя). То же самое и в шахматах. Два соперника во время игры могут видеть совершенно "разные" позиции в один момент времени.
Так чем же компьютер должен отличаться от человека, спросите вы? Ничем. Компьютерные программы, как и люди, не похожи друг на друга: "мыслят" и хранят информацию они по-разному. Но всё же одни из них играют лучше, другие хуже. В чём секрет? По поводу компьютерного "мышления" мы ещё поговорим ниже, а сейчас коснёмся темы хранения данных.
В программировании очень важно правильно выбрать представление данных.
Я думаю, что любой человек в состоянии придумать какой-нибудь способ отображения текущей информации на шахматной доске. Например, можно представить шахматную доску как таблицу (массив) размерами 8х8, где пустой клетке соответствует число - 0, белому королю - 1, и т.д. Увы, у этого способа наряду с преимуществами существует и куча недостатков. Но прогресс, как говорится, не стоит на месте, и был придуман более совершенный способ отображения информации, получивший название "битовые поля" (англ. - bitboards). Это 64-битное слово (то есть последовательность из 64 цифр, каждая из которых может иметь значение 0 либо 1), содержащее информацию об одном аспекте шахматной игры. Каждый бит - это одно поле шахматной доски. (Отсчет может вестись по-разному: поле а8 - это первый бит последовательности, h1 - последний, к примеру.)
Они могут содержать:
поля, атакованные черной пешкой е6 (d5,f5)
00000000
00000000
00000000
00010100
00000000
00000000
00000000
00000000
Для наглядности число разбито по 8 бит, изображающих горизонтали доски.
поля, занятые белыми пешками (фигурами)
поля, куда может пойти белый конь и т.д.
Таким образом, это довольно универсальный способ представления информации. Но это не самое главное его преимущество. Важнее как раз то, что многие операции, которые выполняются периодически при анализе шахматной позиции, легко реализуются как один цикл логических операций над "битовыми полями", что существенно ускоряет процесс поиска ответа.
Генерация ходов
Следующей задачей является научить программу делать ходы. Правила игры в шахматы имеют много аспектов, которые необходимо учитывать при разработке. Среди них взятие на проходе, рокировка, проход пешки в ферзи, и т.д.
Методы анализа
Итак, компьютер сможет "видеть" доску, делать всевозможные доступные ходы в данной позиции. Осталось дело за малым: научить его выбирать лучший ход и предоставить ему возможность оценивать позицию, пользуясь какими-то критериями, которые мы ему предоставим. Что касается первого, то пока ничего лучше не придумано, чем лобовое решение: чтобы выбрать лучший из двух ходов, анализируют последствия каждого из них до какого-то момента, скажем анализ на 5-6 ходов вперед, с последующей оценкой получившейся позиции. При этом делается предположение, что соперники стараются выбирать лучшие ответы на каждом ходе. Кстати, последнее предположение лежит в основе алгоритма MiniMax, являющегося ключевым для всех шахматных программ.
Всё бы было хорошо, но… не тут то было. Вам бы пришлось потратить пять, а может и больше, жизней, чтобы сыграть хотя бы одну партию, пусть даже с самым быстрым компьютером. Так что подумайте прежде чем садиться играть партию с компьютером.
Оценка позиции
И последнее, что необходимо компьютерной программе, чтобы оказать вам достойное сопротивление - это дать ей возможность оценивать позицию. То есть ввести оценочную функцию, которая по положению на доске возвращает число, соответствующее, с её точки зрения, текущему раскладу сил. Это тоже не самая простая задача, хотя существует огромное количество подходов к решению этой проблемы.
