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

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

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

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

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

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

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

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

• Элементы называются вершинами (или точками ) и обозначаются V ;${\displaystyle X}$
• Элементы называются ребрами (или гиперребрами ) и обозначаются E или H.${\displaystyle {\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).

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

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