Властный - Domineering
| Жанр (ы) | игра на основе плитки |
|---|---|
| Игроки | 2 |
| Случайный шанс | никто |
| Требуются навыки | стратегия |
Властный (также называемый Stop-Gate или же Crosscram) это математическая игра который можно воспроизвести на любом наборе квадратов на листе миллиметровая бумага. Например, в нее можно играть на квадрате 6 × 6, прямоугольнике, совершенно неправильной форме. полимино или комбинация любого количества таких компонентов. У двух игроков есть коллекция домино которые они по очереди размещают на сетке, закрывая квадраты. Один игрок кладет плитки вертикально, а другой - горизонтально. (Традиционно эти проигрыватели называются «Левый» и «Правый», соответственно, или «V» и «H». В этой статье используются оба соглашения.) наиболее игры в комбинаторная теория игр, проигрывает первый игрок, который не может двигаться.
Власть - это партизанская игра, в котором игроки используют разные фигуры: беспристрастный версия игры Втиснуть.
Основные примеры
Одна коробка
За исключением пустой игры, в которой нет сетки, самая простая игра - это одиночный ящик.
Очевидно, что в этой игре ни один из игроков не может двигаться. Поскольку это победа второго игрока, значит, это нулевая игра.
Горизонтальные ряды
Эта игра представляет собой сетку 2 на 1. Существует соглашение о присвоении игре положительное число когда Left побеждает и отрицательный один, когда побеждает Райт. В этом случае у Left нет ходов, в то время как Right может играть в домино, чтобы покрыть всю доску, не оставляя ничего, что явно является нулевой игрой. Таким образом, в сюрреалистический номер обозначение, эта игра {| 0} = −1. Это имеет смысл, так как эта сетка дает преимущество на 1 ход для правого.
В этой игре также {| 0} = −1, потому что один ящик не воспроизводится.
Эта сетка - первый случай выбора. Правильно мог сыграйте в два левых поля, оставив -1. В крайних правых квадратах также остается −1. Он также мог играть на двух средних боксах, оставляя два одиночных бокса. Эта опция оставляет 0 + 0 = 0. Таким образом, эту игру можно выразить как {| 0, −1}. Это -2. Если эта игра проводится вместе с другими играми, это два бесплатных хода вправо.
Вертикальные ряды
Вертикальные столбцы оцениваются таким же образом. Если есть строка из 2п или 2п+1 коробки, это считается -п. Столбец такого размера считается +п.
Более сложные сетки
Это более сложная игра. Если первым идет Left, то при любом из этих ходов остается сетка 1 × 2, что равно +1. Право, с другой стороны, может перейти в -1. Таким образом сюрреалистический номер обозначение {1 | −1}. Однако это не сюрреалистическое число, потому что 1> -1. Это игра, а не число. Обозначение для этого ± 1, и это горячая игра, потому что каждый игрок хочет переместиться сюда.
Это сетка 2 × 3, которая еще более сложна, но, как и в любой игре Domineering, ее можно разбить, посмотрев на то, каковы различные ходы для левого и правого. Левый может занять левый столбец (или, что то же самое, правый столбец) и перейти к ± 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]
Втиснуть
Втиснуть это беспристрастный версия Доминирования. Единственное различие в правилах состоит в том, что каждый игрок может размещать свои домино в любой ориентации. Это кажется лишь небольшим изменением в правилах, но это приводит к совершенно другой игре, которую можно проанализировать с помощью Теорема Спрага – Гранди.
Смотрите также
- Блокбастинг (игра) Комбинаторная игра, анализ которой был применен к доминированию.
Рекомендации
- ^ Брейкер, Д. М .; Uiterwijk, J. W.H.M .; ван ден Херик, Х. Дж. (6 января 2000 г.). «Решение проблемы 8 × 8 Доминирование». Теоретическая информатика. 230 (1–2): 195–206. Дои:10.1016 / S0304-3975 (99) 00082-1.
- ^ Натан Баллок Доминирование: решение больших комбинаторных пространств поиска M.Sc. дипломная работа, 2002 г.
- ^ Uiterwijk, J. W.H. 11x11 Власть решена: первый игрок побеждает. Компьютеры и игры, 2016. С. 129–136. Дои:10.1007/978-3-319-50935-8_12.
- ^ Сайт Натана Буллока: Обновленные теоретические значения игры для доминирующих досок
- Альберт, Майкл Х.; Новаковски, Ричард Дж .; Вулф, Дэвид (2007). Уроки в игре: введение в комбинаторную теорию игр. А. К. Петерс, ООО ISBN 978-1-56881-277-9.
- Берлекамп, Элвин Р.; Конвей, Джон Х.; Гай, Ричард К. (2003). Выигрышные способы для ваших математических игр. А. К. Петерс, ООО ISBN 978-0-12-091150-9.
- Гарднер, Мартин (1974). «Математические игры: зубрежка, кроссрам и квадрафаг: новые игры с неуловимыми выигрышными стратегиями». Scientific American. 230 (2): 106–108. Дои:10.1038 / scientificamerican0374-102.