*** Welcome to piglix ***

Maker-Breaker game


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 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.


...
Wikipedia

...