Maker-Breaker game
Encyclopedia
Maker-Breaker games are a subclass of positional game
s.
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
and 
. 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.
It is interesting to note that when tictactoe is played as a Maker–Breaker positional game, Maker has a winning strategy (Maker does not need to block Breaker from obtaining a winning line)
.
(usually taken as the complete graph) and the family of winning sets is 
, where 
is some graph property
(usually taken to be monotone increasing) such as connectivity (see, e.g.).
Positional game
Positional games are a class of combinatorial games. Well-known games that fall into this class include tic-tac-toe, hex and Shannon switching game....
s.
It is a two-person game with complete information
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
played on a hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
(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
and . 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.It is interesting to note that when tictactoe is played as a Maker–Breaker positional game, Maker has a winning strategy (Maker does not need to block Breaker from obtaining a winning line)
.
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 graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
(usually taken as the complete graph) and the family of winning sets is , where is some graph propertyGraph property
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.-Definitions:...
(usually taken to be monotone increasing) such as connectivity (see, e.g.).