Крам (игра)
Зубрежка — это математическая игра , в которую играют на листе миллиметровой бумаги (или на сетке любого типа). Это беспристрастная версия « Доминирования» , и единственная разница в правилах заключается в том, что игроки могут размещать свои домино в любой ориентации, но в результате получается совсем другая игра. Его называли многими именами, в том числе «плагг» Джеффри Мотт-Смита и «точки и пары». Крэм был популяризирован Мартином Гарднером в журнале Scientific American . [1]
Правила
[ редактировать ]В игру играют на листе миллиметровой бумаги, на котором обрисован любой набор рисунков. Чаще всего в нее играют на прямоугольной доске, такой как квадрат 6×6 или шахматная доска , но в нее также можно играть на совершенно неправильном многоугольнике или цилиндрической доске.
У двух игроков есть набор домино , которые они по очереди кладут на сетку. Игрок может разместить домино как горизонтально, так и вертикально. В отличие от родственной игры «Доминирование», возможные ходы для двух игроков одинаковы, и в этом случае игра Cram становится беспристрастной .
Что касается всех беспристрастных игр, то существует два возможных соглашения о победе: в нормальной игре проигрывает тот игрок, который не может двигаться первым, и, наоборот, в версии с мизером побеждает тот игрок, который не может двигаться первым.
Симметричная игра
[ редактировать ] |
Выигрышная стратегия для обычного Cram проста для досок «чет-чет» и «чет-нечет». В случае «чет-чет» второй игрок выигрывает за счет симметричной игры. Это означает, что для любого хода Игрока 1 Игрок 2 имеет соответствующий симметричный ход по горизонтальной и вертикальной осям. В некотором смысле, игрок 2 «имитирует» ходы, сделанные Игроком 1. Если Игрок 2 следует этой стратегии, Игрок 2 всегда будет делать последний ход и, таким образом, выигрывать игру.
В случае «чет-нечет» первый игрок выигрывает благодаря аналогичной симметрии. Игрок 1 кладет свое первое домино в центр двух клеток сетки. Затем игрок 2 делает свой ход, но после этого игрок 1 может играть симметрично, обеспечивая таким образом победу игроку 1. [2]
Симметричная игра — бесполезная стратегия в версии Misère , потому что в этом случае она только гарантирует игроку проигрыш .
Обычная версия
[ редактировать ]Значение Гранди
[ редактировать ]Поскольку Крэм — беспристрастная игра , теорема Спрэга–Грунди указывает, что в нормальной версии любая позиция Крэма эквивалентна куче нимов заданного размера, также называемого значением Гранди . Некоторые значения можно найти в разделе «Пути к победе в математических играх» , в частности, поле 2 × n , значение которого равно 0, если n четное, и 1, если n нечетное.
Стратегия симметрии подразумевает, что доски с четным числом имеют значение Гранди, равное 0, но в случае досок с четным и нечетным это подразумевает только значение Гранди, большее или равное 1.
| п × м | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 2 | 0 | 3 | 0 | 1 |
| 5 | - | 0 | 2 | 1 | 1 | 1 |
| 6 | - | - | 0 | 5 | 0 | 1 |
| 7 | - | - | - | 1 | 3 | 1 |
Известные значения
[ редактировать ]В 2009 году Мартин Шнайдер рассчитал значения Гранди для досок 3 × 9, 4 × 5 и 5 × 7. [3] В 2010 году Жюльен Лемуан и Саймон Вьенно применили к игре Cram алгоритмы, изначально разработанные для игры Sprouts . [4] Это позволило им вычислить значения Гранди до досок 3 × 20, 4 × 9, 5 × 9, 6 × 7 и 7 × 7. [5] Петр Белинг распространил эти результаты на доски 6 × 9, 7 × 8 и 7 × 9. [6]
Последовательность известных на данный момент значений Гранди для досок 3 × n , от n=1 до n=20, следующая: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3. , 1, 4, 0, 1, 0, 2. Никакой закономерности не наблюдается.
В таблице ниже подробно описаны известные результаты для досок, оба размера которых больше 3. Поскольку значение доски n × m такое же, как и значение доски m × n , мы приводим только верхнюю часть таблицы.
Версия страдания
[ редактировать ]Гранди-ценность страдания
[ редактировать ]Значение Мизера Гранди игры G определяется Конвеем в книге «О числах и играх» как уникальное число n, такое, что G+n является победой второго игрока в игре Мизер. [7] Даже если оно очень похоже на обычное значение Гранди в обычной игре, оно не такое мощное. В частности, невозможно вывести значение Misère Grundy для суммы игр только из соответствующих им значений Misère Grundy.
| п × м | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | - | 2 | 1 | 1 | ? | ? |
| 6 | - | - | 1 | ? | ? | ? |
В 2009 году Мартин Шнайдер рассчитал значения Мизер Гранди для досок 3 × 9, 4 × 6 и 5 × 5. [3] В 2010 году Жюльен Лемуан и Симон Вьенно распространили эти результаты на доски 3 × 15, 4 × 9 и 5 × 7, а также на ценность доски 6 × 6. [5]
Последовательность известных на данный момент значений Мизера Гранди для досок 3 × n , от n=1 до n=15, следующая: 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. Предполагается, что эта последовательность периодична периода 3. [5]
В соседней таблице подробно описаны известные результаты Мизера для досок с обоими размерами больше 3.
Ссылки
[ редактировать ]- Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2003). Пути выигрыша в математических играх . АК Питерс, ООО
- ^ Гарднер, Мартин (1974). «Математические игры: набор, перекрестный набор и квадрафаг: новые игры с неуловимыми выигрышными стратегиями». Научный американец . 230 (2): 106–108. doi : 10.1038/scientificamerican0374-102 .
- ^ Уитервейк, Йос (декабрь 2020 г.). «Решение головоломки с использованием теории комбинационных игр» . Исследовательские ворота .
- ^ Jump up to: а б Игра Juvavum , Мартин Шнайдер, Магистерская диссертация, 2009 г.
- ^ Жюльен, Лемуан; Саймон, Вьенно (2010). «Нимберы неизбежны». arXiv : 1011.5841 [ math.CO ].
- ^ Jump up to: а б с Записи вычислений нормального и несчастного Крама , веб-сайт Жюльена Лемуана и Саймона Вьенно
- ^ Программное обеспечение Rust для решения беспристрастных игр Петр Белинг
- ^ Джон Х., Конвей (2000). О числах и играх . АК Питерс, ООО