Ростки (дичь) - Sprouts (game)

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

Ростки это игра с бумагой и карандашом которым могут наслаждаться и взрослые, и дети. Тем не менее, его также можно проанализировать на предмет значительного математический характеристики. Это было изобретено математики Джон Хортон Конвей и Майкл С. Патерсон[1] в Кембриджский университет в начале 1960-х гг. Настройка даже проще, чем у популярных Точки и квадраты игра, но геймплей развивается намного художественнее и органичнее.

Правила

В игру играют два игрока,[2] начиная с нескольких точек, нарисованных на листе бумаги. Игроки ходят по очереди, где каждый ход состоит в рисовании линии между двумя точками (или от точки к себе) и добавлении новой точки где-нибудь вдоль линии. Игроки ограничены следующими правилами.

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

В так называемом нормальная игра, побеждает игрок, сделавший последний ход. В Misère играть в, игрок, который делает последний ход проигрывает. Misère Sprouts - это, пожалуй, единственная комбинаторная игра, в которую играют на соревнованиях на организованном форуме.[3]

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

Количество ходов

Из правил Sprouts не следует, что игра всегда заканчивается, поскольку количество точек увеличивается с каждым ходом. Правильный подход - учитывать количество жизни (возможность подключения линии) вместо количества точек. Затем мы можем показать, что если игра начинается с п пятен, закончится не более чем через 3п−1 ход и не менее 2п движется.

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

Максимальное количество ходов

Игра ростков с п начальные точки (синие), которые заканчиваются на 3п−1 ход

Каждое место начинается с трех жизни и каждый ход уменьшает общее количество жизней в игре на одну (две жизни теряются на концах линии, но на новом месте остается одна жизнь). Итак, в конце игры есть 3п−м оставшиеся жизни. У каждого выжившего места есть только одна жизнь (в противном случае было бы еще одно движение, присоединяющее это место к самому себе), поэтому их ровно 3п−м выжившие. Должен быть хотя бы один выживший, а именно место, добавленное в последнем ходу. Итак 3п−м ≥ 1; следовательно, игра может длиться не более 3п−1 ход.

Эта верхняя граница на самом деле является максимальной, и ее можно достичь многими способами, если в конце игры останется только один выживший. Например, в игре справа один выживший и 3п−1 ход.

Живые пятна (зеленые) и их мертвые соседи (черные).

Минимальное количество ходов

В конце игры у каждого выжившего остается ровно двое мертвых. соседи, в техническом смысле "сосед", отличается от обычного графа понятие смежности; см. диаграмму справа. Никакая мертвая точка не может быть соседом двух разных выживших, иначе к выжившим присоединился бы ход. Все остальные мертвые зоны (не соседи выжившего) называются фарисеи (от иврит за "разделенные "). Предположим, что есть п фарисеи. потом

поскольку начальные места + ходы = общее количество мест в конце игры = выжившие + соседи + фарисеи. Перестановка дает:

Следовательно, игра длится не менее 2п ходов, а количество фарисеев делится на 4.

Игра ростков с п начальные пятна, которые заканчиваются на 2п движется.

Эта нижняя граница длины игры на самом деле является минимальной. На диаграмме справа показана завершенная игра из 2 человек.п движется. Она имеет п выжившие, 2п соседи и 0 фарисеев.

Важность в реальных играх

Реальные игры, кажется, превращаются в битву за то, будет ли количество ходов k или же k+1, а другие возможности маловероятны.[4] Один игрок пытается создать замкнутые области, содержащие выживших (таким образом уменьшая общее количество ходов, которые будут сыграны), а другой пытается создать фарисеев (таким образом, увеличивая количество ходов, которые будут сыграны).

Стратегии победы

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

Когда выигрышная стратегия предназначена для первого игрока, говорят, что исход позиции - это «выигрыш», и когда выигрышная стратегия для второго игрока, говорят, что исход позиции - «проигрыш» (потому что это проигрыш с точки зрения первого игрока) .

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

Нормальная версия

Выигрышные способы для ваших математических игр сообщает, что обычная игра с 6 очками оказалась победой для второго игрока Денисом Моллисоном с ручным анализом 47 страниц. Рекордным он был долгое время, до первого компьютерного анализа, который был проведен в Университет Карнеги Меллон, в 1990 г. Дэвид Эпплгейт, Гай Джейкобсон, и Дэниел Слейтор.[5] Они достигли 11 позиций с одним из лучших доступных на то время аппаратных средств.

Эпплгейт, Джейкобсон и Слейтор наблюдали закономерность в своих результатах и ​​предположили, что у первого игрока есть выигрышная стратегия, когда количество мест, разделенное на шесть, оставляет остаток три, четыре или пять. Это математический способ сказать, что шаблон, отображаемый результатом в таблице ниже, повторяется бесконечно с периодом в шесть точек.

Пятна01234567891011...
Нормальный результатПотеряПотеряПотеряПобедитьПобедитьПобедитьПотеряПотеряПотеряПобедитьПобедитьПобедить...

В 2001 году Риккардо Фокарди и Фламина Луччио описали метод, позволяющий вручную доказать, что обычная игра с 7 очками - это проигрыш.[6]

Затем в 2006 году Джош Джордан расширил результаты вычислений до 14 точек. В 2007 году Жюльен Лемуан и Симон Виенно представили алгоритм, основанный на концепции ловцы для ускорения вычислений до 32 точек.[7] Они расширили подсчет до 44 точек в 2011 году и трех отдельных стартовых позиций с 46, 47 и 53 точками.[8]

Пока все результаты нормальной игры согласуются с гипотезой Эпплгейта, Якобсона и Слейтора.

Версия Misère

История вычислений в «misère» версии Sprouts очень похожа на таковую для обычной версии, с теми же людьми. Тем не менее Misère версию сложнее вычислить, и прогресс был значительно медленнее.

В 1990 году Эпплгейт, Джейкобсон и Слейтор поднялись до девяти мест. Основываясь на своих результатах, они предположили, что результат следует регулярной схеме пятого периода. Однако это предположение было опровергнуто в 2007 году, когда Джош Джордан и Роман Хорков расширили анализ мизера до 12 пунктов: игра с 12 пунктами мизера - это победа, а не предполагаемое поражение. В 2009 году эта же команда поднялась до 16 мест.[9] В том же году Жюльен Лемуан и Симон Вьеннот достигли 17 позиций со сложными алгоритмами.[10] В 2011 году они смогли расширить свой анализ до 20 пунктов.[8]

Теперь предполагается, что результаты для игры misère будут следовать схеме длины шесть (с некоторыми исключительными значениями): первый игрок выигрывает в игре misère Sprouts, когда остальные (мод 6) равно нулю, четырем или пяти, за исключением того, что первый игрок выигрывает игру с одним очком и проигрывает игру с четырьмя очками. В таблице ниже показан образец, где два нестандартных значения выделены жирным шрифтом.

Пятна0123456789101112131415...
Мизер РезультатПобедитьПобедитьПотеряПотеряПотеряПобедитьПобедитьПотеряПотеряПотеряПобедитьПобедитьПобедитьПотеряПотеряПотеря...

Брюссельская капуста

Игра «Брюссельская капуста» с двумя кроссами всегда длится ровно восемь ходов.

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

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

Чтобы доказать это (в предположении, что игра окончена), пусть м обозначают количество ходов и v, е, ж обозначают количество вершин, ребер и граней плоского графа, полученного в конце игры, соответственно. У нас есть:

  • е = 2м так как на каждом ходу игрок добавляет 2 ребра.
  • v = п + м так как на каждом ходу игрок добавляет одну вершину и игра начинается с п вершины.
  • ж = 4п так как в конце игры на каждой грани остается ровно один свободный конец, и количество свободных концов не меняется во время игры.

В Эйлерова характеристика планарных графов равно 2, поэтому

следовательно

Также можно сыграть в комбинацию стандартной и брюссельской капусты. Игра начинается с произвольного количества (n) точек или крестиков. На каждом ходу игрок может добавить точку или крест вдоль только что нарисованной линии. Продолжительность игры составляет от (2n) до (5n - 2), в зависимости от количества добавленных точек или крестиков.

При n = 1, начиная с точки, игра закончится через 2 хода; начиная с крестика, он закончится через 2 хода, если первый игрок добавит точку, через 3 хода, если он добавит крест: следовательно, у первого игрока есть выигрышная стратегия как для нормальной, так и для неправильной версии. При n> 1 анализ не завершен.


Рекомендации

  1. ^ Гарднер, Мартин (октябрь 1970 г.). «Математические игры - фантастические комбинации нового пасьянса Джона Конвея« Жизнь ».'" (PDF). Scientific American. 223: 120–123. Дои:10.1038 / Scientificamerican1070-120. Получено 30 января 2019.
  2. ^ Лам, Т. К. (10 апреля 2018 г.). «Связанные ростки». Американский математический ежемесячник. 104 (2): 116–119. Дои:10.1080/00029890.1997.11990609.
  3. ^ Пламбек, Тейн Э. (2006). «Успехи в проигрыше». п. 21. arXiv:математика / 0603027v1.
  4. ^ «Обсуждения на математическом форуме». Mathforum.org. Получено 2012-09-26.
  5. ^ "Дэвид Эпплгейт, Гай Джейкобсон и Дэниел Слейтор, Компьютерный анализ проростков, 1991". Cs.cmu.edu. Получено 2012-09-26.
  6. ^ Риккардо Фокарди и Фламина Луччо, Новый метод анализа для Sprouts Game, 2001
  7. ^ Жюльен, Лемуан; Саймон, Виеннот (2010). «Компьютерный анализ рассады с венчиками». arXiv:1008.2320 [math.CO ].
  8. ^ а б Записи о вычислениях нормальных и мизерских ростков, Веб-сайт Жюльена Лемуана и Саймона Вьенно
  9. ^ Новый проверенный ужасный результат, Объявление о 16-очковом исходе "Мизер", сайт WGOSA
  10. ^ Жюльен, Лемуан; Саймон, Виеннот (2009). «Анализ игры Misere Sprouts с редуцированными каноническими деревьями». arXiv:0908.4407 [math.CO ].

Библиография

внешняя ссылка