Сильная позиционная игра

Сильная позиционная игра (также называемая игрой Создатель-Создатель ) — это разновидность позиционной игры . ^[1]^: 9–12 Как и большинство позиционных игр, она описывается набором позиций ( $X$ ) и его семейство выигрышных наборов ( ${\mathcal {F}}$ - подмножеств семейство $X$ ). В нее играют два игрока, называемые Первым и Вторым, которые поочередно занимают ранее незанятые позиции.

В сильной позиционной игре побеждает тот игрок, который первым удерживает все элементы выигрышного сета. Если все позиции заняты и ни один игрок не выигрывает, то это ничья. Классические крестики-нолики – пример сильной позиционной игры.

Преимущество первого игрока

В сильной позиционной игре у Второго не может быть выигрышной стратегии. Это можно доказать с помощью аргумента о краже стратегии : если бы Второй имел выигрышную стратегию, то Первый мог бы украсть ее и тоже выиграть, но это невозможно, поскольку есть только один победитель. ^[1]^: 9 Поэтому для каждой сильнопозиционной игры есть только два варианта: либо у Первого выигрышная стратегия, либо у Второго — ничья.

Интересным следствием является то, что если в определенной игре нет ничьих позиций, то у First всегда есть выигрышная стратегия.

Сравнение с игрой Maker-Breaker

У каждой сильной позиционной игры есть вариант игры Maker-Breaker . В этом варианте только первый игрок («Создатель») может выиграть, имея выигрышный сет. Второй игрок («Брейкер») может выиграть, только если не позволит Мейкеру удержать выигрышный сет.

Для фиксированного $X$ и ${\mathcal {F}}$ , сильно-позиционный вариант строго сложнее для первого игрока, так как в нем ему необходимо как «нападать» (стараться получить выигрышный сет), так и «защищаться» (не давать второму игроку получить выигрышный сет), а в В варианте «Создатель-разрушитель» первый игрок может сосредоточиться только на «атаке». Следовательно, каждая выигрышная стратегия Первого в игре с сильной позицией также является выигрышной стратегией Создателя в соответствующей игре Создатель-Разрушитель . Обратное неверно. Например, в варианте «Крестики-нолики» «Мейкер-брейк» «Мейкер» имеет выигрышную стратегию, но в его сильно-позиционном (классическом) варианте «Секундный» имеет стратегию розыгрыша. ^[2]

Точно так же сильно-позиционный вариант строго проще для второго игрока: каждая выигрышная стратегия Брейкера в игре создатель-брейкер также является ничьей-стратегией Секонда в соответствующей сильнопозиционной игре , но обратное неверно.

Парадокс экстра-множества

Предположим, у First есть выигрышная стратегия. Теперь мы добавляем новый набор в ${\mathcal {F}}$ . Вопреки интуиции, вполне возможно, что этот новый набор теперь разрушит выигрышную стратегию и сделает игру ничьей. Интуитивно, причина в том, что Первому, возможно, придется потратить несколько ходов, чтобы не дать Второму завладеть этим дополнительным набором. ^[3]

Парадокс дополнительных наборов не появляется в играх Maker-Breaker.

Примеры

Игра в клику

Кликовая игра является примером сильной позиционной игры. Он параметризуется двумя целыми числами, n и N. В нем:

$X$ содержит все ребра полного графа на {1,...,N};
${\mathcal {F}}$ содержит все клики размера n.

Согласно теореме Рэмси , существует некоторое число R(n,n) такое, что для каждого N > R(n,n) в каждой двухраскраске полного графа на {1,...,N} один цветов должна содержать клику размера n.

Следовательно, согласно приведенному выше следствию, когда N > R(n,n), у First всегда есть выигрышная стратегия. ^[1]^: 10

Многомерные крестики-нолики

Рассмотрим игру в крестики-нолики, в которую играют в d -мерном кубе длины n . По теореме Хейлса-Джеветта , когда d достаточно велико (как функция от n ), каждая 2-раскраска ячеек куба содержит монохроматическую геометрическую линию.

Следовательно, согласно вышеприведенному следствию, у First всегда есть выигрышная стратегия.

Открытые вопросы

Помимо этих экзистенциальных результатов, конструктивных результатов, связанных с сильнопозиционными играми, немного. Например, хотя известно, что первый игрок имеет выигрышную стратегию в игре достаточно большой клики, в настоящее время не известна конкретная выигрышная стратегия. ^[1]^: 11–12

Ссылки

^ Jump up to: ^а ^б ^с ^д Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинар в Обервольфахе. Том 44. Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8 .
^ Кручек, Клей; Эрик Сундберг (2010). «Потенциальные стратегии игры в крестики-нолики на целочисленной решетке с множеством направлений». Электронный журнал комбинаторики . 17 : Р5.
^ Бек, Йожеф (2008). Комбинаторные игры: теория крестиков-ноликов . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-46100-9 .

[:0-1] Jump up to: ^а ^б ^с ^д Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинар в Обервольфахе. Том 44. Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8 .

[kruczek2010-2] Кручек, Клей; Эрик Сундберг (2010). «Потенциальные стратегии игры в крестики-нолики на целочисленной решетке с множеством направлений». Электронный журнал комбинаторики . 17 : Р5.

[beck08-3] Бек, Йожеф (2008). Комбинаторные игры: теория крестиков-ноликов . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-46100-9 .

[1]

[2]

[3]