Игра Avoider-Enforcer - Avoider-Enforcer game - Wikipedia

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

Доска для игры в Сим, игра Avoider-Enforcer

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

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

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

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

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

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

Аналогично Maker-Breaker игры, Игры Avoider-Enforcer тоже имеют дробные обобщения.

Предположим, Avoider нужно избегать приема хотя бы дробной части т элементов в любом выигрышном наборе (т. е. возьмите не более 1-т элементов в любом наборе), и Enforcer должен предотвратить это, то есть Enforcer должен забирать меньше т элементов в некотором выигрышном наборе. Определите константу: ${\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}$).

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

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

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

Рекомендации

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