Сильная позиционная игра (также называется Maker-Maker игра ) является своим родом позиционной игры . [1] : 9–12 Как и большинство позиционных игр, она описывается набором позиций () и его семейство выигрышных наборов (- это семейство подмножеств из). В нее играют два игрока, называемые Первый и Второй, которые поочередно занимают ранее неиспользованные позиции.
В сильной позиционной игре победителем становится тот игрок, который первым владеет всеми элементами выигрышной партии. Если все позиции заняты и ни один игрок не выигрывает, то это ничья. Классические крестики-нолики - пример сильной позиционной игры.
Преимущество первого игрока
В сильной позиционной игре у Second не может быть выигрышной стратегии. Это может быть доказано аргументом в пользу кражи стратегии : если у Second была выигрышная стратегия, то First мог бы украсть ее и тоже выиграть, но это невозможно, так как есть только один победитель. [1] : 9 Следовательно, для каждой сильнопозиционной игры есть только два варианта: либо у Первой есть выигрышная стратегия, либо у Второй есть стратегия ничьей.
Интересное следствие состоит в том, что если в определенной игре нет ничьих позиций, то у First всегда есть выигрышная стратегия.
Сравнение с игрой Maker-Breaker
У каждой сильной позиционной игры есть вариант игры Maker-Breaker . В этом варианте только первый игрок («Создатель») может выиграть, имея выигрышную комбинацию. Второй игрок («Брейкер») может выиграть, только помешав Мейкеру удерживать выигрышный набор.
Для фиксированных а также , вариант с сильной позицией для первого игрока строго сложнее, так как в нем ему нужно как «атаковать» (попытаться получить выигрышный сет), так и «защищаться» (не дать второму игроку получить его), в то время как в вариант «производитель-нарушитель», первый игрок может сосредоточиться только на «атаке». Следовательно, каждая выигрышная стратегия First в игре с сильной позицией также является выигрышной стратегией Maker в соответствующей игре Maker-breaker . Обратное неверно. Например, в варианте Tic-Tac-Toe Maker-breaker Maker имеет выигрышную стратегию, но в его сильнопозиционном (классическом) варианте Second имеет стратегию рисования. [2]
Точно так же вариант с сильной позицией строго проще для второго игрока: каждая выигрышная стратегия Брейкера в игре «производитель-нарушитель» также является стратегией вытягивания Второго в соответствующей игре с сильной позицией , но обратное неверно.
Парадокс экстра-набора
Предположим, у Первого есть выигрышная стратегия. Теперь мы добавляем новый набор в. Вопреки интуиции, возможно, что этот новый набор теперь разрушит выигрышную стратегию и сделает игру ничьей. Интуитивно причина в том, что Первому, возможно, придется потратить несколько ходов, чтобы Второй не стал владельцем этого дополнительного набора. [3]
Парадокс дополнительного набора не проявляется в играх Maker-Breaker.
Примеры
Игра клики
Игра кликами - это пример сильной позиционной игры. Он параметризуется двумя целыми числами n и N. В нем:
- содержит все ребра полного графа на {1, ..., N};
- содержит все клики размера 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
Рекомендации
- ^ a b c d Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Обервольфахские семинары. 44 . Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
- ^ Кручек, Клай; Эрик Сандберг (2010). «Возможные стратегии для крестиков-ноликов на целочисленной решетке с многочисленными направлениями». Электронный журнал комбинаторики . 17 : R5.
- ^ Бек, Йожеф (2008). Комбинаторные игры: теория крестиков-ноликов . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-46100-9.