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

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

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

0

+

игрок КРЕСТИК потенциально может занять строки 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 (a₁, a₂, …, a_n) ,

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

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

b = min (b₁, b₂, …, b_m) ,

где b₁, b₂, …, b_m – значения функции оценки в сыновьях. После нахождения любого значения b_j получаем, что b ≤ b_j, то есть величина b_j определяет верхнюю границу для 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

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

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

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

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

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

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

5. Нас интересует оценка в корне. Для него определяется максимум из оценок сыновей, но в вершине 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. Проще сделать это не аналитически, а путем пошаговых вычислений.

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

Задачи для самостоятельного решения

1. Король (4)

В некоторой клетке доски NN (1  N  20) стоит король. Горизонтали и вертикали доски нумеруются с 1 снизу вверх и слева направо. Координаты клетки определяются как (P, Q), где P – номер строки, а Q – номер столбца. Двое по очереди двигают короля. Разрешается двигать короля только вниз, влево или по диагонали вниз влево. Цель игры – задвинуть короля в угол, то есть в клетку с координатами (1, 1). Требуется написать программу, которая по заданным координатам клетки найдет номер игрока, выигрывающего при правильной игре. Считается, что первый номер имеет игрок, начинающий игру.

Ввод из файла INPUT.TXT. В первой строке задано значение N и число заданных вариантов M (1  M  5) через пробел. В каждой из следующих M строк - по два целых числа от 1 до N через пробел, задающих номера строки и столбца соответственно, т.е. координаты клеток доски.

Вывод в файл OUTPUT.TXT. Выдается M строк. В каждой из них указывается номер игрока (1 или 2), который выигрывает при правильной игре.

Пример

Ввод

3 2

1 2

3 1

Вывод

1

2

14.2. Игра в умножение (6)

Двое играют в умножение: умножают целое число P на одно из чисел от 2 до 5. Первый игрок всегда начинает с P=1, делает умножение, затем число умножает второй игрок, снова первый и т. д. Перед началом игры им задают число N, и победителем считается тот, кто первым добьется условия P ≥ N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.

Ограничения: 2  N 10000, время 1 с.

Ввод из файла INPUT.TXT. В первой строке находится количество партий M. В следующих M строках задаются значения N для каждой партии.

Вывод в файл OUTPUT.TXT. Выводится М строк с числами 1 – если победит первый игрок, или 2 - если победит второй.

Пример

Ввод

1

17

Вывод

1

14.3. Даты (6)

Играют двое. Задается какая-то дата високосного года. Каждый игрок на своём ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не оба сразу. При этом сочетание дня и месяца должно оставаться корректной датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. По заданной дате вывести, кто выиграет.

Ограничения: месяц от 1 до 12, день от 1 до числа дней в месяце, даты "31 декабря" во входных данных нет, время 1 с.

Ввод из файла INPUT.TXT. В первой строке находятся числа, обозначающие день и месяц.

Вывод в файл OUTPUT.TXT. Вывести 1, если выигрывает первый (начинающий) игрок, или 2 - в противном случае.

Пример

Ввод Ввод 2 Ввод 3

30 12 29 12 29 11

Вывод Вывод 2 Вывод 3

2 1 2