А. Шень “Игры и стратегии с точки зрения математики”, МЦНМО

Простые игры и классификация позиций

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

В этой игре второй игрок может гарантировать себе выигрыш. Для этого он должен дополнять ход первого до четырёх спичек (если первый взял одну, второй берёт три и т. п.). Тогда после хода второго сначала останется 8 спичек, затем 4, и, наконец, 0 - первый проиграл.

А что будет, если изначально не 12 спичек, а 15?

В этом случае выигрывает первый: он должен взять три спички, останется 12, а затем дополнять ход противника до 4 спичек.

Легко понять, что будет в общем случае, для N спичек. Если N делится

на 4 без остатка, то второй может гарантировать себе выигрыш, дополняя

ход противника до 4. Если же N не делится на 4 без остатка, то выигрывает

первый. Он должен сначала взять столько спичек, каков остаток, а потом

дополнять ход противника до 4.

Аналогично получается решение для игры, в которой можно брать до 4, 5, …, k спичек за ход. Также существует другая вариация этой игры - когда тот, кто взял последнюю спичку, проигрывает.

Разница в том, что брать три спички нельзя, так что правило «дополнять ход противника до пяти спичек» теперь не годится (если противник взял две). Чтобы проанализировать игру, изобразим возможные варианты (сколько осталось спичек) кружочками, а возможные ходы - стрелками. Если рассмотреть возможные ходы с конца игры, то получим, что все позиции (количество оставшихся спичек), где число спичек делится на 3 будут проигрышными,  где не делится - выигрышными.

Опять же рассмотрим все возможные варианты, начиная с конца игры. Те позиции, которые невозможны - будем зачёркивать. Общего правила для любого N не существует, так как позиции простых чисел можно только вычислять по ходу решения задачи.

Сформулируем общие определения и правила:

  1. Позицией в игре называется уникальное состояние игры плюс кто ходит в данный момент.
  2. Позиция называется выигрышной, если игрок может выиграть вне зависимости от ходов другого игрока.
  3. Позиция называется проигрышной, если игрок не может выиграть при оптимальной игре другого игрока. То есть, другой игрок смог рассчитать игру целиком и всегда ходит так, чтобы выигрывать самому и не давать выигрывать противнику.
  4. Последовательность ходов игрока называется стратегией.
  5. Правила вычисления: Позиция выигрышная, если можно сделать хотя бы один такой ход, чтобы другой игрок оказался в проигрышной позиции.
  6. Позиция проигрышная, если из неё нельзя сделать ход, либо все позиции, в которые можно сделать ход, являются выигрышными.
  7. Выигрышная стратегия - ставить противника в проигрышную позицию.

Игры со многими исходами

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

Назовём игроков Максом и Мином, а результатом игры будем считать сумму, которую Мин выплачивает Максу. (Отрицательный результат при этом означает, что Макс платит Мину.) Имена игроков понятны: Макс хочет, чтобы выплачиваемая ему сумма была как можно больше (результат игры был максимален), а Мин - наоборот (чтобы результат был минимален). Таким образом, игра с ничьей (как крестики-нолики) может иметь три возможных результата: +1 (выигрыш Макса), 0 (ничья) и − 1 (выигрыш Мина).

Но можно анализировать и игры с большим числом исходов.

Прежде всего заметим, что для каждой из клеток доски известно, кто из

игроков (Макс или Мин) в ней ходит. В частности, последний (седьмой) ход

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

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

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

Вычисление такой игры можно реализовать с помощью ленивой динамики:

  1. Из текущего состояния игры перебираем все возможные ходы текущего игрока и запускаем рекурсивно процедуру вычисления.
  2. В зависимости от цели игрока выбираем наилучший в данной позиции ход.
  3. Сохраняем результат игры для данного состояния для того, чтобы вычислять его ещё раз.

(Формально говоря, котов надо назвать Максом и Мином и результатом

игры считать разницу между числом сосисок, съеденных Максом и числом

сосисок, съеденных Мином. Или просто число сосисок, съеденных Максом,

так как второе число дополняет первое до N).

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

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

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

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

Симметрия

Рассмотрим ту же задачу про спички, если у нас есть две кучки спичек:

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

другой n?

Если m != n , то выигрывает первый: он должен своим ходом уравнять кучки, а потом поддерживать равенство. Если же m = n, то игроки меняются местами: второй может восстанавливать равенство после нарушения его первым, тем самым обеспечив себе выигрыш.

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

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

Ним

Предположим, игра состоит из нескольких независимых игр (ход в одной из игр не влияет на состояние любой другой). Например, игра с двумя кучками спичек размера m и n аналогична двум играм: 1) игре с кучкой размера m, из которой можно брать от 1 до m спичек; 2) игре с кучкой размера n, из которой можно брать от 1 до n спичек. Обе из них тривиальны, но становятся более сложной игрой, когда за один раз можно сделать ход только в одной из этих игр.

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

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

Можно представить себе игру, аналогичную игре ним:

Чтобы разобраться с игрой «ним», будем записывать количество спичек в  двоичной системе счисления. В ней число раскладывается не по степеням десятки, как в обычной десятичной, а по степеням двойки.

Допустим, мы хотим узнать, является ли позиция из трёх кучек, в которых 3, 5 и 7 спичек, выигрышной. Запишем числа 3, 5 и 7 друг под другом в двоичной системе (выравнивая их по правому краю, как при сложении в столбик):

3 =   11

5 = 101

7 = 111

Теперь надо подсчитать двоичную сумму по модулю два (xor) всех размеров кучек. Если она равняется нулю, то позиция проигрышная; если не равняется - позиция выигрышная.

Это правило годится для любого количества кучек. (Можно проверить его для частного случая двух кучек. Чётность числа единиц в каждом столбце означает, что там либо два нуля, либо две единицы. Другими словами, проигрышными будут те позиции, где обе двоичных записи одинаковы, что согласуется с уже известным нам ответом.)

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

Нам надо доказать, что чётные позиции проигрышные, а нечётные - выигрышные. Для этого сформулируем и докажем две леммы.

Лемма 1. Сделав любой ход в чётной позиции, мы получаем нечётную позицию.

В самом деле, ход изменяет одно из чисел, оставляя остальные числа неизменными. В изменённом числе есть самый большой изменённый разряд с 1 на 0, и если раньше в его столбце было чётное число единиц, то теперь - нечётное.

Лемма 2. В нечётной позиции всегда можно сделать ход, дающий чётную позицию.

В нечётной позиции есть один или несколько нечётных столбцов. Рассмотрим самый левый из них. В нём нечётное число единиц, и, следовательно, есть хотя бы одна единица. Выберем одну из таких единиц. Заменим её на нуль, сделав столбец чётным. Если справа ещё остались нечётные столбцы, поменяем цифры (в той строке, которую мы уже начали менять) в этих столбцах и сделаем их чётными. Заметим, что изменённое число уменьшилось, так как мы заменили в нём единицу на нуль (что не перевешивается никакими изменениями в младших разрядах).

Леммы 1 и 2 показывают, что чётные и нечётные позиции подчиняются тому же правилу, что проигрышные и выигрышные (проигрышные позиции - те, из которых можно перейти только в выигрышные, а выигрышные - те, из которых можно перейти в проигрышную). Отсюда следует, что если мы будем составлять таблицу выигрышных и проигрышных позиций «с конца» (в порядке возрастания общего числа камней), а также таблицу чётных и нечётных позиций, то они будут заполняться по одним и тем же правилам, и потому будут совпадать. (Первым шагом при таком построении будет позиция, где камней нет ни в одной кучке. Она является одновременно чётной и проигрышной.) Что и требовалось доказать.

Это правило позволяет описать выигрышную стратегию для игры ним: надо ставить противника в чётную (то есть проигрышную) позицию. Например, если в начале игры имеется 3, 5 и 7 камней, то можно забрать один камень из  какой-либо кучки, получив чётную позицию, например, 3, 5, 6.

После хода противника эта позиция станет нечётной, и надо сделать ход, превращающий её в чётную. И так далее до выигрыша.