Domineering
Encyclopedia
Domineering is a mathematical game
played on a sheet of graph paper
, with any set of designs traced out. For example, it can be played on a 6×6 square, a checkerboard
, an entirely irregular polygon
, or any combination thereof. Two players have a collection of dominoes which they place on the grid in turn, covering up squares. One player, Left, plays tiles vertically, while the other, Right, plays horizontally.
As in most games in combinatorial game theory
, the first player who cannot move loses.
In this game, clearly, neither player can move. Since it is a second-player win, it is therefore a zero game
.
This game is a 2-by-1 grid. There is a convention of assigning the game a positive number when Left is winning and a negative one when Right is winning. In this case, Left has no moves, while Right can play a domino to cover the entire board, leaving nothing, which is clearly a zero game. Thus in surreal number
notation, this game is{| 0} = −1. This makes sense, as this grid is a 1-move advantage for Right.
This game is also{| 0} = −1, because a single box is unplayable.
This grid is the first case of a choice. Right could play the left two boxes, leaving −1. The rightmost boxes leave −1 as well. He could also play the middle two boxes, leaving two single boxes. This option leaves 0+0 = 0. Thus this game can be expressed as{| 0,−1}. This is −2. If this game is played in conjunction with other games, this is two free moves for Right.
This is a more complicated game. If Left goes first, either move leaves a 1×2 grid, which is +1. Right, on the other hand, can move to −1. Thus the surreal number
notation is {1|−1}. However, this is not a surreal number because 1 > −1. This is a Game but not a number. The notation for this is ±1, and it is a hot game
, because each player wants to move here.
This is a 2×3 grid, which is even more complex, but, just like any Domineering game, it can be broken down by looking at what the various moves for Left and Right are. Left can take the left column (or, equivalently, the right column) and move to ±1, but it is clearly a better idea to split the middle, leaving two separate games, each worth +1. Thus Left's best move is to +2. Right has four "different" moves, but they all leave the following shape in some rotation
:
This game is not a hot game (also called a cold game), because each move hurts the player making it, as we can see by examining the moves. Left can move to −1, Right can move to 0 or +1. Thus this game is {−1|0,1} = {−1|0} = −½.
Our 2×3 grid, then, is {2|−½}, which can also be represented by the mean value, ¾, together with the bonus for moving (the "temperature"), 1¼, thus:
held a Domineering tournament
, with a $500 prize for the winner. This game was played on an 8×8 board
, which proved sufficiently large to be interesting. The winner was mathematician Dan Calistrate, who defeated David Wolfe in the final. The tournament was detailed in Richard J. Nowakowski's Games of No Chance (p. 85).
Interestingly, Domineering is a first-player win for the 6x6, 7x7, 8x8, 9x9 and 10x10 square boards. The other known values for rectangular boards can be found on the site of Nathan Bullock.
version of Domineering. The only difference in the rules is that each player may place their dominoes in either orientation. It seems only a small variation in the rules, but it results in a completely different game, that can be analyzed with the Sprague–Grundy theorem
. This game is detailed in Cram (games)
.
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
played on a sheet of graph paper
Graph paper
Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting mathematical functions or experimental data and drawing diagrams. It is commonly found in mathematics and...
, with any set of designs traced out. For example, it can be played on a 6×6 square, a checkerboard
Checkerboard
A checkerboard or chequerboard is a board of chequered pattern on which English draughts is played. It is an 8×8 board and the 64 squares are of alternating dark and light color, often red and black....
, an entirely irregular polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
, or any combination thereof. Two players have a collection of dominoes which they place on the grid in turn, covering up squares. One player, Left, plays tiles vertically, while the other, Right, plays horizontally.
As in most games in combinatorial game theory
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
, the first player who cannot move loses.
Single box
Other than the empty game, where there is no grid, the simplest game is a single box.In this game, clearly, neither player can move. Since it is a second-player win, it is therefore a zero game
Zero game
In combinatorial game theory, the zero game is the game where neither player has any legal options. Therefore, the first player automatically loses, and it is a second-player win. The zero game has a Sprague–Grundy value of zero...
.
Horizontal rows
This game is a 2-by-1 grid. There is a convention of assigning the game a positive number when Left is winning and a negative one when Right is winning. In this case, Left has no moves, while Right can play a domino to cover the entire board, leaving nothing, which is clearly a zero game. Thus in surreal number
Surreal number
In mathematics, the surreal number system is an arithmetic continuum containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number...
notation, this game is
This game is also
This grid is the first case of a choice. Right could play the left two boxes, leaving −1. The rightmost boxes leave −1 as well. He could also play the middle two boxes, leaving two single boxes. This option leaves 0+0 = 0. Thus this game can be expressed as
Vertical rows
Vertical columns are evaluated in the same way. If there is a row of 2n or 2n+1 boxes, it counts as −n. A column of such size counts as +n.More complex grids
This is a more complicated game. If Left goes first, either move leaves a 1×2 grid, which is +1. Right, on the other hand, can move to −1. Thus the surreal number
Surreal number
In mathematics, the surreal number system is an arithmetic continuum containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number...
notation is {1|−1}. However, this is not a surreal number because 1 > −1. This is a Game but not a number. The notation for this is ±1, and it is a hot game
Hot game
In combinatorial game theory, a branch of mathematics, a hot game is one in which each player can improve their position by making the next move....
, because each player wants to move here.
This is a 2×3 grid, which is even more complex, but, just like any Domineering game, it can be broken down by looking at what the various moves for Left and Right are. Left can take the left column (or, equivalently, the right column) and move to ±1, but it is clearly a better idea to split the middle, leaving two separate games, each worth +1. Thus Left's best move is to +2. Right has four "different" moves, but they all leave the following shape in some rotation
Rotation
A rotation is a circular movement of an object around a center of rotation. A three-dimensional object rotates always around an imaginary line called a rotation axis. If the axis is within the body, and passes through its center of mass the body is said to rotate upon itself, or spin. A rotation...
:
This game is not a hot game (also called a cold game), because each move hurts the player making it, as we can see by examining the moves. Left can move to −1, Right can move to 0 or +1. Thus this game is {−1|0,1} = {−1|0} = −½.
Our 2×3 grid, then, is {2|−½}, which can also be represented by the mean value, ¾, together with the bonus for moving (the "temperature"), 1¼, thus:
High-level play
The Mathematical Sciences Research InstituteMathematical Sciences Research Institute
The Mathematical Sciences Research Institute , founded in 1982, is an independent nonprofit mathematical research institution whose funding sources include the National Science Foundation, foundations, corporations, and more than 90 universities and institutions...
held a Domineering tournament
Tournament
A tournament is a competition involving a relatively large number of competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses:...
, with a $500 prize for the winner. This game was played on an 8×8 board
Checkerboard
A checkerboard or chequerboard is a board of chequered pattern on which English draughts is played. It is an 8×8 board and the 64 squares are of alternating dark and light color, often red and black....
, which proved sufficiently large to be interesting. The winner was mathematician Dan Calistrate, who defeated David Wolfe in the final. The tournament was detailed in Richard J. Nowakowski's Games of No Chance (p. 85).
Winning strategy
An interesting problem about Domineering is to compute the winning strategy for large boards, and particularly square boards. In 2000, Dennis Breuker, Jos Uiterwijk and Jaap van den Herik computed and published the solution for the 8x8 board. The 9x9 board followed soon after some improvements of their program. Then, in 2002, Nathan Bullock solved the 10x10 board, as part of his thesis on Domineering.Interestingly, Domineering is a first-player win for the 6x6, 7x7, 8x8, 9x9 and 10x10 square boards. The other known values for rectangular boards can be found on the site of Nathan Bullock.
Cram
Cram is the impartialImpartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
version of Domineering. The only difference in the rules is that each player may place their dominoes in either orientation. It seems only a small variation in the rules, but it results in a completely different game, that can be analyzed with the Sprague–Grundy theorem
Sprague–Grundy theorem
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to...
. This game is detailed in Cram (games)
Cram (games)
Cram is a mathematical game played on a sheet of graph paper. It is the impartial version of Domineering and the only difference in the rules is that each player may place their dominoes in either orientation, but it results in a very different game...
.