The Impact of Safe Moves on Perfectly Solving Domineering Boards

Abstract

This is the third and final article reporting on the impact of safe moves on perfectly solving Domineering boards. In the previous two articles (Uiterwijk, 2014b, 2014c) we gave an accurate analysis of obtainable safe moves in a Domineering game.

Based on the results derived from a test set of all Domineering boards with sizes up to 30, new patterns were observed, suggesting general theorems. We prove two such theorems, extending previous theorems (Uiterwijk, 2014a, Lachmann, Moore, and Rapaport, 2002) considerably.

The first theorem states that all 2k × n boards for n = 3, 5, 7, 9, and 11, and all 2k ×13 boards with k ≥ 3, are a win for Vertical. The second theorem states that all m × 2k boards for m = 5, 9, and 13, all m × 2k boards for m = 3 and 7 with k ≥ 2, and all 11 × 2k boards with k ≥ 6, are a win for Horizontal. Moreover, we formulate two conjectures, namely that all (4k + 2) × 15 boards and, more generally, that all (4k + 2) × (4l + 3) boards for l ≤ 6 are a win for Vertical.

From the results presented in the previous two articles in this series and from the theorems presented in this third article we may conclude that (1) the notion of safe moves is a key concept in playing Domineering at a high level and (2) their proper inclusion in our knowledge-based solver is pivotal for perfectly solving them.