Компьютерные программы по шашкам

Введение

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

Что касается Каспарова, то он играл не в полную силу, пунктов на 200 ниже своего рейтинга, а в последней партии просто стал непонятно почему экспериментировать. На самом деле если бы Гарри мог сыграть с Deep Blue 15-20 тренировочных партий, то он "вычесал" бы ее на ноль.

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

Кроме того, компьютерные шахматы имеют очень мощную поддержку, так как пользуются хорошим спросом на игровом рынке, что стимулирует их развитие. Кроме того, создаются специальные исследовательские группы типа Deep Blue, которые только и занимаются программированием шахмат. Если бы нашлись источники финансирования для группы из 3-4 человек, то за один-два года реально создать шашечную программу (в русские шашки), играющую на уровне чемпиона мира. Наглядный пример - канадская программа Chinook. Занимались ей профессионалы несколько лет - теперь она выигрывает у чемпиона мира.

Программа Агафонова (новая тестовая версия для Windows) недавно сыграла несколько партий по 15 минут с известным экс-чемпионом мира. Несколько ничьих, два проигрыша (один в выигранной позиции). Был и выигрыш - человек зевнул комбинацию. Если бы работа над программой велась планомерно, то многие недоработки удалось бы быстро исправить.

Что касается силы игры, то судить трудно, потому что зарубежные программы не включаются в турниры среди людей. В товарищеских встречах в блице на хороших Pentium-ах они способны победить, наверное, любого. При контроле по 1-3 минуты на ход сила игры - примерно на мастерском уровне, может быть, немного слабее. Причина некоего застоя в компьютерных шашках одна - нет хороших стимулов, отсутствует конкуренция. В Нидерландах ежегодно проводится турнир программ, но победитель ничего, кроме морального удовлетворения, не получает. Наглядный пример - DAM 2.xxx. Постоянные третьи-четвертые места в турнирах - и бесплатное распространение.

Так что потенциально шашечные программы уже давно готовы выигрывать у человека. Остается ждать, когда появятся команды с хорошей финансовой поддержкой. Пока же при нормальном контроле сильнейшие программы реально могут сражаться с средними мастерами.

Российская Федерация Шашек официально признает только две разновидности игры - русские и международные шашки.

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

Список дебютов и позиций, применяемых в таких турнирах, постоянно пересматривается и утверждается РФШ раз в два года.

1. Описание задачи

Русские шашки

Доска 8х8 клеток,

шашки занимают первые три ряда с каждой стороны,

простая может бить назад,

дамка может ходить на любое число полей,

при бое простой через поле превращения она превращается в дамку и продолжает бой по правилам дамки.

Бить можно произвольное количество шашек в любых направлениях.

Цель игры - съесть или запереть все шашки противника.

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

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

2. Выбор метода решения

Данную задачу удобно решить методами объектно-ориентированного программирования на языке Турбо - Паскаль. Язык Турбо - Паскаль является универсальным, имеет широкие возможности в области использования графики, а концепция ООП, поддерживаемая им позволит максимально приблизить решение задачи к образу человеческого решения, упростив тем самым задачу.

Описание алгоритма решения

Суть процедуры, генерирующей ход компьютера в зависимости от позиции на доске состоит в следующем:

Проверить для каждой шашки комп., может ли она что-то побить. Если да - то на п.6 , если нет - то на п.2.

Ходить шашкой с максимальным удалением от начальной линии так, чтобы она не попала под бой (такие ходы не всегда есть).

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

Внести соответствующие изменения в массив расположения шашек и вывести его на экран.

Конец хода. Передать ход человеку.

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

Проверить, можно ли еще что-то побить той шашкой, которой мы только что били. Если можно - на п.6., если нельзя - на п.4.

Несмотря на то, что этот алгоритм является далеко не самым лучшим с точки зрения стратегии (следует иметь в виду, что в нем опущены несущественные детали, например, проверка возможности хода вообще (если все мои шашки заперты, то я проиграл)), он тем не менее позволяет играть компьютеру на уровне 8-9 летнего ребенка.

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

4. Описание структуры данных

Информация о расположении шашек хранится в массиве данных перечисляемого типа - W,WD,B,BD,N,G, где

W - белая шашка

WD - белая дамка

B - черная шашка

BD - черная дамка

N - свободное поле

G - поле, не принадлежащее доске. Поля этого типа окаймляют доску и нужны для того, чтобы индексы массива шашек всегда находились в допустимых пределах (мы расширяем размерность массива за счет этих полей, так как процедуры и функции программы могут обращаться к этому массиву с индексами, не принадлежащими [1..8,1..8]).

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

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

Описание процедур и функций

procedure Tdesk.ScanDamk

Превращает шашку в дамку если она достигла нужной позиции.

procedure Beep

Пищит.

procedure TGame.Init

Инициализация графики. Вход в графический режим и обработка ошибок включения графического режима.

procedure TDesk.Init

Установка размера игрового поля и всех графических объектов (кроме текста). При вычислении размеров и места расположения всех графических объектов используется коэффициент, варьируя которым в допустимых пределах можно изменять их размеры.

procedure TGame.Done

Завершение графического режима.

procedure TGame.Run

Выдача сообщений, инициализация игроков и запуск др. модулей.

procedure TGame.CompPlay

Основная процедура, осуществляющая общую координацию в случае если ходит компьютер.

function TDesk.CompMoveFrom

Отдает шашку под бой, когда нет других ходов и возвращает .t. когда походит.

function TDesk.CompKillFrom

Убивает одну или несколько шашек противника, а так же возвращает .t. когда ход закончен.

function TDesk.KillFrom

Возвращает t. если из данной позиции можно походить и не попасть под бой, а так же ходит если эти условия выполнены.

procedure TGame.Play

Основная процедура игры. Осуществляет координацию модулей и движение курсора. Выполняется когда ход принадлежит человеку.

procedure Select (p:position)

Рисует курсор по передаваемым координатам.

function TDesk.Analise

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

function TDesk.MoveFrom

Проверяет возможность хода из данной клетки.

function TDesk.NoFight

Возвращает .t. если бить нечего.

function TDesk.FightFrom

Возвращает .t. если в текущей позиции есть фишка и она должна что - то бить.

function TDesk.NoStep

Возвращает T. если у игрока (Color=.t. - W Color=.f. - B) нет ходов.

function TDesk.StepFrom

Возвращает t. если в текущей клетке есть шашка и ею можно походить.

procedure TPlayer.Init

Инициализация игроков.

procedure TDesk.Draw

Рисует доску и фигуры по данным массива фигур. Для прорисовки фигур используется процедура TDesk.DrawFigure

procedure TDesk.DrawFigure

Рисует шашку используя передаваемые координаты и параметры - цвет, дамка/не дамка.

Заключение

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

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

Список литературы

Зуев. Язык программирования Turbo Pascal 6.0. - М.: Унитех, 1992.- 298 с.

Довгаль С.И., Сбитнев А.И. Персональные ЭВМ: Турбо - Паскаль V 7.0, Объектное программирование.- Киев: Довгаль,1995. - 320 с.

Епаншенков А.М., Епаншенков В.А. Программирование в среде TURBO PASCAL 7.0.- М.: Диалог - МИФИ, 1996. - 288 с.

Турбо Паскаль 7.0 - К.: Торгово-издательское бюро BHV, 1995 - 448 с.