Игра Avoider-Enforcer - Википедия - Avoider-Enforcer game

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}

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

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

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