Позиционная игра

Позиционная игра ^[1]^[2] — разновидность комбинаторной игры для двух игроков. Она описывается:

$X$ – конечный набор элементов. Часто называется доской , а ее элементы называются позициями . $X$
${\mathcal {F}}$ – семейство подмножеств . Эти подмножества обычно называют выигрышными наборами . $X$
Критерий победы в игре.

В ходе игры игроки поочередно занимают ранее не занятые позиции, пока один из игроков не победит. Если все позиции заняты и ни один из игроков не выигрывает, игра считается ничьей. $X$

Классический пример позиционной игры — крестики-нолики . В ней, содержит 9 клеток игрового поля, содержит 8 линий, которые определяют победу (3 горизонтальных, 3 вертикальных и 2 диагональных), а критерий победы: выигрывает первый игрок, который держит весь выигрышный набор. Другие примеры позиционных игр — Hex и игра с переключением Шеннона . $X$ ${\mathcal {F}}$

Для каждой позиционной игры существует ровно три варианта: либо у первого игрока есть выигрышная стратегия , либо у второго игрока есть выигрышная стратегия, либо у обоих игроков есть стратегии, позволяющие добиться ничьей. ^[2]^{: 7} Главный вопрос, представляющий интерес при изучении этих игр, заключается в том, какой из этих трех вариантов имеет место в любой конкретной игре.

Позиционная игра конечна, детерминирована и имеет совершенную информацию ; поэтому теоретически возможно создать полное игровое дерево и определить, какой из этих трех вариантов имеет место. Однако на практике игровое дерево может быть огромным. Поэтому позиционные игры обычно анализируются с помощью более сложных комбинаторных методов.

Альтернативная терминология

Часто вход в позиционную игру рассматривается как гиперграф . В этом случае:

Элементы называются вершинами (или точками ) и обозначаются V ; $X$
Элементы называются ребрами (или гиперребрами ) и обозначаются E или H. ${\mathcal {F}}$

Варианты

Существует множество вариантов позиционных игр, различающихся правилами и критериями выигрыша.

Различные критерии победы

Сильная позиционная игра (также называемая игрой Maker-Maker): Первый игрок, заявивший все элементы выигрышного набора, побеждает. Если игра заканчивается с заявкой на все элементы доски, но ни один игрок не заявил все элементы выигрышного набора, объявляется ничья. Примером может служить классическая игра «крестики-нолики» .
Игра Maker-Breaker: Два игрока называются Maker и Breaker. Maker побеждает, заявляя права на все элементы выигрышного набора. Если игра заканчивается, когда все элементы доски заявляются, а Maker еще не победил, то Breaker побеждает. Ничья невозможна. Примером может служить игра Shannon switching .
Игра Avoider-Enforcer: Игроки называются Avoider и Enforcer. Enforcer побеждает, если Avoider когда-либо заберет все элементы выигрышного набора. Если игра заканчивается, когда все элементы доски захвачены, а Avoider не забрал выигрышный набор, то Avoider побеждает. Как и в играх Maker-Breaker, ничья невозможна. Примером может служить Sim .
Игра в несоответствие: Игроки называются Balancer и Unbalancer. Balancer побеждает, если он гарантирует, что во всех выигрышных наборах каждый игрок имеет примерно половину вершин. В противном случае побеждает Unbalancer.

Разные правила игры

Игра «Официант-Клиент» (также называется игрой «Выбиратель-Выбиратель»): Игроки называются Официант и Клиент. В каждом ходе Официант выбирает две позиции и показывает их Клиенту, который может выбрать одну из них.
Предвзятая позиционная игра: Каждая позиционная игра имеет смещенный вариант, в котором первый игрок может брать p элементов за раз, а второй игрок может брать q элементов за раз (в несмещенном варианте p = q =1).

Конкретные игры

В следующей таблице перечислены некоторые конкретные позиционные игры, широко изученные в литературе.

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

Топологическая игра , обобщение позиционной игры на бесконечные множества
Игра Банаха-Мазура , игра, в которую играют на топологическом пространстве , выбирая среди определенных подмножеств, с условиями выигрыша, напоминающими условия игры «создай-сними»

Ссылки

^ Бек, Йожеф (2008). Комбинаторные игры: теория крестиков-ноликов . Кембридж: Cambridge University Press. ISBN 978-0-521-46100-9.
^ Аб Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинары в Обервольфахе. Том. 44. Базель: Биркхойзер Верлаг ГмбХ. ISBN 978-3-0348-0824-8.