Игры двух лиц

Игры, в которых участвуют два игрока, широко известны. Как правило, такие игры являются антагонистическими: выигрыш одного игрока означает проигрыш другого.

Рассмотрим детерминированую игру, в которой игроки делают ходы поочередно. Детерминированность игры определяется следующими моментами:

Определена исходная позиция (в картах или домино это не так).

Оба игрока имеют полную информацию о текущей позиции (снова в картах или домино это не выполняется).

Ходы делаются в пределах правил, но по желанию игроков (в нардах и других играх с костями это не так).

Примерами детерминированных игр являются шашки, шахматы, крестики-нолики.

Сложные игры вроде шахмат имеют с первых ходов много вариантов продолжения. Из-за этого трудно сформулировать беспроигрышный " алгоритм игры”. Мы опишем общий подход к программированию таких игр [1].

С другой стороны есть большое количество более простых игр с известной стратегией. Это значит, что один из игроков может гарантировать себе наилучший результат при любой игре соперника. Главное в этих играх – найти методику выбора ходов в зависимости от позиции и ответных ходов противника. Такие игры будут рассмотрены во второй части раздела [3].

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

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

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

Назовем игроков ПЛЮС и МИНУС. Выбор хода каждого игрока соответствует выбору одного из сыновей вершины, которая описывает текущую позицию. В дереве игры уровни вершин, в которых выбираются ходы игроков ПЛЮС и МИНУС, чередуются. Рассмотрим простейший способ построения оценочной функции позиций с точки зрения одного из игроков, например, игрока ПЛЮС.

Присвоим листьям, соответствующим выигрышным позициям, оценку +1, ничейным 0, проигрышным -1. Пусть некоторая вершина дерева A, сыновями которой являются только листья, соответствует ходу игрока ПЛЮС. Очевидно, он должен выбрать одного из сыновей с масимальным значением оценки, поэтому примем это максимальное значение в качестве оценки вершины A. Отцовская для A вершина B соответствует ходу игрока МИНУС. Поскольку оценки в листьях устанавливались для игрока ПЛЮС, игрок МИНУС должен наоборот выбирать сына с минимальной оценкой, предполагая, что его противник сделает лучший ход, то есть оценкой вершины B станет минимум оценок сыновей. В этом и состоит принцип минимакса. Он получен в предположении, что каждый игрок стремится к наивысшему результату при условии наилучших ходов противника.

Таким образом, корень дерева получит оценку +1, 0 или –1, что предопределяет результат игры. На практике все обстоит сложнее. В сложных играх дерево настолько велико, что не поддается подобным расчетам. Например, в шахматах белые могут сделать 20 вариантов первого хода, на каждый из которых может быть 20 вариантов ответа противника, то есть после полного первого хода может получиться 400 различных позиций. Приходится дерево игры строить не до конечных позиций, а в листьях прибегать к статической оценке. С каждым сделанным ходом дерево достраивается вниз. Чем глубже строится дерево игры и чем точнее статические оценки, тем сильнее игрок, будь то человек или программа. Шахматист применяет неявные статические оценки, используя теорию, интуицию, пристрастие к определенным позициям, антипатии противника по отношению к некоторым позициям и т. п.

Рассмотрим простой пример игры в крестики-нолики на поле 3× 3. Игроки поочередно ставят крестик либо нолик в клетках поля. Выигрывает тот, кто получит 3 крестика либо нолика подряд по горизонтали, вертикали либо диагонали.

Построим сначала статическую оценочную функцию. Пусть M – сумма числа строк, столбцов и диагоналей, которые при данной позиции теоретически могут быть заняты игроком КРЕСТИК, а N – аналогичная величина для игрока НОЛИК. Примем за оценку позиции значение F = M – N.

Например, для позиции

+

игрок КРЕСТИК потенциально может занять строки 2, 3, столбцы 1, 3 и обе диагонали, то есть M = 6, а игрок НОЛИК может занять строки 1, 3 и столбцы 1, 3, то есть N = 4. Таким образом, позиция оценивается величиной F = M – N = 2.

Можно проверить, что если придерживаться принципа минимакса, пользоваться описанной функцией оценки и строить дерево игры на свой ход и ответ противника, то есть на 2 уровня, то первый ход игрока должен быть сделан в центр поля. Для игрока КРЕСТИК этот ход имеет оценку 1, тогда как ход в угол поля оценивается величиной –1, а ход в середину крайней строки или столбца величиной –2.

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

A(2) B(2) C(2) D(2) E(1)

Позиция E имеет самую низкую оценку, но она выигрышная (как и D), а позиции A, B и C – ничейные, хотя и имеют более высокие оценки.

Для отсечения бесперспективных вариантов в игровых программах используется процедура α – β отсечения, использующая идеи метода ветвей и границ. Пусть имеется дерево игры и построена функция оценки, наибольшие значения которой определяют ход игрока ПЛЮС.

Допустим, что некоторая вершина дерева соответствует ходу игрока ПЛЮС. Оценка для нее вычисляется как

a = max (a1, a2, …, an),

где a1, a2, …, an – значения функции оценки в сыновьях этой вершины. Пусть нашли некоторое значение ai. Тогда a ≥ ai, то есть величина ai определяет нижнюю границу для a, называемую α – значением. Эту границу можно использовать для отсечения некоторых ветвей дерева игры.

Аналогично для вершины, соответствующей ходу игрока МИНУС, оценка вычисляется как

b = min (b1, b2, …, bm),

где b1, b2, …, bm – значения функции оценки в сыновьях. После нахождения любого значения bj получаем, что b ≤ bj, то есть величина bj определяет верхнюю границу для b или β – значение.

Рассмотрим процедуру α – β отсечения на примере. На рисунке показан фрагмент дерева игры. Как и раньше, приведены оценки с точки зрения игрока ПЛЮС. Вершины дерева, соответствующие ходу игрока ПЛЮС, показаны квадратиками, а игрока МИНУС – кружками. Для игрока ПЛЮС оценка вершины определяется как максимум оценок сыновей, а для игрока МИНУС – как минимум. Корню соответствует текущая позиция. В листьях указаны статические оценки соответствующих позиций.

Оценка MAX: ≥ 3

Оценка MIN: ≤ 3 =3 после β – отсечения ≤ 2

MAX:

=3 ≥ 5 ≥ 4

1 3 0 2 5 3 4 2 2 1 0 2 0 2 0 1 1 0

β – отсечение α - отсечение

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

После получения показанных на рисунке оценок в листовых вершинах a, b и c получаем в вершине D оценку 3. Значит, в вершину p поднимется оценка ≤ 3.

Оцениваем вершины d и e. После получения оценки 5 в вершине f можно заключить, что в вершине H будет оценка ≥ 5, то есть вершина H не сможет оказать влияние на оценку вершины p. Отсюда других сыновей вершины H (на рисунке f) можно не рассматривать. Значит, имеет смысл строить дерево в процессе оценок, а не заранее.

Аналогично получив в вершине h оценку 4, заключаем, что в вершине L будет оценка ≥ 4, поэтому вершины k и l можно не рассматривать. Это примеры β – отсечения, так как рассматривались сыновья вершины p, в которой оценка находится по минимуму оценок сыновей. Таким образом, в вершине p устанавливается окончательная оценка 3.

Оцениваем вершины n, o и p, получая оценку 2 в вершине B. Значит, в вершине q оценка ≤ 2.

Нас интересует оценка в корне. Для него определяется максимум из оценок сыновей, но в вершине p уже достигнуто значение 3. Значит, вершина q с оценкой ≤ 2 не может оказать влияние на оценку корня, поэтому в корень поднимается оценка 3. Вершины S и T со всеми своими сыновьями можно не рассматривать, а соответствующие части дерева игры не строить вообще. Это примеры α - отсечения.

Оценки вершин a, b и c сказались на 2 уровня выше, как и оценка q. Процедура α – β отсечения позволяет, например, в шашках сократить объем вычислений в 4-6 раз.

Эффективность процедуры зависит от порядка перебора вершин. Например, перебирая вершины в порядке d, e, f, h, k, l, a, b, c, для вершины p получали бы последовательно ограничения ≤ 5, ≤ 4, ≤ 3, то есть β – отсечения не было бы совсем. Поэтому важно как можно раньше получать удовлетворительный ход, что возможно на основе дополнительной информации об игре. Опытный игрок вообще не рассматривает бесперспективные варианты.

Методы теории вероятности позволяют распространить описанные подходы и на недетерминированные игры.

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

Перейдем к играм, в которых просматривается выигрышная стратегия. Рассмотрим следующую известную игру.

Спички. Имеется кучка из N спичек. Два игрока поочередно забирают из кучки от 1 до M спичек. Выигрывает игрок, после хода которого кучка спичек опустеет. Кто выигрывает при правильной игре и как надо играть?

В данной игре позиция определяется количеством оставшихся спичек K и номером игрока, имеющего право хода.

Предположим, что сейчас наш ход. Если K = 0, то мы уже проиграли. Если K = 1, 2, …, M, то у нас есть победный ход – взять все оставшиеся K спичек. Если K = M + 1, то любой наш ход сделает K равным одному из чисел 1, 2, …, M, и тогда победит противник. Следовательно, K = 1, 2, …, M выигрышные для нас позиции, а K = 0 и K = M + 1 – проигрышные.

Если K = M + 2, M + 3, …, 2M + 1, то наш соответствующий ход 1, 2, …, M приведет соперника к проигрышной позиции с K = M + 1. Значит, это выигрышные позиции. Если же K = 2M + 2, то любой ход приведет в позицию с K = M + 2, M + 3, …, 2M + 1 – выигрышную для противника и проигрышную для нас.

Отсюда просматривается общая стратегия игры. Нужно после каждого хода " загонять” противника в позиции, когда N mod (M+1) = 0. Значит, при правильной игре обоих противников исходная позиция является выигрышной для начинающего игрока тогда и только тогда, когда N mod (M+1) ≠ 0. Строго говоря, это доказывается по индукции.

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

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

Касса. Касса содержит N копеек (N ≥ 3). Два игрока по очереди берут из кассы по целому числу копеек. За ход можно взять не менее одной копейки, но не более удвоенного числа копеек, взятых соперником на предыдущем ходу. Первый ход – одна или две копейки. Выигрывает тот, кто своим ходом опустошит кассу. Кто выигрывает при правильной игре и как надо играть?

При N = 3 выигрывает второй игрок. При N = 4 выигрывает первый игрок. Он должен взять одну копейку, обеспечив проигрышную позицию для противника.

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

Позиция (K, M) является выигрышной, если существует ход L от 1 до Max (K, 2M) такой, что позиция (K - L, L) проигрышная. Это рекурсивное определение имеет, как говорят, " дно”: позиции (1, M) и (2, M) при любом M выигрышные, а позиции (0, M) – проигрышными.

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

Первый индекс массива равен остатку K денег в кассе, второй – значению последнего хода противника M. Значением элемента S[K, M] для выигрышной позиции (K, M) будет один из возможных ходов L, приводящий противника к проигрышной позиции (K - L, L). Проигрышные позиции будем отмечать нулевыми значениями.

Очевидно, S[1, M] = 1, а S[2, M] = 2 для всех значений M. Остальные строки пока обнулим.

Пусть теперь K ≥ 3. Если K ≤ 2M, то ход K опустошает кассу, значит S[K, M] = K. При K > 2M переберем все возможные ходы от 1 до 2M и используем элементы предыдущих строк таблицы. Если S[K-L, L] = 0 хотя бы для одного значения L, значит, ход L приводит противника в проигрышную позицию (K - L, L), поэтому нужно положить S[K, M] = L. Можно даже выбрать максимальное значение L, чтобы ускорить игру. Если же для всех L от 1 до 2M окажется S[K-L, L] ≠ 0, то S[K, M] соответствует проигрышной позиции и остается равным нулю.

Как пользоваться массивом S? Если достаточно решить вопрос о победителе, то условие S[N, 1] > 0 является критерием выигрыша первого игрока, а S[N, 1] ≠ 0 обозначает выигрыш второго игрока. Если же требуется указывать ходы, то в выигрышной позиции (K, M) делаем ход S[K, M], а в проигрышной - какой-либо другой допустимый ход, продолжающий игру.

Остается определить, сколько столбцов должно быть в массиве S, т.е. каким может быть максимальный ход. При K ≤ 2M выигрышный ход K понятен и без массива S. Значит, можно считать, что K > 2M, т.е. M < K div 2 ≤ N div 2, где div обозначает операцию целочисленного деления, как в языке Паскаль.

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

Слитки. В ряд разложены N (N ≤ 200) золотых слитков различной стоимости. Два игрока по очереди берут несколько слитков в левом конце ряда. Первый ход – один или два слитка. Далее можно взять не менее одного, но не более удвоенного числа слитков, взятых соперником на предыдущем ходу. Цель каждого игрока – получить как можно большую суммарную стоимость взятых слитков. Определить, кто выигрывает при правильной игре и как надо играть, а также какие суммы могут обеспечить себе первый и второй игрок.

Пусть, например, имеется четыре слитка, стоимости которых 1, 2, 4, 8. Ход состоит в указании количества слитков, которые берутся в текущий момент с левой стороны. Первый игрок не позволит второму набрать более 6, если сделает ход 1. Тогда второй игрок возьмет слитки 2 и 4, оставив последний слиток первому игроку. Итак, играя правильно, первый набирает не менее 9, а второй не менее 6.

В данной задаче главной является сумма, которую можно набрать. Сумма зависит как от оставшихся слитков, так и от последнего хода противника, поэтому позиция определяется парой (K, M), где K номер первого из оставшихся слитков, а M – последний ход. Обозначим максимум суммы, которую можно набрать, начиная с позиции (K, M) через S(K, M), а сумму стоимостей всех слитков, начиная с K-го, через R(K).

Игрок получит все, что не сможет забрать его соперник. Значит, нужно ходить так, чтобы соперник после сделанного хода мог набрать как можно меньше. Иными словами, нужно сделать такой ход L, чтобы минимизировать максимум суммы, которую может набрать противник в получающейся позиции (K + L, L). Отсюда при L ≤ 2M и K + 2M ≤ N

S(K, M) = R(K) – min S(K + L, L),

а ход состоит в выборе такого значения L, при котором достигается min S(K + L, L).

Первым ходом первого игрока может быть 1 или 2, поэтому можно считать начальной позицию (1, 1). Если S(1, 1) > R(1)/2, то выигрывает первый игрок, при S(1, 1) < R(1)/2 выигрывает второй игрок, а при S(1, 1) = R(1)/2 игра заканчивается вничью.

Значения R(K) для K = 1, 2, …, N можно вычислить сразу. Для вычисления S(1, 1) используем двумерный массив S из N строк и C столбцов, в котором будем сохранять значения функции S. Количество столбцов C мы определим позже.

Будем заполнять массив S построчно, начиная с последней строки - все значения в ней равны стоимости последнего слитка R(N). В каждой очередной строке K для любого возможного значения M величина S(K, M) вычисляется по приведенной формуле, если K+2M ≤ N, иначе S(K, M) = R(K).

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

Найдем необходимое число столбцов C массивов S и T для заданного ограничения игры N ≤ 200. На первом шаге возможен ход 1 или 2, на втором от 1 до 4, на третьем от 1 до 8 и т. д. После каждого шага количество столбцов удваивается. Образуются такие позиции, как (3, 2), (7, 4), (15, 8), (31, 16), (63, 32).

Из позиции (63, 32) возможные ходы от 1 до 64 приводят к позициям (63+L, L), из которых в свою очередь возможен ход I от 1 до 2L, но при условии 63+ L + I ≤ 200

Найдем наибольшее возможное I из условий

63+ L + 2L ≥ 200

63+ (L-1) + 2(L-1) < 200

63+ L + I ≤ 200

Отсюда L = 46, I ≤ 91, т. е. достаточно C = 91 столбцов таблицы. Подобные расчеты можно выполнить и для других значений N. Проще сделать это не аналитически, а путем пошаговых вычислений.

В рассмотренной игре позиции не являются выигрышными или проигрышными, а имеют числовую оценку. Очередным ходом игрок " загоняет” противника в позицию с минимальной оценкой его максимального выигрыша. Мы уже встречались с этим принципом минимакса в первой части раздела. При построении алгоритма игры используется подход динамического программирования.