Остатки несладки

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

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

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

Рис. 3. Примеры проигрышных (слева) и выигрышных состояний

Используя это определение, можно про каждое состояние выяснить, проигрышное оно или выигрышное.

Теперь можно строго сформулировать, что же такое — выигрышная стратегия. Это последовательность ходов одного из игроков, после каждого из которых его соперник получает проигрышное состояние шоколадки. Такая стратегия (если она вообще есть) есть только у одного из игроков. У какого? В этом и состоит пункт в).

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

В пункте в) министру и вам не помешает подумать о том, может ли откусывание правого верхнего уголка быть выигрышным первым ходом.

а) Внимательно поглядев на рис. 3, можно понять, как получаются проигрышные состояния из небольшого числа клеток.

Рис. 4. Еще одно проигрышное состояние

Состояние, изображенное на рис. 4, тоже проигрышное. Его можно достичь из сложившейся в пункте а) условия ситуации (рис. 2) за один ход, который и следует сделать министру (см. рис. 5).

Рис. 5. Решение пункта а)

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

Рис. 6. Откусывать верхнюю дольку плохо: дальше король сможет каждый раз оставлять министру нижний ряд на 1 дольку длиннее верхнего

Рис. 7. Откусывать слишком мало справа плохо: король сможет сделать, чтобы осталось состояние как на рис. 4. Это верно для любого хода министра «правее» второго столбика из долек (независимо от «высоты» хода)

Рис. 8. Откусывать слишком много сверху тоже плохо

Итак, получается, что в ситуации из пункта а) у министра всего один выигрышный ход. Остается надеяться, что он его тоже придумает.

б) Из решения пункта а) видно, что приходится перебирать варианты. Сначала нужно проанализировать состояния из небольшого числа долек (это сравнительно легко). К счастью, это достаточно сделать всего один раз — дальше можно пользоваться полученными результатами.

Затем нужно аккуратно понять, какие более сложные состояния сводятся к уже исследованным за один ход. И так далее. Это и есть раскручивание игры с конца. С увеличением размера исходной шоколадки вариантов становится всё больше и больше, причем это число растет очень быстро. Но шоколадку 8 × 3 еще можно исследовать «руками».

Например, ясно, что если в какой-то момент король оставит министру состояние из пункта а), то дальше министр сможет выиграть. Другое дело, что король тоже не глуп, и постарается этого не допустить. Это довольно просто — в шоколадке должно будет остаться еще много долек, и он просто сможет пойти как-нибудь еще, чтобы избежать этого состояния. Обсуждать все эти варианты — ход министра, ответный ход короля, и т. д. — довольно трудоемкое занятие, но нам это и не нужно, а достаточно просто предъявить выигрышную стратегию для министра. То есть последовательность проигрышных состояний, которые он сможет оставлять после каждого своего хода.

Первый ход показан на рис. 9.

Рис. 9. Первый ход министра

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

Рис. 10. Все проигрышные состояния, в которых верхний ряд не длиннее трех клеток, которые еще могут возникнуть после первого хода. Некоторые из них уже встречались ранее

в) Ответим на вопрос из подсказки 3. Допустим, что откусывание верхнего правого кусочка является выигрышным ходом. Тогда министру надо ходить первым, ходить именно так и дальше спокойно доводить дело до победы.

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

А теперь самое главное соображение. Любое состояние, которое могло получиться после первого хода второго игрока, первый игрок может достичь сам своим первым ходом. Действительно, после хода второго от шоколадки будет отломан какой-то прямоугольный кусок — формы вроде изображенных справа на рис. 1 получить он не сможет. Значит, первому нужно не отламывать правую верхнюю дольку, а сразу отломать весь прямоугольник. А дальше он может «украсть» стратегию второго и выиграть.

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

Эта игра, придуманная в такой формулировке американским математиком и экономистом Дэвидом Гейлом (David Gale), занимает важное место в теории игр. Это честная игра с полной информацией для двух игроков. В комбинаторной теории игр игра называется честной, если, во-первых, множество допустимых ходов определяется только текущей позицией и не зависит от того, кто из игроков должен сделать ход, а во-вторых, условия выигрыша и проигрыша для них одинаковы. В игре с полной информацией выполнены следующие условия:

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

Приведенные формулировки не совсем строгие, но дают представление о том, что изучает один из разделов теории игр.

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

Рассмотренную нами игру в англоязычной литературе обычно называют Chomp по характерному звуку при отламывании кусочка шоколадки. Название, по всей видимости, придумал Мартин Гарднер.

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

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

На удивление просто разобраться со случаем квадратной шоколадки n × n. Тут первым ходом нужно откусить большой кусок — квадрат (n – 1) × (n – 1), чтобы осталась отравленная долька с двумя растущими из нее рядами долек. А дальше первому игроку нужно просто ходить симметрично ходам второго.

Еще один вопрос, который возникает при анализе игры: всегда ли выигрышный первый ход единственный? Для шоколадок 3 × n при n < 130 000 ответ, судя по всему, положительный. А наименьший из известных примеров, когда больше одного такого хода, — шоколадка 8 × 10.

Помимо того, что мы обсуждали выше, у игры есть много разных вариантов и обобщений. Подчас — довольно непростых и требующих специальных математических знаний. Все они кроме чисто «спортивного» представляют и теоретический интерес — часто объекты, изучаемые в теории игр, служат моделями для реальных процессов, например в экономике.

Вот лишь некоторые из таких вариантов:

• Игра происходит на бесконечной вправо и вверх шоколадке. Тут работает та же стратегия, что и для квадратной шоколадки.
• Игра происходит на трёхмерной (конечной или бесконечной) «шоколадке». Тут есть довольно простой случай 2 × 2 × n. Остальные случаи при хоть сколько-нибудь больших размерах «шоколадки» еще подлежат исследованию.
• На самом деле, игру можно вести на любом частично упорядоченном множестве, в котором есть наименьший элемент. Это множество, некоторые элементы которого можно сравнивать, но при этом не обязательно каждая пара элементов сравнима. Например, в нашей игре множество состоит из «подшоколадок» исходной шоколадки, а порядок на них такой: кусок A больше куска B, если A входит в B.
  

  Рис. 11. Сравнимые куски шоколадки

  На рис. 11 изображены сравнимые куски шоколадки, а на рис. 12 — несравнимые. Ход состоит в исключении какого-либо элемента множества и всех больше него. Проигрывает тот, кому достанется наименьший элемент.

  

  Рис. 12. Несравнимые куски шоколадки