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 $* 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 n$ boards is completely regular, namely a value $* 0$ for n being even and $* 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 $* 11$ among single-fragment Cram positions. It appears that for a $* n$ value to occur a board size with $\approx 3 n$ squares is needed, some more for very tall boards ( $1 \times n$ ), some less for wider boards ( $4 \times n$ ). So far no single-fragment Cram positions were encountered with nimber values $⩾ * 12$ , although we show a construction of larger multi-fragment positions with nimber values from $* 12$ up to $* 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.

1. Introduction

Cram is a variant of Domineering, which is a two-player perfect-information game invented by Göran Andersson around 1973. Both games were popularized to the general public in an article by Martin Gardner (1974) (where Domineering was called CrossCram). Both games can be played on any subset of a square lattice, though mostly they are restricted to rectangular $m \times n$ boards, where m denotes the number of rows and n the number of columns.

Play consists of the two players alternately placing a $1 \times 2$ tile (domino) on the board. For Domineering the first player may place the tile only in a vertical alignment, the second player only horizontally; for Cram there is no such restriction: each player may place a tile vertically or horizontally. The first player being unable to move loses the game, his opponent (who made the last move) being declared the winner. Since the board is gradually filled, i.e., Domineering and Cram are converging games, the games always end, and ties are impossible. With these rules the games belong to the category of combinatorial games, for which a whole theory, the Combinatorial Game Theory (CGT) has been developed (Albert et al. (2007); Berlekamp (1988); Berlekamp et al. (1982); Conway (1976)).

Among combinatorial game theorists Domineering received quite some attention, but this was limited to rather small or irregular boards (Albert et al. (2007); Berlekamp (1988); Berlekamp et al. (1982); Conway (1976); Kim (1996); Wolfe (1993)). Larger (rectangular) boards were solved using α-β search, leading to solving all boards up to the standard $8 \times 8$ board (Breuker et al. (2000)), later extended to the $9 \times 9$ board (van den Herik et al. (2002); Uiterwijk and van den Herik (2000)), and to larger boards up to $10 \times 10$ (Bullock (2002a; 2002b)), and finally we recently reported the solutions of several larger boards including the $11 \times 11$ board (Uiterwijk (2016a)).

The only difference between Domineering and Cram is that in the latter both players are allowed to place a domino both horizontally and vertically, i.e., in any position both players have the same possible moves. By this fact Cram belongs to the category of impartial games (Albert et al. (2007); Berlekamp et al. (1982); Conway (1976)).

Cram received not that much attention as Domineering in scientific research. $1 \times n$ Cram, also called Linear Cram, was proposed as early as 1934 by Dawson and completely solved by Guy and Smith in 1956 (Guy and Smith (1956)). The sequence of values of the game (which is called $\cdot$ 07 by them) is quite irregular, but turns out to be periodic from $n = 53$ onwards, with a period of 34. Cram was further described in several sources on Combinatorial Game Theory (Albert et al. (2007); Berlekamp et al. (1982); Conway (1976)), where many values were given, but mainly for small boards. For the $2 \times n$ boards it was stated (Berlekamp et al. (1982)) that all even-width boards have value 0 and all odd-width boards value $* 1$ , though no formal proof was given. The first systematic investigation of larger Cram boards was the 2009 master thesis by Martin Schneider (2009). It reported the solution of $3 \times n$ boards up to $n = 9$ , and the $4 \times 5$ , $5 \times 5$ and $5 \times 7$ boards. More recently Lemoine and Viennot (2012) extended this to $3 \times n$ boards up to $n = 18$ , $4 \times n$ boards up to $n = 9$ , and $5 \times n$ boards up to $n = 8$ . A few later results ( $3 \times 19$ , $3 \times 20$ , $5 \times 9$ , $6 \times 7$ , and $7 \times 7$ ) were published on their website (Lemoine and Viennot (2018)). No CGT endgame databases for Cram have been constructed so far.

2. Combinatorial game theory for Cram

For combinatorial games a whole theory has recently been developed, the Combinatorial Game Theory (CGT in short) (Albert et al. (2007); Berlekamp (1988); Berlekamp et al. (1982); Conway (1976)). According to this theory the main distinction in combinatorial games is in partizan games and impartial games. In partizan games both players have their own moves, for which the types and CGT values may vary wildly. Domineering belongs to this category, and a survey on different (types of) values occurring in Domineering positions was given in Uiterwijk and Barton (2015). For impartial games the Sprague–Grundy Theorem (Sprague (1935); Grundy (1939)) states that any position is equivalent to some Nim pile and the value of that position is then always a nimber $* n$ , where n is the size of the equivalent Nim pile.

2.1. Nimbers

Nimbers are a special type of CGT values commonly occuring in impartial games. Their main characteristics are that the options (moves) of the first player (in CGT denoted by Left) and the second player (Right) are identical, following a certain schema, and that they are their own negatives. While nimbers may theoretically occur in Domineering, which is not an impartial game, the only frequent representatives of this group are the endgame $* 0$ and the star $* 1$ . In game notation the endgame looks as $G = {|} = * 0 = 0$ (in fact the value of the endgame is the only CGT value being a nimber and a number at the same time), and denotes a terminal position where neither player has a possible move. Therefore the endgame is a loss for the player to move. A star looks as $G = {0 | 0} = * 1 = *$ and is a win for the player to move. Fig. 1 shows a $* 1$ position in Domineering.

The next nimber, $* 2$ , is defined as $* 2 = {0, * | 0, *}$ , and in general a nimber $* n$ is defined as $* n = {0, *, ..., * (n - 1) | 0, *, ..., * (n - 1)}$ . Clearly, the first player to move in a nimber game with value $* n$ with $n \neq 0$ wins by moving to 0. This introduces an interesting property of nimbers: every nimber is its own negative, i.e., $* n = - * n$ . As a consequence, when two identical nimbers occur, they cancel each other: $* n + * n = 0$ , where n is any integer ⩾ 0.

Fig. 1.

A Domineering $* 1$ position and its Left and Right options.

Although the nimber $* 1$ abunds in the partizan game of Domineering, positions with higher nimber values are really rare there. However, the assumption by Drummond-Cole (2005) that none would exist in “regular” Domineering positions (i.e., reachable by legal play from empty rectangular boards) is recently refuted by the discovery of several regular $* 2$ and $* 3$ Domineering positions (Uiterwijk and Barton (2015)), as illustrated in Fig. 2.

Using such $* 2$ and $* 3$ fragments it is easy to “construct” many other interesting Domineering positions with $* 2$ and $* 3$ values (Uiterwijk (2016b)). So far, no Domineering positions with nimber values of $* 4$ or higher have been discovered.

Fig. 2.

Two Domineering positions with the game-theoretical values $* 2$ (left) and $* 3$ (right).

Since in Cram both players have the same options in any position, it is obvious that nimbers will abund. In fact, since Cram is an impartial game, all Cram positions have a nimber as CGT value. By definition, the value of an arbitrary Cram position is obtained as the mex function applied to the followers of the position. The followers (or children) of a position are the positions reachable in one move from that position. This is a recursive definition, but since this series converges (every child of a position has two less empty squares) to positions in which no more moves are possible (hence with value $* 0$ ), the values of Cram positions are well-defined. The mex function (minimal excludant) is defined as the smallest nimber not among the followers. E.g., if a position has children with values $* 0$ , $* 1$ , $* 2$ , and $* 4$ , its value is $* 3$ .

2.2. Disjunctive sums of subgames

According to the Sprague–Grundy Theorem a Cram position with value $* n$ is equivalent to a single heap of n tokens in the game of Nim. Therefore, the Combinatorial Game Theory for Nim can be applied to (sums of) Cram positions. As a consequence, if a position is decomposed into several disjoint subgames, the CGT value of the whole position is the Nim sum of the CGT values of the components. This Nim-addition rule was already discovered in 1902 by Bouton in analyzing the game of Nim (Bouton (1902)). In particular, if two Cram fragments have nimber values $* m$ and $* n$ , their sum is given by the Nim-addition $* m \oplus * n$ , where ⊕ is the exclusive-or operator applied to the binary representations of m and n.

2.3. Cram strategies

For empty rectangular positions in Cram it is easy to give some general observations regarding the CGT values. These were already given by Gardner (1974).

Theorem 1.
Every even × even empty Cram board is a second-player win.
Proof.
The second-player’s strategy to reach this is easy: after every first-player’s move the second player responds by playing the symmetrical move (with respect to the centre of the board), ensuring that he/she will make the last move and win the game. Consequently, even × even empty boards have value $* 0$ . □
Theorem 2.
Every even × odd empty Cram board is a first-player win.
Proof.
The winning strategy of the first player is by occupying with the first move the two central squares, after which he/she plays according to the strategy above (pretending to be the second player from now on), securing the win. Consequently, even × odd (and odd × even) empty boards have value $* n$ with $n ⩾ 1$ . □
Regarding odd × odd empty boards both theorems give no clue about their values, and no other optimal strategy is known, so they can be either first-player wins (with any positive nimber value) or second-player wins (with value $* 0$ ).
3. Cram CGT databases

In this section we first give a short overview how the databases have been constructed. Then we discuss the way how the databases were filled with CGT values.

3.1. Construction of the databases

We have constructed the databases in a straightforward way. Each database is associated with a rectangular board. Since each square of the board can in principle be empty or filled, it means that for an $m \times n$ database there are $2^{m \times n}$ fillings and each entry can simply be represented as a binary string of size $m \times n$ .

It is difficult to determine which entries represent legal Cram positions (i.e., can be reached by legal moves on an empty board), except for the $1 \times n$ positions. This stems mainly from the fact that the positions may be generated as subgames on larger boards. Therefore we have decided to not distinguish the entries whether they represent legal or illegal Cram positions, which makes the process of filling the database much easier.

Due to the fact that every entry represents a Cram position, legal or not, the CGT value is always a nimber. These are stored as their integer counterparts. In practice CGT values never will exceed $* 255$ , so that 1-byte entries can be used. Consequently, the size of an $m \times n$ database will be $2^{m \times n}$ bytes.

3.2. Filling the databases

Since we opted for not distinguishing between legal and illegal positions, the filling of the database is quite straightforward. We use the method of retrograde analysis (Thompson (1986)).

We first mark all entries as being empty. We then loop through all entries, creating for each empty entry the associated position. Next we generate the legal moves in that position. If there are none it means it is an endgame position and we fill the entry with value 0. If there is only 1 legal move, its follower must be an endgame position with value 0, so the current position has value $* 1$ . If there are more legal moves, all are investigated, by generating all children. For each child we then check in the database if its value is already stored. If all children have values, we calculate the value of the parent as the mex of the children values and store it. If on the other hand, at least one child has no value yet, we skip this entry and continue with the next one in the table. When all entries have been examined (we call this an iteration), we start all over again. This process is continued until no more new values can be calculated, what will happen necessarily as soon as all entries in the database are filled.

4. Results

In this section we give experimental details on generation of and values in the databases. Next, we investigate trends in the values and prove the validity of one such pattern as a theorem.

4.1. Values

Thus far the following complete CGT databases have been created: $1 \times n$ for $n = 1 – 29$ , $2 \times n$ for $n = 2 – 14$ , $3 \times n$ for $n = 3 – 9$ , $4 \times n$ for $n = 4 – 7$ , and $5 \times 5$ . Results are given in Tables 1–3. In these tables the first column gives the size of the database, the second column the CGT value of the corresponding empty Cram board, the third column the number of iterations needed to fill the database, and the last column the maximum nimber value occurring in the database.

An overview of some frequencies of nimbers occurring in the databases is given in Table 4. We selected some small databases (of size 12), some medium databases (size 24), and the largest $m \times n$ databases for each $m ⩽ 4$ .

Table 1
Details for the $1 \times n$ CGT databases for Cram

Size nimber value # of iterations max nimber

$1 \times 1$ ∗0 1 ∗0

$1 \times 2$ ∗1 1 ∗1

$1 \times 3$ ∗1 2 ∗1

$1 \times 4$ ∗2 2 ∗2

$1 \times 5$ ∗0 3 ∗2

$1 \times 6$ ∗3 3 ∗3

$1 \times 7$ ∗1 4 ∗3

$1 \times 8$ ∗1 4 ∗3

$1 \times 9$ ∗0 5 ∗3

$1 \times 10$ ∗3 5 ∗3

$1 \times 11$ ∗3 6 ∗3

$1 \times 12$ ∗2 6 ∗3

$1 \times 13$ ∗2 7 ∗3

$1 \times 14$ ∗4 7 ∗4

$1 \times 15$ ∗0 8 ∗4

$1 \times 16$ ∗5 8 ∗5

$1 \times 17$ ∗2 9 ∗5

$1 \times 18$ ∗2 9 ∗5

$1 \times 19$ ∗3 10 ∗6

$1 \times 20$ ∗3 10 ∗6

$1 \times 21$ ∗0 11 ∗7

$1 \times 22$ ∗1 11 ∗7

$1 \times 23$ ∗1 12 ∗7

$1 \times 24$ ∗3 12 ∗7

$1 \times 25$ ∗0 13 ∗7

$1 \times 26$ ∗2 13 ∗7

$1 \times 27$ ∗1 14 ∗7

$1 \times 28$ ∗1 14 ∗7

$1 \times 29$ ∗0 15 ∗7

Size	nimber value	# of iterations	max nimber
$1 \times 1$	∗0	1	∗0
$1 \times 2$	∗1	1	∗1
$1 \times 3$	∗1	2	∗1
$1 \times 4$	∗2	2	∗2
$1 \times 5$	∗0	3	∗2
$1 \times 6$	∗3	3	∗3
$1 \times 7$	∗1	4	∗3
$1 \times 8$	∗1	4	∗3
$1 \times 9$	∗0	5	∗3
$1 \times 10$	∗3	5	∗3
$1 \times 11$	∗3	6	∗3
$1 \times 12$	∗2	6	∗3
$1 \times 13$	∗2	7	∗3
$1 \times 14$	∗4	7	∗4
$1 \times 15$	∗0	8	∗4
$1 \times 16$	∗5	8	∗5
$1 \times 17$	∗2	9	∗5
$1 \times 18$	∗2	9	∗5
$1 \times 19$	∗3	10	∗6
$1 \times 20$	∗3	10	∗6
$1 \times 21$	∗0	11	∗7
$1 \times 22$	∗1	11	∗7
$1 \times 23$	∗1	12	∗7
$1 \times 24$	∗3	12	∗7
$1 \times 25$	∗0	13	∗7
$1 \times 26$	∗2	13	∗7
$1 \times 27$	∗1	14	∗7
$1 \times 28$	∗1	14	∗7
$1 \times 29$	∗0	15	∗7

Table 2

Details for the $2 \times n$ CGT databases for Cram

Size	nimber value	# of iterations	max nimber
$2 \times 2$	∗0	2	∗1
$2 \times 3$	∗1	3	∗2
$2 \times 4$	∗0	4	∗3
$2 \times 5$	∗1	5	∗3
$2 \times 6$	∗0	6	∗3
$2 \times 7$	∗1	7	∗4
$2 \times 8$	∗0	8	∗5
$2 \times 9$	∗1	9	∗7
$2 \times 10$	∗0	10	∗7
$2 \times 11$	∗1	11	∗8
$2 \times 12$	∗0	12	∗9
$2 \times 13$	∗1	13	∗10
$2 \times 14$	∗0	14	∗11

Table 3

Details for the $m \times n$ CGT databases for Cram, with m and $n ⩾ 3$

Size	nimber value	# of iterations	max nimber
$3 \times 3$	∗0	5	∗3
$3 \times 4$	∗1	6	∗4
$3 \times 5$	∗1	8	∗5
$3 \times 6$	∗4	9	∗7
$3 \times 7$	∗1	11	∗8
$3 \times 8$	∗3	12	∗9
$3 \times 9$	∗1	14	∗11
$4 \times 4$	∗0	8	∗6
$4 \times 5$	∗2	10	∗8
$4 \times 6$	∗0	12	∗9
$4 \times 7$	∗3	14	∗11
$5 \times 5$	∗0	13	∗9

Table 4

Frequencies of nimbers (in percentages) occurring in some $m \times n$ CGT databases for Cram

Size	∗0	∗1	∗2	∗3	∗4	∗5	∗6	∗7	∗8	∗9	∗10	∗11
$1 \times 12$	40.3	40.3	9.40	9.99	–	–	–	–	–	–	–	–
$2 \times 6$	38.7	39.5	10.5	11.3	–	–	–	–	–	–	–	–
$3 \times 4$	36.0	37.7	13.1	13.2	0.0488	–	–	–	–	–	–	–
$1 \times 24$	33.5	33.5	16.5	16.5	0.0106	0.0109	0.00143	0.00117	–	–	–	–
$2 \times 12$	31.3	31.3	18.4	18.3	0.322	0.323	0.0458	0.0252	0.00105	0.000191	–	–
$3 \times 8$	28.4	28.5	20.4	20.4	1.04	0.987	0.203	0.123	0.00838	0.000787	–	–
$4 \times 6$	27.6	27.6	20.7	20.8	1.40	1.33	0.297	0.163	0.0140	0.000739	–	–
$1 \times 29$	31.7	31.7	18.3	18.3	0.0137	0.0136	0.00311	0.00318	–	–	–	–
$2 \times 14$	29.8	29.8	19.8	19.8	0.389	0.396	0.0842	0.0788	0.00208	0.00113	0.0000671	0.00000745
$3 \times 9$	27.3	27.4	21.2	21.2	1.19	1.18	0.294	0.256	0.0191	0.00579	0.000292	0.00000894
$4 \times 7$	26.0	26.0	21.8	21.7	1.75	1.73	0.475	0.420	0.0442	0.0146	0.000970	0.0000462

An evident observation is that existence and frequencies of larger nimbers grow with database size, roughly needing $3 n$ squares for nimbers $* n$ to occur. Secondly we observe that these numbers also depend on the width/height ratio of the boards, being smaller for taller boards and larger for wider boards.

4.2. Patterns in CGT values for Cram

It is obvious that for $2 \times n$ boards Cram exhibits a strict pattern, with value $* 0$ for 2 × even boards and $* 1$ for 2 × odd boards. The values $* 0$ for all 2 × even boards were already explained in Section 2.3 by Theorem 1. For the 2 × odd boards we know from Theorem 2 that the first player wins, hence that the CGT values are nimbers $* n$ with $n ⩾ 1$ , but so far no proof has been published to our knowledge why all these values are exactly $* 1$ . To fill this gap we here provide a proof by induction.

Theorem 3.
Every $2 \times n$ empty Cram board with odd n has CGT value $* 1$ .
Proof.
Base case: the theorem holds for $n = 1$ , since in the $2 \times 1$ board there is only one option, leading to the endgame, so its value is $* 1$ .

Induction hypothesis: Assume that all $2 \times x$ boards for odd $x ⩽ n$ have value $* 1$ .

Induction step: Prove that the $2 \times (n + 2)$ board also has value $* 1$ .

For this proof we distinguish between vertical moves and horizontal moves in the $2 \times (n + 2)$ board. For brevity we indicate a position after a vertical move as a “vertical child”, and likewise for “horizontal” children.

For any vertical child it holds that the move splits the board in two separate smaller boards, one with size $2 \times n_{1}$ and one with size $2 \times n_{2}$ , with $n_{1} ⩾ 0$ and $n_{2} ⩾ 0$ , and $n_{1} + n_{2} = (n + 1)$ .1
¹
If $n_{1}$ or $n_{2} = 0$ , then we just consider this board as having zero width, on which no moves are possible, hence with value $* 0$ .

Since n is odd it follows that $n_{1} + n_{2} =$ even, hence either both $n_{1}$ and $n_{2}$ are even or both are odd (see Fig. 3 as an example for $n = 5$ ). In case both $n_{1}$ and $n_{2}$ are even, both have value $* 0$ (Theorem 1) and their Nim sum is $* 0$ as well. In case both $n_{1}$ and $n_{2}$ are odd with $n_{1}, n_{2} < (n + 2)$ , so $n_{1}, n_{2} ⩽ n$ , they both have value $* 1$ according to the induction hypothesis, hence their Nim sum is $* 0$ as well. Concludingly, all vertical children of the $2 \times (n + 2)$ position have value $* 0$ .

Next we consider the horizontal children. So suppose that for the $2 \times (n + 2)$ position the first player made an arbitrary horizontal move. Then one of the options of the next player is to play the horizontal move exactly below or above the first move (see Fig. 4). This results in removing two adjacent columns in the board, leading to two separate smaller boards, one with size $2 \times n_{1}$ and one with size $2 \times n_{2}$ , with $n_{1} ⩾ 0$ and $n_{2} ⩾ 0$ , and $n_{1} + n_{2} = n$ . Since n is odd it follows that $n_{1} + n_{2} =$ odd as well, hence one of $n_{1}$ and $n_{2}$ is odd and the other is even. Assuming arbitrarily that $n_{1}$ is even and $n_{2}$ is odd with $n_{2} ⩽ n$ , the $2 \times n_{1}$ board has value $* 0$ (by Theorem 1) and the $2 \times n_{2}$ board has value $* 1$ (according to the induction hypothesis), and consequently their Nim sum is $* 1$ . This means that each horizontal child has a child with value $* 1$ , and hence each horizontal child has itself a value different from $* 1$ (the mex of the followers). Concludingly, all horizontal children have values different from $* 1$ .
Fig. 3.
All asymmetric vertical children of the $2 \times 5$ board.

Since all vertical children have value $* 0$ and all horizontal children have values $\neq * 1$ , it follows that the $2 \times (n + 2)$ board for odd n has value $* 1$ . □
Fig. 4.
The two asymmetric horizontal children of the $2 \times 5$ board plus one selected follower of each.

Although we scrutinized occurring CGT values in Cram positions for other trends, no such pattern has been found so far.
4.3. Interesting Cram positions

The nimber values found for the empty boards were in the previous tables. The maximum nimber is $* 5$ for the $1 \times 16$ board. Moreover, the maximum nimber found over all positions in the databases is $* 11$ , found in several boards, namely $2 \times 14$ , $3 \times 9$ , and $4 \times 7$ . Figure 5 shows for all nimbers $⩾ * 8$ some position on an $m \times n$ board, for $m = 2 – 5$ .

All these positions are single-fragment positions. This means that the value given for such a position is a “genuine” value, and not the Nim-sum of smaller fragments. Of course it is easy to “construct” positions with larger nimbers that can be obtained as the Nim-sum of smaller fragments. This means that positions with values $* 12$ – $* 15$ can easily be constructed. To show this we start with a $* 4$ position on the $3 \times 4$ board (see Fig. 6). Using this we can build $* 12$ – $* 15$ positions on $3 \times n$ boards for appropriate n by gluing together the $* 8$ – $* 11$ positions on $3 \times n$ boards from Fig. 5 with the $* 4$ position from Fig. 6 separated by a single occupied column, as demonstrated in Fig. 7.

Fig. 5.

Some single-fragment Cram positions with values $* n$ with $n ⩾ 8$ .

Fig. 6.

A $* 4$ Cram position at the $3 \times 4$ board.

Fig. 7.

Cram positions with values $* 12$ – $* 15$ as sums of positions with values $* 8$ – $* 11$ with a position with value $* 4$ .

5. Preliminary experimental results

In order to test the effect of using the Cram CGT endgame databases on solving power, a simple alpha-beta solver was built by Lando Kroes (2018), then a master student at our laboratory. His program uses transposition tables including recognition of symmetrical positions. No move ordering is incorporated yet. The most important feature is recognition of positions consisting of multiple fragments fitting within one of the available databases. He used the databases described in Section 3, except the $3 \times 9$ , $4 \times 6$ , $4 \times 7$ , and $5 \times 5$ databases, due to program limitations. His test set consisted of 37 empty Cram boards, that were investigated both without (if feasible in a short time) and with the database support. The experiments were run on a standard laptop computer. The results are given in Table 5.

In this table the first column shows the board investigated. The second column gives the winner, with “1” denoting a first-player win and “2” a second-player win. In all cases the winner is in accordance with results from the literature (Schneider (2009); Lemoine and Viennot (2012)). The next two columns give the number of nodes and time required to solve the board without using CGT endgame databases, with a “–” denoting that the board was not solved. The last two columns give the data when CGT endgame databases are used.

Table 5
Experimental results for solving empty Cram boards, without and with using CGT databases

Size Winner Without database support With database support

Nodes Runtime (sec) Nodes Runtime (sec)

$2 \times 2$ 2 3 0 1 0

$2 \times 3$ 1 7 0 1 0

$2 \times 4$ 2 22 0 1 0

$2 \times 5$ 1 52 0 1 0

$2 \times 6$ 2 135 0 1 0

$2 \times 7$ 1 350 0 1 0

$2 \times 8$ 2 1,204 0 1 0

$2 \times 9$ 1 2,478 0 1 0

$2 \times 10$ 2 8,199 0 1 0

$2 \times 11$ 1 17,199 1 1 0

$2 \times 12$ 2 69,372 5 1 0

$2 \times 13$ 1 118,281 10 1 0

$2 \times 14$ 2 508,789 51 1 0

$2 \times 15$ 1 867,676 96 26 0

$2 \times 16$ 2 – – 1,883 0

$2 \times 17$ 1 – – 21,205 4

$2 \times 18$ 2 – – 92,265 19

$2 \times 19$ 1 – – 329,564 70

$2 \times 20$ 2 – – 1,213,782 277

$2 \times 21$ 1 – – 4,080,640 916

$3 \times 3$ 2 44 0 1 0

$3 \times 4$ 1 219 0 1 0

$3 \times 5$ 1 986 0 1 0

$3 \times 6$ 1 4,975 0 1 0

$3 \times 7$ 1 24,259 1 1 0

$3 \times 8$ 1 78,074 5 1 0

$3 \times 9$ 1 568,196 52 33,169 5

$3 \times 10$ 1 3,236,859 374 241,744 43

$3 \times 11$ 2 – – 2,058,587 401

$4 \times 4$ 2 1,353 0 1 0

$4 \times 5$ 1 11,565 0 1 0

$4 \times 6$ 2 162,343 12 19,575 3

$4 \times 7$ 1 717,911 70 359,106 59

$4 \times 8$ 2 – – 5,969,869 1,104

$5 \times 5$ 2 173,853 13 30,760 5

$5 \times 6$ 1 4,556,619 539 2,073,064 396

Size	Winner	Without database support	With database support
$2 \times 2$	2	3	0	1	0
$2 \times 3$	1	7	0	1	0
$2 \times 4$	2	22	0	1	0
$2 \times 5$	1	52	0	1	0
$2 \times 6$	2	135	0	1	0
$2 \times 7$	1	350	0	1	0
$2 \times 8$	2	1,204	0	1	0
$2 \times 9$	1	2,478	0	1	0
$2 \times 10$	2	8,199	0	1	0
$2 \times 11$	1	17,199	1	1	0
$2 \times 12$	2	69,372	5	1	0
$2 \times 13$	1	118,281	10	1	0
$2 \times 14$	2	508,789	51	1	0
$2 \times 15$	1	867,676	96	26	0
$2 \times 16$	2	–	–	1,883	0
$2 \times 17$	1	–	–	21,205	4
$2 \times 18$	2	–	–	92,265	19
$2 \times 19$	1	–	–	329,564	70
$2 \times 20$	2	–	–	1,213,782	277
$2 \times 21$	1	–	–	4,080,640	916
$3 \times 3$	2	44	0	1	0
$3 \times 4$	1	219	0	1	0
$3 \times 5$	1	986	0	1	0
$3 \times 6$	1	4,975	0	1	0
$3 \times 7$	1	24,259	1	1	0
$3 \times 8$	1	78,074	5	1	0
$3 \times 9$	1	568,196	52	33,169	5
$3 \times 10$	1	3,236,859	374	241,744	43
$3 \times 11$	2	–	–	2,058,587	401
$4 \times 4$	2	1,353	0	1	0
$4 \times 5$	1	11,565	0	1	0
$4 \times 6$	2	162,343	12	19,575	3
$4 \times 7$	1	717,911	70	359,106	59
$4 \times 8$	2	–	–	5,969,869	1,104
$5 \times 5$	2	173,853	13	30,760	5
$5 \times 6$	1	4,556,619	539	2,073,064	396

We observe that the use of CGT endgame databases is very beneficial for solving Cram boards. When the board fits within the databases, of course no search is needed at all (so just 1 node is investigated). For the larger boards we see large improvements, depending on board size, though the amount of data is limited, since most of these boards were unsolvable in short time without database support.

6. Conclusions and future work

We have constructed all Cram CGT endgame databases for rectangular boards with sizes smaller than 30 squares. For the empty $2 \times n$ boards we proved formally that the sequence of CGT values of $* 0, * 1, * 0, * 1, \dots$ has indeed a strict period of 2. Examining the databases we found single-fragment Cram positions with nimber values up to $* 11$ . Using these we showed multi-fragment positions with values up to $* 15$ . No positions with values $⩾ * 16$ were found so far.

The preliminary results using the CGT endgame databases into a simple alpha-beta solver are very promising, with reductions of at least 50% in worst case and around 80–90% on average, for non-trivial boards. This shows that the effect on solving power for the impartial game Cram is comparable to those for the partizan game Domineering (Barton and Uiterwijk (2014)) and the partizan all-small game Clobber (Uiterwijk and Griebel (2017)), which cover three important classes of combinatorial games.

As future work we will enhance the simple solver into a more sophisticated alpha-beta solver for Cram, using domain-dependent and domain-independent techniques. Especially move ordering based on fragmenting power of possible moves seems promising. Moreover, larger available (and maybe new) databases will be incorporated.

We then have the following goals. 1) We hope to increase the solving power of the enhanced alpha-beta solver even further compared to that of the simple one. 2) We will try solving larger boards than currently known. With larger boards solved larger nimbers will be encountered, not only as sum of several fragments, but most probably also as single fragments. It is interesting to see if a Cram position with value $* 16$ will be found. 3) Finally, we hope to extend our knowledge of and insight into the game of Cram and find more patterns in the CGT values, which hopefully can be explained and preferably be proved as well.

References

Albert, M.H., Nowakowski, R.J. & Wolfe, D. (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. Wellesley, MA: A K Peters.

Barton, M. & Uiterwijk, J.W.H.M. (2014). Combining combinatorial game theory with an α-β solver for Domineering. In

Grootjen ,

Otworowska and

Kwisthout (Eds.), BNAIC 2014 – Proceedings of the 26th Benelux Conference on Artificial Intelligence (pp. 9–16). Nijmegen: Radboud University.

Berlekamp, E.R. (1988). Blockbusting and Domineering. Journal of Combinatorial Theory, Series A, 49, 67–116. doi:10.1016/0097-3165(88)90028-3.

Berlekamp, E.R., Conway, J.H. & Guy, R.K. (1982). Winning Ways for Your Mathematical Plays (Vols. 1–2). London: Academic Press; 2nd ed., in four volumes: Vol. 1 (2001), Vols. 2, 3 (2003), Vol. 4 (2004). Wellesley, MA: A K Peters.

Bouton, C.I. (1902). Nim, a game with a complete mathematical theory. Annals of Mathematics, 3, 35–39. doi:10.2307/1967631.

Breuker, D.M., Uiterwijk, J.W.H.M. & van den Herik, H.J. (2000). Solving

8 \times 8

Domineering. Theoretical Computer Science, 230, 195–206. doi:10.1016/S0304-3975(99)00082-1.

Bullock, N. (2002a). Domineering: Solving large combinatorial search spaces. MSc thesis, University of Alberta.

Bullock, N. (2002b). Domineering: Solving large combinatorial search spaces. ICGA Journal, 25, 67–84. doi:10.3233/ICG-2002-25202.

Conway, J.H. (1976). On Numbers and Games. London: Academic Press.

10.

Drummond-Cole, G.C. (2005). Positions of value

* 2

in generalized Domineering and Chess. Integers: Electronic Journal of Combinatorial Number Theory, 5, #G06.

11.

Gardner, M. (1974). Mathematical games. Scientific American, 230, 106–108. doi:10.1038/scientificamerican0674-106.

12.

Grundy, P.M. (1939). Mathematics and games. Eureka, 2, 6–8.

13.

Guy, R.K. & Smith, C.A.B. (1956). The G-values of various games. Proceedings of the Cambridge Philosophical Society, 52(3), 514–526. doi:10.1017/S0305004100031509.

14.

Kim, Y. (1996). New values in Domineering. Theoretical Computer Science, 156, 263–280. doi:10.1016/0304-3975(95)00150-6.

15.

Kroes, L. (2018). Incorporating combinatorial game theory into an alpha-beta solver for the impartial game of Cram. Master thesis, Maastricht University.

16.

Lemoine, J. & Viennot, S. (2012). Nimbers are inevitable. Theoretical Computer Science, 462, 70–79. doi:10.1016/j.tcs.2012.09.002.

17.

Lemoine, J. & Viennot, S. (2018). Records. Available at: http://sprouts.tuxfamily.org/wiki/doku.php?id=records#cram. Last accessed Feb. 8.

18.

Schneider, M. (2009) Das Spiel Juvavum. Master thesis, Universität Salzburg.

19.

Sprague, R.P. (1935). Über mathematische Kampfspiele. Tohoku Mathematical Journal, 41, 438–444.

20.

Thompson, K. (1986). Retrograde analysis of certain endgames. ICCA Journal, 9, 131–139.

21.

Uiterwijk, J.W.H.M. (2016a).

11 \times 11

Domineering is solved: The first player wins. In A. Plaat, W.A. Kosters and H.J. van den Herik (Eds.), Computers and Games – 9th International Conference, CG 2016. Lecture Notes in Computer Science (LNCS) (Vol. 10068, pp. 129–136).

22.

Uiterwijk, J.W.H.M. (2016b). Polymerization and crystallization of snowflake molecules in Domineering. Theoretical Computer Science, 644, 143–158. doi:10.1016/j.tcs.2016.06.030.

23.

Uiterwijk, J.W.H.M. & Barton, M. (2015). New results for Domineering from combinatorial game theory endgame databases. Theoretical Computer Science, 592, 72–86. doi:10.1016/j.tcs.2015.05.017.

24.

Uiterwijk, J.W.H.M. & Griebel, J. (2017). Combining combinatorial game theory with an α-β solver for Clobber: Theory and experiments. In

Bosse and

Bredeweg (Eds.), BNAIC 2016 – Artificial Intelligence. 28th Benelux Conference on Artificial Intelligence. Communications in Computer and Information Science (Vol. 765, pp. 78–92). doi:10.1007/978-3-319-67468-1_6.

25.

Uiterwijk, J.W.H.M. & van den Herik, H.J. (2000). The advantage of the initiative. Information Sciences, 122, 43–58. doi:10.1016/S0020-0255(99)00095-X.

26.

van den Herik, H.J., Uiterwijk, J.W.H.M. & van Rijswijck, J. (2002). Games solved: Now and in the future. Artificial Intelligence, 134, 277–311. doi:10.1016/S0004-3702(01)00152-7.

27.

Wolfe, D. (1993). Snakes in Domineering games. Theoretical Computer Science, 119, 323–329. doi:10.1016/0304-3975(93)90163-N.