A Maker-Breaker game is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements (
X
l{F}
X
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.
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, Breaker 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[1] 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
G
l{F}=\{E'\subsetE\vertG[E']\hbox{hasproperty}l{P}\}
l{P}
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,l{F})
(X,l{F}).
Moreover, for every game
(X,l{F})
(X,l{F*})
(X,l{F})
(X,l{F*})
Furthermore, there is an alternative Misère convention of a Maker-Breaker game called an Avoider-Enforcer game.
Maker-Breaker game is PSPACE-complete even if the size of each set is restricted to 6.[4] The first result was from 1978 where the size of each set was restricted to 11,[5] where the game was mentioned as
G
Several kinds of strategies are commonly used to solve Maker-Breaker games.
See main article: pairing strategy. 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.
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.
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:
Then, Maker wins iff the potential-sum is more than 0, and Breaker wins iff the potential-sum is less than 1. Hence:
Paul Erdős and John Selfridge presented a general condition that guarantees Breaker a winning strategy.[6] They used a potential-based strategy. They defined the potential of any (non-broken) winning-set
E
|E|
2-|E|
2-0=1
2-(|E|-1)
2-|E|
2-|E|
w(v):=\sumv\in2-|E|
If
\sumE\in
l{F}
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
\sumE\in
In particular, if the winning-sets are all of size k (i.e., the game-hypergraph is k-uniform), then the Erdős-Selfridge theorem implies that Breaker wins whenever
|l{F}|<2k-1
2k-1
The number
2k-1
k
2k-1
k-1
2k-1
2k-1
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
4k
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
d2
k
2k-3 ⋅ d2 ⋅ |X|
The strategy uses the same potential function used by Erdos and Selfridge: the potential of a winning-set
E
|E|
2-|E|
Whenever Maker takes an element, the potential of every winning-set that contains it increases by
2-|E|
2-|E|
2-|E|
2-(|E|-1)
2-|E|
d2 ⋅ |X|/8
|l{F}| ⋅ 2-k
If
|l{F}| ⋅ 2-k>d2 ⋅ |X|/8
The chromatic number of
l{F}
l{F}
l{F}
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).
| \mathcal | < 2^ | Breaker | \mathcal | \geq 2^ | Potential strategy | |||
| Disjoint winning-sets, size at least 2 | Breaker | Pairing strategy | ||||||
| Almost-disjoint sets, | \mathcal | < 4^ | Breaker | |||||
| Pair-degree d2, | \mathcal | > 2^\cdot d_2\cdot | X | Maker | Potential strategy |
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
2k-1
l{F}
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?
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
2m-1
2-r(E)
2-m
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\leq1
ct:=(2t)t ⋅ (2-2t)1-t=2 ⋅ tt ⋅ (1-t)1-t
t=1,ct\to2
\sumE\in
\sumE\in
In particular, if all sets are of size k and their number is less than
| k | |
| {c | |
| t} |
The strategy uses a potential function. The potential of a winning-set is defined as
(2t)-r(2-2t)-s
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)2 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.
The definition of Maker-Breaker game has a subtlety when there are infinitely many vertices (
|V|=infty
|H|=infty