Программирование шахмат - основы
Прислано admin на Ноября 29 2006 13:06:03

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

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

Итак, приступим…

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

Способ хранения информации о текущей позиции

Во время игры человек видит, что происходит на доске. Аналогично и компьютер должен "видеть" как ему играть дальше.

Правила игры
То есть "объяснить" железному другу как в данной ситуации ходить можно, а как запрещено.

способ выбора хода
Цель - предоставить компьютеру средства для выбора из всевозможных доступных ходов одного.

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

пользовательский интерфейс
Я думаю здесь всё ясно

Ниже вкратце я расскажу вам о каждом из них. Более детально мы рассмотрим их позже.

Представление данных
Каждый из нас по-разному воспринимает входную информацию. На полотне Леонардо Да Винчи один человек может увидеть Джоконду, другой сто долларовую купюру, третий тещу (или зятя). J То же самое и в шахматах. Два соперника во время игры могут видеть совершенно "разные" позиции в один момент времени. Увы, один из них порой бывает неправ, тем более обидно, если им оказываешься ты.

Так чем же компьютер должен отличаться от человека, спросите вы? Ничем. Компьютерные программы, как и люди, не похожи друг на друга: "мыслят" и хранят информацию они по-разному. Но всё же одни из них играют лучше, другие хуже. В чём секрет? По поводу компьютерного "мышления" мы ещё поговорим ниже, а сейчас коснёмся темы хранения данных.

В программировании очень важно правильно выбрать представление данных.

Я думаю, что любой человек в состоянии придумать какой-нибудь способ отображения текущей информации на шахматной доске. Например, можно представить шахматную доску как таблицу (массив) размерами 8х8, где пустой клетке соответствует число - 0, белому королю - 1, и т.д. Увы, у этого способа наряду с преимуществами существует и куча недостатков (порассуждайте на досуге - что это за недостатки J). Но прогресс, как говорится, не стоит на месте, и был придуман (догадайтесь где) более совершенный способ отображения информации, получивший название "битовые поля" (Прим.авт. - cразу же прошу прощения за фривольность перевода; англ. - bitboards). Это 64-битное слово (то есть последовательность из 64 цифр, каждая из которых может иметь значение 0 либо 1), содержащее информацию об одном аспекте шахматной игры. Каждый бит - это одно поле шахматной доски. (Отсчет может вестись по-разному: поле а8 - это первый бит последовательности, h1 - последний, к примеру.)

Они могут содержать:

поля, атакованные черной пешкой е6 (d5,f5)
00000000
00000000
00000000
00010100
00000000
00000000
00000000
00000000

Для наглядности число разбито по 8 бит, изображающих горизонтали доски.

поля, занятые белыми пешками (фигурами)

поля, куда может пойти белый конь и т.д.

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

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

Методы анализа
Итак, компьютер сможет "видеть" доску, делать всевозможные доступные ходы в данной позиции. Осталось дело за малым: научить его выбирать лучший ход и предоставить ему возможность оценивать позицию, пользуясь какими-то критериями, которые мы ему предоставим. Что касается первого, то пока ничего лучше не придумано (по крайней мере, я не слышал об этом, если кто-нибудь знает, то, пожалуйста, напишите), чем лобовое решение: чтобы выбрать лучший из двух ходов, анализируют последствия каждого из них до какого-то момента, скажем анализ на 5-6 ходов вперед, с последующей оценкой получившейся позиции. При этом делается предположение, что соперники стараются выбирать лучшие ответы на каждом ходе. Кстати, последнее предположение лежит в основе алгоритма MiniMax, являющегося ключевым для всех шахматных программ.
Всё бы было хорошо, но… не тут то было. Вам бы пришлось потратить пять, а может и больше, жизней, чтобы сыграть хотя бы одну партию, пусть даже с самым быстрым компьютером. Так что подумайте прежде чем садиться играть партию с компьютером J. Впоследствии я расскажу, что было придумано, чтобы заставить вашего железного друга соображать быстрее.

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