Пример разработки компьютерной игры позиционного типа

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

РЕВЕРСИ — логическая игра, рассчитанная на двух участников, которые играют на доске размером 8×8 фишками разного цвета.

Участники начинают игру, имея по две фишки, стоящие в центре доски по диагонали друг от друга. В процессе игры совер­шаются ходы, в результате которых число фишек увеличивается. Цель каждого игрока заключается в том, чтобы к моменту окон­чания игры число его фишек преобладало над числом фишек противника. В игре приняты следующие нормативные правила:

• при очередном ходе фишку можно ставить на свободную клетку в любом направлении, но обязательно рядом хотя бы с од­ной из фишек противника;
• фишка должна ставиться так, чтобы хотя бы одна из фишек противника оказалась замкнутой своими фишками. При этом зам­кнутые фишки противника меняют цвет и становятся своими;
• фишки могут неоднократно менять цвет, но не могут пере­ставляться на доске;
• игра заканчивается, если доска заполнена, или на ней при­сутствуют фишки только одного цвета, или ни один из игроков не может сделать очередной ход.

Примеры возможных позиций в игре показаны на рис. 3.13. При написании компьютерного игрока возникают следующие задачи:

1. Выделение и представление объектов игры.
2. Реализация операций, соответствующих правилам переме­ щения и изменения объектов.
3. Построение правил принятия решений при выборе хода.
4. Управление последовательностью игры.

В данном случае объектами игры являются свободная клетка и занятые клетки двух цветов (белая и черная). Над объектами совер­шаются операции — ходы, которые заключаются в занятии свобод­ной клетки в соответствии с заданными правилами. Изменение цвета одной или нескольких клеток является результатом хода.

Интеллект компьютерного игрока проявляется в процессах принятия решений.

На уровне новичка компьютер выбирает оптимальный для се­бя ход, не рассматривая возможные ответные ходы противника.

Возможные ходы белой фишкой из позиции Q Рис. 3.13. Позиции игры РЕВЕРСИ

Оценочная функция имеет вид

где х, у =1,…,8 — координаты клетки, в которую можно совершить ход;

 — подмножество полного множества клеток XxY, на кото­рые можно поставить очередную фишку;

 — число замыкаемых клеток;

 — ценность i-й замыкаемой клетки;

 — ценность клетки, на которую совершается ход.

Значенияи ss вычисляются на основе следующих эмпири­чески подобранных констант:•для кромочной клетки поля. Такие клетки могут быть замкнуты только вдоль кромки доски, поэтому они предпочти­тельнее внутренних клеток;

•для остальных клеток;

• угловые клетки поля не могут быть замкнуты, они являются наиболее ценными для захвата;

• ss = 0.8, если ход делается на угловую клетку;

• ss = 0.4, если ход делается на кромочную клетку;

• ss = 0 для всех остальных клеток.

Анализ возможности хода осуществляется следующим обра­зом.

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

где— координаты клеток, на которые может поставить свою фишку че­ловек при ходе компьютера в клетку с координатами х, у; пара­метр dep указывает на игрока, для которого вычисляется оценка эффективности хода. Нулевое значение соответствует ходу ком­пьютера;соответствует вычислению эффективности хода, который может совершить противник (человек), по формуле .

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

Проведенные эксперименты показали существенное преиму­щество применения тактики, учитывающей вероятные ходы про­тивника. Эксперименты с увеличением глубины просмотра вероятных ходов компьютера и человека показали, что «заглядывать» дальше чем на два хода не имеет смысла, так как опытные игроки сознательно препятствуют разыгрываемым компьютером комби­нациям, а неопытные делают то же самое, не понимая целей ком­пьютерного игрока.