In combinatorial game theory, Maker-Breaker games are a subclass of positional games introduced by Paul Erdős and John Selfridge.
It is a two-person game with complete information played on a hypergraph (V,H) where V is an arbitrary set (called the board of the game) and H is a family of subsets of V, called the winning sets. The two players alternately occupy previously unoccupied elements of V.
The first player, Maker, has to occupy a winning set to win; and the second player, Breaker, has to stop Maker from doing so; if Breaker successfully prevents maker from occupying a winning set to the end of the game, then Breaker wins. Thus, in a Maker–Breaker positional game, Maker wins if he occupies all elements of some winning set and Breaker wins if he prevents Maker from doing so. There can be no draw in a Maker-Breaker positional game: one player always wins.
The definition of Maker-Breaker game has a subtlety when
Erdős and Selfridge proved that, when the winning sets are large and the number of winning sets is small, Breaker can always win. More precisely, if the winning sets are all of size
When tictactoe is played as a Maker–Breaker positional game, Maker has a winning strategy. This difference from tictactoe arises because, in tictactoe, when the second player (Breaker) takes two squares in a line, the first player (Maker) must respond to the threat by blocking the line. This forced response may be used to divert Maker from getting a winning line. In the corresponding Maker-Breaker game, Maker can ignore these threats, because getting three in a row first is not a winning condition for Breaker.
Maker-Breaker games on graphs
There has been quite some research done on playing Maker-Breaker games when the board of the game is the edge-set of a graph