Blokus

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

Правила игры

Игра ведется на квадратном поле размером 14 на 14 клеток. Каждый игрок обладает набором из 21 фигуры (наборы для обоих игроков одинаковы). На рисунке 1 изображен набор фигур, который есть у каждого игрока на начало игры.

Игроки совершают свои ходы по очереди. В каждый ход игрок может разместить на поле одну фигуру. Первая фигура должна быть размещена таким образом, чтобы «покрывать» особую – стартовую клетку. На поле имеется две стартовые клетки (для каждого из игроков). На рисунке 2 приведено поле с указанными стартовыми клетками (заштрихованные клетки) и примером размещения фигуры первым игроком.

После первого хода каждого игрока фигуры должны размещаться таким образом, чтобы каждая новая размещаемая фигура касалась другой фигуры такого же цвета, но только углом. Фигуры одного цвета не должны касаться друг друга краями. На рисунке 3 приведены примеры правильного и неправильного размещения фигур (справа).

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

Используемые алгоритмы

Нахождение точек соприкосновения

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

Рисунок 4 – Нахождение точек соприкосновения

Перебор вариантов хода

Известно, что у каждого игрока набор из 21 фигуры. Каждая фигура, в свою очередь, обладает несколькими состояниями, которые изначально заданы в XML-файле и при запуске игры считываются из него и загружаются в память, – это возможности поместить ее на игровой карте (см. рисунок 5).

Рисунок 5 – Пример всех состояний фигуры

Суть данного алгоритма заключается в следующем: зная координаты точек соприкосновения и координаты состояний фигур пытаемся поместить состояние каждой фигуры в каждой точке соприкосновения всеми возможными способами (см. рисунок 6). Это реализуется следующим образом: совместим точку соприкосновения с первой клеткой текущего состояния, после чего рассчитаем координаты для остальных клеток текущего состояния фигуры. Теоретически располагая фигуру на игровом поле, проверим не противоречит ли это правилам, т.е. каждая клетка игрового поля, куда будет располагаться клетка фигуры не должна быть равна 1 и 2, а также соседние клетки(слева, справа, снизу и сверху) не должны равняться цифре, которой обозначены фигуры данного игрока. Если какое-то из условий нарушилось, то совместим точку соприкосновения со следующей клеткой текущего состояния и повторим вышеописанные этапы. В случае если ни одно из состояний текущей фигуры не удалось расположить в данной точке соприкосновения, то перейдем к следующей фигуре. В случае каждого удачного расположения состояния фигуры подсчитываем значение функции, роль которой будет рассмотрена далее.

Рисунок 6 – Возможности расположения одного состояния фигуры в одной точке соприкосновения по-разному

Выбор оптимального хода

Выбор оптимального хода базируется на максимизации функции

<math>F=w_1*m+w_2*S</math>,

где <math>m</math> - количество ходов, которое противник не сможет сделать,

<math>S</math> – площадь фигуры(количество клеток)

<math>w_1,w_2</math> – коэффициенты важности.

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

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

Рисунок 7 – Выгодность ходов

После ряда сыгранных игр, для коэффициентов <math>w_1</math> и <math>w_2</math> были подобраны значения 3 и 7 соответственно. Это объясняется тем, что при увеличении коэффициента <math>w_1</math> компьютер начинает "гоняться" за возможными ходами соперника, что в конечном итоге не приводит его к победе. Следовательно коээффициенты подобраны таким образом, чтобы компьютер вел себя наиболее умно.

Особенности реализации под MS Zune

Для разработки приложений под MS Zune вам потребуется:

• XNA framework
• .net framework 3.5

Также, если вы хотите управлять вашим проектом при запуске под ОС Windows, необходимо продублировать управления для клавиатуры в коде, либо подключить Xbox 360™ Controller, представленный на рисунке 8. Драйвер на джойстик можно скачать отсюда. Подробное руководство по установке приложения на MS Zune здесь.

Рисунок 8 – Внешний вид игрового контроллера Xbox 360™ Controller

Результаты тестирования

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

Demonprofi 04:30, 23 ноября 2009 (MSK)