Maker-Breaker game

Maker-Breaker game

Maker-Breaker games are a subclass of positional games[1].

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 |V|=\infty and |H|=\infty. 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) [2].

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 G = (V,E) (usually taken as the complete graph) and the family of winning sets is \mathcal{F}=\{F\subset E\vert G[F]\hbox{ has property }\mathcal{P}\}, where \mathcal{P} is some graph property (usually taken to be monotone increasing) such as connectivity (see, e.g., [3]).

References

  1. ^ J. Beck: Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008.
  2. ^ Kruczek, Klay; Eric Sundberg (2010). "Potential-based strategies for tic-tac-toe on the integer latticed with numerous directions". The Electronic Journal of Combinatorics 17: R5. 
  3. ^ Chvatal; Erdos (1978). "Biased positional games". Annals of discrete mathematics 2: 221–229. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Dracula (adventure game) — Dracula Publisher(s) CRL Group Designer(s) Rod Pike, Ian Ellery Platform(s) Amstrad CPC, Commodore 64, ZX Spectrum …   Wikipedia

  • Список игр на Game Boy Advance — Содержание 1 0 9 2 A 3 B 4 C 5 D 6 E …   Википедия

  • Liste De Jeux Game Boy Advance — Listes de jeux vidéo 0 9 A B C D E F G H I J K L M N O P Q R S T …   Wikipédia en Français

  • Liste de jeux Game Boy Advance —   Liste des listes de jeux vidéo  Liste des jeux vidéo sortis sur la console de jeu Game Boy Advance …   Wikipédia en Français

  • Liste de jeux game boy advance — Listes de jeux vidéo 0 9 A B C D E F G H I J K L M N O P Q R S T …   Wikipédia en Français

  • Liste des jeux Game Boy Advance — Liste de jeux Game Boy Advance Listes de jeux vidéo 0 9 A B C D E F G H I J K L M N O P Q R S T …   Wikipédia en Français

  • Rose Bowl Game — Granddaddy of Them All redirects here. For the pay per view wrestling event, see WrestleMania. Rose Bowl Game The Granddaddy of Them All 2011 Rose Bowl game logo Stadium Rose Bowl Location Pasadena, California …   Wikipedia

  • Mastermind (board game) — For other uses, see Mastermind (disambiguation). Mastermind (board game) A game of Mastermind completed. Players 2 Age range 8 and up Setup time < 5 minutes …   Wikipedia

  • List of Nitrome Limited games — This is a list of the games made by Nitrome. Contents 1 Main games 2 Mini games 3 Mobile games 4 Notes 5 …   Wikipedia

  • Anexo:Juegos de nitrome — Los juegos hechos por Nitrome pueden ser clasificados en diferentes categorías. La categoría Hot games ,[1] literalmente Juegos calientes , son los dieciséis juegos más recientes, y los considerados más populares ( Hot es popular). Estos juegos… …   Wikipedia Español

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”