Предвзятая позиционная игра

Предвзятая позиционная игра [ 1] [2] : 27–42  является вариантом позиционной игры . Как и большинство позиционных игр, она описывается набором позиций/точек/элементов ( ) и семейством подмножеств ( ), которые обычно называются выигрышными наборами . В нее играют два игрока, которые по очереди выбирают элементы, пока все элементы не будут взяты. В то время как в стандартной игре каждый игрок выбирает один элемент за ход, в предвзятой игре каждый игрок берет разное количество элементов. Х {\displaystyle X} Ф {\displaystyle {\mathcal {F}}}

Более формально, для любых двух положительных целых чисел p и q (p:q)-позиционная игра — это игра, в которой первый игрок выбирает p элементов за ход, а второй игрок выбирает q элементов за ход.

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

Пример

В качестве примера рассмотрим игру треугольник . В этой игре элементами являются все ребра полного графа на n вершинах, а выигрышные множества — все треугольники (=клики на 3 вершинах). Предположим, что мы играем в нее как в игру Maker-Breaker , т. е. цель Maker (первого игрока) — взять треугольник, а цель Breaker (второго игрока) — не дать Maker взять треугольник. Используя простой анализ случаев, можно доказать, что у Maker есть выигрышная стратегия, когда n не меньше 6. Поэтому интересно спросить, может ли это преимущество быть смещено, если Breaker выбирает больше 1 элемента за ход.

Действительно, можно доказать, что: [1]

  • Для каждого Мейкер выигрывает в игре треугольника (1: q ) на n вершинах. д ≤ 0,5 н {\displaystyle q\leq 0.5{\sqrt {n}}}
  • Для каждого Брейкер выигрывает в игре треугольника (1: q ) на n вершинах. д ≥ 2 н {\displaystyle q\geq 2{\sqrt {n}}}

Условие выигрыша для Breaker

В непредвзятой игре Maker-Breaker теорема Эрдеша-Селфриджа дает выигрышное условие для Breaker . Это условие можно обобщить для предвзятых игр следующим образом: [3] [2] : 30–32 

  • Если , то у Брейкера есть выигрышная стратегия в игре (p:q), когда он ходит первым. ∑ Э ∈ Ф ( 1 + д ) − | Э | / п < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<1}
  • Если , то у Брейкера есть выигрышная стратегия в игре (p:q), даже если он играет вторым. ∑ E ∈ F ( 1 + q ) − | E | / p < 1 1 + q {\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<{1 \over 1+q}}

Стратегия использует потенциальную функцию, которая обобщает функцию Эрдоша-Селфриджа. Потенциал (неразбитого) выигрышного набора E с | E | невзятыми элементами определяется как . Если Maker выигрывает игру, то существует набор E с | E |=0, так что его потенциал равен 1; следовательно, чтобы доказать, что Breaker выигрывает, достаточно доказать, что окончательная потенциальная сумма меньше 1. Действительно, по предположению, потенциальная сумма на первом ходу Breaker меньше 1; и если Breaker всегда выбирает элемент, который максимизирует потенциальное падение, можно показать, что потенциальная сумма всегда слабо уменьшается. ( 1 + q ) − | E | / p {\displaystyle (1+q)^{-|E|/p}}

Когда каждый выигрышный набор имеет элементы, для некоторого фиксированного k условие выигрыша Breaker упрощается до: (когда играет первым) или (когда играет вторым). Это условие является жестким: существуют k -однородные семейства наборов с наборами, где Maker выигрывает. [4] k {\displaystyle k} | F | < ( q + 1 ) k / p {\displaystyle |{\mathcal {F}}|<(q+1)^{k/p}} | F | < ( q + 1 ) k / p − 1 {\displaystyle |{\mathcal {F}}|<(q+1)^{k/p-1}} | F | = ( q + 1 ) k / p − 1 {\displaystyle |{\mathcal {F}}|=(q+1)^{k/p-1}}

Выигрышное условие для Maker

В непредвзятой игре Maker-Breaker теорема Бека дает выигрышное условие для Maker . Она использует парную степень гиперграфа - обозначенную как . Это условие можно обобщить на предвзятые игры следующим образом: [3] d 2 {\displaystyle d_{2}}

Если , то у Мейкера есть выигрышная стратегия в игре (p:q), когда он ходит первым. ∑ E ∈ F p + q p − | E | > p 2 q 2 ( p + q ) 3 ⋅ d 2 ⋅ | X | {\displaystyle \sum _{E\in {\mathcal {F}}}{p+q \over p}^{-|E|}>{p^{2}q^{2} \over (p+q)^{3}}\cdot d_{2}\cdot |X|}

Условие выигрыша для Avoider

В предвзятой игре «Избегающий-Исполняющий» следующие условия гарантируют, что у Избегающего есть выигрышная стратегия: [2] : 47–49 

  • Если , то Avoider выигрывает игру (p:q), играя первым, как при строгом, так и при монотонном наборе правил. Это почти точно: существует бесконечное семейство игр (p:q), в которых это выражение немного больше 1, и Enforcer выигрывает. ∑ E ∈ F ( 1 + 1 / p ) p − | E | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}(1+1/p)^{p-|E|}<1} [5] В частности, в игре без смещения условие становится . Если граф является k -однородным, условие становится . Примечательно, что это условие вообще не зависит от q . ∑ E ∈ F 2 1 − | E | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}2^{1-|E|}<1} | F | < ( 1 + 1 / p ) k − 1 {\displaystyle |{\mathcal {F}}|<(1+1/p)^{k-1}}
  • Если каждый выигрышный набор содержит не более k элементов, и , то Avoider выигрывает игру (p:q), когда играет первым. ∑ E ∈ F ( 1 + q p k ) p − | E | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}\left(1+{q \over pk}\right)^{p-|E|}<1} [6]

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

Ссылки

  1. ^ ab Chvátal, V.; Erdös, P. (1978). «Предвзятые позиционные игры». Annals of Discrete Mathematics . 2 (C): 221–229. doi :10.1016/S0167-5060(08)70335-2. ISSN  0167-5060.
  2. ^ abc Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинары в Обервольфахе. Том. 44. Базель: Биркхойзер Верлаг ГмбХ. ISBN 978-3-0348-0824-8.
  3. ^ Аб Бек, Дж. (1982). «Замечания о позиционных играх. I». Acta Mathematica Academiae Scientiarum Hungaricae . 40 (1–2): 65–71. дои : 10.1007/bf01897304 . ISSN  0001-5954.
  4. ^ Сандберг, Эрик Ларс (2013-05-02). "Экстремальные гиперграфы для предвзятой теоремы Эрдёша-Селфриджа". Электронный журнал комбинаторики . 20 (1). doi : 10.37236/2394 . ISSN  1077-8926.
  5. ^ Хефец, Дэн ; Кривелевич, Майкл; Сабо, Тибор (2007-07-01). «Игры избегающего--принуждающего». Журнал комбинаторной теории, серия A. 114 (5): 840–853. doi : 10.1016/j.jcta.2006.10.001 . ISSN  0097-3165.
  6. ^ Беднарска-Бздега, Малгожата (2014-01-12). «Игры избегания-форсера на гиперграфах с малым рангом». Электронный журнал комбинаторики . 21 (1): 1–2. doi : 10.37236/3095 . ISSN  1077-8926.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Biased_positional_game&oldid=1131390786"