Игра Создатель-Разрушитель

Игра Maker-Breaker — это разновидность позиционной игры . ^[1]^: 13–24 Как и большинство позиционных игр, она описывается набором позиций/точек/элементов ( $X$ ) и его семейство выигрышных наборов ( ${\mathcal {F}}$ - подмножеств семейство $X$ ). В нее играют два игрока, которых зовут Создатель и Разрушитель, которые поочередно берут ранее не взятые элементы.

В игре Мейкер-Брейкер Мейкер выигрывает, если ему удается удержать все элементы выигрышного набора, а Брейкер выигрывает, если ему удается предотвратить это, т.е. удержать хотя бы один элемент в каждом выигрышном наборе. Ничья невозможна. В каждой игре Maker-Breaker у Maker или Breaker есть выигрышная стратегия. Главный вопрос исследования этих игр заключается в том, какой из этих двух вариантов верен.

Примеры

Классическая игра Maker-Breaker — Hex . Здесь выигрышными наборами являются все пути с левой стороны доски на правую. Создатель выигрывает, владея подключенным путем; Breaker выигрывает, владея соединенным путем сверху вниз, поскольку он блокирует все связанные пути слева направо.

В «Крестики-нолики» можно играть как игру «Создатель-Разрушитель»: в этом варианте цель Создателя — выбрать 3 квадрата подряд, а цель Разрушителя — просто помешать Создателю сделать это. В этом варианте у Брейкера есть выигрышная стратегия. В этом отличие от классического варианта (сильной позиционной игры ), где у второго игрока есть стратегия розыгрыша (см. Сильная позиционная игра # Сравнение с игрой Maker-Breaker ).

Неупорядоченная CNF игра ^[2] на положительном CNF (все положительные литералы) можно рассматривать как игру Maker-Breaker, в которой Maker хочет фальсифицировать CNF, а Breaker хочет удовлетворить его.

Было проведено некоторое исследование игры Maker-Breaker, когда игровое поле представляет собой крайний набор. $E$ какого-то графа $G$ (обычно рассматривается как полный граф ), а семейство выигрышных наборов ${\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ has property }}{\mathcal {P}}\}$ , где ${\mathcal {P}}$ — это некоторое свойство графа (обычно считается монотонно возрастающим [уточнить?]), такое как связность. ^[3] Например, игра с переключением Шеннона — это игра «Создатель-Разрушитель», в которой выигрышными множествами являются пути между двумя выделенными вершинами.

Двойственность Разрушителя-Создателя

В игре Maker-Breaker обычно первым играет Maker. Но также возможно позволить Брейкеру играть первым. Играть первым всегда выгодно: любая выигрышная стратегия для Создателя, играющего вторым. $(X,{\mathcal {F}})$ дает выигрышную стратегию для Создателя, играющего первым на $(X,{\mathcal {F}}).$ То же самое относится и к Брейкеру. ^[1]^: 15

Более того, для каждой игры $(X,{\mathcal {F}})$ мы можем определить его трансверсальную игру $(X,{\mathcal {F^{*}}})$ , в котором выигрышными сетами являются минимальные наборы, соприкасающиеся с каждым выигрышным сетом в исходной игре. Например, если в исходной игре выигрышными сетами являются {{1,2,3},{4,5,6}}, то в двойной игре это {{1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Затем выигрышные стратегии для Брейкера, играющего первым на $(X,{\mathcal {F}})$ — это именно выигрышные стратегии для Мейкера, играющего первым на $(X,{\mathcal {F^{*}}})$ . ^[4]^: 2

Кроме того, существует альтернативная конвенция Мизера для игры Maker-Breaker, называемая игрой Doesr-Enforcer .

Вычислительная сложность

Игра Maker-Breaker является PSPACE-полной, даже если размер каждого набора ограничен 6. ^[5] Первый результат был получен в 1978 году, когда размер каждого набора был ограничен 11. ^[6] где игра упоминалась как $G$ (ПОС ЦНФ 11).

Стратегии

Для решения игр Maker-Breaker обычно используются несколько видов стратегий.

Стратегии спаривания

В некоторых играх можно разбить элементы X (или их подмножество) на набор попарно непересекающихся пар. При определенных условиях игрок может выиграть, используя следующую жадную стратегию: «каждый раз, когда ваш оппонент выбирает элемент пары i , выберите другой элемент пары i ».

«Определенные условия» различны для Создателя и Разрушителя; см. стратегию сопряжения .

Стратегии сильных позиционных игр

Каждая выигрышная стратегия для Первого в сильной позиционной игре также является выигрышной стратегией для Создателя в варианте Создатель-Разрушитель (см. Сильная позиционная игра#Сравнение с игрой Создатель-Разрушитель ). В частности, если в сильно-позиционном варианте ничьей быть не может, то в варианте мейкер-брейкер у мейкера есть выигрышная стратегия. Обратное не обязательно верно: выигрышная стратегия для Создателя в варианте «Создатель-разрыв» не обязательно является выигрышной стратегией для Первого в сильном варианте, поскольку в сильном варианте Второй может выиграть, забрав выигрышный сет раньше Первого. .

Напротив, каждая выигрышная стратегия для Брейкера в игре создатель-брейкер также является стратегией ничьей для Второго в сильнопозиционном варианте.

Стратегии, основанные на потенциале

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

Потенциал выигрышного сета находится между 0 и 1;
Когда Брейкер берет элемент, потенциал всех наборов, содержащих его, падает до 0 и остается равным 0;
Когда Создатель берет элемент, потенциал всех (неразбитых) множеств, содержащих его, увеличивается;
Потенциал набора, принадлежащего Создателю, равен 1.

Тогда Maker выигрывает, если потенциальная сумма больше 0, а Breaker выигрывает, если потенциальная сумма меньше 1. Следовательно:

Если начальная сумма больше 0 и Создатель может играть так, что потенциальная сумма слабо увеличивается, то это выигрышная стратегия для Создателя;
Если начальная сумма меньше 1 и Брейкер может играть так, что потенциальная сумма слабо уменьшается, то это выигрышная стратегия для Брейкера.

Условие победы для Брейкера

Пол Эрдеш и Джон Селфридж представили общее условие, гарантирующее Брейкеру выигрышную стратегию. ^[7] Они использовали стратегию, основанную на потенциале. Они определили потенциал любого (неразбитого) выигрышного сета. $E$ с $|E|$ незанятые вершины как $2^{-|E|}$ . Таким образом, потенциал набора, занятого Создателем, действительно $2^{-0}=1$ . Всякий раз, когда Создатель берет элемент, потенциал каждого набора, содержащего его, увеличивается до $2^{-(|E|-1)}$ , т. е. увеличивается на $2^{-|E|}$ ; всякий раз, когда Брейкер берет элемент, потенциал каждого содержащего его множества падает до 0, т. е. уменьшается на $2^{-|E|}$ . Каждому элементу мы присваиваем значение , равное общему увеличению потенциала в случае, если его примет Создатель, т. е. $w(v):=\sum _{v\in E}2^{-|E|}$ . Выигрышная стратегия Breaker — выбрать элемент с наибольшим значением . Это гарантирует, что с первого хода Брейкера потенциал всегда слабо снижается. Следовательно, если потенциал на первом ходу Брейкера меньше 1, Брейкер побеждает. В первый ход Создателя он может максимум удвоить потенциал (взяв элемент, содержащийся во всех выигрышных наборах). Поэтому достаточно, чтобы в начале игры потенциал был меньше 1/2. Подводя итог, теорема Эрдеша-Селфриджа гласит, что:

Если $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1/2$ , затем ${\mathcal {F}}$ это победа Брейкера .

Теорема дает очень легко проверяемое условие, а когда это условие удовлетворяется, она также дает эффективный алгоритм вычисления оптимальной стратегии Брейкера.

Потенциальная функция имеет вероятностную интерпретацию. Потенциал выигрышного набора — это вероятность того, что, если с этого момента игра будет вестись случайным образом, этот набор будет принадлежать Создателю. Таким образом, потенциальная сумма — это ожидаемое количество выигрышных наборов, принадлежащих Создателю, если игра ведется случайным образом. Всякий раз, когда потенциальная сумма меньше 1, должен быть способ вести игру так, чтобы количество наборов, принадлежащих Создателю, было равно 0. Гарантируя, что потенциальная сумма остается ниже 1, Брейкер по существу дерандомизирует это вероятностное утверждение. пока в конце игры это не станет несомненным.

Обратите внимание: если Брейкер играет первым, условие меняется на $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1$ .

В частности, если все выигрышные множества имеют размер k (т. е. гиперграф игры k -однороден), то из теоремы Эрдеша-Селфриджа следует, что Брейкер выигрывает всякий раз, когда $|{\mathcal {F}}|<2^{k-1}$ , т. е. число выигрышных сетов меньше $2^{k-1}$ . ^[7]

Число $2^{k-1}$ тесно: есть $k$ -однородные гиперграфы, в которых количество выигрышных наборов точно равно $2^{k-1}$ , и где у Maker есть выигрышная стратегия. Например, рассмотрим идеальное двоичное дерево высоты $k-1$ . Он имеет $2^{k-1}$ листья. Определим V как множество узлов дерева, а H как семейство всех $2^{k-1}$ пути от корня к листу. Maker начинает с выбора корня. Затем, если Брейкер выбирает элемент в левом поддереве, Создатель выбирает корень правого поддерева, и наоборот. Продолжая этот путь, Maker всегда сможет выбрать полный путь, то есть выигрышный сет.

Непересекающиеся и почти непересекающиеся гиперграфы.

Если все выигрышные наборы попарно непересекающиеся и их размер не менее 2, то Брейкер может выиграть, используя стратегию спаривания.

Предположим теперь, что выигрышные множества почти не пересекаются, т. е. любые два выигрышных множества имеют не более одного общего элемента. Если все выигрышные сеты имеют размер $k$ , а количество выигрышных сетов меньше $4^{k-c{\sqrt {k}}}$ (при некоторой фиксированной константе c), то у Брейкера есть выигрышная стратегия. ^[8] Таким образом, эта ситуация проще для Брейкера, чем общий случай, но сложнее, чем случай непересекающихся выигрышных наборов.

Условие победы для Maker

Определим степень набора элементов как количество различных выигрышных наборов, содержащих этот набор. Определим парную степень множества-семейства, обозначим $d_{2}$ , как максимальная степень пары элементов (максимум по всем парам). Если все выигрышные сеты имеют размер $k$ , а количество выигрышных сетов больше $2^{k-3}\cdot d_{2}\cdot |X|$ , то у Maker есть выигрышная стратегия. ^[9]^{: Теорема 1}

В стратегии используется та же потенциальная функция, которую использовали Эрдос и Селфридж: потенциал выигрышного сета. $E$ с $|E|$ незанятые элементы (и ни один элемент, занятый Брейкером) не $2^{-|E|}$ . Ценность элемента — это общее уменьшение потенциала, если Разрушитель заберет этот элемент, что совпадает с общим увеличением потенциала, если его заберет Создатель. Стратегия Maker состоит в том, чтобы просто взять элемент с наибольшей ценностью.

Каждый раз, когда Создатель берет элемент, потенциал каждого выигрышного набора, содержащего его, увеличивается на $2^{-|E|}$ ; всякий раз, когда Брейкер берет элемент, потенциал каждого набора, который его содержит и не содержит элемент Создателя, уменьшается на $2^{-|E|}$ . Следовательно, если мы рассматриваем только выигрышные наборы, которые были затронуты один раз, потенциальная сумма слабо увеличивается. Потенциальная сумма может уменьшаться только за счет наборов, содержащих как элемент Создателя, так и элемент Разрушителя. Эти наборы приобретают $2^{-|E|}$ но потом проиграешь $2^{-(|E|-1)}$ , так что в целом они проигрывают $2^{-|E|}$ . Поскольку в таких множествах не менее двух элементов, каждое такое множество теряет не более 1/4. По предположению об ограниченной степени пары число таких множеств не превосходит d ₂ . Следовательно, после каждого раунда сумма потенциалов падает не более чем на d _2/4 . Число раундов равно |X|/2, поэтому конечный потенциал меньше начального не более чем на $d_{2}\cdot |X|/8$ . Начальный потенциал $|{\mathcal {F}}|\cdot 2^{-k}$ .

Если $|{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8$ , итоговый потенциал больше 0, поэтому существует хотя бы один выигрышный набор с потенциалом 1. Этот набор принадлежит Maker.

Хроматические числа и выигрышные стратегии

Хроматическое число ${\mathcal {F}}$ — наименьшее количество цветов, необходимое для раскраски элементов X так, чтобы ни один набор цветов не был ${\mathcal {F}}$ является монохромным. Если хроматическое число ${\mathcal {F}}$ равно 3, то у Создателя есть выигрышная стратегия. ^[10]

Сводная таблица

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

Во всех условиях k — размер выигрышных наборов (т. е. гиперграф игры является k -равномерным).


Состояние	Победитель	Герметичность	Комментарии
$\|{\mathcal {F}}\|<2^{k-1}$	Выключатель ^[7]	$\|{\mathcal {F}}\|\geq 2^{k-1}$	Потенциальная стратегия
Непересекающиеся выигрышные наборы, размер не менее 2	Выключатель		Стратегия спаривания
Почти непересекающиеся множества, $\|{\mathcal {F}}\|<4^{k-c{\sqrt {k}}}$	Выключатель ^[8]
Парная степень d ₂ , $\|{\mathcal {F}}\|>2^{k-3}\cdot d_{2}\cdot \|X\|$	Создатель ^[9]		Потенциальная стратегия

Игра Брейкер-Брейкер

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

Применение этой стратегии — эффективный алгоритм раскраски гиперграфа. Предположим, мы хотим раскрасить вершины k -однородного гиперграфа в два цвета так, чтобы в каждом гиперребре были представлены оба цвета. доказал Еще в 1963 году Эрдеш вероятностным методом , что такая раскраска существует всякий раз, когда число гиперребер меньше $2^{k-1}$ Другими словами, для существования такой раскраски гиперграф должен быть 2-однородным. (см. свойство Б ). Однако доказательство не было конструктивным. Используя конструктивную выигрышную стратегию Брейкера, мы можем раскрасить гиперграф ${\mathcal {F}}$ позволяя двум Брейкерам играть друг против друга, используя свои выигрышные стратегии. Оба игрока выиграют, поэтому у каждого игрока будет хотя бы одна вершина в каждом гиперребре. ^[1]^: 17–20

Частичное изготовление

Предположим, что для победы Мейкеру не нужно занимать весь выигрышный набор — ему достаточно владеть лишь частью такого набора. Когда Брейкер сможет победить в этом случае?

Постоянное частичное изготовление

m элементов в одном наборе (где Breaker не владеет ни одним элементом). Если размер каждого выигрышного сета не менее m, а количество сетов меньше $2^{m-1}$ , то у Брейкера все еще есть выигрышная стратегия. В стратегии используется потенциальная функция: потенциал «разорванного» множества равен 0, а потенциал неразрывного множества E равен $2^{-r(E)}$ , где r(E) — количество элементов, которые Создатель должен взять, чтобы выиграть. Таким образом, начальный потенциал каждого выигрышного сета равен $2^{-m}$ , а потенциал множества, занимаемого Создателем, равен 1. Отсюда доказательство такое же, как и в теореме Эрдоша-Селфриджа. ^[9]^{: Лемма 1}

Дробное изготовление

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

Если $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1$ , то у Брейкера есть выигрышная стратегия, когда он играет первым . ^[9]^{: Лемма 3}
Если $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<{1 \over 2-2t}$ , то у Брейкера есть выигрышная стратегия, когда он играет вторым . ^[11]

В частности, если все множества имеют размер k и их число меньше ${c_{t}}^{k}$ , то у Брейкера (играющего первым) есть выигрышная стратегия.

Стратегия использует потенциальную функцию. Потенциал выигрышного сета определяется как $(2t)^{-r}(2-2t)^{-s}$ , где r — количество элементов, которое необходимо взять Создателю, чтобы занять набор, а s — количество элементов, которое необходимо взять Разрушителю, чтобы разбить его. Если Создатель занимает множество, то его потенциал в какой-то момент будет равен 1. Следовательно, Брейкер выигрывает, если ему удается сохранить потенциал-сумму ниже 1. Стратегия Брейкера состоит в том, чтобы взять элемент с наибольшим значением, определяемым как сумма потенциалов выигрышных наборов, содержащих этот элемент.

Всякий раз, когда Создатель берет элемент, потенциал каждого набора, содержащего его, умножается на 2 t , поэтому он увеличивается в (2 t -1) раз по сравнению с текущим потенциалом. Всякий раз, когда Брейкер берет элемент, потенциал каждого набора, содержащего его, умножается на (2-2 t ), поэтому он увеличивается в (1-2 t ) раза по сравнению с текущим потенциалом. Всякий раз, когда Брейкер и Создатель касаются одного и того же набора, его потенциал умножается на 2 t (2-2 t ), поэтому он увеличивается на -(2 t -1). ² раз превышает текущий потенциал. Поскольку элемент Брейкера имеет наибольшее значение, потенциальная сумма всегда уменьшается. Следовательно, если начальная потенциальная сумма меньше 1, выигрывает Брейкер.

Бесконечные доски

Определение игры Maker-Breaker имеет тонкости, когда существует бесконечно много вершин ( $|V|=\infty$ ) и бесконечно много выигрышных сетов ( $|H|=\infty$ ). В этом случае мы говорим, что у Брейкера есть выигрышная стратегия, если для всех j > 0 Брейкер может помешать Мэйкеру полностью занять выигрышный набор к ходу j .

См. также

Ссылки

^ Jump up to: ^а ^б ^с Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинар в Обервольфахе. Том 44. Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8 .
^ Рахман, штат Мэриленд Лютфар; Уотсон, Томас (2018). Сложность неупорядоченных игр CNF . Замок Дагштуль — Центр компьютерных наук Лейбница. doi : 10.4230/LIPIcs.ISAAC.2018.9 . OCLC 1081450453 .
^ Хватал, В.; Эрдеш, П. (1978). «Предвзятые позиционные игры». Анналы дискретной математики . 2 : 221–229. дои : 10.1016/S0167-5060(08)70335-2 . ISBN 9780720410433 .
^ Черненский, Андраш; Мандити, К. Иветт; Плухар, Андраш (2009). «О позиционных играх Chooser-Picker» . Дискретная математика . 309 (16): 5141–5146. дои : 10.1016/j.disc.2009.03.051 . ISSN 0012-365X .
^ Рахман, штат Мэриленд Лютфар; Уотсон, Томас (2021). Блэзер, Маркус; Монмеге, Бенджамин (ред.). «Игра 6-Uniform Maker-Breaker завершена для PSPACE» . 38-й Международный симпозиум по теоретическим аспектам информатики (STACS 2021) . Международные труды Лейбница по информатике (LIPIcs). 187 . Дагштуль, Германия: Замок Дагштуль – Центр информатики Лейбница: 57:1–57:15. doi : 10.4230/LIPIcs.STACS.2021.57 . ISBN 978-3-95977-180-1 .
^ Шефер, Томас Дж. (апрель 1978 г.). «О сложности некоторых игр двух лиц с совершенной информацией». Журнал компьютерных и системных наук . 16 (2): 185–225. дои : 10.1016/0022-0000(78)90045-4 . ISSN 0022-0000 .
^ Jump up to: ^а ^б ^с Эрдеш, П .; Селфридж, Дж. Л. (1973). «Об одной комбинаторной игре» (PDF) . Журнал комбинаторной теории . Серия А. 14 (3): 298–301. дои : 10.1016/0097-3165(73)90005-8 . МР 0327313 .
^ Jump up to: ^а ^б Бек, Йожеф (1981). «О позиционных играх» . Журнал комбинаторной теории . Серия А. 30 (2): 117–133. дои : 10.1016/0097-3165(81)90001-7 . ISSN 0097-3165 .
^ Jump up to: ^а ^б ^с ^д Бек, Йожеф (1981). «Игры типа Ван дер Вардена и Рэмси». Комбинаторика . 1 (2): 103–116. дои : 10.1007/bf02579267 . ISSN 0209-9683 . S2CID 36276515 .
^ Хейлз, Альфред В.; Джуэтт, Роберт И. (1963). «Регулярность и позиционные игры» . Труды Американского математического общества . 106 (2): 222–229. дои : 10.1090/S0002-9947-1963-0143712-1 . МР 0143712 .
^ Сяоюнь, Лу (29 ноября 1991 г.). «Игра на совпадение» . Дискретная математика . 94 (3): 199–207. дои : 10.1016/0012-365X(91)90025-W . ISSN 0012-365X .

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

[2] Рахман, штат Мэриленд Лютфар; Уотсон, Томас (2018). Сложность неупорядоченных игр CNF . Замок Дагштуль — Центр компьютерных наук Лейбница. doi : 10.4230/LIPIcs.ISAAC.2018.9 . OCLC 1081450453 .

[ChvatalErdos1978-3] Хватал, В.; Эрдеш, П. (1978). «Предвзятые позиционные игры». Анналы дискретной математики . 2 : 221–229. дои : 10.1016/S0167-5060(08)70335-2 . ISBN 9780720410433 .

[4] Черненский, Андраш; Мандити, К. Иветт; Плухар, Андраш (2009). «О позиционных играх Chooser-Picker» . Дискретная математика . 309 (16): 5141–5146. дои : 10.1016/j.disc.2009.03.051 . ISSN 0012-365X .

[5] Рахман, штат Мэриленд Лютфар; Уотсон, Томас (2021). Блэзер, Маркус; Монмеге, Бенджамин (ред.). «Игра 6-Uniform Maker-Breaker завершена для PSPACE» . 38-й Международный симпозиум по теоретическим аспектам информатики (STACS 2021) . Международные труды Лейбница по информатике (LIPIcs). 187 . Дагштуль, Германия: Замок Дагштуль – Центр информатики Лейбница: 57:1–57:15. doi : 10.4230/LIPIcs.STACS.2021.57 . ISBN 978-3-95977-180-1 .

[6] Шефер, Томас Дж. (апрель 1978 г.). «О сложности некоторых игр двух лиц с совершенной информацией». Журнал компьютерных и системных наук . 16 (2): 185–225. дои : 10.1016/0022-0000(78)90045-4 . ISSN 0022-0000 .

[es-7] Jump up to: ^а ^б ^с Эрдеш, П .; Селфридж, Дж. Л. (1973). «Об одной комбинаторной игре» (PDF) . Журнал комбинаторной теории . Серия А. 14 (3): 298–301. дои : 10.1016/0097-3165(73)90005-8 . МР 0327313 .

[:0-8] Jump up to: ^а ^б Бек, Йожеф (1981). «О позиционных играх» . Журнал комбинаторной теории . Серия А. 30 (2): 117–133. дои : 10.1016/0097-3165(81)90001-7 . ISSN 0097-3165 .

[beck81-9] Jump up to: ^а ^б ^с ^д Бек, Йожеф (1981). «Игры типа Ван дер Вардена и Рэмси». Комбинаторика . 1 (2): 103–116. дои : 10.1007/bf02579267 . ISSN 0209-9683 . S2CID 36276515 .

[10] Хейлз, Альфред В.; Джуэтт, Роберт И. (1963). «Регулярность и позиционные игры» . Труды Американского математического общества . 106 (2): 222–229. дои : 10.1090/S0002-9947-1963-0143712-1 . МР 0143712 .

[11] Сяоюнь, Лу (29 ноября 1991 г.). «Игра на совпадение» . Дискретная математика . 94 (3): 199–207. дои : 10.1016/0012-365X(91)90025-W . ISSN 0012-365X .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]