| alekhin | Date: Суббота, 14.02.2009, 06:04:30 | Message # 1 |
Авторитет
Группа: Чемпион месяца
Сообщения: 1118
Признак жизни: Offline
| Постановка задачи
В данной статье я не ставлю перед собой цель ознакомить вас с ультрамодными алгоритмами шахматного программирования. Моя цель - дать человеку представление о том, что такое "искусственный интеллект" в приложении к шахматам:
а) что представляет собой "мозг" шахматной программы;
б) каким образом компьютер из моря вариантов выбирает единственный;
в) что необходимо, чтобы заставить компьютерного оппонента играть быстрее и т.д.
Итак, приступим…
Основные компоненты шахматной программы
Сразу определимся с минимальными требованиями для шахматной программы. То есть, что необходимо любой из них, чтобы противостоять человеку. Среди них можно выделить нижеследующие:
Способ хранения информации о текущей позиции
Во время игры человек видит, что происходит на доске. Аналогично и компьютер должен "видеть" как ему играть дальше.
Правила игры
То есть "объяснить" железному другу как в данной ситуации ходить можно, а как запрещено.
способ выбора хода
Цель - предоставить компьютеру средства для выбора из всевозможных доступных ходов одного.
возможность сравнения ходов и позиций
Это необходимо для того, чтобы в результате анализа был выбран лучший в каком-то смысле ход.
пользовательский интерфейс
Я думаю здесь всё ясно J
Ниже вкратце я расскажу вам о каждом из них. Более детально мы рассмотрим их позже.
Представление данных
Каждый из нас по-разному воспринимает входную информацию. На полотне Леонардо Да Винчи один человек может увидеть Джоконду, другой сто долларовую купюру, третий тещу (или зятя). J То же самое и в шахматах. Два соперника во время игры могут видеть совершенно "разные" позиции в один момент времени. Увы, один из них порой бывает неправ, тем более обидно, если им оказываешься ты. L
Так чем же компьютер должен отличаться от человека, спросите вы? Ничем. Компьютерные программы, как и люди, не похожи друг на друга: "мыслят" и хранят информацию они по-разному. Но всё же одни из них играют лучше, другие хуже. В чём секрет? По поводу компьютерного "мышления" мы ещё поговорим ниже, а сейчас коснёмся темы хранения данных.
В программировании очень важно правильно выбрать представление данных.
Я думаю, что любой человек в состоянии придумать какой-нибудь способ отображения текущей информации на шахматной доске. Например, можно представить шахматную доску как таблицу (массив) размерами 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. Впоследствии я расскажу, что было придумано, чтобы заставить вашего железного друга соображать быстрее.
Оценка позиции
И последнее, что необходимо компьютерной программе, чтобы оказать вам достойное сопротивление - это дать ей возможность оценивать позицию. То есть ввести оценочную функцию, которая по положению на доске возвращает число, соответствующее, с её точки зрения, текущему раскладу сил. Это тоже не самая простая задача, хотя существует огромное количество подходов к решению этой проблемы.
Заключение
Теперь, когда вы получили общее представление о том, что же такое программирование шахмат, можно будет приступать к более детальному изучению вышеприведенных компонентов шахматной программы.
Итак, после того как мы определили, что потребуется для создания программы, можно приступать к анализу и проектированию.
Выявление классов и объектов (основные абстракции предметной области)
Определимся сразу какими объектами и классами должна оперировать наша программа.
Шахматы - это игра. //класс
В любой шахматной партии(игре) участвует два игрока.
Игроки делают ходы на шахматной доске.
Игрок обязан делать ход в соответствии с определенными правилами, для этого обязан существовать механизм вычисления (генерации) всевозможных ходов в данной позиции.
Естественно, всего этого будет недостаточно для полноценной программы. Однако остановимся пока и опишем подробнее эти абстракции. Их вполне достаточно, чтобы два человека могли сыграть партейку между собой. Но для этого следует добавить в пирог начинку.
Выяснение семантики классов и объектов (определение поведения и атрибутов абстракций)
Любой объект характеризуется поведением (т.е. теми действиями, которые он может выполнить) и атрибутами (т.е. признаками, позволяющими отличить один предмет от другого)
Пр.Возьмем, к примеру, часы Поведение: идти , показывать текущее время и др. Атрибуты: текущее время и др.
Прежде всего имеет смысл определить поведение объекта, так как его атрибуты(данные) могут быть представлены по-разному и этот вопрос требует большего внимания.
Игра
Поведение:
Те, кто любят играть в компьютерные игры, много раз встречались с меню:
НОВАЯ ИГРА
ЗАГРУЗИТЬ ИГРУ
СОХРАНИТЬ ИГРУ
ВЫЙТИ ИЗ ИГРЫ
Это и есть видимое поведение объекта. Кроме того, существует и другое, о котором пользователю знать не надо. Конечно, нет четкой границы между этими двумя видами поведения, но чем меньше человек знает, тем лучше для него.
Пр.Любая игра начинается выбором опции меню НОВАЯ ИГРА, но шахматная партия начинается с расстановки фигур на доске, а HITMAN2 с прогулки по саду на Сицилии. Принято различать интерфейс и реализацию. Первое есть то, что представляет собой обертку от конфеты. Второе же есть на самом деле то, что заставляет конфету пахнуть так, а не иначе.
Я надеюсь, что все вышесказанное понятно. Сейчас нет необходимости описывать внутреннее поведение объекта. Этим мы займемся на этапе реализации.
Атрибуты:
Любые две программы хотите вы того или нет не могут быть абсолютно идентичными: в программировании есть различные пути, приводящие к одной и той же цели.
Пр. Для тех, кто хоть немного знаком с программированием (сразу прошу прощения у остальных), приведу замечательный пример:
МОЯ ПЕРВАЯ ПРОГРАММА: "HELLO, WORLD". Сколько существует способов написать её? Наверное, не знает никто.
К чему бы это всё спросите вы?
А к тому, что если внешнее поведение объекта можно определить сразу, атрибуты(данные) имеет смысл определять после следующей итерации. (см.выявление связей между классами и объектами)
Игрок
Это вторая ключевая абстракция, определенная явно. Только не надо пугаться слова "абстракция": игрок - понятие растяжимое, это необязательно одушевленный объект, характеризующийся возрастом, цветом глаз и образованием. В данном случае компьютер также может выступать в роли игрока и т.д.
Поведение:
Опять-таки, остановимся лишь на видимом поведении объекта. Единственной (было бы прекрасно, если бы это было так на самом деле) функцией игрока является:
ВЫБРАТЬ ХОД
Ход
Ход - это перемещение фигуры на шахматной доске. Как таковым поведением он не обладает(ещё лучше). Поэтому не будем останавливаться на нём сейчас.
Шахматная доска
Пожалуй, один из самых сложных объектов в игре. Поэтому на первом этапе есть смысл определить лишь очевидные действия.
ПРИМЕНИТЬ ХОД
ОТМЕНИТЬ ХОД
РАССТАВИТЬ ПОЗИЦИЮ
УБРАТЬ ФИГУРУ С ДОСКИ
СНЯТЬ ВСЕ ФИГУРЫ С ДОСКИ
ПОСТАВИТЬ ФИГУРУ НА ДОСКУ
Генератор ходов
Поведение данного класса тоже очевидно. В его задачи входит:
ВЫЧИСЛЕНИЕ ВСЕВОЗМОЖНЫХ ХОДОВ ПОИСК ХОДА СРЕДИ ВОЗМОЖНЫХ
Выявление связей между классами и объектами
Объекты не могут существовать изолированно друг от друга.
Пр. Кошка хочет съесть мышку; режиссер снимает фильмы; дети любят смотреть мультфильмы; продюсер зарабатывает деньги.
Так почему бы продюсеру не заработать денег, наняв режиссера, снимающего мультфильмы, которые любят смотреть дети, про кошку и мышку.
Наши объекты тоже взаимосвязаны, но прежде чем показать её, надо сказать пару слов про виды связей. Существуют различные отношения между объектами: Пр. Доска использует генератор ходов для нахождения всевозможных ходов в данной позиции;
Игра содержит доску и двух игроков;
Человек есть один из видов игроков и т.д.
В объектно-ориентированном программировании вышеприведенные примеры выражают соответственно отношения:
использования
агрегации
наследования
Однако, существуют и другие виды связей. Здесь опять возникают трудности, так как можно отобразить связь между объектами по-разному:
Стрелка отражает связь между объектами. А вот вид связи выбирает программист.
После того, как оговорены все формальные моменты и заложена концептуальная модель, есть смысл приступить к разработке. Программирование - это итерационный процесс и порой приходиться несколько раз начинать сначала (семь раз подумай, а затем… решай сам, нужен ли тебе восьмой). Кроме того, именно сейчас необходимо выбрать язык реализации. Я использую ObjectPascal по нескольким причинам:
заметно облегчается создание графического интерфейса приложения;
у меня нет множественного наследования (это ситуация, когда объект-потомок обладает свойствами своих предков, количество которых 2 и более);
и наконец он мне просто нравится (сейчас посыплются реплики "На Pascale пишут чайники", "Это даже не язык программирования, а так…"). У каждого человека своё мнение и он может выражать его словами и делами.
Ход
Как говорилось выше, это пожалуй самая простая абстракция в нашей программе, поэтому имеет смысл начать с неё.
TMove = class(TPersistent)
private
FMovingPiece: Integer;
FMoveEvaluationType: Integer;
FMoveEvaluation: Integer;
FCapturedPiece: Integer;
FDestinationSquare: Integer;
FSearchDepth: Integer;
FMoveType: Integer;
FSourceSquare: Integer;
function GetStandartNotation: ShortString;
function GetAbbreviatedNotation: ShortString;
function GetCoordinatedNotation: ShortString;
public
property MovingPiece: Integer read FMovingPiece write FMovingPiece;
property CapturedPiece: Integer read FCapturedPiece write FCapturedPiece;
property SourceSquare: Integer read FSourceSquare write FSourceSquare;
property DestinationSquare: Integer read FDestinationSquare write FDestinationSquare;
property MoveType: Integer read FMoveType write FMoveType;
property MoveEvaluation: Integer read FMoveEvaluation write FMoveEvaluation;
property MoveEvaluationType: Integer read FMoveEvaluationType write FMoveEvaluationType;
property SearchDepth: Integer read FSearchDepth write FSearchDepth;
property StandartNotation: ShortString read GetStandartNotation;
property AbbreviatedNotation: ShortString read
property CoordinatedNotation: ShortString read GetCoordinatedNotation;
public
constructor Create;
procedure Reset;
function Equals(Move: TMove): Boolean;
procedure Assign(Source: TPersistent);override;
end;
TPersistent - это класс бибилиотеки VCL. Он предоставляет возможность сохранения состояния объекта в потоке, а также присваивание одного объекта другому посредством метода Assign. Как видно из интерфейса любой объект класса TMove содержит следующую информацию о ходе:
MovingPiece
Фигура, которой делают ход
MoveType
Тип хода: взятие, обыкновенный, длинная и короткая рокировки, пат, мат и др.
SourceSquare
Поле, откуда делается ход
DestinationSquare
Поле, куда делается ход
CapturedPiece
Фигура, стоящая на поле, куда делается ход
MoveEvaluationType, SearchDepth
Дополнительная информация, необходимая в дальнейшем при разработке нашего искусственного интеллекта.
Замечание: На данном этапе эти свойства можно не включать в абстракцию.
Игрок
Рассмотрим теперь класс "игрок". На предыдущем этапе мы сделали заключение, что единственной пока функцией игрока является выбор хода (было бы правильнее сказать осуществление хода). Пришло время определить этот термин более четко.
Во-первых, надо понимать, что человек и компьютер делают ход по-разному. Если человек должен нажать на соответствующем поле мышкой, перетащить фигуру на другое поле и отпустить мышь, то компьютер делает это иначе (скажем, по событию OnTimer, т.е. фигура будет плавно перемещаться с начального поля на конечное). Заметьте, ход может быть сделан некорректно, однако это не входит в обязанности игрока. За этим будет следить другой класс. Однако в любом случае эти две абстракции обладают общностью и прежде всего общностью своих свойств: любой игрок будь то человек, компьютер или ещё кто-нибудь играют за какую-то сторону (здесь два варианта либо за белых, либо за чёрных, хотя можно и за обе).
Таким образом, можно было бы написать так:
interface
type
TSide = ( sdWhite, sdBlack );
TPlayer = class
private
FSide: TSide;
public
property Side: TSide read FSide write FSide;
end;
TPlayerHuman = class( TPlayer )
private
FOnMouseDown: TMouseEvent;
FOnMouseUp: TMouseEvent;
FOnMouseMove: TMouseMoveEvent;
procedure DoMouseDown( Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer );
procedure DoMouseUp( Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer );
procedure DoMouseMove( Sender: TObject; Shift: TShiftState; X, Y: Integer );
public
property OnMouseDown: TMouseEvent read FOnMouseDown write FOnMouseDown;
property OnMouseMove: TMouseMoveEvent read FOnMouseMove write FOnMouseMove;
property OnMouseUp: TMouseEvent read FOnMouseUp write FOnMouseUp;
end;
Замечание: Существует возможность расширить возможности человека. К примеру, позволить осуществлять ввод хода с клавиатуры.
TPlayerAI = class( TPlayer )
private
FOnDragOver: TNotifyEvent;
FTimer: TTimer;
procedure DoStartDrag( Sender: TObject; Move: TMove );
procedure DoDragOver( Sender: TObject );
procedure DoEndDrag( Sender: TObject; Move : TMove );
protected
property Timer: TTimer read FTimer;
public
constructor Create;
destructor Destroy; override;
property OnDragOver: TNotifyEvent read FOnDragOver write FOnDragOver;
end;
Итак, мы имеем информацию о ходе, а также двух партнёрах. Теперь нам понадобится доска….
Источник:
Часть 1
Часть 2
Часть 3
Шахматы учат быть обьективным.(А.Алехин)
|
| |
| |
