Сильная позиционная игра - Википедия - Strong positional game

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

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

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

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

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

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

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

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

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

Парадокс экстра-набора

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

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

Примеры

Игра клики

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

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

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

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

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

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

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

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

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