Maker-Breaker game
Maker-Breaker game
A Maker-Breaker game is a kind of positional-game. Like most positional games, it is described by its set of positions/points/elements (<math>X</math>) and its family of winning-sets (<math>\mathcal{F}</math>- a family of subsets of <math>X</math>). 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-(board-game)|Hex]]. There, the winning-sets are all paths from the top side of the board to the bottom side. Maker wins by owning a connected path; Breaker wins by owning a connected path from left to right, since it blocks all connected paths from top to bottom.
- tic-tac-toe** can be played as a Maker-Breaker game. 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 this 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|Strong positional game#Comparison to Maker-Breaker game]]).
Unordered CNF Game 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 <math>E</math> of some graph <math>G</math> (usually taken as a complete graph), and the family of winning-sets is <math>\mathcal{F}=\{E'\subset E\vert G[E']\hbox{ has property }\mathcal{P}\}</math>, where <math>\mathcal{P}</math> is some graph property (usually taken to be monotone increasing [clarify?]) such as connectivity. 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 <math>(X,\mathcal{F})</math> yields a winning strategy for Maker playing first on <math>(X,\mathcal{F}).</math> The same is true for Breaker.
Furthermore, there is an alternative misère convention of a Maker-Breaker game called an avoider-enforcer-game.
Computational Complexity Maker-Breaker game is PSPACE-complete even if the size of each set is restricted to 5. The first result was from 1978 where the size of each set was restricted to 11, where the game was mentioned as <math>G </math>(POS CNF 11). It was first improved to size 6 in 2021.
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. They used a potential-based strategy. They defined the potential of any (non-broken) winning-set <math>E</math> with <math>|E|</math> unoccupied vertices as <math>2^{-|E|}</math>. So the potential of a set occupied by Maker is indeed <math>2^{-0}=1</math>. Whenever Maker takes an element, the potential of every set containing it increases to <math>2^{-(|E|-1)}</math>, i.e., increases by <math>2^{-|E|}</math>; whenever Breaker takes an element, the potential of every set containing it drops to 0, i.e., decreases by <math>2^{-|E|}</math>. To every element, we assign a value which equals the total potential-increase in case Maker takes it, i.e., <math>w(v) := \sum_{v\in E} 2^{-|E|}</math>. 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 Erdős-Selfridge theorem says that:
- If <math>\sum_{E\in \mathcal{F}} 2^{-|E|} < 1/2</math>, then <math>\mathcal{F}</math> 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 <math>\sum_{E\in \mathcal{F}} 2^{-|E|} < 1</math>.
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 <math>|\mathcal{F}| < 2^{k-1}</math>, i.e., the number of winning-sets is less than <math>2^{k-1}</math>. 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 <math>d_2</math>, as the maximum degree of a pair of elements (maximum over all pairs). If all winning-sets are of size <math>k</math>, and the number of winning-sets is more than <math>2^{k-3}\cdot d_2\cdot |X|</math>, then Maker has a winning strategy.
The strategy uses the same potential function used by Erdos and Selfridge: the potential of a winning-set <math>E</math> with <math>|E|</math> unoccupied elements (and no element occupied by Breaker) is <math>2^{-|E|}</math>. 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 <math>2^{-|E|}</math>; whenever Breaker takes an element, the potential of every set that contains it and does not contain Maker's element decreases by <math>2^{-|E|}</math>. 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 <math>2^{-|E|}</math> but then lose <math>2^{-(|E|-1)}</math>, so all in all they lose <math>2^{-|E|}</math>. 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 d2. Hence, after each round the potential-sum drops by at most d2/4. The number of rounds is |X|/2, so the final potential is smaller than the initial potential by at most <math>d_2\cdot |X|/8</math>. The initial potential is <math>|\mathcal{F}|\cdot 2^{-k}</math>.
If <math>|\mathcal{F}|\cdot 2^{-k} > d_2\cdot |X|/8</math>, 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 <math>\mathcal{F}</math> is the smallest number of colors needed to color the elements of X such that no single set in <math>\mathcal{F}</math> is monochromatic. If the chromatic number of <math>\mathcal{F}</math> is 3, then Maker has a winning-strategy.
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). {| class="wikitable" |+ !Condition !Winner !Tightness !Comments |- |<math>|\mathcal{F}| < 2^{k-1}</math> |Breaker
In particular, if all sets are of size k and their number is less than <math>{c_t}^{k}</math>, then Breaker (playing first) has a winning strategy.
The strategy uses a potential function. The potential of a winning-set is defined as <math>(2 t)^{-r} (2-2t)^{-s}</math>, 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)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.