Игра Maker-Breaker
Категория позиционных игр

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

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

Примеры

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

В крестики-нолики можно играть как в игру Maker-Breaker: в этом варианте цель Maker — выбрать 3 квадрата в ряд, а цель Breaker — просто помешать Maker сделать это. В этом варианте у Breaker есть выигрышная стратегия. Это отличается от классического варианта (который является сильной позиционной игрой ), где у второго игрока есть стратегия розыгрыша (см. Strong positional game#Comparison to Maker-Breaker game ).

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

Были проведены некоторые исследования по игре в игры Maker-Breaker, когда игровое поле представляет собой множество ребер некоторого графа (обычно рассматриваемого как полный граф ), а семейство выигрышных множеств — , где — некоторое свойство графа (обычно рассматриваемое как монотонно возрастающее [уточнить?]), такое как связность. [3] Например, игра с переключением Шеннона — это игра Maker-Breaker, в которой выигрышные множества — это пути между двумя выделенными вершинами. Э {\displaystyle E} Г {\displaystyle G} Ф = { Э ′ ⊂ Э | Г [ Э ′ ]  имеет собственность  П } {\displaystyle {\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ имеет свойство }}{\mathcal {P}}\}} П {\displaystyle {\mathcal {P}}}

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

В игре Maker-Breaker обычно Maker играет первым. Но также возможно позволить Breaker играть первым. Играть первым всегда выгодно: любая выигрышная стратегия для Maker, играющего вторым, даёт выигрышную стратегию для Maker, играющего первым . То же самое верно и для Breaker. [1] : 15  ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})} ( Х , Ф ) . {\displaystyle (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} }. Тогда выигрышные стратегии для Breaker, играющего первым, в точности совпадают с выигрышными стратегиями для Maker, играющего первым . [4] : 2  ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})} ( Х , Ф ∗ ) {\displaystyle (X,{\mathcal {F^{*}}})} ( Х , Ф ) {\displaystyle (X,{\mathcal {F}})} ( Х , Ф ∗ ) {\displaystyle (X,{\mathcal {F^{*}}})}

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

Сложность вычислений

Игра Maker-Breaker является PSPACE-полной, даже если размер каждого набора ограничен 6. [5] Первый результат был получен в 1978 году, когда размер каждого набора был ограничен 11, [6] и тогда игра упоминалась как (POS CNF 11). Г {\displaystyle G}

Стратегии

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

Стратегии парного сочетания

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

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

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

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

Напротив, каждая выигрышная стратегия для Breaker в игре Maker-Braker является также стратегией ничьей для Second в варианте с сильной позицией.

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

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

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

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

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

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

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

Если , то победа Брейкера ∑ Э ∈ Ф 2 − | Э | < 1 / 2 {\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}<1/2} Ф {\displaystyle {\mathcal {F}}} .

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

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

Обратите внимание: если Брейкер ходит первым, условие меняется на . ∑ Э ∈ Ф 2 − | Э | < 1 {\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}<1}

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

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

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

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

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

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

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

Стратегия использует ту же функцию потенциала, которую использовали Эрдос и Селфридж: потенциал выигрышного набора с незанятыми элементами (и без элементов, занятых Breaker) равен . Значение элемента равно общему потенциальному уменьшению, если Breaker берет этот элемент, что равно общему потенциальному увеличению, если Maker берет его. Стратегия Maker заключается в том, чтобы просто взять элемент с наивысшей ценностью. Э {\displaystyle E} | Э | {\displaystyle |E|} 2 − | Э | {\displaystyle 2^{-|E|}}

Всякий раз, когда Maker берет элемент, потенциал каждого выигрышного набора, который его содержит, увеличивается на ; всякий раз, когда Breaker берет элемент, потенциал каждого набора, который его содержит и не содержит элемент Maker, уменьшается на . Следовательно, если мы рассмотрим только выигрышные наборы, которые были затронуты один раз, потенциальная сумма слабо увеличивается. Потенциальная сумма может уменьшиться только из-за наборов, которые содержат как элемент Maker, так и элемент Breaker. Эти наборы получают, но затем теряют , так что в целом они теряют . Поскольку такие наборы имеют по крайней мере два элемента, каждый такой набор теряет не более 1/4. По предположению об ограниченной степени пары количество таких наборов не более d 2 . Следовательно, после каждого раунда потенциальная сумма падает не более чем на d 2 /4. Количество раундов равно |X|/2, поэтому окончательный потенциал меньше начального потенциала не более чем на . Начальный потенциал равен . 2 − | Э | {\displaystyle 2^{-|E|}} 2 − | Э | {\displaystyle 2^{-|E|}} 2 − | Э | {\displaystyle 2^{-|E|}} 2 − ( | Э | − 1 ) {\displaystyle 2^{-(|E|-1)}} 2 − | Э | {\displaystyle 2^{-|E|}} г 2 ⋅ | Х | / 8 {\displaystyle d_{2}\cdot |X|/8} | Ф | ⋅ 2 − к {\displaystyle |{\mathcal {F}}|\cdot 2^{-k}}

Если , то конечный потенциал больше 0, значит, есть по крайней мере один выигрышный набор с потенциалом 1. Этот набор принадлежит Maker. | Ф | ⋅ 2 − к > г 2 ⋅ | Х | / 8 {\displaystyle |{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение игры Maker-Breaker имеет тонкость, когда есть бесконечно много вершин ( ) и бесконечно много выигрышных множеств ( ). В этом случае мы говорим, что Breaker имеет выигрышную стратегию, если для всех j  > 0 Breaker может помешать Maker полностью занять выигрышное множество к ходу  j . | В | = ∞ {\displaystyle |V|=\infty } | ЧАС | = ∞ {\displaystyle |H|=\infty }

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

Ссылки

  1. ^ abc Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинары в Обервольфахе. Том. 44. Базель: Биркхойзер Верлаг ГмбХ. ISBN 978-3-0348-0824-8.
  2. ^ Рахман, Мэриленд Лютфар; Уотсон, Томас (2018). Сложность неупорядоченных игр CNF . Замок Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.ISAAC.2018.9 . ОСЛК  1081450453.
  3. ^ Chvatal, V.; Erdös, P. (1978). «Предвзятые позиционные игры». Annals of Discrete Mathematics . 2 : 221–229. doi :10.1016/S0167-5060(08)70335-2. ISBN 9780720410433.
  4. ^ Черненски, Андраш; Мандити, К. Иветт; Плухар, Андраш (2009). «О позиционных играх Селектор – Пикер». Дискретная математика . 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. doi :10.1016/0022-0000(78)90045-4. ISSN  0022-0000.
  7. ^ abc Erdős, P. ; Selfridge, JL (1973). "О комбинаторной игре" (PDF) . Журнал комбинаторной теории . Серия A. 14 (3): 298–301. doi : 10.1016/0097-3165(73)90005-8 . MR  0327313.
  8. ^ ab Beck, József (1981). «О позиционных играх». Журнал комбинаторной теории . Серия A. 30 (2): 117–133. doi : 10.1016/0097-3165(81)90001-7 . ISSN  0097-3165.
  9. ^ abcd Бек, Йожеф (1981). «Игры типа Ван дер Вардена и Рэмси». Комбинаторика . 1 (2): 103–116. дои : 10.1007/bf02579267. ISSN  0209-9683. S2CID  36276515.
  10. ^ Хейлз, Альфред В.; Джуэтт, Роберт И. (1963). «Регулярность и позиционные игры». Труды Американского математического общества . 106 (2): 222–229. doi : 10.1090/S0002-9947-1963-0143712-1 . MR  0143712.
  11. ^ Сяоюнь, Лу (1991-11-29). «Игра на соответствие». Дискретная математика . 94 (3): 199–207. doi : 10.1016/0012-365X(91)90025-W . ISSN  0012-365X.
Взято с "https://en.wikipedia.org/w/index.php?title=Maker-Breaker_game&oldid=1249357246"