Универсальный алгоритм для компьютерных логических игр / Alexey Nurgaliev

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

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

Антагонистическая игра (или игра с нулевой суммой) - некооперативная игра, в которой участвуют два игрока, выигрыши которых противоположны.

Рассмотрим каждую часть отдельно.

1. Алгоритм выбора оптимального хода

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

Игрок в текущей позиции пытается сделать все возможные ходы и максимизировать свой выигрыш, а также минимизировать выигрыш другого игрока. Перебор позиций проводится при помощи поиска в глубину (depth-first search, DFS) до достижения некоторой заданной глубины \(d\) или конца игры.

Обозначим:

Если позиция p является терминальной, то для нее определена функция \(f(p)\), определяющая выигрыш игрока, которому принадлежит ход в этой позиции.

Позиция называется терминальной, если из нее нет разрешенных ходов (достигнуты конец игры или необходимая глубина перебора).

Выигрыш игрока будет равен:

\[F(p) = f(p),\]

если позиция \(p\) – терминальная, иначе

\[F(p) = max(-F(p_i))\]

Достоинства:

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

Количество перебираемых вариантов можно уменьшить, если прекращать поиск точной оценки хода, когда стало известно, что этот ход не может стать лучше, чем один из ходов, рассмотренных ранее[1].

Алгоритм альфа-бета отсечений при вычислении оценки позиции иcпользует верхнюю и нижнюю допустимые границы.

Обозначим:

Функция Fab должна удовлетворять условиям:

Достоинства:

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

Сравнение количества перебранных позиций для первых 10 ходов в игре «Реверси» на поле 8х8 при использовании алгоритмов минимаксного дерева и альфа-бета отсечений (глубина перебора 6 позиций, программа играет против человека, человек делает ход первым)

Номер хода Минимаксное дерево поиска (полный перебор) Перебор с использованием альфа-бета отсечений
1 16 251 1 015
2 61 730 1 712
3 568 484 10 948
4 1 083 976 14 325
5 1 624 623 13 598
6 2 412 356 18 287
7 1 847 605 15 328
8 5 389 480 30 807
9 4 870 334 22 508
10 3 390 729 21 994

Альтернативой алгоритму минимаксного дерева является использование метода Монте-Карло.

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

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

Достоинства:

Недостатки:

Например, одна из сильнейших программ для игры в го, «MoGo», использующая этот метод, запускалась на компьютере производительностью 15 Терафлопс[3] (для сравнения, производительность процессора Intel Core i7-975 0.06 Терафлопс[2], а производительность суперкомпьютера СКИФ МГУ 47,17 Терафлопс[4]).

График зависимости количества выигранных партий в игру «Реверси» на поле 8х8 для программы, использующей метод Монте-Карло с разным числом разыгрываемых случайных партий, играющей против программы, использующей алгоритм альфа-бета отсечений с глубиной перебора 6 позиций.

2. Способы описания правил.

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

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

1. Набор функций для каждой игры описывается вместе с остальными функциями (алгоритмом выбора хода и т.п.) и компилируется в один исполняемый файл.

Достоинства:

Недостатки:

2. Подключение набора функций в виде внешнего модуля (например, DLL).

Большинство шахматных программ подключается к шахматным оболочкам в виде внешних модулей (для взаимодействия обычно используется специальный протокол UCI - Universal Chess Interface).

Достоинства:

Недостатки:

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

Достоинства:

Недостатки:

Пример программы на интерпретируемом языке, описывающей правила игры “Крестики-нолики” на поле 3х3:

function init #загрузка параметров игры
{
 setHeight({3})   #высота игрового поля
 setWidth({3})    #ширина игрового поля
 setDepth({2})    #глубина перебора позиций
}

function checkMove #проверка правильности хода
{
 if cellEmpty(param0[{1}],param0[{2}]) #проверка, свободна ли клетка
	 return {1}
 return {0} 
}

function makeMove #сделать ход и установить счет игроков (предполагается, что ход возможен)
{
 setCell(param0[{1}],param0[{2}],param0[{0}])
 if equal($win(),param0[{0}])
  setScore(param0[{0}],{1}) #в случае победы, игроку сделавшему ход, начисляется 1
				#очко
}

function endGame #признак конца игры
{	
 if $win() 
  return {1} #игра закаканчивается, если кто-либо выиграл
	
 #также игра заканчивается, если не осталось пустых клеток
 i = {-1}
 while less(i=inc(i),{3})
  if notequal(VNum({0},i),{0})
   return {0}			
 return {1}
}

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

Такой подход использует среда разработки Scratch, разработанная в MIT.

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

Достоинства:

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

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

Файлы на Github

Литература:

  1. An Analysis of Alpha-Beta Pruning [Article] / auth. Knuth D. E. Moore R. W. // Artificial Intelligence. - 1975. - 4 : Vol. 6
  2. Processors - Intel® microprocessor export compliance metrics [Online]. - http://www.intel.com/support/processors/sb/cs-023143.htm
  3. Sensei’s Library: MoGo [Online]. - http://senseis.xmp.net/?MoGo
  4. SKIF MSU [Online] // TOP500 Supercomputing Sites. - http://www.top500.org/system/ranking/9240

Данная статья была опубликована в сборнике “Энергия и талант молодёжи - залог развития наукоёмких производств. Сборник научных трудов XII Областной научно-практической конференции молодых учёных. - Т. 1 - Псков: Издательство ППИ, 2010.

Лицензия Creative Commons
Code More Team - GitHub