Construction and investigation of Cram endgame databases

Abstract

In this paper we investigate the game of Cram, which is the impartial version of Domineering. We have built Cram endgame databases for all board sizes < 30 squares. We developed a program that fills the databases with their Combinatorial Game Theory (CGT) values. Since Cram is an impartial game, all CGT values for Cram positions are so-called nimbers, indicated by $\ast \mathit{n}$ . The nimber value of a position not only directly determines the game-theoretic value (first- or second-player win), but also provides an optimal playing strategy.

When analyzing the resulting databases we observed the following facts. Firstly we confirmed that the CGT values of all investigated empty boards are in agreement with results published in the literature. Since the value of an empty board depends completely on the values of many partially filled positions in the database, this is a strong indication that our process of filling the database with CGT values is correct. Secondly, although the series of values for $2\times \mathit{n}$ boards is completely regular, namely a value $\ast 0$ for n being even and $\ast 1$ for n being odd, this was not proven formally so far. We were able to provide such a proof.

We also investigated the databases for their contents. So far we encountered nimber values up to $\ast 11$ among single-fragment Cram positions. It appears that for a $\ast \mathit{n}$ value to occur a board size with $\approx 3\mathit{n}$ squares is needed, some more for very tall boards ( $1\times \mathit{n}$ ), some less for wider boards ( $4\times \mathit{n}$ ). So far no single-fragment Cram positions were encountered with nimber values $⩾\ast 12$ , although we show a construction of larger multi-fragment positions with nimber values from $\ast 12$ up to $\ast 15$ .

In a preliminary experiment we incorporated the CGT endgame databases constructed into a simple alpha-beta solver for the game. Results revealed a large improvement in solving power.