Властный
 Пример игры «Доминирование», играемой на доске 5х5, где горизонтальный игрок («H» или «Право») делает первый ход и проигрывает в 13-м раунде игры. | |
| Жанры | игра с плитками |
|---|---|
| Игроки | 2 |
| Шанс | никто |
| Навыки | стратегия |
Domineering (также называемая Stop-Gate или Crosscram ) — это математическая игра , в которую можно играть с любым набором квадратов на листе миллиметровой бумаги . Например, в нее можно играть на квадрате 6х6, прямоугольнике, полностью неправильном полимино или на комбинации любого количества таких компонентов. У двух игроков есть набор домино , которые они по очереди кладут на сетку, закрывая квадраты. Один игрок размещает плитки вертикально, а другой — горизонтально. (Традиционно этих игроков называют «Левым» и «Правым» соответственно или «V» и «H». В этой статье используются оба обозначения.)Как и в большинстве игр комбинаторной теории игр , проигрывает тот игрок, который первым не может сделать ход.
Domineering — это партизанская игра , в которой игроки используют разные фигуры: беспристрастная версия игры — Cram .
Основные примеры
[ редактировать ]Одиночная коробка
[ редактировать ]Если не считать пустой игры, в которой нет сетки, самой простой игрой является игра с одним ящиком.
Очевидно, что в этой игре ни один игрок не может двигаться. Поскольку это победа второго игрока, то это нулевая игра .
Горизонтальные ряды
[ редактировать ]
Эта игра представляет собой сетку 2 на 1. Существует соглашение, согласно которому игре присваивается положительное число , когда выигрывает Левый, и отрицательное , когда выигрывает Правый. В этом случае у Левого нет ходов, а Правый может сыграть в домино, чтобы покрыть всю доску, ничего не оставив, что явно является нулевой игрой. Таким образом, в сюрреалистической записи чисел эта игра равна {|0} = −1. Это имеет смысл, поскольку эта сетка дает преимущество в 1 ход для правого.
В этой игре также {|0} = −1, поскольку в один ящик играть невозможно.
Эта сетка является первым случаем выбора. Правый может сыграть на двух левых полях, оставив −1. Крайние правые поля также оставляют −1. Он также мог играть в двух средних ящиках, оставив два одиночных ящика. Этот вариант оставляет 0+0 = 0. Таким образом, эту игру можно выразить как {|0,−1}. Это −2. Если в эту игру играют вместе с другими играми, это два бесплатных хода для правой стороны.
Вертикальные ряды
[ редактировать ]Вертикальные столбцы оцениваются таким же образом. Если есть ряд из 2 n или 2 n +1 ящиков, он считается как − n . Столбец такого размера считается как + n .
Более сложные сетки
[ редактировать ]
Это более сложная игра. Если первым идет «Влево», любой ход оставляет сетку 1×2, что равно +1. С другой стороны, Right может перейти в −1. Таким образом, сюрреалистическая запись чисел равна {1|−1}. Однако это не сюрреалистическое число, поскольку 1 > −1. Это игра, а не число. Обозначение для этого — ±1, и это горячая игра , потому что каждый игрок хочет сюда пойти.
Это сетка 2×3, которая еще более сложна, но, как и в любой игре «Доминирование», ее можно разбить, посмотрев, каковы различные ходы для левого и правого направления. Левый может взять левый столбец (или, что то же самое, правый столбец) и переместиться на ±1, но явно лучше разделить середину, оставив две отдельные игры, каждая из которых стоит +1. Таким образом, лучший ход Левого — +2. оставляют следующую форму Справа есть четыре «разных» хода, но все они при некотором вращении :
Эта игра не является горячей игрой (также называемой холодной игрой ), поскольку каждый ход причиняет вред игроку, который его делает, как мы можем видеть, изучая ходы. Левый может переместиться на −1, правый может перейти на 0 или +1. Таким образом, эта игра есть {−1|0,1} = {−1|0} = − 1 ⁄ 2 .
Тогда наша сетка 2×3 равна {2|− 1 ⁄ 2 }, что также может быть представлено средним значением, 3 ⁄ 4 вместе с бонусом за перемещение («температура»), 1 + 1 ⁄ 4 , таким образом:
Игра на высоком уровне
[ редактировать ]В НИИ математических наук «Доминирование» был проведен турнир с призом в 500 долларов для победителя. В эту игру играли на доске 8×8. Победителем стал математик Дэн Калистрейт, победивший Дэвида Вулфа в финале . Турнир подробно описан в книге Ричарда Дж. Новаковски «Без шансов» (стр. 85).
Выигрышная стратегия
[ редактировать ]
Проблема Доминирования заключается в вычислении выигрышной стратегии для больших досок, особенно для квадратных. В 2000 году Деннис Бройкер, Йос Уитервейк и Яап ван ден Херик вычислили и опубликовали решение для доски 8х8. [1] Доска 9x9 появилась вскоре после некоторых улучшений их программы. Затем, в 2002 году, Натан Баллок решил задачу на доске 10x10 в рамках своей диссертации на тему «Доминирование». [2] Доска 11x11 была решена Йосом Уитервейком в 2016 году. [3]
Доминирование — это победа первого игрока на квадратных досках 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 и 11x11, а также победа второго игрока на досках 1x1 и 5x5. Некоторые другие известные значения прямоугольных досок можно найти на сайте Натана Буллока. [4]
Зубрить
[ редактировать ]Крам — беспристрастная версия Доминирования. Единственная разница в правилах заключается в том, что каждый игрок может размещать свои домино в любой ориентации. Кажется, что это всего лишь небольшое изменение в правилах, но в результате получается совершенно другая игра, которую можно проанализировать с помощью теоремы Спрага–Грунди .
См. также
[ редактировать ]- Блокбастер (игра) Комбинаторная игра, анализ которой был применен к Доминированию.
Ссылки
[ редактировать ]- ^ Брейкер, Д.М.; Уитервейк, JWHM; ван ден Херик, HJ (6 января 2000 г.). «Решение доминирования 8х8» . Теоретическая информатика . 230 (1–2): 195–206. дои : 10.1016/S0304-3975(99)00082-1 .
- ^ Натан Баллок Доминирование: Решение больших комбинаторных пространств поиска, магистр наук. диссертация, 2002 г.
- ^ Уитервейк, JWH 11x11 Проблема доминирования решена: побеждает первый игрок . Компьютеры и игры 2016. С. 129–136. дои : 10.1007/978-3-319-50935-8_12 .
- ^ Натан Буллок. «Обновленные теоретические ценности игр для доминирующих досок» . webdocs.cs.ualberta.ca . Проверено 16 февраля 2023 г.
- Альберт, Майкл Х .; Новаковски, Ричард Дж.; Вулф, Дэвид (2007). Уроки игры: введение в комбинаторную теорию игр . АК Питерс, ООО ISBN 978-1-56881-277-9 .
- Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2003). Пути выигрыша в математических играх . АК Питерс, ООО ISBN 978-0-12-091150-9 .
- Гарднер, Мартин (1974). «Математические игры: зубрежка, перекрестная зубрежка и квадрафаг: новые игры с неуловимыми выигрышными стратегиями». Научный американец . 230 (2): 106–108. doi : 10.1038/scientificamerican0374-102 .