Domineering (also called Stop-Gate or Crosscram) is a
mathematical game
A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...
that can be played on any collection of squares on a sheet of
graph paper
Graph paper, coordinate paper, grid paper, or squared paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting graphs of functions or experimental data and drawing curves. I ...
. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular
polyomino
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
Polyominoes have been used in pop ...
, or a combination of any number of such components. Two players have a collection of
domino
Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...
es which they place on the grid in turn, covering up squares. One player places tiles vertically, while the other places them horizontally. (Traditionally, these players are called "Left" and "Right", respectively, or "V" and "H". Both conventions are used in this article.)
As in
most
Most or Möst or ''variation'', may refer to:
Places
* Most, Kardzhali Province, a village in Bulgaria
* Most (city), a city in the Czech Republic
** Most District, a district surrounding the city
** Most Basin, a lowland named after the city
** A ...
games in
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
, the first player who cannot move loses.
Domineering is a
partisan game In combinatorial game theory, a game is partisan (sometimes partizan) if it is not impartial. That is, some moves are available to one player and not to the other.
Most games are partisan. For example, in chess, only one player can move the white ...
, in that players use different pieces: the
impartial
Impartiality (also called evenhandedness or fair-mindedness) is a principle of justice holding that decisions should be based on objective criteria, rather than on the basis of bias, prejudice, or preferring the benefit to one person over another ...
version of the game is
Cram
Cram may refer to:
* Cram (surname), a surname, and list of notable persons having the surname
* Cram.com, a website for creating and sharing flashcards
* Cram (Australian game show), a television show
* ''Cram'' (game show), a TV game show that ...
.
Basic examples
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
In combinatorial game theory, the zero game is the game where neither player has any legal options. Therefore, under the normal play convention, the first player automatically loses, and it is a second-player win. The zero game has a Sprague–G ...
.
Horizontal rows
This game is a 2-by-1 grid. There is a convention of assigning the game a
positive number
In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
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
In mathematics, the surreal number system is a totally ordered proper class containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number. The surreals ...
notation, this game is
= −1. This makes sense, as this grid is a 1-move advantage for Right.
This game is also = −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 . This is −2. If this game is played in conjunction with other games, this is two free moves for Right.
Vertical rows
Vertical columns are evaluated in the same way. If there is a row of 2''n'' or 2''n''+1 boxes, it counts as −''n''. A column of such size counts as +''n''.
More complex grids
This is a more complex 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
In mathematics, the surreal number system is a totally ordered proper class containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number. The surreals ...
notation is . 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
Rotation, or spin, is the circular movement of an object around a '' central axis''. A two-dimensional rotating object has only one possible central axis and can rotate in either a clockwise or counterclockwise direction. A three-dimensional ...
:
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 = = −½.
Our 2×3 grid, then, is , 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 Institute
The Simons Laufer Mathematical Sciences Institute (SLMath), formerly the Mathematical Sciences Research Institute (MSRI), is an independent nonprofit mathematical research institution on the University of California campus in Berkeley, Califo ...
held a Domineering tournament
A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses:
# One or more competitions held at a single venue and concentr ...
, with a $500 prize for the winner. This game was played on an 8×8 board. 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
A 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
Hendrik Jacob (Jaap) van den Herik (born 8 October 1947 in Rotterdam) is a Dutch computer scientist, and professor at the University of Leiden, known for his contribution in the fields of computer chess and artificial intelligence.
Biography
...
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. The 11x11 board has been solved by Jos Uiterwijk in 2016.
Domineering is a first-player win for the 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10, and 11x11 square boards, and a second-player win for the 1x1 and 5x5 boards. Some other known values for rectangular boards can be found on the site of Nathan Bullock.[Nathan Bullock'site ]
Updated Game Theoretic Values for Domineering Boards
/ref>
Cram
Cram is the impartial
Impartiality (also called evenhandedness or fair-mindedness) is a principle of justice holding that decisions should be based on objective criteria, rather than on the basis of bias, prejudice, or preferring the benefit to one person over another ...
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
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...
.
See also
* Blockbusting (game) A combinatorial game whose analysis has been applied to Domineering.
References
*
*
*
External links
* {{bgg, 7450, Stop-gate
Playable version at Pencil and Paper Games
Abstract strategy games
Mathematical games
Combinatorial game theory
Paper-and-pencil games