Игра Chomp

 


 

(----)


Правила игры

Играют два игрока, которые ходят по очереди. Игра ведется на прямоугольном поле. В начале игры на каждое поле помещается фишка. Ход делается так: игрок выбирает какую-нибудь фишку и снимает её и все фишки, которые находятся правее и выше её. Вот так:

Проигрывает тот, кто забирает фишку из левого нижнего угла поля — «отравленную» фишку. То же самое можно сформулировать так: выигрывает тот, кто не может сделать ход.

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

Теорема

На поле из одной клетки выигрывает игрок, который ходит вторым. На всех остальных полях выигрывает первый игрок.

Неформальное доказательство

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

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

Формальное доказательство

Клетки на поле будем обозначать парой натуральных чисел. Левая нижняя клетка будет иметь координаты (1, 1). Позиция — подмножество (обычно конечное) множества всех клеток. Ход можно обозначить как бесконечное множество пар натуральных чисел m(i0, j0) = {(i, j)| i ≥ i0 ∧ j ≥ j0}. Ходы применяются к позициям: q = p \ a, где p — позиция до хода a, q — позиция после хода, \ — вычитание множеств. Ход можно применить к позиции, только если их пересечение не пусто.

Так как ходы — множества, то для ходов a, b и позиции p верно a ⊂ b ⇒ p \ a \ b = p \ b. Если ход b содержит ход a, то последовательное применение ходов a и b приводит к той же позиции, что и единственный ход b.

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

Для всех позиций определим булеву функцию W. Для пустой позиции значение W — истина. Пусть W определена для всех позиций с количеством клеток не больше K. Определим W для позиции p из K + 1 клетки. Любой ход из p приводит нас в некоторую позицию q с числом клеток не больше K, для которой уже определено значение W(q). Определим, что W(p) — ложь, тогда и только тогда, когда W истинна для всех таких q. Соответственно, W(p) — истина тогда и только тогда, когда есть q такая, что W(q) — ложь.

Пусть первый игрок ходит из позиции p: W(p) — истина. Выберем ход в позицию q: W(q) — ложь. Любой ход второго игрока приведет нас в некоторую позицию r: W(r) — истина. Если первый игрок ходит из истинной позиции, то при любых действиях противника он может добиться того, что после пары ходов он снова окажется в истинной позиции. И так далее, пока игра не кончится в пустой позиции. W в пустой позиции — истина. Значит, ход будет у первого игрока. Он выиграет.

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

Докажем, что любая прямоугольная позиция M*N (M или N больше единицы) — выигрышная. Предположим, что это не так и позиция M*N — проигрышная. Пусть ход a = m(M, N) — ход с координатами (M, N). Позиция M*N \ a — выигрышная. Значит, есть некоторый выигрышный ход b — такой, что позиция M*N \ a \ b — проигрышная. Заметим, что a ⊂ b, следовательно, M*N \ a \ b = M*N \ b.

Мы предполагаем, что M*N — проигрышная, следовательно, M*N \ b должна быть выигрышной. То есть, одна и та же позиция и выигрышная, и проигрышная. Это противоречие; значит, исходное предположение неверно. Позиция M*N — выигрышная.

Итоги

Эта теорема — пример теоремы существования. Известно, что первый игрок выигрывает, но теорема не дает рецепта победы. Пока единственный способ — построить функцию W для всех возможных позиций. К счастью, ее можно вычислять прямо по определению. К сожалению, эти вычисления могут быть громоздкими.

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

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

История

В 1952 году Фред Шух (Fred Schuh) придумал «игру в делители». Игра получилась довольно абстрактной, её правила трудно объяснить нематематику. В 1974 году американский математик Дэвид Гейл (David Gale) независимо от Шуха изобретает её простой и наглядный вариант, который вы видели в начале этой статьи. Имя игре дал Мартин Гарднер, известный своим вкладом в занимательную математику. И Гейл, и Шух проанализировали игру для полей 2*N и N*N.

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

Осторожный Гейл предложил $100 за полный анализ игры в пространстве. Приз не востребован до сих пор: задача осталась нерешенной даже на плоскости.

Гейл также высказал гипотезу, что начальный выигрывающий ход уникален. Гарднер описал игру и гипотезу в своей колонке в Scientific American. Кен Томпсон (Ken Thompson), один из авторов Unix, опроверг гипотезу: на поле 8*10 оказалось два выигрышных хода. Проверка для полей 3*N показала, что выигрышный ход уникален для любых N вплоть до 130000.

Поля 3*N изучены лучше, чем остальные. Andries E. Brouwer заметил периодические закономерности в проигрышных позициях. Дорон Зельбергер (Doron Zeilberger) также обратил на них внимание. Ему не удалось доказать существование периода в общем случае, но он написал программу, которая проверяет гипотезу периодичности в частных случаях. Эта программа формулирует и проверяет гипотезы о периодах и, в конце концов, строит формулу, описывающую период.

Точную формулировку гипотезы о периодичности дал Xinyu Sun — студент Зельбергера. Доказал ее в общей форме Стив Бёрнс (Steve Byrnes) в 2002 году. Зельбергер, пользуясь результатами Бёрнса, сумел улучшить свою программу для поиска проигрышных позиций на поле 3*N.

Несколько обобщений

Обобщать Chomp можно самыми разными способами. Первое, что пришло в голову еще Гейлу — это попробовать сыграть в игру не на плоскости, а в пространстве.

«Игра в делители» Шуха тоже обобщает Chomp: возьмем целое число N и выпишем все его делители. Ход в игре состоит в выборе какого-нибудь делителя и удалении его и всех делителей, на которые он делится сам. Проигрывает тот, кто вынужден удалить число N. Связь между «игрой в делители» и Chomp становится ясной, если взять два различных простых числа p и q и вписать в клетки поля произведения их степеней. Например:

 p4q0   p3q0   p2q0   p1q0   p0q0 
 p4q1   p3q1   p2q1   p1q1   p0q1 
 p4q2   p3q2   p2q2   p1q2   p0q2 
 N = p4q3   p3q3   p2q3   p1q3   p0q3 

Таблица перечисляет все делители числа N. Удаление любого делителя влечет также удаление всех делителей правее и выше него. Chomp в пространстве — тоже частный случай «игры в делители».

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

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

Chomp в Интернете

Chaotic Chomp: the mathematics of crystal growth sheds light on a tantalizing game — Chomp пытались исследовать специалисты по динамическим системам. Кажется, их результаты больше полезны в динамических системах. В этой статье есть и исторический обзор.

Chomp on Wikipedia — Википедия посвятила игре отдельную небольшую статью.

Combinatorial Games, Combinatorial Game Theory — Chomp относится к классу комбинаторных игр. Первая страничка вводит в теорию комбинаторных игр, вторая — коллекция ссылок, относящихся к этому же предмету.

Ivars Peterson's MathTrek — еще один обзор игры.

Playing with Java: The Chomp game — Mati Pentus сделал апплет на Java для игры в Chomp.

CHOMP! — еще одна игра на страничке Thomas S. Ferguson.

Игра упомянута в книге А. К. Мусихин, "Логика или фортуна? Игры для всех." 1990 года издания. Ищите "Щёлк" в оглавлении.

Как устроена эта программа

Построение графа игры

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

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

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

Граф игры — это направленный граф, в котором позиции являются вершинами, а ходы — дугами. Работу алгоритма можно представить как раскрашивание вершин и ребер графа в два цвета: один для выигрывающих элементов, второй для проигрывающих.

Математика

Сколько времени понадобится на построение такого графа и сколько места нужно будет для его хранения? Подсчитаем число вершин и дуг в графе игры на поле M*N.

Каждую позицию можно представить в виде невозрастающей последовательности целых чисел — высот столбцов. Длина списка будет M. Каждое число может принимать значение от 1 до N. Каждое следующее число не больше предыдущего. Формула для числа таких последовательностей известна математикам: это число сочетаний из M + N по М или C(M + N, M)

C(n, k) = n! / (k!(n - k)!)

C(M + N, M) = (M + N)! / (M!N!)

Как можно вывести эту формулу? Возьмем любую позицию и пройдемся по ее краю между клетками из левого верхнего угла поля в правый нижний. Наш маршрут будет состоять из шагов вниз и направо. Шагов вниз будет сделано ровно N, шагов вправо — M. Вот пример для позиции на поле 9*7:

Если шаги обозначить стрелочками, то этой позиции будет соответствовать строка ↓→→→→→↓→↓→↓↓↓→↓→, начальной позиции — строка →→→→→→→→→↓↓↓↓↓↓↓, пустой позиции — строка ↓↓↓↓↓↓↓→→→→→→→→→. И наоборот, каждой последовательности стрелочек будет соответствовать своя позиция. Единственное требование — чтобы число стрелок направо было равно ширине поля, а число стрелок вниз — высоте. Сколько таких последовательностей? В строке длиной M + N надо выбрать места для M горизонтальных стрелок (остальные места займут вертикальные стрелки). Число разных способов выбора равно C(M + N, M).

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

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

Дополнение пустой позиции — полная и наоборот. Дополнение дополнения — сама исходная позиция. Число ходов на позиции и ее дополнении равна MN. Если взять все позиции и все их дополнения, то суммарное количество ходов будет MN C(M + N, M).

В списке дополнений каждая позиция встречается ровно один раз. Значит, в общем списке позиций и их дополнений каждая позиция встречается два раза. Следовательно, каждый ход тоже посчитан два раза. Окончательная формула для числа ходов из всех позиций на поле M*N:

MN C(M + N, M) / 2

Арифметика

Для поля 16*16 граф игры будет состоять из 601 080 390 позиций и 153 876 579 840 ходов. Современный компьютер может сделать в секунду около 3 миллиардов операций. Для построения функции W сложные операции не нужны — все сводится к перебору ходов из заданной позиции и чтению значений W из таблицы. Каждый ход будет просмотрен ровно один раз. Если тратить на просмотр хода ровно одну операцию, то время работы программы будет 154*109 / 3*109 ≈ 60 секунд. Это приемлемое время.

Сколько надо будет памяти? Все позиции перенумеруем, в каждой позиции сохраним список номеров позиций, в которые можно сделать ход. Номер займет 4 байта, всего понадобится 4 * 154*109 = 616*109 ≈ 574 Gb. Такой объем не поместится в оперативную память обычного компьютера. На большой жесткий диск эта таблица влезет, при этом операция обращения к таблице замедлится в тысячи или десятки тысяч раз.

К счастью, каждое ребро графа просматривается только один раз. Процедуры построения графа и вычисления функции W можно совместить, тогда ребра графа хранить в памяти не надо. Берем очередную позицию из списка, делаем из нее все возможные ходы, выбираем из таблицы значения W для уже подсчитанных позиций. Хранить надо будет только список, который должен будет обеспечивать быстрый поиск любой позиции и извлечение значения W для нее.

Хотя из таблицы убраны все ребра графа, при помощи нее все еще можно играть в Chomp. Чтобы найти выигрышный ход из какой-нибудь позиции, надо сделать из нее все ходы и проверить, не ведет ли хотя бы один из ходов в проигрышную позицию. Если такой ход есть, то он выигрышный. Если такого хода нет, то вам не повезло — вы сами в проигрышной позиции.

Если объем оперативной памяти — 4 Gb, то на одну позицию можно будет отвести самое большее 4 Gb * 8 бит / 600*106 ≈ 57 бит. Это много, тем более что можно позицию поместить в один бит. Вернее так: позиция займет ноль бит, и один бит будет отведен под значение W. Даже еще лучше: для хранения W достаточно будет четверти бита на позицию.

Двоичный Chomp

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

0111110101000101

Позиции однозначно сопоставлена строка из нулей и единиц, то есть число в двоичном представлении. В таком представлении удобно делать ходы. Надо выбрать отрезок строки, на котором обязательно встречается подстрока 10, затем все нули на этом отрезке снести влево, а единицы вправо. Ход сделан:

0111110101000101

0111110101000101

0111000011110101

0111000011110101

Играть в Chomp можно на двоичных строках по следующим правилам. Игроки договариваются о числе единичек и нулей в строке. Выписывают строку, в начале которой все единицы, в конце все нули. Ход состоит в выборе отрезка строки, внутри отрезка все нули переносятся влево, все единицы вправо. Ход обязательно должен привести к изменению строки. Выигрывает тот, кто не может сделать ход — все единицы оказались прижаты к правому краю строки. Назовем этот вариант "двоичный Chomp". Играть в него людям не очень удобно, но возможно. Для реализации на компьютере этот вариант подходит идеально. Позиция — число, ход — функция, которая по числу получает другое число. Числа эти могут быть индексами в битовом массиве, где будут храниться значения W. В этом смысле позиция не требует памяти — она просто индекс, который нигде хранить не надо. Битовый массив потребует 512 Mb для хранения 232 бит.

Чтобы вычислить функцию W надо сделать три вещи:

Первое требование — ход приводит к уменьшению числа. Докажем более сильное утверждение: если позиция A ⊂ B, то A < B (кстати, обратное неверно). Чтобы сравнить два числа, надо сравнить их битовые строки лексикографически. Перед сравнением более короткую строку надо дополнить слева нулями до длины более длинной.

Пусть A ⊂ B. Выпишем их битовые строки. Они одинаковой длины. Найдем первую слева пару различающихся битов. В позиции A несовпадающий бит будет нулевым (стрелка вниз), в B — единичным (стрелка направо). Иначе быть не может: нарушится условие A ⊂ B. Следовательно, A лексикографически меньше B. Следовательно, A < B.

Второе требование — перечисление всех позиций сводится к перебору всех битовых строк с определенным числом единичных битов. Эта задача хорошо изучена: она нужна для быстрой генерации сочетаний из n по k. Загляните в книгу «Алгоритмические трюки для программистов» Генри Уоррена младшего.

Третье требование — по позиции надо перечислить все ходы из нее. Решение также основано на идеях из книги Уоррена. Идея перебора проста: перебираем все отрезки бинарной строки и переупорядочиваем в них биты. Пара хитростей позволяет всегда работать только с теми отрезками, из которых можно сделать ход, и пропускать бесполезные.

Двоичное представление позволяет очень быстро перебирать позиции и очень быстро делать из них ходы. За секунду компьютер с тактовой частотой 2 GHz может перебрать около 250 миллионов ходов. То есть на один ход требуется в среднем восемь инструкций. Конечно, это только перебор, здесь не учитывается работа со списком в памяти. Но все равно результат впечатляющий: задача почти идеально ложится на архитектуру двоичного компьютера.

Последние шаги

До сих пор мы работали с позициями на поле фиксированного размера: битовая строка фиксированной длины с фиксированным числом единичных бит. Что будет, если отказаться от этих ограничений? Надо будет изменить перебор позиций: раньше перебирались только числа с фиксированным числом единиц, теперь будем перебирать все подряд. Все остальные части алгоритма остаются неизменными. Перебор всех чисел из k бит позволит играть на любом поле M*N при условии, что M + N ≤ k.

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

Проигрышные позиции — редкость. Вместо того чтобы хранить битовый массив, можно хранить список проигрышных позиций. Для 32-битовых позиций массив займет 256 Mb (хранятся только четные позиции, а их 231 штук), а список — ≈ 58 Mb (15 220 362 проигрышных позиций по 4 байта каждая).

Каждая позиция хранится в таблице вместе с ее зеркальным отражением относительно диагонали. Отражение строится так: переворачиваем строку битов задом наперед и инвертируем сами биты, затем отрезаем хвост из единиц. Из позиции и ее отражения можно оставить только один элемент — например, тот, что меньше. Таблица уменьшится почти в два раза — выигрыша не будет на симметричных позициях.

Таблица 32-битовых позиций строится около часа. Для скорости таблица хранится в памяти в виде битого массива. Почти все время уходит на его заполнение. Сжатие массива в список и удаление зеркальных дубликатов проходят почти мгновенно.

Можно было бы обработать и позиции с большим числом битов. Процессор современного компьютера будет обрабатывать 64-битовые позиции так же быстро, как и 32-битовые. Львиную долю времени будут съедать обращения к таблице. Сама таблица может перестать помещаться в память.

число
бит
время
работы
проигрышные
позиции
память
для проигрышных
позиций
память
для битового
массива
2512.3 s189 710741.05 Kb2 Mb
2627.3 s363 6031.39 Mb4 Mb
2757.1 s632 1052.41 Mb8 Mb
282.0 m1 154 4684.40 Mb16 Mb
294.3 m2 356 8868.99 Mb32 Mb
309.4 m3 893 67914.85 Mb64 Mb
3120.0 m8 295 97731.65 Mb128 Mb
3244.2 m15 220 36258.06 Mb256 Mb
33≈ 1.6 h≈ 105.09 Mb512 Mb
34≈ 3.3 h≈ 237.77 Mb1 Gb
35≈ 7.0 h≈ 430.36 Mb2 Gb
36≈ 14.9 h≈ 778.95 Mb4 Gb
37≈ 1.3 d≈ 1.38 Gb8 Gb
38≈ 2.8 d≈ 2.49 Gb16 Gb
39≈ 5.9 d≈ 4.51 Gb32 Gb
40≈ 12.5 d≈ 8.16 Gb64 Gb
41≈ 26.6 d≈ 14.78 Gb128 Gb
42≈ 56.3 d≈ 32.10 Gb256 Gb
43≈ 119.4 d≈ 58.10 Gb512 Gb
44≈ 253.2 d≈ 105.15 Gb1 Tb
45≈ 1.5 y≈ 190.33 Gb2 Tb

Там где в таблице указаны примерные значения — это экстраполяция. Количество проигрышных позиций и требуемая для них память даны без учета симметрии — их можно смело делить на два. Времена работы даны для алгоритма, работающего на битовом массиве. С целью экономии памяти можно перейти на список проигрышных позиций. Время работы тогда вырастет раз в 50-100 — оценку еще надо будет уточнить. Другой вариант — перенести таблицу из оперативной памяти на диск.

Кроме требований по памяти удручает быстрый рост времени работы. Здесь может помочь распределение алгоритма на несколько процессоров или компьютеров. Для этого будем вычислять W для позиций в порядке роста их площади. Если у вас таблица для позиций площади S или меньше, составьте список позиций площади S + 1 и раздайте его частями на разные процессоры. Полученные данные можно будет добавить в таблицу потом: на работу компьютеров на этапе S + 1 они не влияют.

Игра

Имея таблицу на сервере, не сложно сделать игру по сети. Клиент на JavaScript обеспечивает интерфейс и отсылку AJAX-запросов на сервер. Запрос включает позицию, ответ на запрос — список проигрышных позиций, достижимых в один ход. Клиент по паре позиций до и после хода восстанавливает сам ход и делает его. Если проигрышные позиции недостижимы, клиент делает какой-нибудь ход из одной клетки подальше от краев доски в надежде, что его противник сделает ошибку и можно будет перехватить инициативу.

Сервер написан на PHP. Чтобы ответить на запрос, он генерирует все ходы из присланной позиции и отыскивает получающиеся после ходов позиции в таблице, изготовленной заранее программой на C++. Сервер отвечает настолько быстро, что клиент даже делает задержку, чтобы пользователь увидел, что машина работает.

Открытые вопросы

Найти эффективную выигрышную стратегию для игры. Это, видимо, неразрешимая задача, но кто знает…

Сколько ходов можно сделать из всех позиций размером не более k бит? Или какой размер будет у графа игры для всех позиций размером не более k бит?

Вычислить таблицы W для возможно большего числа бит. 32 бита — решенная задача, 40 бит — кажется вполне достижимой, 48 бит — за пределами возможностей современной вычислительной техники?

Вычислить таблицы W для Chomp в пространстве. Нужно придумать эффективное представление позиций.

Таблицы W для Chomp больших размерностей. Все еще более туманно, чем в предыдущем вопросе.


Станислав Володарский
25 октября – 14 ноября 2009 года