Игра Avoider-Enforcer

Игра, в которой игроки избегают проигрышных сетов

Игра Avoider-Enforcer ^{[1] : 43–60} (также называемая игрой Avoider-Forcer ^[2] или игрой Antimaker-Antibreaker ^{[3] : sec.5} ) является разновидностью позиционной игры . Как и большинство позиционных игр, она описывается набором позиций/точек/элементов ( ) и семейством подмножеств ( ), которые здесь называются lose-sets . В нее играют два игрока, называемые Avoider и Enforcer, которые по очереди выбирают элементы, пока все элементы не будут взяты. Avoider выигрывает, если ему удается избежать взятия проигрышного набора; Enforcer выигрывает, если ему удается заставить Avoider взять проигрышный набор. ${\displaystyle X}$ ${\displaystyle {\mathcal {F}}}$

Доска для игры « Сим» , игра жанра «Избегатель-Исполнитель»

Классический пример такой игры — Sim . Там позициями являются все ребра полного графа на 6 вершинах. Игроки по очереди закрашивают линию в свой цвет и проигрывают, когда формируют полный треугольник своего цвета: проигрышные наборы — все треугольники.

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

Условие выигрыша игры Avoider-Enforcer полностью противоположно условию выигрыша игры Maker-Breaker на том же . Таким образом, игра Avoider-Enforcer является вариантом игры Misère игры Maker-Breaker. Однако между этими типами игр есть контринтуитивные различия. ${\displaystyle {\mathcal {F}}}$

Например, рассмотрим предвзятую версию игр, в которой первый игрок берет p элементов каждый ход, а второй игрок берет q элементов каждый ход (в стандартной версии p = 1 и q = 1). Игры Maker-Breaker являются предвзятыми монотонными : взятие большего количества элементов всегда является преимуществом. Формально, если Maker выигрывает игру Maker-Breaker ( p : q ), то он также выигрывает игру ( p +1: q ) и игру (p:q-1). Игры Avoider-Enforcer не являются предвзятыми монотонными: взятие большего количества элементов не всегда является преимуществом . Например, рассмотрим очень простую игру Avoider-Enforcer, где проигрышными наборами являются {w,x} и {y,z}. Затем Avoider выигрывает игру (1:1), Enforcer выигрывает игру (1:2), а Avoider выигрывает игру (2:2).

Существует монотонный вариант правил игры ( p : q ) Avoider-Enforcer, в котором Avoider должен выбирать не менее p элементов каждый ход, а Enforcer должен выбирать не менее q элементов каждый ход; этот вариант является смещенно-монотонным. ^{[1] : 45–46}

Частичное избегание

Подобно играм Maker-Breaker , игры Avoider-Enforcer также имеют дробные обобщения.

Предположим, Avoider должен избегать взятия по крайней мере части t элементов в любом выигрышном наборе (т. е. брать не более 1- t элементов в любом наборе), а Enforcer должен предотвратить это, т. е. Enforcer должен взять меньше, чем часть t элементов в некотором выигрышном наборе. Определим константу: (в стандартном варианте, ). ${\displaystyle c_{t}:=(2t)^{t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}}$ ${\displaystyle t=1,c_{t}\to 2}$

• Если , и общее количество элементов четное , то у Avoider есть выигрышная стратегия, ${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1}$ когда он играет первым . ^{[3] : thm A5}

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

Предвзятая позиционная игра#Условие победы для Avoider

Ссылки

1. Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинары в Обервольфахе. Том. 44. Базель: Биркхойзер Верлаг ГмбХ. ISBN 978-3-0348-0824-8.
2. Беднарска-Бздега, Малгожата (2014-01-12). «Игры избегания-форсера на гиперграфах с малым рангом». Электронный журнал комбинаторики . 21 (1): 1–2. ISSN  1077-8926.
3. Lu, Xiaoyun (1991-11-29). "Игра на соответствие". Дискретная математика . 94 (3): 199–207. doi : 10.1016/0012-365X(91)90025-W . ISSN  0012-365X.