Note: [1] Department of Knowledge Engineering (DKE), Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands. email:[email protected]
Abstract: This is Part 2 of three articles on the impact of safe moves on perfectly solving Domineering boards. In Part 1 (Uiterwijk, 2014b) we provided an exact analysis of 1-step safe moves obtainable in the very first phase of a Domineering game. In this part we show that, provided the board is wide or high enough, a player may obtain additional (multi-step) safe moves. Such multi-step safe moves can be divided into two categories. The first category contains safe moves resulting from making double-threats, of which only one can be prevented, the so-called 2-step safe moves. Their number depends on the exact dimensions of the board and on the counter strategy used by the opponent. The second category contains so-called x-step safe moves. We show that threatening to play extended double-destroying (xDD) moves possibly leads to an additional x-step safe move. Finally, we show how these two categories of multi-step safe moves should be combined with 1-step safe moves in order to achieve more accurate lower bounds for the number of safe moves obtainable by a player. We incorporated the findings of this extended analysis in our rules for perfectly solving Domineering boards. Using these enhanced rules, 35 more Domineering boards have been perfectly solved, 20 being a win for Vertical, 15 for Horizontal. Among the newly solved boards are 4 boards for which the game-theoretic values were not known so far, i.e., 6 × 19, 10 × 15, 14 × 15, and 18 × 15, all being a win for Vertical.
DOI: 10.3233/ICG-2014-37303
Journal: ICGA Journal, vol. 37, no. 3, pp. 144-160, 2014
