Войти
Игра «Ростки» с двумя точками. Игра заканчивается, когда первый игрок не может провести соединительную линию между двумя свободными точками, отмеченными зеленым. Ростки - это игра с карандашом и бумагой, в которую можно играть просто как взрослыми, так и детьми. Однако его также можно проанализировать на предмет его важных математических свойств. Его изобрели математики Джон Хортон Конвей и Майкл С. Патерсон в Кембриджском университете в начале 1960-х годов. Настройка даже проще, чем в популярной игре Точки и квадраты, но игровой процесс развивается намного художественнее и органичнее.
Игра ведется двумя игроками, начиная с нескольких точек, нарисованных на лист бумаги. Игроки ходят по очереди, где каждый ход состоит в рисовании линии между двумя точками (или от точки к себе) и добавлении новой точки где-нибудь вдоль линии. Игроки ограничены следующими правилами.
В так называемой нормальной игре игрок, который делает последний ход побеждает. В игре misère игрок, сделавший последний ход, проигрывает . Misère Sprouts - это, пожалуй, единственная комбинаторная игра-мизер, в которую играют соревновательно на организованном форуме.
На диаграмме справа показана игра на 2 места с обычными Sprouts. После четвертого хода большинство точек мертвы - к ним прикреплены три линии, поэтому их нельзя использовать в качестве конечных точек для новой линии. Есть два пятна (показаны зеленым), которые все еще живы, и к ним прикреплено менее трех линий. Однако невозможно сделать еще один ход, потому что линия от активной точки к самой себе будет иметь четыре привязки, а линия от одной активной точки к другой будет пересекать линии. Следовательно, пятый ход невозможен, и первый игрок проигрывает. Живые места в конце игры называются выжившими и играют ключевую роль в анализе Ростков.
Из правил Sprouts не очевидно, что игра всегда заканчивается, поскольку количество точек увеличивается с каждым ходом. Правильный подход - учитывать количество жизней (возможностей подключения линии), а не количество точек. Затем мы можем показать, что если игра начинается с n точек, она закончится не более чем за 3n − 1 ходов и не менее чем за 2n ходов.
В следующих доказательствах мы предполагаем, что игра начинается с n точек и длится ровно m ходов.
Игра ростков с n начальными точками (синим цветом), которая заканчивается 3n − 1 ходом Каждая точка начинается с трех жизней, и каждый ход уменьшает общее количество жизней в игре на одну (две жизни теряются на концах линии, но на новом месте одна жизнь). Таким образом, в конце игры остается 3n − m жизней. У каждой выжившей точки есть только одна жизнь (в противном случае было бы еще одно движение, присоединяющее эту точку к самому себе), поэтому выживших ровно 3n − m. Должен быть хотя бы один выживший, а именно место, добавленное в последнем ходу. Итак, 3n − m ≥ 1; следовательно, игра может длиться не более 3n − 1 ходов.
Этот верхний предел на самом деле является максимумом, и его можно достичь многими способами, если в конце игры останется только один выживший. Например, в игре справа один выживший и 3n − 1 ходов.
Живые точки (зеленые) и их мертвые соседи (черные). В конце игры у каждого выжившего есть ровно два мертвых соседа, в техническом смысле «сосед» ", отличное от понятия смежности в обычном графе; см. диаграмму справа. Никакая мертвая точка не может быть соседом двух разных выживших, иначе к выжившим присоединился бы ход. Все остальные мертвые зоны (не соседи выжившего) называются фарисеями (от иврита для «разделенных »). Допустим, есть пфарисеи. Тогда
, поскольку начальные точки + перемещаются = общее количество мест в конце игры = выжившие + соседи + фарисеи. Перестановка дает:
Следовательно, игра длится не менее 2n ходов, а количество фарисеев делится на 4.
Игра ростков с n начальными точками, которая заканчивается за 2n ходов. Эта нижняя граница длины игры на самом деле является минимальной. На диаграмме справа показана завершенная игра из 2n ходов. У него n выживших, 2n соседей и 0 фарисеев.
Реальные игры, кажется, превращаются в битву за то, будет ли количество ходов k или k + 1, при этом другие возможности маловероятны. Один игрок пытается создать замкнутые области, содержащие выживших (таким образом уменьшая общее количество ходов, которые будут сыграны), а другой пытается создать фарисеев (таким образом, увеличивая количество ходов, которые будут сыграны).
Поскольку Sprouts - это конечная игра, в которой ничья невозможна, идеальная стратегия существует либо для первого, либо для второго игрока, в зависимости от количества начальных мест. Главный вопрос о данной стартовой позиции состоит в том, чтобы определить, какой игрок может добиться победы, если он или она играет идеально.
Когда выигрышная стратегия предназначена для первого игрока, говорят, что результатом позиции является «выигрыш», а когда выигрышная стратегия предназначена для второго игрока, говорят, что исход позиции позиция - это «проигрыш» (потому что это проигрыш с точки зрения первого игрока).
Результат определяется путем разработки дерева игр начальной позиции. Это можно сделать вручную только для небольшого количества точек, и все новые результаты с 1990 года были получены путем обширного поиска с помощью компьютеров.
Winning Ways for your Mathematical Plays сообщает, что обычная игра с шестью точками была доказана Денисом Моллисоном победой для второго игрока с помощью ручного анализа 47 страниц. Он оставался рекордом долгое время, пока не был проведен первый компьютерный анализ, который был выполнен в Университете Карнеги-Меллона в 1990 году Дэвидом Эпплгейтом и Дэниелом Слейтором. Они достигли 11 позиций с одним из лучших аппаратных средств, доступных в то время.
Эпплгейт, Якобсон и Слейтор наблюдали закономерность в своих результатах и предположили, что у первого игрока есть выигрышная стратегия, когда количество мест, деленное на шесть, оставляет остаток три, четыре или пять. Это математический способ сказать, что модель, отображаемая результатом в таблице ниже, повторяется бесконечно с периодом в шесть точек.
| Пятна | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ... |
| Нормальный результат | Убыток | Убыток | Убыток | Выигрыш | Выигрыш | Выигрыш | Выигрыш | Убыток | Выигрыш | Выигрыш | Победа | Победа | ... |
В 2001 году Риккардо Фокарди и Фламина Луччио описали метод, позволяющий вручную доказать, что обычная игра из 7 пунктов - это проигрыш.
Затем в 2006 году Джош Джордан расширил результаты вычислений до 14 точек. В 2007 году Жюльен Лемуан и Симон Вьенно представили алгоритм, основанный на концепции пилотов, для ускорения вычислений, достигая 32 точек. Они расширили вычисление до 44 точек в 2011 году и трех отдельных стартовых позиций, с 46, 47 и 53 точками.
Все результаты нормальной игры на данный момент согласуются с гипотезой Эпплгейта, Якобсона и Слеатор.
История вычислений Мизерной версии Спроутса очень похожа на ту, что и в обычной версии, с теми же людьми. Однако версию misère труднее вычислить, и прогресс был значительно медленнее.
В 1990 году Эпплгейт, Джейкобсон и Слейтор достигли девяти позиций. Основываясь на своих результатах, они предположили, что результат следует регулярной схеме пятого периода. Однако это предположение было опровергнуто в 2007 году, когда Джош Джордан и Роман Хорков расширили анализ мизера до 12 пунктов: игра с 12 пунктами мизера - это победа, а не предполагаемое поражение. В 2009 году та же команда достигла 16 позиций. В том же году Жюльен Лемуан и Симон Вьеннот достигли 17 позиций со сложными алгоритмами. В 2011 году они смогли расширить свой анализ до 20 очков.
Теперь предполагается, что результаты для игры «Мизер» следуют схеме длины шесть (с некоторыми исключительными значениями): первый игрок выигрывает в «Мизер Спрутс», когда остаток (mod 6) равен нулю, четырем или пяти, за исключением того, что первый игрок выигрывает игру с одним очком и проигрывает игру с четырьмя точками. В таблице ниже показан образец, где два нестандартных значения выделены жирным шрифтом.
| Пятна | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ... |
| Misère Outcome | Win | Win | Loss | Loss | Loss | Win | Win | Loss | проигрыш | проигрыш | выигрыш | выигрыш | выигрыш | проигрыш | проигрыш | Проигрыш | ... |
Игра в Брюссельскую капусту с двумя кроссами всегда длится ровно восемь ходов Вариант игры под названием Брюссельская капуста после крестоцветный овощ начинается с ряда крестиков, то есть пятен с четырьмя свободными концами. Каждый ход включает в себя соединение двух свободных концов кривой, опять же без пересечения существующей линии, а затем нанесение короткой черты поперек линии, чтобы создать два новых свободных конца. Эта игра конечна, и общее количество ходов (и, следовательно, победитель игры) предопределено начальным количеством крестиков: игроки не могут повлиять на результат своей игрой.
Каждый ход удаляет два свободных конца и добавляет еще два. При n начальных крестиках количество ходов будет 5n - 2, поэтому игра, начинающаяся с нечетного числа крестов, будет выигрышем первого игрока, а игра, начинающаяся с четного числа, будет выигрышом второго игрока, независимо от ходов..
Чтобы доказать это (предполагая, что игра окончена), пусть m обозначает количество ходов, а v, e, f обозначает количество вершин, ребер и граней плоского графа, полученного в конце игры соответственно. Имеем:
Эйлерова характеристика для плоских графов равно 2, поэтому
отсюда
Библиография
