Maker-Breaker game

A Maker-Breaker game is a kind of positional game.^[1]^: 13–24 Like most positional games, it is described by its set of positions/points/elements ( $X$ ) and its family of winning-sets ( ${\mathcal {F}}$ - a family of subsets of $X$ ). It is played by two players, called Maker and Breaker, who alternately take previously-untaken elements.

In a Maker-Breaker game, Maker wins if he manages to hold all the elements of a winning-set, while Breaker wins if he manages to prevent this, i.e. to hold at least one element in each winning-set. Draws are not possible. In each Maker-Breaker game, either Maker or Breaker has a winning strategy. The main research question about these games is which of these two options holds.

Examples[]

A classic Maker-Breaker game is Hex. There, the winning-sets are all paths from the left side of the board to the right side. Maker wins by owning a connected path; Breaker wins by owning a connected path from top to bottom, since it blocks all connected paths from left to right.

Tic-tac-toe can be played as a Maker-Breaker game: in that variant, the goal of Maker is to pick 3 squares in a row, and the goal of Breaker is just to prevent Maker from doing so. In that variant, Maker has a winning strategy. This is in contrast to the classic variant (which is a Strong positional game) where the second player has a drawing strategy (see Strong positional game#Comparison to Maker-Breaker game).

Unordered CNF Game^[2] on a positive CNF (all positive literals) can be considered as a Maker-Breaker game where Maker wants to falsify the CNF, and Breaker wants to satisfy it.

Some research has been done on playing Maker-Breaker games when the board of the game is the edge set $E$ of some graph $G$ (usually taken as a complete graph), and the family of winning-sets is ${\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ has property }}{\mathcal {P}}\}$ , where ${\mathcal {P}}$ is some graph property (usually taken to be monotone increasing [clarify?]) such as connectivity.^[3] For instance, the Shannon switching game is a Maker-Breaker game in which the winning sets are the paths between two distinguished vertices.

Breaker-Maker duality[]

In a Maker-Breaker game, usually Maker plays first. But it is also possible to let Breaker play first. Playing first is always advantageous: any winning strategy for Maker playing second on $(X,{\mathcal {F}})$ yields a winning strategy for Maker playing first on $(X,{\mathcal {F}}).$ The same is true for Breaker.^[1]^: 15

Moreover, for every game $(X,{\mathcal {F}})$ we can define its transversal game $(X,{\mathcal {F^{*}}})$ , in which the winning-sets are the minimal sets touching each winning-set in the original game. For example, if in the original game the winning-sets are { {1,2,3},{4,5,6} } then in the dual game they are { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Then, the winning strategies for Breaker playing first on $(X,{\mathcal {F}})$ are exactly the winning-strategies for Maker playing first on $(X,{\mathcal {F^{*}}})$ .^[4]^: 2

Computational Complexity[]

Maker-Breaker game is PSPACE-complete even if the size of each set is restricted to 6.^[5] The first result was from 1978 where the size of each set was restricted to 11,^[6] where the game was mentioned as $G$ (POS CNF 11).

Strategies[]

Several kinds of strategies are commonly used to solve Maker-Breaker games.

Pairing Strategies[]

In some games, it is possible to partition the elements of X (or a subset of them) into a set of pairwise-disjoint pairs. Under certain conditions, a player can win using the following greedy strategy: "whenever your opponent picks an element of pair i, pick the other element of pair i".

The "certain conditions" are different for Maker and for Breaker; see pairing strategy.

Strategies from strong positional games[]

Every winning-strategy for First in a strong positional game, is also a winning strategy for Maker in the maker-breaker variant (see Strong positional game#Comparison to Maker-Breaker game). In particular, if in the strong-positional variant there can be no draw, then in the maker-breaker variant Maker has a winning strategy. The opposite is not necessarily true: a winning-strategy for Maker in the maker-breaker variant is not necessarily a winning-strategy for First in the strong variant, since in the strong variant, Second can win by claiming a winning-set before First.

In contrast, every winning-strategy for Breaker in a maker-breaker game, is also a drawing-strategy for Second in the strong-positional variant.

Potential-based strategies[]

Suppose we can find a function that assigns, to each winning-set, a potential based on the number of elements already taken from it by Maker/Breaker. The potential function should satisfy the following properties:

The potential of a winning-set is between 0 and 1;
When Breaker takes an element, the potential of all sets containing it drops to 0 and remains 0;
When Maker takes an element, the potential of all (non-broken) sets containing it increases;
The potential of a set owned by Maker is 1.

Then, Maker wins iff the potential-sum is more than 0, and Breaker wins iff the potential-sum is less than 1. Hence:

If the initial sum is more than 0, and Maker can play such that the potential-sum weakly increases, then this is a winning strategy for Maker;
If the initial sum is less than 1, and Breaker can play such that the potential-sum weakly decreases, then this is a winning strategy for Breaker.

A winning condition for Breaker[]

Paul Erdős and John Selfridge presented a general condition that guarantees Breaker a winning strategy.^[7] They used a potential-based strategy. They defined the potential of any (non-broken) winning-set $E$ with $|E|$ unoccupied vertices as $2^{-|E|}$ . So the potential of a set occupied by Maker is indeed $2^{-0}=1$ . Whenever Maker takes an element, the potential of every set containing it increases to $2^{-(|E|-1)}$ , i.e., increases by $2^{-|E|}$ ; whenever Breaker takes an element, the potential of every set containing it drops to 0, i.e., decreases by $2^{-|E|}$ . To every element, we assign a value which equals the total potential-increase in case Maker takes it, i.e., $w(v):=\sum _{v\in E}2^{-|E|}$ . The winning strategy of Breaker is pick an element with a highest value. This guarantees that, from the first turn of Breaker onwards, the potential always weakly decreases. Hence, if the potential at the first Breaker turn is less than 1, Breaker wins. In Maker's first turn, he can, at most, double the potential (by taking an element contained in all winning-sets). Therefore, it is sufficient that, at the game start, the potential is less than 1/2. To summarize, the Erdos-Selfridge theorem says that:

If $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1/2$ , then ${\mathcal {F}}$ is Breaker's win.

The theorem gives a very easy-to-check condition, and when this condition is satisfied, it also gives an efficient algorithm for computing Breaker's optimal strategy.

The potential function has a probabilistic interpretation. The potential of a winning-set is the probability that, if the game is played randomly from now on, Maker will own that set. The potential-sum is thus the expected number of winning-sets owned by Maker if the game is played randomly. Whenever the potential-sum is less than 1, there must be a way to play the game such that the number of sets owned by Maker is 0. By ensuring that the potential-sum remains below 1, Breaker essentially de-randomizes this probabilistic claim until at the end of the game, it becomes a certainty.

Note that if Breaker plays first, the condition changes to $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1$ .

In particular, if the winning-sets are all of size k (i.e., the game-hypergraph is k-uniform), then the Erdos-Selfridge theorem implies that Breaker wins whenever $|{\mathcal {F}}|<2^{k-1}$ , i.e., the number of winning-sets is less than $2^{k-1}$ .^[7]

The number $2^{k-1}$ is tight: there are $k$ -uniform hypergraphs where the number of winning sets is exactly $2^{k-1}$ , and where Maker has a winning strategy. For example, consider a perfect binary tree of height $k-1$ . It has $2^{k-1}$ leaves. Define V as the set of tree nodes, and H as the family of all $2^{k-1}$ paths from the root to a leaf. Maker starts by picking the root. Then, if Breaker picks an element in the left subtree, Maker picks the root of the right subtree, and vice versa. By continuing this way, Maker can always pick a full path, i.e., a winning-set.

Disjoint and almost-disjoint hypergraphs[]

If all winning-sets are pairwise-disjoint and their size is at least 2, then Breaker can win using a pairing strategy.

Suppose now that the winning-sets are almost disjoint, i.e., any two winning-sets have at most one element in common. If all winning-sets are of size $k$ , and the number of winning sets is less than $4^{k-c{\sqrt {k}}}$ (for some fixed constant c), then Breaker has a winning strategy.^[8] So this situation is easier for Breaker than the general case, but harder than the case of disjoint winning-sets.

A winning condition for Maker[]

Define the degree of a set of elements as the number of different winning-sets that contain this set. Define the pair-degree of a set-family, denoted $d_{2}$ , as the maximum degree of a pair of elements (maximum over all pairs). If all winning-sets are of size $k$ , and the number of winning-sets is more than $2^{k-3}\cdot d_{2}\cdot |X|$ , then Maker has a winning strategy.^[9]^{: Theorem 1}

The strategy uses the same potential function used by Erdos and Selfridge: the potential of a winning-set $E$ with $|E|$ unoccupied elements (and no element occupied by Breaker) is $2^{-|E|}$ . The value of an element is the total potential-decrease if Breaker takes that element, which is the same as the total potential-increase if Maker takes it. Maker's strategy is simply to take the highest-value element.

Whenever Maker takes an element, the potential of every winning-set that contains it increases by $2^{-|E|}$ ; whenever Breaker takes an element, the potential of every set that contains it and does not contain Maker's element decreases by $2^{-|E|}$ . Therefore, if we consider only the winning-sets that were touched once, the potential-sum weakly increases. The potential-sum can decrease only due to sets that contain both Maker's element and Breaker's element. These sets gain $2^{-|E|}$ but then lose $2^{-(|E|-1)}$ , so all in all they lose $2^{-|E|}$ . Since such sets have at least two elements, each such set loses at most 1/4. By the limited-pair-degree assumption, the number of such sets is at most d₂. Hence, after each round the potential-sum drops by at most d₂/4. The number of rounds is |X|/2, so the final potential is smaller than the initial potential by at most $d_{2}\cdot |X|/8$ . The initial potential is $|{\mathcal {F}}|\cdot 2^{-k}$ .

If $|{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8$ , the final potential is more than 0, so there is at least one winning-set with potential 1. This set is owned by Maker.

Chromatic numbers and winning strategies[]

The chromatic number of ${\mathcal {F}}$ is the smallest number of colors needed to color the elements of X such that no single set in ${\mathcal {F}}$ is monochromatic. If the chromatic number of ${\mathcal {F}}$ is 3, then Maker has a winning-strategy.^[10]

Summary table[]

The following table summarizes some conditions that guarantee that one of the players has a winning strategy. The condition in the "tightness" column indicates when specific hypergraphs are known on which the strategy stops working.

In all conditions, k is the size of winning-sets (i.e., the game hypergraph is k-uniform).


Condition	Winner	Tightness	Comments
$\|{\mathcal {F}}\|<2^{k-1}$	Breaker^[7]	$\|{\mathcal {F}}\|\geq 2^{k-1}$	Potential strategy
Disjoint winning-sets, size at least 2	Breaker		Pairing strategy
Almost-disjoint sets, $\|{\mathcal {F}}\|<4^{k-c{\sqrt {k}}}$	Breaker^[8]
Pair-degree d₂, $\|{\mathcal {F}}\|>2^{k-3}\cdot d_{2}\cdot \|X\|$	Maker^[9]		Potential strategy

Breaker-Breaker game[]

It is possible to play a game in which both players want to attain the goal of Breaker (i.e., have at least one element in each winning-set). Then, the game is not necessarily zero-sum - it is possible that both players will win. In fact, whenever Breaker has a winning strategy in the Maker-Breaker game, it is possible that two Breakers will both win in the Breaker-Breaker game.

An application of this strategy is an efficient algorithm for coloring a hypergraph. Suppose we want to color the vertices of a k-uniform hypergraph in two colors such that in each hyperedge, both colors are represented. Erdos proved already in 1963, using the probabilistic method, that such a coloring exists whenever the number of hyperedges is less than $2^{k-1}$ (see Property B). However, the proof was not constructive. Using Breaker's constructive winning strategy, we can color the hypergraph ${\mathcal {F}}$ by letting two Breakers play one against the other with their winning strategies. Both players will win - so each player will have at least one vertex in every hyperedge.^[1]^: 17–20

Partial making[]

Suppose that, in order to win, Maker does not need to occupy an entire winning-set - he only needs to own a part of such a set. When can Breaker win in this case?

Constant partial making[]

m elements in one set (where Breaker does not own any element). If the size of each winning-set is at least m, and the number of sets is less than $2^{m-1}$ , then Breaker still has a winning strategy. The strategy uses a potential function: the potential of a "broken" set is 0, and the potential of a non-broken set E is $2^{-r(E)}$ , where r(E) is the number of elements Maker has to take in order to win it. So the initial potential of every winning-set is $2^{-m}$ , and the potential of a set occupied by Maker is 1. From here the proof is the same as the Erdos-Selfridge theorem.^[9]^{: Lemma 1}

Fractional making[]

Suppose that, in order to win, Maker needs to own only a fraction t of the elements in one winning-set, where $1/2<t\leq 1$ . So Breaker needs to own a fraction larger than (1-t) of the points in every set. Define the constant: $c_{t}:=(2t)^{t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}$ (in the standard variant, $t=1,c_{t}\to 2$ ).

If $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1$ , then Breaker has a winning strategy when playing first.^[9]^{: Lemma 3}
If $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<{1 \over 2-2t}$ , then Breaker has a winning strategy when playing second.^[11]

In particular, if all sets are of size k and their number is less than ${c_{t}}^{k}$ , then Breaker (playing first) has a winning strategy.

The strategy uses a potential function. The potential of a winning-set is defined as $(2t)^{-r}(2-2t)^{-s}$ , where r is the number of elements Maker needs to take in order to occupy the set, and s is the number of elements Breaker needs to take in order to break it. If Maker occupies a set, then its potential will at some point be at least 1. Therefore, Breaker wins if he manages to keep the potential-sum below 1. Breaker's strategy is to take the element with the highest value, defined as the sum of potentials of winning-sets containing that element.

Whenever Maker takes an element, the potential of every set containing it is multiplied by 2t, so it increases by (2t-1) times the current potential. Whenever Breaker takes an element, the potential of every set containing it is multiplied by (2-2t), so it increases by (1-2t) times the current potential. Whenever Breaker and Maker both touch the same set, its potential is multiplied by 2t(2-2t), so it increases by -(2t-1)² times the current potential. Since Breaker's element has a highest value, the potential-sum always decreases. Therefore, if the initial potential-sum is less than 1, Breaker wins.

Infinite boards[]

The definition of Maker-Breaker game has a subtlety when there are infinitely many vertices ( $|V|=\infty$ ) and infinitely many winning sets ( $|H|=\infty$ ). In this case we say that Breaker has a winning strategy if, for all j > 0, Breaker can prevent Maker from completely occupying a winning set by turn j.

References[]

^ Jump up to: ^a ^b ^c Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
^ Rahman, Md Lutfar Watson, Thomas (2018). Complexity of Unordered CNF Games. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. OCLC 1081450453.CS1 maint: multiple names: authors list (link)
^ Chvatal; Erdos (1978). "Biased positional games". . 2: 221–229. doi:10.1016/S0167-5060(08)70335-2. ISBN 9780720410433.
^ Csernenszky, András; Mándity, C. Ivett; Pluhár, András (2009). "On Chooser–Picker positional games". Discrete Mathematics. 309 (16): 5141–5146. doi:10.1016/j.disc.2009.03.051. ISSN 0012-365X.
^ Rahman, Md Lutfar; Watson, Thomas (2021). Bläser, Markus; Monmege, Benjamin (eds.). "6-Uniform Maker-Breaker Game Is PSPACE-Complete". 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 187: 57:1–57:15. doi:10.4230/LIPIcs.STACS.2021.57. ISBN 978-3-95977-180-1.
^ Schaefer, Thomas J. (April 1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4. ISSN 0022-0000.
^ Jump up to: ^a ^b ^c Erdős, P.; Selfridge, J. L. (1973). "On a combinatorial game" (PDF). Journal of Combinatorial Theory. Series A. 14 (3): 298–301. doi:10.1016/0097-3165(73)90005-8. MR 0327313.
^ Jump up to: ^a ^b Beck, József (1981). "On positional games". Journal of Combinatorial Theory, Series A. 30 (2): 117–133. doi:10.1016/0097-3165(81)90001-7. ISSN 0097-3165.
^ Jump up to: ^a ^b ^c ^d Beck, József (1981). "Van der waerden and ramsey type games". Combinatorica. 1 (2): 103–116. doi:10.1007/bf02579267. ISSN 0209-9683. S2CID 36276515.
^ Hales, Alfred W.; Jewett, Robert I. (1963). "Regularity and positional games". Trans. Amer. Math. Soc. 106 (2): 222–229. doi:10.1090/S0002-9947-1963-0143712-1. MR 0143712.
^ Xiaoyun, Lu (1991-11-29). "A matching game". Discrete Mathematics. 94 (3): 199–207. doi:10.1016/0012-365X(91)90025-W. ISSN 0012-365X.

[:02-1] Jump up to: ^a ^b ^c Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.

[2] Rahman, Md Lutfar Watson, Thomas (2018). Complexity of Unordered CNF Games. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. OCLC 1081450453.CS1 maint: multiple names: authors list (link)

[ChvatalErdos1978-3] Chvatal; Erdos (1978). "Biased positional games". . 2: 221–229. doi:10.1016/S0167-5060(08)70335-2. ISBN 9780720410433.

[4] Csernenszky, András; Mándity, C. Ivett; Pluhár, András (2009). "On Chooser–Picker positional games". Discrete Mathematics. 309 (16): 5141–5146. doi:10.1016/j.disc.2009.03.051. ISSN 0012-365X.

[5] Rahman, Md Lutfar; Watson, Thomas (2021). Bläser, Markus; Monmege, Benjamin (eds.). "6-Uniform Maker-Breaker Game Is PSPACE-Complete". 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 187: 57:1–57:15. doi:10.4230/LIPIcs.STACS.2021.57. ISBN 978-3-95977-180-1.

[6] Schaefer, Thomas J. (April 1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4. ISSN 0022-0000.

[es-7] Jump up to: ^a ^b ^c Erdős, P.; Selfridge, J. L. (1973). "On a combinatorial game" (PDF). Journal of Combinatorial Theory. Series A. 14 (3): 298–301. doi:10.1016/0097-3165(73)90005-8. MR 0327313.

[:0-8] Jump up to: ^a ^b Beck, József (1981). "On positional games". Journal of Combinatorial Theory, Series A. 30 (2): 117–133. doi:10.1016/0097-3165(81)90001-7. ISSN 0097-3165.

[beck81-9] Jump up to: ^a ^b ^c ^d Beck, József (1981). "Van der waerden and ramsey type games". Combinatorica. 1 (2): 103–116. doi:10.1007/bf02579267. ISSN 0209-9683. S2CID 36276515.

[10] Hales, Alfred W.; Jewett, Robert I. (1963). "Regularity and positional games". Trans. Amer. Math. Soc. 106 (2): 222–229. doi:10.1090/S0002-9947-1963-0143712-1. MR 0143712.

[11] Xiaoyun, Lu (1991-11-29). "A matching game". Discrete Mathematics. 94 (3): 199–207. doi:10.1016/0012-365X(91)90025-W. ISSN 0012-365X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]