| Жанр (ы) | игра на основе плитки |
|---|---|
| Игроки | 2 |
| Случайный шанс | никто |
| Требуются навыки | стратегия |
Доминирование (также называемое Stop-Gate или Crosscram ) - математическая игра, в которую можно играть на любом наборе квадратов на листе миллиметровой бумаги . Например, в нее можно играть на квадрате 6 × 6, прямоугольнике, совершенно неправильном полимино или на комбинации любого количества таких компонентов. У двух игроков есть набор домино, которые они по очереди кладут на сетку, закрывая квадраты. Один игрок кладет плитки вертикально, а другой - горизонтально. (Традиционно эти игроки называются «Левый» и «Правый», соответственно, или «V» и «H». В этой статье используются оба соглашения.) Как и в большинстве игр вВ комбинаторной теории игр проигрывает первый игрок, который не может двигаться.
Доминирование - это партизанская игра , в которой игроки используют разные фишки: беспристрастная версия игры - Крэм .
Основные примеры [ править ]
Одно окно [ править ]
За исключением пустой игры, в которой нет сетки, самая простая игра - это одиночный ящик.
Очевидно, что в этой игре ни один из игроков не может двигаться. Так как это выигрыш второго игрока, это нулевая игра .
Горизонтальные ряды [ править ]
Эта игра представляет собой сетку 2 на 1. Существует соглашение присваивать игре положительное число, когда выигрывает левый, и отрицательное, когда выигрывает право. В этом случае у Left нет ходов, в то время как Right может играть в домино, чтобы покрыть всю доску, не оставляя ничего, что явно является нулевой игрой. Таким образом, в сюрреалистической нотации чисел эта игра равна {| 0} = −1. Это имеет смысл, поскольку эта сетка дает преимущество на 1 ход для правого.
В этой игре также {| 0} = −1, потому что один ящик не воспроизводится.
Эта сетка - первый случай выбора. Правый может сыграть в два левых поля, оставив -1. В крайних правых ячейках также остается −1. Он также мог играть на двух средних боксах, оставляя два одиночных бокса. Эта опция оставляет 0 + 0 = 0. Таким образом, эту игру можно выразить как {| 0, −1}. Это -2. Если эта игра проводится вместе с другими играми, это два бесплатных хода вправо.
Вертикальные ряды [ править ]
Вертикальные столбцы оцениваются таким же образом. Если есть строка из 2 n или 2 n +1 ящиков, она считается как - n . Столбец такого размера считается как + n .
Более сложные сетки [ править ]
Это более сложная игра. Если первым идет Left, то при любом из этих ходов остается сетка 1 × 2, что равно +1. Право, с другой стороны, может переместиться в -1. Таким образом, сюрреалистическая запись чисел - {1 | −1}. Однако это не сюрреалистическое число, потому что 1> -1. Это игра, а не число. Обозначение для этого - ± 1, и это горячая игра , потому что каждый игрок хочет двигаться сюда.
Это сетка 2 × 3, которая еще более сложна, но, как и в любой игре «Доминирование», ее можно разбить на части, посмотрев на то, каковы различные ходы для левого и правого. Левый может занять левый столбец (или, что то же самое, правый столбец) и перейти к ± 1, но явно лучше разделить середину, оставив две отдельные игры, каждая из которых стоит +1. Таким образом, лучший ход левых - до +2. Справа есть четыре «разных» хода, но все они при некотором вращении оставляют следующую форму :
Эта игра не является горячей игрой (также называемой холодной игрой ), потому что каждый ход вредит игроку, который его делает, как мы можем видеть, изучив ходы. Левый может перемещаться на -1, Правый может перемещаться на 0 или +1. Таким образом, эта игра равна {−1 | 0,1} = {−1 | 0} = −½.
Таким образом, наша сетка 2 × 3 равна {2 | −½}, что также может быть представлено средним значением, ¾, вместе с бонусом за перемещение («температура»), 1¼, таким образом:
Игра высокого уровня [ править ]
Институт математических наук провел турнир « Доминирование» , победитель получил приз в размере 500 долларов. В эту игру играли на доске 8 × 8 . Победителем стал математик Дэн Калистрат, победивший в финале Дэвида Вулфа . Турнир подробно описан в « Играх без шансов» Ричарда Новаковски (стр. 85).
Стратегия победы [ править ]
Проблема Domineering состоит в том, чтобы вычислить выигрышную стратегию для больших досок, особенно квадратных. В 2000 году Деннис Брейкер, Йос Уитервейк и Яап ван ден Херик вычислили и опубликовали решение для доски 8x8. [1] Доска 9x9 появилась вскоре после некоторых улучшений их программы. Затем, в 2002 году, Натан Буллок решил доску 10х10 в рамках своей диссертации на тему «Власть». [2] Доска 11x11 была решена Йосом Уитервейком в 2016 году. [3]
Доминирование - это победа первого игрока на квадратных досках 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 и 11x11, а также победа второго игрока на досках 1x1 и 5x5. Другие известные значения прямоугольных досок можно найти на сайте Натана Буллока. [4]
Втиснуть [ править ]
Крэм - беспристрастная версия Доминирования. Единственное различие в правилах состоит в том, что каждый игрок может размещать свои домино в любой ориентации. Кажется, что это всего лишь небольшое изменение правил, но оно приводит к совершенно другой игре, которую можно проанализировать с помощью теоремы Спрага – Гранди .
См. Также [ править ]
- Blockbusting (игра) Комбинаторная игра, анализ которой был применен к Domineering.
Ссылки [ править ]
- ^ Брейкер, DM; Uiterwijk, JWHM; ван ден Херик, HJ (2000-01-06). «Решение проблемы с властью 8 × 8». Теоретическая информатика . 230 (1-2): 195-206. DOI : 10.1016 / S0304-3975 (99) 00082-1 .
- ^ Натан Баллок Власть: решение больших комбинаторных пространств поиска M.Sc. дипломная работа, 2002 г.
- ^ Uiterwijk, JWH 11x11 Власть решена: первый игрок побеждает . Компьютеры и игры, 2016. С. 129–136. DOI : 10.1007 / 978-3-319-50935-8_12 .
- ^ Nathan Bullock'site: Обновленные значения Игры Теоретико для властных советы
- Альберт, Майкл Х .; Новаковски, Ричард Дж .; Вулф, Дэвид (2007). Уроки в игре: Введение в комбинаторную теорию игр . АК Петерс, ООО ISBN 978-1-56881-277-9.
- Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2003). Выигрышные способы для ваших математических пьес . АК Петерс, ООО ISBN 978-0-12-091150-9.
- Гарднер, Мартин (1974). «Математические игры: зубрежка, кроссрам и квадрафаг: новые игры с неуловимыми выигрышными стратегиями». Scientific American . 230 (2): 106–108. DOI : 10.1038 / Scientificamerican0374-102 .
Внешние ссылки [ править ]
- Стоп-ворота в BoardGameGeek
- Игровая версия в Pencil and Paper Games
