The Impact of Safe Moves on Perfectly Solving Domineering Boards

Abstract

In this article we elaborate on the importance of safe moves for perfectly solving Domineering boards. Previously we have defined perfectly solving as “solving without any search”, i.e., finding a knowledge-based solution. We applied our method to the game of Domineering (cf. Uiterwijk, 2014). A test set of 841 Domineering games, consisting of all non-trivial boards with dimensions up to 30, was investigated. No less than 283 boards were perfectly solved.

For the 283 boards safe moves were essential for almost half of them, even though only a rough underestimate of the number of safe moves obtainable by a player was used. In the present article series, we analyse the nature of safe moves in detail. In this first part, we concentrate on safe moves a player is guaranteed to obtain in the first phase of the game, when a player only uses so-called safe-making (SM) moves. We call this 1-step safe moves.

Based on this analysis, we define a set of new rules for perfectly solving Domineering boards. Using these rules, 14 new Domineering boards have been perfectly solved, 5 being a win for Vertical, 9 for Horizontal. They include rather complex boards, among which 3 boards that were not solved before, i.e., 6 × 15, being a win for Vertical, and 11 × 14 and 11 × 18, both being a win for Horizontal.

In a follow-up article we will extend our analysis to more difficult ways of obtaining safe moves. We will show that this leads to many more new Domineering boards being perfectly solved.