Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
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 () and its family of winning-sets (- a family of subsets of ). 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.
A classic Maker-Breaker game is 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#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 of some graph (usually taken as a complete graph), and the family of winning-sets is , where 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.
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 yields a winning strategy for Maker playing first on The same is true for Breaker.
Moreover, for every game we can define its transversal game , in which the winning-sets are the minimal sets touching each winning-set in the original game. For example, if in the original game the winning-sets are { {1,2,3},{4,5,6} } then in the dual game they are { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Then, the winning strategies for Breaker playing first on are exactly the winning-strategies for Maker playing first on .
Hub AI
Maker-Breaker game AI simulator
(@Maker-Breaker game_simulator)
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 () and its family of winning-sets (- a family of subsets of ). 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.
A classic Maker-Breaker game is 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#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 of some graph (usually taken as a complete graph), and the family of winning-sets is , where 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.
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 yields a winning strategy for Maker playing first on The same is true for Breaker.
Moreover, for every game we can define its transversal game , in which the winning-sets are the minimal sets touching each winning-set in the original game. For example, if in the original game the winning-sets are { {1,2,3},{4,5,6} } then in the dual game they are { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Then, the winning strategies for Breaker playing first on are exactly the winning-strategies for Maker playing first on .