Solving 8×8 Domineering

✍ Scribed by D.M. Breuker; J.W.H.M. Uiterwijk; H.J. van den Herik

• Book ID: 104326755
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 174 KB
• Volume: 230
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00082-1

✦ Synopsis

So far the game of Domineering has mainly been investigated by combinatorial-games researchers. Yet, it is a genuine two-player zero-sum game with perfect information, of which the general formulation is a topic of AI research. In that domain, many techniques have been developed for two-person games, especially for chess. In this article we show that one such technique, i.e., transposition tables, is ÿt for solving standard Domineering (i.e., on an 8×8 board). The game turns out to be a win for the player ÿrst to move. This result coincides with a result obtained independently by Morita Kazuro. Moreover, the technique of transposition tables is also applied to di erently sized m × n boards, m ranging from 2 to 8, and n from m to 9. The results are given in tabular form. Finally, some conclusions on replacement schemes are drawn. In an appendix an analysis of four tournament games is provided.