Obsequi's Domineering Page
(Horizontal to play, horizontal wins.)
(Horizontal to play, horizontal wins.)
Domineering was introduced by Göran Andersson around 1973.
Domineering is a two player, perfect information game. The game is usually played on an nxm grid, although it can be played on any size or shape of grid, in which the two players take turns placing 2x1 tiles on the grid, one vertically and one horizontally. The first player who is unable to play loses.
The game of Domineering has previously been solved for a number of board sizes, including 9x9 domineering, by DOMI. DOMI is a program which was written by Breuker et al., to solve domineering on different sizes of boards. One of the main purposes of this program was to look at what affect different replacement schemes had on the affectiveness of transposition tables. Beside 9x9 domineering, DOMI also solved the game on a number of other board sizes, these results can be found here.
This information has then also been extended to larger board sizes by using the theoretical properties of this game, see here.
Obsequi is a program with a purpose very similar to DOMI, to solve the game of domineering on various sizes of boards. This program started as a course project and from there progressed into the subject of my Master's thesis.
This program uses a greatly superior evaluation function to what DOMI used and as a result needs to examine far fewer board positions in order to determine who will win on a a particular board. This also enables Obsequi to solve larger sizes of boards than what DOMI was able to solve.
Obsequi builds off the work done by the creators of DOMI. Some of the ideas which we have used from DOMI are in the areas of move ordering and the use of a transposition table.
Besides the ideas which we have borrowed from DOMI, we have also used a number of other enhancements to help reduce the branching factor, reduce the search depth, and to increase the chance of transpositions in Obsequi's search. Some of these enhancements are:
| Board Size | Result | Nodes |
| 4x19 | H | 314,148,901 |
| 4x21 | H | 3,390,074,758 |
| 6x14 | H | 1,864,870,370 |
| 8x10 | H | 4,125,516,739 |
| 10x10 | 1 | 3,541,685,253,370 |
Updated game theoretical values for various board sizes is here.
Here is a presentation I gave describing the research I did for my thesis.
Also, here is my thesis and the obsequi.tgz for Obsequi.
| Email me at nathan_kent_bullock -at- yahoo -dot- ca. | Last Updated: June 2002 |