WikiDer > Властный

Пример игры «Доминирование», сыгранной на доске 5x5, когда горизонтальный игрок («H» или «вправо») делает первый ход и проигрывает в 13-м раунде игры.

Властный (также называемый 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¼, таким образом: ${ displaystyle textstyle left {2 left | - { frac {1} {2}} right. right } = { frac {3} {4}} pm { frac {5} {4}}}$

Игра на высоком уровне

В Институт математических наук провел властную турнир, с призом в 500 долларов для победителя. В эту игру играли Доска 8 × 8. Победителем стал математик Дэн Калистрат, победивший Дэвид Вулф в финале. Турнир был подробно описан в книге Ричарда Новаковски. Игры без шанса (стр. 85).

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

Изображение игровое дерево для игры «Доминирование», проводимой на доске 4x4 с горизонтальным игроком («H») в начале и двумя уже сыгранными ходами. Дерево было обрезано альфа-бета обрезка, и минимакс включены значения, указывающие на то, что H имеет выигрышную стратегию от корня.

Проблема Domineering состоит в том, чтобы вычислить выигрышную стратегию для больших досок, особенно квадратных. В 2000 году Деннис Брейкер, Йос Уйервейк и Яап ван ден Херик вычислил и опубликовал решение для платы 8x8.^[1] Доска 9x9 последовала вскоре после некоторых улучшений их программы. Затем, в 2002 году, Натан Буллок решил доску 10х10 в рамках своей диссертации на тему «Власть».^[2] Доска 11x11 была решена Йосом Уитервейком в 2016 году.^[3]

Доминирование - это победа первого игрока на квадратных досках 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 и 11x11, а также победа второго игрока на досках 1x1 и 5x5. Другие известные значения прямоугольных досок можно найти на сайте Натана Буллока.^[4]

Втиснуть

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

Смотрите также

• Блокбастинг (игра) Комбинаторная игра, анализ которой был применен к доминированию.

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

• Альберт, Майкл Х.; Новаковски, Ричард Дж .; Вулф, Дэвид (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.

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

• Стоп-ворота в НастольнаяИграГик
• Игровая версия в Pencil and Paper Games