Введение
Математическая игра на бумаге и карандаше
Sprouts – это беспристрастная игра на бумаге и карандаше, математические свойства которой можно анализировать. Она была изобретена математиками Джоном Хортоном Конвеем и Майклом С. Паттерсоном в Кембриджском университете в начале 1960-х годов. Подготовка к игре еще проще, чем в популярной игре "точки и квадраты", но игровой процесс развивается гораздо более художественно и органично.
Правила
В игру играют два игрока, начиная с нескольких точек, нарисованных на листе бумаги. Игроки ходят по очереди, и каждый ход состоит в том, чтобы нарисовать линию между двумя точками (или от точки к самой себе) и добавить новую точку где-нибудь на этой линии. Игроки ограничены следующими правилами: линия может быть прямой или изогнутой, но не должна касаться или пересекать сама себя или любую другую линию. Новую точку нельзя размещать на одной из конечных точек новой линии. Таким образом, новая точка разделяет линию на две более короткие линии. Ни одна точка не может иметь более трех присоединенных к ней линий. Для целей этого правила линия от точки к самой себе считается двумя присоединенными линиями, а новые точки считаются имеющими две линии, уже присоединенные к ним. Нельзя коснуться одной точки дважды одной линией, а затем соединить ее с другой точкой. В так называемой нормальной игре побеждает игрок, сделавший последний ход. В игре мизер проигрывает игрок, сделавший последний ход. Misère Sprouts – пожалуй, единственная мизер-комбинаторная игра, в которую соревнуются на организованной площадке. Диаграмма справа показывает игру на 2 точки в обычной игре Sprouts. После четвертого хода большинство точек становятся «мертвыми» – к ним прикреплены три линии, поэтому их нельзя использовать в качестве конечных точек для новой линии. Есть две точки (показаны зеленым цветом), которые все еще «живы», поскольку к ним прикреплено менее трех линий. Однако сделать следующий ход невозможно, потому что линия от живой точки к самой себе создаст четыре соединения, а линия от одной живой точки к другой пересечет другие линии. Следовательно, пятый ход невозможен, и первый игрок проигрывает. Живые точки в конце игры называются «выжившими» и играют ключевую роль в анализе Sprouts.
The line may be straight or curved, but must not touch or cross itself or any other line. The new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines. No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them. You cannot touch a dot twice with one line then connect it to another. In so called normal play, the player who makes the last move wins. In misère play, the player who makes the last move loses. Misère Sprouts is perhaps the only misère combinatorial game that is played competitively in an organized forum. The diagram on the right shows a 2 spot game of normal play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line. There are two spots (shown in green) that are still alive, having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts.
Количество ходов
Игра в Sprouts всегда заканчивается, хотя этот факт не следует из правил игры, поскольку число точек увеличивается с каждым ходом. Чтобы понять, почему игра всегда завершается, следует рассматривать количество жизней (возможностей провести линию) вместо количества точек. Тогда можно показать, что если игра начинается с n точек, она закончится не более чем за 3n - 1 хода и не менее чем за 2n ходов. В последующих доказательствах предполагается, что игра начинается с n точек и продолжается ровно m ходов.
Максимальное количество ходов
Каждое место начинается с трех жизней, и каждый ход уменьшает общее количество жизней в игре на единицу (две жизни теряются на концах линии, но новое место получает одну жизнь). Таким образом, в конце игры остаётся 3n − m жизней. Каждое выжившее место имеет только одну жизнь (иначе был бы ещё один ход, соединяющий это место с самим собой), поэтому выживает ровно 3n − m мест. Должен быть хотя бы один выживший, а именно место, добавленное в последнем ходе. Следовательно, 3n − m ≥ 1; значит, игра может длиться не более 3n − 1 ходов. Эта верхняя граница фактически является максимальной, и её можно достичь многими способами, обеспечивая наличие только одного выжившего в конце игры. Например, в игре, показанной справа, есть один выживший и 3n − 1 ход.
Минимальное количество движений
В конце игры мертвое место называется соседом выжившего, если оно либо смежно с этим выжившим, либо, если у выжившего есть петля, оно смежно с местом, смежным с выжившим. Это иллюстрируется на диаграмме справа. У каждого выжившего ровно два мертвых соседа. Ни одно мертвое место не может быть соседом двух разных выживших, иначе бы существовал ход, соединяющий этих выживших. Все остальные мертвые места (не являющиеся соседями выживших) называются фарисеями (от еврейского слова, означающего "отделенные"). Предположим, что фарисеев p. Тогда, поскольку начальное количество мест + количество ходов = общее количество мест в конце игры = количество выживших + количество соседей + количество фарисеев. Перегруппировав, получим:
since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:
Consequently, a game lasts for at least 2n moves, and the number of pharisees is divisible by 4. This lower bound on the length of a game is actually the minimum. The diagram on the right shows a completed game of 2n moves. It has n survivors, 2n neighbors and 0 pharisees.
Следовательно, игра длится не менее 2n ходов, и количество фарисеев делится на 4. Эта нижняя граница длины игры является минимальной. Диаграмма справа показывает завершенную игру, состоящую из 2n ходов. В ней n выживших, 2n соседей и 0 фарисеев.
since initial spots + moves = total spots at end of game = survivors + neighbors + pharisees. Rearranging gives:
Consequently, a game lasts for at least 2n moves, and the number of pharisees is divisible by 4. This lower bound on the length of a game is actually the minimum. The diagram on the right shows a completed game of 2n moves. It has n survivors, 2n neighbors and 0 pharisees.
Значение в реальных играх
Реальные игры, кажется, превращаются в борьбу за то, чтобы количество ходов было равно k или k + 1, при этом другие варианты крайне маловероятны. Один игрок стремится создавать замкнутые области, в которых находятся выжившие (тем самым сокращая общее число ходов, которые будут сделаны), а другой – создавать "фарисеев" (тем самым увеличивая число ходов, которые будут сделаны).
Выигрышные стратегии
Поскольку Sprouts — это конечная игра, в которой ничья невозможна, идеальная стратегия существует либо для первого, либо для второго игрока, в зависимости от количества начальных точек. Основной вопрос, касающийся данной начальной позиции, заключается в определении того, какой игрок может обеспечить победу при безупречной игре. Если выигрышная стратегия есть у первого игрока, то говорят, что исход позиции — "выигрыш", а если у второго игрока — то исход позиции — "проигрыш" (поскольку это проигрыш с точки зрения первого игрока). Исход определяется путем построения игрового дерева начальной позиции. Это можно сделать вручную только для небольшого числа точек, а все новые результаты, полученные после 1990 года, были получены в результате масштабного компьютерного поиска.
Нормальная версия
В книге «Winning Ways for your Mathematical Plays» сообщается, что игра с 6 фишками в нормальной позиции была доказана как выигрышная для второго игрока Денисом Моллисоном, посредством ручного анализа объёмом 47 страниц. Этот результат долгое время оставался рекордным, пока в 1990 году в Университете Карнеги-Меллон Дэвид Апплегейт, Гай Джейкобсон и Дэниел Слейтор не провели первый компьютерный анализ. Им удалось исследовать позиции с количеством фишек до 11, используя лучшее доступное на тот момент оборудование. Апплегейт, Джейкобсон и Слейтор обнаружили закономерность в полученных результатах и выдвинули предположение, что у первого игрока есть выигрышная стратегия, если число фишек при делении на шесть даёт остаток 3, 4 или 5. Математически это означает, что закономерность, демонстрируемая результатами в приведенной ниже таблице, повторяется бесконечно с периодом в шесть фишек.
In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7 spot game is a loss. Then, the computation results were extended in 2006 by Josh Jordan up to 14 spots. In 2007, Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of nimbers to accelerate the computation, reaching up to 32 spots. They have extended the computation up to 44 spots in 2011, and three isolated starting positions, with 46, 47 and 53 spots. The normal play results so far are all consistent with the conjecture of Applegate, Jacobson, and Sleator.
Фишки 0 1 2 3 4 5 6 7 8 9 10 11
Нормальный исход Проигрыш Проигрыш Проигрыш Выигрыш Выигрыш Выигрыш Проигрыш Проигрыш Проигрыш Выигрыш Выигрыш Выигрыш
In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7 spot game is a loss. Then, the computation results were extended in 2006 by Josh Jordan up to 14 spots. In 2007, Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of nimbers to accelerate the computation, reaching up to 32 spots. They have extended the computation up to 44 spots in 2011, and three isolated starting positions, with 46, 47 and 53 spots. The normal play results so far are all consistent with the conjecture of Applegate, Jacobson, and Sleator.
В 2001 году Риккардо Фокарди и Фламина Луччо описали метод ручного доказательства того, что нормальная игра с 7 фишками является проигрышной. В 2006 году Джош Джордан расширил результаты вычислений до 14 фишек. В 2007 году Жюльен Лемойн и Саймон Вьенно разработали алгоритм, основанный на понятии ним-чисел, для ускорения вычислений и достигли 32 фишек. В 2011 году они расширили вычисления до 44 фишек, а также исследовали три изолированные начальные позиции с 46, 47 и 53 фишками. Результаты нормальной игры, полученные на данный момент, полностью согласуются с гипотезой Апплегейта, Джейкобсона и Слейтора.
In 2001, Riccardo Focardi and Flamina Luccio described a method to prove by hand that the normal 7 spot game is a loss. Then, the computation results were extended in 2006 by Josh Jordan up to 14 spots. In 2007, Julien Lemoine and Simon Viennot introduced an algorithm based on the concept of nimbers to accelerate the computation, reaching up to 32 spots. They have extended the computation up to 44 spots in 2011, and three isolated starting positions, with 46, 47 and 53 spots. The normal play results so far are all consistent with the conjecture of Applegate, Jacobson, and Sleator.
Версия Мизера
История вычислений для мизэрной версии Sprouts очень похожа на историю вычислений для обычной версии, с участием тех же исследователей. Однако мизэрная версия сложнее в вычислениях, и прогресс был значительно медленнее. В 1990 году Апплегейт, Джейкобсон и Слейтор достигли девяти точек. На основании их результатов они предположили, что исход подчиняется регулярному паттерну с периодом пять. Однако это предположение было опровергнуто в 2007 году, когда Джош Джордан и Роман Хорков расширили анализ мизэрной игры до 12 точек: игра в 12 точек в мизэрной версии является выигрышной, а не проигрышной, как предполагалось. Та же команда достигла 16 точек в 2009 году. В том же году Жюльен Лемойн и Саймон Виенно достигли 17 точек, используя сложные алгоритмы. Им удалось расширить свой анализ до 20 точек в 2011 году. В настоящее время считается, что результаты мизэрной игры следуют паттерну длиной шесть с некоторыми исключениями: первый игрок выигрывает в мизэрных Sprouts, когда остаток от деления на 6 равен нулю, четырем или пяти, за исключением того, что первый игрок выигрывает в игре в одну точку и проигрывает в игре в четыре точки. Таблица ниже показывает этот паттерн, где два нерегулярных значения выделены жирным шрифтом. Точки 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Исход мизэрной игры Выигрыш Выигрыш Проигрыш Проигрыш **Проигрыш** Выигрыш Выигрыш Проигрыш Проигрыш **Проигрыш** Выигрыш Выигрыш Выигрыш Проигрыш Проигрыш Проигрыш