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

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

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

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

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

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

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

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

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

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

Варианты

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

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

Сильная позиционная игра (также называемая игрой Создатель-Создатель): Побеждает тот игрок, который первым заберет все элементы выигрышного набора. Если игра заканчивается, когда все элементы доски заявлены, но ни один игрок не забрал все элементы выигрышного набора, то это ничья. Пример — классические крестики-нолики .
Игра Создатель-Разрушитель: Двух игроков зовут Создатель и Разрушитель. Создатель выигрывает, забирая все элементы выигрышного набора. Если игра заканчивается, когда все элементы доски заявлены, а Создатель еще не выиграл, то побеждает Брейкер. Ничья невозможна. Примером может служить игра с переключением Шеннона .
Игра Избегатель-Инфорсер: Игроков зовут Избегатель и Инфорсер. Enforcer побеждает, если Избежатель когда-либо заберет все элементы выигрышного набора. Если игра заканчивается, когда все элементы доски заявлены, а Избегатель не забрал выигрышный сет, то Избегатель побеждает. Как и в играх «мейкер-брейк», ничья невозможна. Пример — Сим .
Игра на несоответствие: Игроков зовут Балансир и Дисбалансер. Балансировщик выиграет, если он обеспечит, чтобы во всех выигрышных наборах у каждого игрока была примерно половина вершин. В противном случае Unbalancer побеждает.

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

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

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

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


Имя	Позиции	Выигрышные сеты
Многомерные крестики-нолики	Все квадраты в многомерной коробке	Все прямые
Шеннон переключает игру	Все ребра графа	Все пути от s до t
Да	Все ребра между 6 вершинами.	Все треугольники [проигрышные сеты].
Игра-клика (она же игра Рэмси )	Все ребра полного графа размера n	Все клики размера k
Игра с подключением	Все ребра полного графа	Все пролетные деревья
игра гамильтоновости	Все ребра полного графа	Все гамильтоновы пути
Непланарная игра	Все ребра полного графа	Все неплоские подграфы
Игра «Арифметическая прогрессия»	Числа {1,...,n}	Все арифметические прогрессии размера k

См. также

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

Ссылки

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

[beck08-1] Бек, Йожеф (2008). Комбинаторные игры: теория крестиков-ноликов . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-46100-9 .

[pg14-2] Перейти обратно: ^а ^б Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинар в Обервольфахе. Том 44. Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8 .

[1]

[2]