View source for Domineering

{{Short description|Mathematical game}}
{{about|the pen-and-paper-game|the concept of domination|Domination (disambiguation)}}
{{redirects|Stop-Gate|the waterway feature|floodgate}}
{{Infobox game
|title=Domineering
|image=Domineering5x5.svg
|caption=Sample game of Domineering played on a 5x5 board, with the horizontal player ("H" or "Right") making the first move, and losing in the 13th round of play.
|players=2
|setup_time=
|random_chance=none
|skills=[[strategy]]
|playing_time=
|genre=[[tile-based game]]
}}

'''Domineering''' (also called '''Stop-Gate''' or '''Crosscram''') is a [[mathematical game]] that can be played on any collection of squares on a sheet of [[graph paper]]. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular [[polyomino]], or a combination of any number of such components. Two players have a collection of [[domino]]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 [[Normal play convention|most]] games in [[combinatorial game theory]], the first player who cannot move loses.

Domineering is a [[partisan game]], in that players use different pieces: the [[impartial game|impartial]] version of the game is [[Cram (game)|Cram]].

==Basic examples==

===Single box===
Other than the empty game, where there is no grid, the simplest game is a single box.

[[Image:20x20square.png]]

In this game, clearly, neither player can move. Since it is a second-player win, it is therefore a [[zero game]].

===Horizontal rows===
[[Image:20x20square.png]][[Image:20x20square.png]]

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 number|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 <nowiki>{|</nowiki>0} = −1. This makes sense, as this grid is a 1-move advantage for Right.

[[Image:20x20square.png]][[Image:20x20square.png]][[Image:20x20square.png]]

This game is also <nowiki>{|</nowiki>0} = −1, because a single box is unplayable.

[[Image:20x20square.png]][[Image:20x20square.png]][[Image:20x20square.png]][[Image:20x20square.png]]

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 <nowiki>{|</nowiki>0,−1}. 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===
[[Image:20x20square.png]][[Image:20x20square.png]]<br>
[[Image:20x20square.png]][[Image:20x20square.png]]

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

[[Image:20x20square.png]][[Image:20x20square.png]][[Image:20x20square.png]]<br>
[[Image:20x20square.png]][[Image:20x20square.png]][[Image:20x20square.png]]

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]]:

[[Image:20x20square.png]][[Image:20x20square.png]][[Image:20x20square.png]]<br>
[[Image:20x20square.png]]

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} = −{{frac|1|2}}.

Our 2×3 grid, then, is {2|−{{frac|1|2}}}, which can also be represented by the mean value, {{frac|3|4}}, together with the bonus for moving (the "temperature"), {{frac|1|1|4}}, thus: <math>\textstyle\left\{2 \left| -\frac{1}{2}\right.\right\} = \frac{3}{4} \pm \frac{5}{4}</math>

==High-level play==

The [[Mathematical Sciences Research Institute]] held a Domineering [[tournament]] 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 (mathematician)|David Wolfe]] in the final.  The tournament was detailed in Richard J. Nowakowski's ''Games of No Chance'' (p.&nbsp;85).

==Winning strategy==

[[Image:Domineering-4x4-game-tree.svg|thumb|Depiction of the [[game tree]] for a game of Domineering played over a 4x4 board, with the horizontal player ("H") starting and two moves already played.  The tree has been pruned with [[alpha-beta pruning]], and [[minimax]] values are included indicating that H has a winning strategy from the root.]]

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]] computed and published the solution for the 8x8 board.<ref>{{Cite journal|title = Solving 8×8 Domineering|journal = Theoretical Computer Science|date = 2000-01-06|pages = 195–206|volume = 230|issue = 1–2|doi = 10.1016/S0304-3975(99)00082-1|first = D. M.|last = Breuker|first2 = J. W. H. M.|last2 = Uiterwijk|first3 = H. J.|last3 = van den Herik|doi-access = free}}</ref> 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.<ref>Nathan Bullock [http://webdocs.cs.ualberta.ca/~games/domineering/thesis.ps Domineering:Solving Large Combinatorial Search Spaces] M.Sc. thesis, 2002</ref> The 11x11 board has been solved by Jos Uiterwijk in 2016.<ref>{{Cite conference|title = 11x11 Domineering Is Solved: The First Player Wins.|conference = Computers and Games 2016|pages = 129–136|doi = 10.1007/978-3-319-50935-8_12|first = J. W. H.|last = Uiterwijk}}</ref>

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.<ref>{{Cite web|author=Nathan Bullock|title=Updated Game Theoretic Values for Domineering Boards|url=http://webdocs.cs.ualberta.ca/~games/domineering/updated.html|access-date=2023-02-16|website=webdocs.cs.ualberta.ca}}</ref>

==Cram==
{{Further|Cram (game)}}
'''Cram''' is the [[impartial game|impartial]] 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]].

== See also ==
* [[Blockbusting (game)]] A combinatorial game whose analysis has been applied to Domineering.

== References ==
<references />
* {{cite book | first=Michael H. | last=Albert      | authorlink= Michael H. Albert
             | first2=Richard J. | last2=Nowakowski
             | first3=David      | last3=Wolfe      | author3-link= David Wolfe (mathematician)
  | title=Lessons in Play: An Introduction to Combinatorial Game Theory | publisher=A K Peters, Ltd.
  | year=2007 | isbn= 978-1-56881-277-9
  }}
* {{cite book | first=Elwyn R.   | last=Berlekamp | authorlink=Elwyn Berlekamp
             | first2=John H.    | last2=Conway   | author2-link=John Horton Conway
             | first3=Richard K. | last3=Guy      | author3-link=Richard K. Guy
  | title=Winning Ways for Your Mathematical Plays 
  | publisher=A K Peters, Ltd. | year=2003 | isbn=978-0-12-091150-9 
  | title-link=Winning Ways for Your Mathematical Plays }}
* {{cite journal | first=Martin | last=Gardner |authorlink=Martin Gardner | title=Mathematical Games: Cram, crosscram and quadraphage: new games having elusive winning strategies
  | journal=Scientific American | volume=230 | issue=2 | year=1974 | pages=106–108
  | doi=10.1038/scientificamerican0374-102 }}

== External links ==
* {{bgg|7450|Stop-gate}}
* [http://www.papg.com/show?1TX6 Playable version at Pencil and Paper Games]

[[Category:Abstract strategy games]]
[[Category:Mathematical games]]
[[Category:Combinatorial game theory]]
[[Category:Paper-and-pencil games]]