Сильная позиционная игра (также называемая игрой Maker-Maker ) — это разновидность позиционной игры . [1] : 9–12 Как и большинство позиционных игр, она описывается своим набором позиций ( ) и своим семейством выигрышных наборов ( - семейство подмножеств ) . В нее играют два игрока, называемые Первым и Вторым, которые поочередно занимают ранее не занятые позиции.
В сильной позиционной игре победителем становится первый игрок, который удерживает все элементы выигрышного набора. Если все позиции заняты и ни один игрок не выигрывает, то это ничья. Классический крестики-нолики является примером сильной позиционной игры.
В сильной позиционной игре у Второго не может быть выигрышной стратегии. Это можно доказать с помощью аргумента о краже стратегии : если бы у Второго была выигрышная стратегия, то Первый мог бы украсть ее и тоже победить, но это невозможно, поскольку победитель только один. [1] : 9 Следовательно, для каждой сильной позиционной игры есть только два варианта: либо у Первого есть выигрышная стратегия, либо у Второго есть ничья.
Интересным следствием является то, что если в определенной игре нет ничейных позиций, то у Первого всегда есть выигрышная стратегия.
Каждая сильная позиционная игра имеет вариант, который является игрой Maker-Breaker . В этом варианте только первый игрок («Maker») может выиграть, удерживая выигрышный сет. Второй игрок («Breaker») может выиграть, только не дав Maker удержать выигрышный сет.
Для фиксированных и вариант с сильной позицией строго сложнее для первого игрока, так как в нем ему нужно как «атаковать» (попытаться получить выигрышный сет), так и «защищаться» (не дать второму игроку получить его), в то время как в варианте с мейкером-брейкером первый игрок может сосредоточиться только на «атаке». Следовательно, каждая выигрышная стратегия Первого в игре с сильной позицией также является выигрышной стратегией Мейкера в соответствующей игре с мейкером-брейкером . Обратное неверно. Например, в варианте с мейкером-брейкером в крестиках-ноликах у Мейкера есть выигрышная стратегия, но в варианте с сильной позицией (классическом) у Второго есть стратегия ничьей. [2]
Аналогично, вариант с сильной позицией строго проще для второго игрока: каждая выигрышная стратегия Брейкера в игре с создателем-брейкером также является ничьей-стратегией Второго в соответствующей игре с сильной позицией , но обратное неверно.
Предположим, что у First есть выигрышная стратегия. Теперь мы добавляем новый набор к . Вопреки интуиции, возможно, что этот новый набор теперь разрушит выигрышную стратегию и сделает игру ничьей. Интуитивно, причина в том, что First, возможно, придется потратить несколько ходов, чтобы помешать Second завладеть этим дополнительным набором. [3]
Парадокс дополнительного набора не встречается в играх Maker-Breaker.
Игра в клики является примером сильной позиционной игры. Она параметризуется двумя целыми числами, n и N. В ней:
Согласно теореме Рамсея , существует некоторое число R(n,n), такое, что для любого N > R(n,n) в любой двухцветной раскраске полного графа на {1,...,N} один из цветов должен содержать клику размера n.
Следовательно, согласно приведенному выше следствию, когда N > R(n,n), у First всегда есть выигрышная стратегия. [1] : 10
Рассмотрим игру крестики-нолики, сыгранную в d -мерном кубе длины n . По теореме Хейлза–Джеветта , когда d достаточно велико (как функция n ), каждая 2-раскраска ячеек куба содержит одноцветную геометрическую линию.
Следовательно, согласно приведенному выше следствию, у Первого всегда есть выигрышная стратегия.
Помимо этих экзистенциальных результатов, есть несколько конструктивных результатов, связанных с сильными позиционными играми. Например, хотя известно, что у первого игрока есть выигрышная стратегия в достаточно большой кликовой игре, в настоящее время не известно никакой конкретной выигрышной стратегии. [1] : 11–12
