DOMINEERING: SOLVING LARGE COMBINATORIAL SEARCH SPACES

Article type: Research Article

Authors: Bullock, Nathan^{; 1}

Affiliations: Edmonton, Alberta, Canada

Note: [1] Department of Computing Science, University of Alberta, Canada. Email: bullock@cs.ualbeila.ca

Abstract: Domineering, also known as crosscram, is a perfect-information, two-player game. We have created a search program which is able to prove who wins on many different sizes of boards. Some of the board sizes no one else has ever been able to solve. The main improvement is our evaluation function which can determine statically a winner at a shallower point in the search tree than was previously possible by other evaluation functions. It allows us to eliminate large portions of the search space. Along with a few other improvements, the evaluation function enabled us to solve board positions with just a fraction of the number of nodes which previous solvers needed.

DOI: 10.3233/ICG-2002-25202

Journal: ICGA Journal, vol. 25, no. 2, pp. 67-84, 2002