Допустим, что некая игра для двух игроков имеет следующие свойства:
1. В любой момент времени каждый игрок обладает всей информацией, чтобы решить, каким должен быть следующий ход.
2. Игроки совершают ходы поочередно.
3. В игре полностью отсутствует элемент неопределенности.
4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.
При этих условиях можно показать, что обязательно существует выигрышная стратегия для одного из двух игроков: первого (игрок А) или второго (игрок Б). Допустим, что выигрышной стратегии для игрока А не существует, иными словами, для игрока Б всегда будет существовать ход, на который у игрока А не найдется достойного ответа, и он проиграет. Это означает, что победит игрок Б. Таким образом, для него существует выигрышная стратегия. Подобные рассуждения лишь доказывают, что в подобных играх всегда существует выигрышная стратегия, но это не означает, что ее будет легко обнаружить.
Для игр, в которых партия не обязательно содержит конечное число ходов, применимость этого утверждения зависит от принятия так называемой аксиомы выбора. Эта известная и противоречивая математическая аксиома утверждает, что для каждого семейства (конечного или бесконечного) непустых непересекающихся множеств существует новое множество, образованное путем выбора определенного элемента из каждого множества этого семейства. С помощью этой аксиомы Банах, Мазур и Улам в 1930 году определили бесконечную игру и доказали, что в ней не существует выигрышной стратегии ни для одного из игроков.
Использование преимуществ и определение стратегий. Игра Ним и ей подобные
Вернемся к классификации игр и сосредоточим внимание на так называемых стратегических играх. Их можно разделить на два типа. Те, что описываются простыми правилами, длятся короткое время и количество информации в которых ограничено или относительно невелико, будем называть малыми стратегическими играми. В других, подобных шахматам или го, полный контроль невозможен ввиду длительности партии, сложности правил и в особенности из-за огромного числа возможных ходов в каждой позиции. На примере малых стратегических игр мы увидим, как математика используется в анализе игр для определения преимущества одного из игроков и для нахождения выигрышной стратегии.
«Игра в шахматы» — полотно, созданное в 1555 году художницей эпохи Возрождения Софонисбой Ангиссолой. В этой игре отсутствует элемент случайности, но число возможных ходов столь велико, что не поддается математическому контролю.
Взаимосвязь между математикой и играми может касаться различных аспектов игр, как уже говорилось в первой главе. Применительно к стратегическим играм математика особенно полезна для определения выигрышной стратегии. Стратегическая игра очень похожа на процесс решения математической задачи: речь идет не о том, чтобы выиграть одну партию, совершая более удачные ходы, но о том, чтобы найти способ, как выигрывать всегда. По этой причине при определении выигрышных стратегий используются эвристические методы: способ «от обратного»; предположение, что игра «решена»; применение симметрии; проведение аналогии с другой, уже решенной игрой и прочие. Они аналогичны тем, что используются при решении математических задач. Поэтому когда для некоторой игры известна выигрышная стратегия, игра из развлечения превращается в решенную задачу. Понятно, что это верно только для определенных игр, которые выходят за рамки простых развлечений и описываются в математических теориях. О подобных теориях, порой достаточно сложных, мы поговорим далее.
Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.
Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она рассматривается далее в этой книге в параграфе «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.
Определение общей выигрышной стратегии, применимой к любой игре такого типа, — одно из ярчайших проявлений того, как математика используется для анализа игр, и в особенности того, насколько эффективно представление чисел в двоичной системе.
«Мариенбад» — одна из версий игры Ним.
Об определении стратегии
Сначала мы проанализируем игры с одной группой фишек, в которых на каждом ходу можно брать со стола минимум одну и максимум n фишек. Мы рассмотрим два частных случая, затем приведем обобщение. Самый простой вариант подобной игры таков.
Игра 1: выигрывает первый
На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если читатель незнаком с этой игрой, перед прочтением следующих страниц ему будет интересно попробовать сыграть в нее самому и постараться ответить на заданные выше вопросы.
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2011), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру можно обобщить и дальше, изменив число фишек, которые можно брать на каждом ходу.
Игра 2: выигрывает второй
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, ..., 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 - n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.
Игра 3: общий случай
Допустим, что на столе m фишек и каждым ходом можно брать от 1 до n фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?
Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:
1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n+1. Для этого на каждом ходу, если первый игрок берет p фишек (0 2. Остаток от деления равен r(0
Это общее решение применимо к бесконечному множеству игр. Читатель может применить его для такой игры: на столе 2010 фишек, на каждом ходу можно брать от 1 до 49 фишек. Для какого игрока существует выигрышная стратегия? В чем она заключается? Если мы изменим правила и тот, кто берет последнюю фишку, будет проигрывать, то достаточно заметить следующее: для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно m - 1, а не m.
Все подобные игры, в которых используется только одна группа фишек, можно считать упрощенными вариантами игры Ним, о которой мы поговорим далее.
Сложная стратегия: игра Ним
Все игры, о которых мы говорили до этого, можно обобщить еще больше: будем считать, что фишки лежат не в одной кучке, а в нескольких. Число кучек произвольное и конечное. В начале игры Ним фишки на столе лежат в нескольких кучках. Число фишек в кучках может отличаться. По правилам на каждому ходу игрок может брать минимум одну и максимум все фишки из выбранной кучки. Выигрывает тот, кто берет последнюю фишку. Также можно поменять правила и считать проигравшим того, кто должен взять последнюю фишку.
Игра 4: первая версия игры Ним
В начале игры на столе три кучки, состоящие из 1, 3 и 5 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?
Анализ игры позволяет увидеть, что такая стратегия существует для первого игрока, но из всех возможных начальных ходов только один гарантирует победу. Если читатель попрактикуется в этой игре, то увидит, что ни одному из игроков не выгодно делать следующие ходы:
1. Оставлять на столе две кучки с одинаковым числом фишек.
2. Забирать все фишки из одной кучки.
Если игрок А выполняет ход 1, игрок Б забирает все фишки из третьей кучки и выигрывает, симметрично повторяя ходы соперника. Если игрок А забирает из одной кучки гг фишек, игрок Б забирает столько же фишек из другой, и, когда А заберет все фишки из одной кучки, игрок Б заберет все фишки из другой и выиграет. Аналогично если игрок А совершит ход 2, то Б заберет нужное число фишек из той кучки, в которой их осталось больше. На столе останутся две одинаковые кучки, и игрок Б снова одержит победу, действуя как в предыдущем случае. Поэтому победу одерживает тот, кто заставит противника совершить один из двух «запрещенных» ходов. В рассматриваемом случае, если первый игрок берет 3 фишки из кучки, в которой 5 фишек, на столе останутся три кучки с 1, 2 и 3 фишками. Первый игрок выигрывает, так как его соперник будет вынужден или взять все фишки из одной кучки, или уравнять число фишек в двух кучках (оставив в них по 1 или по 2 фишки).
Очевидно, что это слишком частный случай и его сложно обобщить на произвольное число кучек и даже для трех кучек, но с большим числом фишек. Несмотря на это, математические методы позволяют найти выигрышную стратегию общего вида, применимую для любого количества кучек и фишек в каждой из них. Для этого нужно записать число фишек в каждой кучке в двоичной системе так, чтобы единицы были записаны под единицами. Каждым ходом четность как минимум в одном из столбцов будет меняться, так как после каждого хода будет изменяться только одно из чисел в одном или нескольких столбцах. Как минимум одна из цифр изменится с 1 на 0 или наоборот. Если в начальном расположении фишек сумма всех цифр каждого столбца четна, существует выигрышная стратегия для второго игрока: он должен ходить так, чтобы после хода сумма цифр во всех столбцах была четной. Первый игрок не может сделать такой ход. Если же хотя бы в одном столбце сумма цифр нечетна, то выигрышная стратегия существует для первого игрока: первым ходом он сможет сделать сумму цифр во всех столбцах четной и довести игру до победы.
Чтобы лучше понять суть этой стратегии, рассмотрим несколько примеров. Сначала мы рассмотрим три кучки с 1, 3 и 5 фишками (это игра 4, которую мы решили ранее). Затем мы перейдем к более привычной версии игры Ним под названием Мариенбад. В ней четыре кучки с 1, 3, 5 и 7 фишками.
В первом случае число фишек в кучках равно 1, 3 и 5.
1 в двоичной системе: 1
3 в двоичной системе: 11
5 в двоичной системе: 101
Сложим единицы в каждом столбце и увидим, что сумма цифр каждого столбца нечетная (справа налево: 3, 1 и 1). В этом случае существует выигрышная стратегия для первого игрока. Для этого ему нужно ходить так, чтобы суммы цифр во всех столбцах оставались четными. Единственный способ сделать это — забрать фишки из кучки, где их 5 (101), оставив 2 (10), то есть забрать 3 фишки из кучки с 5 фишками. Получим:
1 в двоичной системе: 1
3 в двоичной системе: 11
2 в двоичной системе: 10
Теперь сумма цифр в каждом столбце четная. Любой ход второго игрока сделает сумму цифр в одном из столбцов нечетной. После этого первый игрок сможет снова сделать все суммы цифр четными и так далее до финального положения. В финальном положении все цифры будут равны 0. Ноль — четное число, то есть суммы цифр во всех столбцах снова будут четными.
Игра 5: Мариенбад
На столе четыре кучки фишек. В кучках лежат 1, 3, 5 и 7 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?
Аналогично предыдущему случаю получим:
1 в двоичной системе: 1
3 в двоичной системе: 11
5 в двоичной системе: 101
7 в двоичной системе: 111
Так как в начальной позиции суммы цифр в каждом столбце четные, первый игрок не может выиграть. Выигрышная стратегия существует для второго игрока. Любой ход первого игрока сделает сумму цифр хотя бы в одном столбце нечетной. Допустим, что первый игрок взял одну фишку из кучки с тремя фишками. Получим:
1 в двоичной системе: 1
2 в двоичной системе: 10
5 в двоичной системе: 101
7 в двоичной системе: 111
В начале 50-х годов XX века инженеры английской компании Ferranti создали первый компьютер, предназначенный только для игр. Он назывался NIMROD. Первые три буквы NIM означали игру, для которой он и был спроектирован. На панели компьютера находились светящиеся лампочки, которые представляли положение фишек в игре. Прототип компьютера был представлен на выставке «Фестиваль Британии» в 1951 году. Считается, что это послужило началом эпохи электронных игр.
Теперь второй игрок должен сделать такой ход, чтобы сумма цифр в правом столбце стала четной, а остальные не изменились, так как они уже четные. Значит, нужно взять одну фишку из любой кучки, кроме второй. В двоичной системе это означает, что нужно заменить 1 на 0 в правом столбце.
Хотя найти стратегию игры Ним было намного сложнее, чем для предыдущих игр, о которых мы рассказали, для всех этих игр справедлива одна общая идея. Нужно найти равновесную ситуацию, которая совпадает с конечным положением, и определить, какой из игроков всегда сможет сохранять подобную ситуацию, а какой — никогда. Так, в первой игре этой главы («Игра 1: выигрывает первый») равновесная ситуация такова: нужно оставить на столе число фишек, кратное 3. Во второй игре («Игра 2: выигрывает второй») нужно записать число, кратное 11, а в последней игре Ним нужно оставить в каждой кучке такое число фишек, чтобы при записи количества фишек в двоичной системе сумма цифр в столбцах всегда была четной.
Во многих случаях для игры Ним используются противоположные правила: тот, кто забирает последнюю фишку, не выигрывает, а проигрывает. В этом случае выигрывает тот же игрок, что и при обычных правилах. Изначально используется та же стратегия, единственное различие появляется, когда во всех кучках остается менее двух фишек. В этом случае выигрышный ход — оставить всего одну фишку в нечетном числе кучек. В игре по обычным правилам нужно оставить одну фишку в четном числе кучек.
Как только мы узнали выигрышную стратегию для любой игры типа Ним, возникает вопрос: можно ли создать игру подобного типа, для которой бы не существовало выигрышной стратегии в общем случае? Ответ на этот вопрос положительный и ведет нас к так называемым играм типа Нимбус. Эти варианты игры Ним имеют одно существенное отличие: если мы хотим взять больше одной фишки из определенного ряда (кучки), это можно сделать только тогда, когда фишки расположены рядом, то есть между ними нет промежутков, образованных после предыдущих ходов. Появляется правило, касающееся расположения фишек в рядах, что раньше не учитывалось. Это аналогично следующему: всякий раз, когда мы берем фишки из ряда, этот ряд разделяется на два. Это будет происходить всегда, если мы не будем снимать одну из крайних фишек. Поскольку образуются новые кучки, игра меняется так, что для нее уже нельзя использовать стратегию игры Ним.
Это позиционная система счисления, в которой любое число можно представить с помощью всего двух цифр: 0 и 1. Чтобы преобразовать двоичное число в десятичное, нужно заменить все единицы степенями двойки. Показатели этих степеней будут зависеть от позиции цифры: правый разряд соответствует 20, следующий — 21 и так далее. Например, двоичное число 110101 в десятичной системе выглядит так: 1 • 20 + 0 • 21 + 1 • 22 + 0 • 23 + 1 • 24 + 1 • 25 = 1 + 4 + 16 + 32 = 53.
Аналогично для записи десятичного числа в двоичном виде нужно разделить его на 2, полученный результат снова разделить на 2 и так далее до тех пор, пока результатом деления не будет 1. Последний результат деления будет первой цифрой справа. Все прочие остатки отделения, от последнего к первому, составят следующие разряды (остаток от деления на 2 может равняться только 0 или 1). Например, 39 в двоичной системе записывается как 100111, так как 39:2 дает 19 (и остаток 1), 19:2 дает 9 (остаток 1), 9:2 дает 4 (остаток 1), 4:2 дает 2 (остаток 0), 2:2 дает 1 (остаток 0). Мы выразили число в виде суммы степеней двойки.
Итак, 39 =1 + 2 + 4 + 32 = 1•20 +1•21+1•22+0•23+0•24+1•25 = 100111 по основанию 2. Хотя двоичная нотация появилась сравнительно недавно, свойство, на котором она основана («всякое число можно представить в виде суммы различных степеней двойки»), было известно и применялось еще в древности. Например, древние египтяне использовали для умножения такую систему. Один из сомножителей удваивался, второй делился на 2. Если число было нечетным, то на 2 делилось предыдущее число. Этот метод дает верный результат именно благодаря указанному свойству.
Страница бюллетеня Французской академии наук, посвященная двоичной системе счисления, разработанной Лейбницем в 1703 году.
Вращаем кубик. Это стратегическая игра для двух игроков. Первый игрок ставит кубик на стол выбранной стороной вверх. Второй игрок поворачивает кубик на четверть оборота так, что на верхней грани будет уже другое число очков, и прибавляет это число к первому. Затем каждый игрок по очереди вращает кубик на четверть оборота (так можно получить любое число, кроме тех, что расположены на верхней или нижней грани кубика) и прибавляет число очков на верхней грани к общей сумме. Тот, кто набирает в сумме 31, выигрывает.
Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?
Разрезаем прямоугольник. Это стратегическая игра для двух игроков. На листе бумаги в клетку нужно нарисовать прямоугольник размерами 17 × 15 клеток. Затем нужно пометить квадратик в нижнем правом углу. Каждый из игроков своим ходом делит прямоугольник на две части вертикальной или горизонтальной линией и удаляет ту часть прямоугольника, которая не содержит маленький отмеченный квадрат. Тот, кто не сможет разделить прямоугольник (то есть от прямоугольника останется только один отмеченный квадратик), проигрывает.
Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?
Пересекаем круг. Это стратегическая игра для двух игроков. На листе бумаги нужно нарисовать окружность и обозначить на ней восемь произвольных точек. На каждом ходу игрок соединяет две точки отрезком. Он может соединить любые две точки, кроме уже соединенных, но нарисованный им отрезок не должен пересекать никакой другой отрезок. Игрок, которому не удастся провести такой отрезок, проигрывает.
Какой из игроков имеет преимущество? Что изменится, если изменить начальное число точек?
Цели и правила игры: эквивалентные и отличающиеся игры
При анализе целей и правил игры можно увидеть, что во многих случаях на первый взгляд отличающиеся стратегические игры на самом деле эквивалентны. И напротив, очень похожие игры в действительности сильно отличаются друг от друга и выигрышные стратегии для них явно разнятся.
Игра 6: продвижение по шестиугольным клеткам
Игровое поле изображено на рисунке 1. Каждый игрок берет единственную фишку, которая изначально расположена в ячейке S, и передвигает ее на соседнюю клетку. При этом он всегда должен двигаться вправо — по горизонтали или по диагонали. Игрок, который поставит фишку в крайнюю клетку М, выигрывает.
Рисунок 1.
Если читатель попытается решить игру сам, то легко увидит, в какие клетки нужно ставить фишку, чтобы победить. Если рассуждать в обратном направлении, то станет понятно, что первый игрок будет всегда выигрывать, если будет ставить фишку в помеченные крестиком клетки. Совсем не очевидно, что эта игра аналогична игре 1 («выигрывает первый»), если не заметить, что допустимые ходы можно интерпретировать как переход на два шага вперед (если мы передвигаем фишку в горизонтальном ряду) или на один шаг вперед (если мы двигаем фишку по диагонали и переставляем ее в другой ряд). Если пронумеровать клетки таким способом, то станет четко видна аналогия между этими играми (рисунок 2).
Рисунок 2.
Игра 7: поставь последнюю фишку
На игровой доске всего один ряд из шести клеток. На нем расставлены три фишки. На каждом ходу игрок выбирает фишку и передвигает ее вправо на любое количество клеток (минимум на одну и максимум на пять, в крайнюю правую клетку). Цель игры — поставить все фишки в крайнюю правую клетку. Тот, кто ставит в эту клетку последнюю фишку, выигрывает. В одной клетке могут одновременно находиться несколько фишек. Заметим, что эта игра эквивалентна первой рассмотренной нами версии игры Ним (игра 4): каждая фишка соответствует кучке, перенос фишки вправо соответствует взятию фишек из кучки в игре Ним. Когда фишка попадает в крайнюю правую клетку, это равносильно тому, что из кучки в игре Ним взяты все фишки. Рассмотрим еще две игры и проанализируем их эквивалентность.
Игра 8: цзяньшицзы
На стол выкладываются две кучки фишек, например 7 и 5 фишек. Каждый игрок может брать из выбранной кучки любое число фишек (минимум одну). Он также может брать фишки из двух кучек сразу, но в этом случае нужно брать одинаковое число фишек из каждой кучки.
Игра 9: спасти ферзя
На одну из клеток шахматной доски, например клетку h8, ставится ферзь. Каждый игрок может передвигать ферзя на любое количество клеток влево, вниз или по диагонали (то есть одновременно влево и вниз). Тот, кто поставит ферзя в клетку a1, то есть в левую нижнюю клетку, выигрывает.
Первая игра под названием цзяньшицзы — это игра типа Ним, в которой можно брать фишки из нескольких кучек. Эта возможность до сих пор не рассматривалась, и она существенно осложняет поиск общей выигрышной стратегии. Анализ возможных ходов во второй игре, «Спасти ферзя», позволяет сразу же увидеть, что эта игра аналогична первой. Ходы ферзя нужно рассматривать как взятие фишек: движение в горизонтальном ряду — это взятие фишек из первой кучки, движение в вертикальном ряду — взятие фишек из второй кучки, движение по диагонали — взятие одинакового количества фишек из обеих кучек сразу.
Из этих примеров становится понятно, что порой игры, кажущиеся совершенно разными, на самом деле полностью эквивалентны. Для этого достаточно иметь возможность преобразовать цель и правила одной игры в цель и правила другой. Однако в других случаях происходит обратное. Игры, которые кажутся полностью аналогичными, в действительности очень отличаются, особенно если разбирать их выигрышные стратегии. Рассмотрим еще одну игру, которая, кажется, полностью совпадает с игрой 1, о которой мы говорили выше.
Игра 10: маргаритка
Нарисуем маргаритку с 11 лепестками и поставим по одной фишке на каждом лепестке. На каждом ходу игрок может брать одну или две фишки, причем две фишки можно брать только с соседних лепестков.
Начальная позиция в игре«Маргаритка».
Эта игра очень похожа на первую игру из этой главы, но фишек не 20, а 11. Кажется, что выигрышная стратегия для первого игрока — взять две фишки на первом ходу, затем всегда оставлять число фишек, кратное трем. Однако наложенное ограничение (можно брать не любые две фишки, а только соседние) полностью нейтрализует эту стратегию. Теперь главную роль играет не количество фишек, а их расположение. Фактически исходное число фишек неважно, так как если фишек больше трех, то выигрышная стратегия звучит одинаково для любого числа фишек.
Эта игра уже не относится к семейству игр Ним. Она принадлежит к играм типа Нимбус, и общая стратегия для игр подобного типа неизвестна. Здесь мы рассказали о простейшей из игр такого типа. В нашем конкретном примере можно заметить, что второй игрок всегда будет выигрывать независимо от исходного числа фишек, если будет использовать симметричную стратегию. Попрактиковавшись в этой игре, можно увидеть, что если один из игроков разделит фишки на две одинаковые группы (если все фишки в одной группе находятся рядом, то и во второй они также должны находиться рядом), то будет всегда выигрывать, используя симметричную стратегию. Иными словами, он должен будет повторять для своей группы фишек ходы, которые делает соперник на другой группе фишек, причем положение фишек должно оставаться симметричным. Первый игрок не может разделить фишки на две группы первым ходом. Для этого ему нужно будет взять две фишки, не расположенные рядом друг с другом, что невозможно. Значит, после его хода между фишками образуется промежуток, и второй игрок сможет образовать второй промежуток, разделив фишки на две группы.
Современные абстрактные стратегические игры, несмотря на очевидную простоту, очень сложно анализировать. Хотя для них можно определить существование выигрышной стратегии, найти такую стратегию почти невозможно. Игра «Вавилон» французского автора Бруно Файдутти — наглядный пример подобных игр. На стол кладутся 12 фишек четырех разных цветов, по 3 фишки каждого цвета. Каждый из двух игроков берет одну стопку (изначально все стопки имеют высоту в 1 фишку) и кладет ее поверх другой, соблюдая следующие условия: одну стопку можно поставить на другую, если они имеют одинаковую высоту или же если верхние фишки обеих стопок одинакового цвета. Тот игрок, который не может поставить стопку поверх другой, проигрывает.
Хотя на первый взгляд кажется, будто решение можно найти, рассмотрев частные случаи с последующим обобщением, тщательный компьютерный анализ показывает, что найти стратегию, которую мог бы запомнить и использовать человек, невозможно.
«Вавилон»— игра, созданная Бруно Файдутти.
Игры и псевдоигры
Существуют игры, похожие на те, о которых мы только что говорили. Однако в действительности их нельзя назвать стратегическими играми, так как ни один из игроков не может повлиять на исход партии. Другими словами, выигрышная стратегия содержится в самих правилах, поэтому решения, принимаемые игроками, не имеют значения и не влияют на исход партии. Игры подобного типа, часто встречающиеся среди математических игр, получили название псевдоигр. Найти выигрышную стратегию для таких игр невозможно, так как ее не существует. Вместо этого можно доказать, что результат игры действительно не зависит от решений игроков и что правила однозначно определяют, кто будет всегда выигрывать. Рассмотрим три примера псевдоигр.
Игра 11: только нечетные
На столе лежит 20 фишек. Каждый из двух игроков своим ходом может взять 1, 3 или 5 фишек. Тот, кто забирает последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым или вторым? Что произойдет, если изменится число фишек? Эта игра является стратегической, как предыдущие, или же отличается от них?
Попрактиковавшись в этой игре, мы быстро увидим, что второй игрок всегда выигрывает, и первый игрок никак не может этому помешать. Можно сказать, что второй игрок будет выигрывать даже тогда, когда специально захочет проиграть. В отличие от предыдущих игр в этой игре определяющим условием является начальное число фишек и количество фишек, которое могут забирать игроки на каждом ходу. Значит, в этом случае нельзя говорить о выигрышной стратегии, так как победитель игры определен ее правилами.
Если изначально на столе лежит 20 фишек (или любое другое четное число) и первый игрок берет 1, 3 или 5 фишек (или любое другое нечетное число), то на столе останется нечетное число фишек (если вычесть из четного числа нечетное, получим нечетное). После этого второй игрок также должен взять нечетное количество фишек, и на столе останется четное число фишек (если вычесть из нечетного числа нечетное, получим четное число). Поэтому после хода первого игрока на столе всегда будет оставаться нечетное число фишек, а после хода второго игрока — четное. Так как 0 является четным числом, то побеждать всегда будет второй игрок вне зависимости от того, какие ходы будут совершать оба игрока. Аналогично, если начальное число фишек нечетно, победа всегда будет оставаться за первым игроком.
Игра 12: круги и квадраты
Нарисуем несколько кругов и квадратов, расположив их в ряд. Каждый игрок может убирать две одинаковые фигуры (два круга или два квадрата) и заменять их одним кругом, либо же забирать две разные фигуры и заменять их одним квадратом. Количество фигур будет постоянно уменьшаться, и в конце игры останется только одна. Если останется квадрат, выигрывает первый игрок, если останется круг — второй игрок. Существует ли стратегия, которая позволяет всегда выигрывать? Что произойдет, если изменить начальное число кругов и квадратов? Является ли эта игра стратегической? Рассмотрим начальную позицию, изображенную на рисунке ниже.
Сыграв несколько партий для такой расстановки, мы увидим, что второй игрок, кажется, всегда выигрывает (последней фигурой всегда будет круг). Если изменить число кругов, то кажется, что результат останется прежним. Если изменить число квадратов, то исход игры изменится.
Замкнуть треугольник. Это стратегическая игра для двух игроков. На листе бумаги нужно нарисовать окружность и обозначить на ней шесть произвольных точек. На каждом ходу игрок соединяет две точки отрезком. Один из игроков использует черный карандаш, второй игрок — красный карандаш. Каждый игрок может соединять любые две точки, кроме уже соединенных. Тот, кто нарисует треугольник со сторонами одного цвета, выигрывает.
Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать? Что изменится, если изменить начальное число точек? Можно играть по обратным правилам: тот, кто нарисует треугольник одного цвета, проигрывает. Что произойдет в этом случае?
Плитка шоколада (1). Плитка шоколада состоит из 28 окошек, расположенных в 4 ряда по 7 квадратиков. Первый игрок делит плитку на две части, не ломая ни одно из окошек. Второй игрок берет одну из полученных частей (другая откладывается в сторону) и снова делит ее. На каждом ходу игрок берет одну из двух только что полученных частей и делит ее на две части вдоль линий, разделяющих окошки. Тот, кто не сможет разделить плитку подобным образом, проигрывает.
Как нужно играть, чтобы выигрывать? Что изменится, если плитка будет состоять из 27 окошек, расположенных в 3 ряда по 9?
Плитка шоколада (2). На этот раз плитка состоит из 50 квадратных окошек, расположенных в 5 рядах по 10. Каждый игрок делит плитку (или ее часть) вдоль вертикальной или горизонтальной линии, не ломая ни одно из окошек. На этот раз ни одна из частей не откладывается в сторону, все они продолжают участвовать в игре. Первый игрок, который своим ходом получит одно отдельное окошко, проигрывает.
Как нужно играть, чтобы выигрывать? Что произойдет, если победителем будет объявляться тот, кто первым получит одно отдельное окошко?
Чтобы понять, что на самом деле это не игра и что победитель всегда определяется начальным положением фигур и самими правилами, нужно проанализировать, как меняется число квадратов по ходу партии. После каждого хода число квадратов может либо остаться неизменным (если два круга заменяются одним кругом, или если квадрат и круг заменяются квадратом), либо уменьшиться на два (если два квадрата заменяются одним кругом). Это означает, что если начальное число квадратов четное, то оно останется четным в течение всей партии. Следовательно, квадрат не может остаться последней фигурой, так как единица — нечетное число.
В этой главе мы говорили о стратегических играх, а именно о тех, которые можно полностью проанализировать. Мы увидели, как математика помогает найти выигрышную стратегию для одного из игроков, если такая стратегия существует. Такие эвристические методы, как изучение частных случаев; предположение, что игра завершена, и рассуждение в обратном направлении; использование симметрии, применяются при решении математических задач и полезны при анализе игр подобного типа. Как только для игры найдена выигрышная стратегия, это уже не игра, а решенная математическая задача.
В общих чертах проанализированные игры принадлежат к играм типа Ним, где важно количество фишек, и к играм типа Нимбус, где, помимо количества, также важно расположение фишек, поэтому выигрышные стратегии для игр типа Ним здесь неприменимы. В целом стратегии для игр типа Нимбус определять сложнее.