Analyzing a variant of Clobber: The game of San Jego

Abstract

San Jego is a two-player game with perfect information. It is a variation of the games Clobber (2001) and Cannibal Clobber. Given is a rectangular board with black and white pieces on the cells. Multiple pieces which are stacked on each other are called towers. The piece on top of a tower indicates her owner. A move consists of picking an own tower and placing it completely on top of an adjacent tower. If both players can not move anymore, the game ends. Winner is the player with the highest tower. An upper bound for the state-space complexity of San Jego is determined. Furthermore, the game-tree complexity is approximated theoretically and numerically. For small board sizes, the optimal game-theoretic values are calculated and the advantage of the first move is determined.

Keywords

Board game Clobber variant state-space complexity game-tree complexity game-theoretic value

1. Introduction

San Jego is a two-player game with perfect information. It was designed by Althöfer (2015). The game is played on a rectangular board with $m \cdot n$ cells. These cells are arranged in an $m \times n$ grid with the four directions North, East, South, and West. At the beginning of a game, each cell is occupied by one piece. The pieces are either black or white. Each color is assigned to one player. Consequently, the players are denoted as Black and White. In the starting position, the pieces are placed in a chessboard pattern. The top left cell always belongs to Black.

The players move alternatingly. In each move the player chooses one of her towers. A tower belongs to the player who has the top piece. This tower will be completely moved on top of a directly neighboring tower. The neighborhood is given by the four directions North, East, South, and West. Thus, each tower has at most four neighbors. It is not allowed to move a tower to an empty cell. If one player can not move any more, the other player has to make all her remaining moves. The game ends when neither of the players can move any more. The player with the highest tower wins the game. The value of the game is given by the height difference of the highest towers of the players. The game ends in a draw, if the highest towers of Black and White have the same height.

In Fig. 1, the rules are illustrated for the $3 \times 4$ board. (A perfect game for $4 \times 6$ board can be found in Fig. 5 in the Appendix.) Black is the first player. She plays one of the 17 legal moves. This leads to a tower of height two and an empty cell. Empty cells remain empty. Afterwards, it is the turn of White and so on. The alternating turn order ends after Black did its fourth move (cf. Fig. 1h). White has no legal moves anymore, but the game is not over, yet. Black still has to execute her remaining moves. If neither Black nor White can move anymore the game ends. In the final position (cf. Fig. 1i) Black has one tower of height seven while White has one tower of height two and one tower of height three. Seven is larger than three. Consequently, Black wins by margin (game value) $7 - 3 = 4$ .

(Cannibal) Clobber and San Jego are played on the same board, with the same pieces and same start configuration. One of the main differences between (Cannibal) Clobber and San Jego is the execution of the moves. In San Jego, the pieces are stacked to towers, while the pieces clobb each other in (Cannibal) Clobber. The condition of win also differs. In (Cannibal) Clobber the player who can not move any more loses the game instantly by fixed margin 1. On the other side, in San Jego the difference of height between the highest towers decides on win, loss or draw.

Fig. 1.

A San Jego game on the $3 \times 4$ board. Black towers are represented by circles and white towers by squares. The number within a shape is the height of the tower. Arrows indicate the legal moves and the selected move is colored gray.

The paper is organized as follows. In Section 2, the state-space complexity and game-tree complexity of San Jego are determined. These complexities are compared with the complexities of the related games Clobber and Cannibal Clobber. Section 3 contains the optimal game values for small board sizes and different starting positions. These results were calculated with a customized NegaScout algorithm. The paper concludes with a summary, discussion and ideas for new variants in Section 4.

2. Complexity of San Jego

There exist two common ways to measure the complexity of games. These are the state-space complexity and the game-tree complexity.

2.1. State-space complexity

The state-space complexity is the number of all game positions which can be reached from the starting position. Not all possible game positions can be reached from the starting position. Thus, the calculation of the exact state-space complexity is typically very difficult or practically impossible. However, the number of all possible game positions is an upper bound. The following theorem provides an upper bound of the state-space complexity of San Jego.

Theorem 1.
For the $m \times n$ board, the state-space complexity of San Jego is smaller than $\begin{array}{l} (1) & 1 + \sum_{k = 1}^{m n - 1} [(\binom{m n - 1}{k - 1}) \cdot (\binom{m n}{k}) \cdot (\binom{m n}{⌈ \frac{m n}{2} ⌉})] . \end{array}$
Proof.
In Equation (1), the sum symbol considers all game positions with at least one tower and at most $m \cdot n - 1$ towers. The position with $m \cdot n$ towers is the unique starting position and corresponds to the $+ 1$ in front of the sum symbol.

The first binomial coefficient describes the number of possibilities to assign the $m \cdot n$ pieces (ignoring the color) to exactly k distinguishable towers. Each tower has to contain at least one piece. To prove the correctness of the binomial coefficient the method of stars and bars is used (cf. Feller, 1970, p. 38 f.). In this method, the $m \cdot n$ pieces are arranged in one line. Afterwards, the pieces are split up in k towers by placing $k - 1$ bars between the pieces. There are $m \cdot n - 1$ positions to place these $k - 1$ bars. It is not possible to assign two bars to the same position. Otherwise a tower would have height zero.

The second binomial coefficient indicates the number of possibilities to distribute k towers onto $m \cdot n$ cells. On the board there are always $m \cdot n$ pieces; $⌈ \frac{m n}{2} ⌉$ black ones and $⌊ \frac{m n}{2} ⌋$ white ones. The third binomial coefficient describes the possibilities to arrange these pieces within the towers. □
Remark 2.
Three comments on Equation (1) of Theorem 1:
If $m \cdot n$ is even, then using Stirling’s formula results in $(\binom{m n}{⌈ \frac{m n}{2} ⌉}) \sim \sqrt{\frac{2}{π}} \cdot \frac{2^{m n}}{\sqrt{m n}}$ . Table 5 contains some numerical results. If $m \cdot n$ is odd, the result is similar but not so simple.

If $n ⩾ 2$ and $m = n$ , then Expression (1) is approximately $10^{n^{2}}$ , or in more detail $1.8 \cdot 10^{0.91 n^{2} - 0.23 n - 1.25}$ . The approximation is based on a nonlinear regression (cf. Fig. 6 in the Appendix) for the data points $n = 2, 3, \dots, 18$ .

San Jego is a 3 dimensional game: The board has two dimensions, and the towers give dimension 3. Consequently, it is natural to consider all pieces and their colors to characterize a tower. An alternative approach would be the characterization of a tower only by its height and top color. In this case, $(\binom{m n}{⌈ \frac{m n}{2} ⌉})$ can be replaced by $2^{k}$ , which reduces the state space complexity. Side remark: We have variants of San Jego in mind where in the end the colors within the towers play a role. For such variants like “Fractional San Jego” the state-space complexity is only bounded by the larger values.

2.2. Game-tree complexity

The second complexity measure is the game-tree complexity. This represents the number of leafs in the game tree and corresponds to the number of playable games. In the sequel, the game-tree complexity is approximated by multiplying the average numbers of moves for all levels in the game tree. The calculation of these average move numbers is based on the following heuristic modeling as a branching process.

Definition 3.
A game position is called random with parameter $p \in [0, 1]$ , if each cell is independently and randomly assigned to one of the three states: black tower, white tower and empty cell. Each cell has with probability $\frac{1}{2} p$ a black tower and with probability $\frac{1}{2} p$ a white tower. Each cell is empty with probability $1 - p$ .
For the average number of legal moves, the height of the towers is not relevant. Consequently, the heights of the towers are not specified in Definition 3. The natural case with probabilities $\frac{1}{3}$ for each state is achieved for $p = \frac{2}{3}$ . Lemma 4.
Assume a random game position for the $m \times n$ board with $1 ⩽ m ⩽ n$ . If $p \in [0, 1]$ , then the current player has on average $p^{2} \cdot (2 n m - n - m)$ legal moves.
Proof.
The proof is presented only for $m \times n$ boards with $2 ⩽ m ⩽ n$ . The proof for $1 \times n$ boards works analogously.

Assume without loss of generality that Black is to move. First, the average number of legal moves is calculated for an arbitrary cell $(i, j)$ . The cells are grouped in three categories: corners, edge cells and inner cells. Consequently, three cases have to be considered.

The first case concerns edge cells which are not corners. Let $X_{i j}$ be the number of legal moves for Black with the tower on such a cell $(i, j)$ . $\begin{array}{l} X_{i j} = \{\begin{matrix} 0, & with probability \frac{1}{2} p \cdot 1 \cdot p^{0} \cdot {(1 - p)}^{3} + 1 - \frac{1}{2} p \\ 1, & with probability \frac{1}{2} p \cdot 3 \cdot p^{1} \cdot {(1 - p)}^{2} \\ 2, & with probability \frac{1}{2} p \cdot 3 \cdot p^{2} \cdot {(1 - p)}^{1} \\ 3, & with probability \frac{1}{2} p \cdot 1 \cdot p^{3} \cdot {(1 - p)}^{0} \end{matrix} \end{array}$ For $X_{i j} = 0$ , the probability is the sum of two sub cases: black tower on $(i, j)$ with no neighbors; and no black tower on $(i, j)$ . In the other three cases, the tower on $(i, j)$ has to be black. This happens with probability $\frac{1}{2} p$ . With probability $\frac{1}{2} p$ each neighboring cell contains a white tower and with the same probability a black tower. Consequently, each neighboring cell contains a tower of arbitrary color with probability p and is empty with probability $1 - p$ .

Based on these $X_{i j}$ , the average number of legal moves for this outer cell is: $\begin{array}{l} E (X_{i j}) = 3 \cdot (\frac{1}{2} p^{4}) + 2 \cdot (\frac{3}{2} p^{3} (1 - p)) + 1 \cdot (\frac{3}{2} p^{2} {(1 - p)}^{2}) = \frac{3}{2} p^{2} . \end{array}$

The remaining two cases (corners and inner cells) are analyzed analogously. Details are skipped here. Altogether, the expected number of legal moves for an arbitrary cell $(i, j)$ is: $\begin{array}{l} (2) & E (X_{i j}) = \{\begin{matrix} \frac{2}{2} p^{2}, & if (i, j) is a corner \\ \frac{3}{2} p^{2}, & if (i, j) is an edge cell, but not a corner \\ \frac{4}{2} p^{2}, & if (i, j) is an inner cell . \end{matrix} \end{array}$

Equation (2) is used to calculate the expected number of legal moves for the complete board. Let $X : = \sum_{i = 1}^{m} \sum_{j = 1}^{n} X_{i j}$ be the total number of legal moves for Black in a random game position. Then the expected value of X is: $\begin{array}{l} (3) & \begin{matrix} E (\sum_{i = 1}^{m} \sum_{j = 1}^{n} X_{i j}) & = \sum_{i = 1}^{m} \sum_{j = 1}^{n} E (X_{i j}) \\ = 4 \cdot p^{2} + 2 (m + n - 4) \cdot \frac{3}{2} p^{2} + (m - 2) (n - 2) \cdot 2 p^{2} . \end{matrix} \end{array}$

The first equality of Equation (3) holds because of the linearity of expectation values. After the second equal sign, the cells are grouped in the three categories corner, edge and inner cell. Further simplifications of Equation (3) lead to the result of the lemma. □
Observe: The larger p, the higher is the expected number of legal moves. Let $p = \frac{k}{m n}$ for $0 ⩽ k ⩽ m n$ . A random game position for this parameter p contains in the average k towers. Consequently, Lemma 4 provides an estimate for the average number of legal moves, if k towers are on the board. In Table 1, these estimates are compared with the exact values for the move numbers which were determined by computer calculations. For these calculations, the complete game tree was built until a given depth and for each level the average number of legal moves was calculated.

In the following, even and odd depths are discussed separately. For even depths and $n \times n$ boards, the error of Lemma 4 is in the magnitude of $\frac{depth}{n}$ . Consequently, the approximation of the average number of legal moves works quite well for small depths. However, the error grows linearly with increasing depth. For odd depths, the additive error is larger than two, but decreases with increasing depth. A reason might be, that in a random position black and white towers occur with the same probability. However, in odd depths one player is one move behind.

Table 1
Average number of legal moves as a function of the game tree depth

Depth $6 \times 6$ board $8 \times 8$ board $10 \times 10$ board

Exact Lemma 4 Error Exact Lemma 4 Error Exact Lemma 4 Error

0 60.00 60.00 0.00 112.00 112.00 0.00 180.00 180.00 0.00

1 54.07 56.71 2.64 105.79 108.53 2.74 173.62 176.42 2.80

2 53.20 53.52 0.32 104.86 105.11 0.25 172.67 172.87 0.20

3 48.04 50.42 2.38 99.09 101.75 2.66 166.58 169.36 2.78

4 46.76 47.41 0.65 97.92 98.44 0.52 165.46 165.89 0.43

5 42.23 44.49 2.26 92.55 95.18 2.64

6 40.68 41.67 0.99

In all cases of Table 1, the exact value is smaller or equal than the value of Lemma 4. Consequently, Lemma 4 provides an upper bound for the average number of legal moves.
Theorem 5.
Assume $2 ⩽ m ⩽ n$ and $k^{} = ⌈ \frac{m n}{\sqrt{2 m n - m - n}} ⌉$ . Then the branching process from above approximates the game-tree complexity of San Jego by the bound* ${[\frac{(m n)!}{(k^{} - 1)!}]}^{2} {[\frac{2 m n - m - n}{m^{2} n^{2}}]}^{m n + 1 - k^{}}$ .
Proof.
Let $p = \frac{k}{m n}$ for $0 ⩽ k ⩽ m n$ . A random game position for this parameter p contains in the average k towers. Consequently, Lemma 4 provides an estimate for the average number of legal moves, if k towers are on the board. For the approximation of the game tree these average numbers are multiplied. The cases with $k < k^{}$ are ignored because the player has in the average less than one legal move. This leads to the following equation: $\begin{array}{l} \prod_{k = k^{}}^{m n} [{(\frac{k}{m n})}^{2} (2 m n - m - n)] = {[\frac{2 m n - m - n}{m^{2} n^{2}}]}^{m n + 1 - k^{}} \prod_{k = k^{}}^{m n} k^{2} . \end{array}$ It is easy to see that the product behind the ∏-symbol on the right side is equal to ${[\frac{(m n)!}{(k^{*} - 1)!}]}^{2}$ . □
Remark 6.
Theorem 5 gives also a hint for an upper bound for the game-tree complexity of Cannibal Clobber.
2.3. Comparison of the complexities for Clobber, Cannibal Clobber and San Jego

Depth	$6 \times 6$ board	$8 \times 8$ board	$10 \times 10$ board
0	60.00	60.00	0.00	112.00	112.00	0.00	180.00	180.00	0.00
1	54.07	56.71	2.64	105.79	108.53	2.74	173.62	176.42	2.80
2	53.20	53.52	0.32	104.86	105.11	0.25	172.67	172.87	0.20
3	48.04	50.42	2.38	99.09	101.75	2.66	166.58	169.36	2.78
4	46.76	47.41	0.65	97.92	98.44	0.52	165.46	165.89	0.43
5	42.23	44.49	2.26	92.55	95.18	2.64
6	40.68	41.67	0.99

In the sequel, the complexities of San Jego are compared with those of the related games Clobber and Cannibal Clobber. In the Computer Olympiads between 2005 and 2018, Clobber was played on $5 \times 6$ , $8 \times 8$ and $10 \times 10$ boards. For the comparisons, quadratic boards are preferred. Consequently, $5 \times 6$ was replaced by $6 \times 6$ . Tables 2 and 3 contain the results.

The data for the state-space complexity of San Jego is based on Theorem 1. For Cannibal Clobber, there exist at most $3^{m n}$ game positions. Claessen (2011) provided the results for Clobber. On the one hand, the state-space complexities for Clobber and Cannibal Clobber are pretty similar. They only differ by approximately factor 10. On the other hand, San Jego is much more complex than Cannibal Clobber. This had to be expected, because for each game position of Cannibal Clobber there are typically several game positions of San Jego with the same color pattern.

The state-space complexity of San Jego is smaller than the state-space complexity of Cannibal Clobber to the power of two. More precisely, we proved theoretically (cf. Appendix) that for arbitrary $m \times n$ board the numbers of positions $CC$ in Cannibal Clobber and $SJ$ in San Jego behave like $SJ ⩽ {CC}^{δ}$ , where $δ = \frac{log (8)}{log (3)} \approx 1.89$ .

For the approximation of the game-tree complexity we used two approaches. Besides the theoretic approach of Subsection 2.2, Monte-Carlo simulations (MC simulations) were executed. In each MC simulation, $10^{8}$ random games were played. For each game, the length of the game and the average number of legal moves were counted. Afterwards, the mean value of the $10^{8}$ game lengths and legal move numbers were calculated. The approximated game-tree complexity comes from the average number of legal moves to the power of the average game length (which is of course only an upper bound, due to monotonicity of arithmetic and geometric means).

Table 2
State-space complexity for the games Clobber, Cannibal Clobber and San Jego

Board Clobber Cannibal Clobber San Jego

$6 \times 6$ $2.41 \cdot 10^{16}$ $1.50 \cdot 10^{17}$ $2.01 \cdot 10^{30}$

$8 \times 8$ $4.16 \cdot 10^{29}$ $3.43 \cdot 10^{30}$ $2.19 \cdot 10^{55}$

$10 \times 10$ $5.01 \cdot 10^{46}$ $5.15 \cdot 10^{47}$ $4.57 \cdot 10^{87}$

Board	Clobber	Cannibal Clobber	San Jego
$6 \times 6$	$2.41 \cdot 10^{16}$	$1.50 \cdot 10^{17}$	$2.01 \cdot 10^{30}$
$8 \times 8$	$4.16 \cdot 10^{29}$	$3.43 \cdot 10^{30}$	$2.19 \cdot 10^{55}$
$10 \times 10$	$5.01 \cdot 10^{46}$	$5.15 \cdot 10^{47}$	$4.57 \cdot 10^{87}$

The game-tree complexity of Cannibal Clobber is significantly larger than the game-tree complexity of Clobber. One reason is the larger number of legal moves and the associated increase of the game length. Between Cannibal Clobber and San Jego there is only a small increase of complexity. More precisely, they differ approximately by the multiplicative factor $\frac{n}{2} - 1$ . The reason for this difference is the condition for the end of the game: Cannibal Clobber ends if one player can not move any more, whereas San Jego ends only if none of the two players has legal moves left.

Table 3

Game-tree complexity for the games Clobber, Cannibal Clobber and San Jego

Game	Board	Results Monte-Carlo simulation			Theorem 5

		Moves	Length	Complexity
Clobber	$6 \times 6$	20.9	22.9	${20.9}^{22.9} \approx 1.43 \cdot 10^{30}$
Cannibal Clobber	$6 \times 6$	26.0	25.5	${26.0}^{25.5} \approx 1.43 \cdot 10^{36}$	$4.77 \cdot 10^{37}$
San Jego	$6 \times 6$	25.7	25.8	${25.7}^{25.8} \approx 2.89 \cdot 10^{36}$	$4.77 \cdot 10^{37}$
Clobber	$8 \times 8$	37.5	41.1	${37.5}^{41.1} \approx 4.33 \cdot 10^{64}$
Cannibal Clobber	$8 \times 8$	47.5	46.0	${47.5}^{46.0} \approx 1.32 \cdot 10^{77}$	$6.76 \cdot 10^{81}$
San Jego	$8 \times 8$	47.2	46.3	${47.2}^{46.3} \approx 3.69 \cdot 10^{77}$	$6.76 \cdot 10^{81}$
Clobber	$10 \times 10$	59.1	64.6	${59.1}^{64.6} \approx 3.03 \cdot 10^{114}$
Cannibal Clobber	$10 \times 10$	75.5	72.4	${75.5}^{72.4} \approx 9.62 \cdot 10^{135}$	$1.89 \cdot 10^{146}$
San Jego	$10 \times 10$	75.1	72.8	${75.1}^{72.8} \approx 3.65 \cdot 10^{136}$	$1.89 \cdot 10^{146}$

Random agents do not distinguish between good and bad moves. Consequently, the random games often end rather early, which underestimates the size of the game tree. Clobber is a good example for this phenomenon. Claessen (2011) let the strong program MILA play 400 times against itself. MILA is the program which had won the Clobber tournament of the ICGA 2005 event (Willemson and Winands, 2005). Based on his runs, he got an average game length of 46.3 and 71.6 for the $8 \times 8$ or $10 \times 10$ board, respectively.

3. Game-theoretic results

3.1. NegaScout algorithm

The NegaScout algorithm of Reinefeld (1983) was used to calculate the optimal game values for several given starting positions. This algorithm combines the classical Alpha-beta pruning with a null window search. The basic algorithm is well known, for that reason the details are skipped. Instead, two San Jego specific customizations are presented to improve the performance.

A two phase heuristic was used to sort the legal moves. In the first phase, moves with high enemy towers on the target cell are preferred. To the contrary, target cells with high own towers have the lowest priority. Often the preferences of Phase 1 do not give unique candidates. Here we had a tie-breaking Phase 2: a local weight is assigned to each cell. From center to border the weights are decreasing. For cells with the same preference after Phase 1 the move with the higher weight for the target cell is preferred.

Depending on the board size, the starting position is horizontally or vertically symmetric. So it is not necessary to consider all legal moves. For instance, for the $3 \times 4$ board with its horizontal symmetry (c.f. Fig. 1a) it is enough to investigate 10 out of the 17 legal moves.

For the adapted NegaScout algorithm, the improvement of performance by move ordering is illustrated in Table 4. Just Phase 1 cuts off a large area of the game tree while only Phase 2 is not effective. However, combining both phases works very well. In comparison with the basic NegaScout algorithm with random move order, the number of visited end positions is reduced to approximately 2.2%.

Table 4
Number of visited end positions for the customized NegaScout algorithm and the $4 \times 4$ board

Symmetry Random Only Phase 1 Only Phase 2 Phase 1 and 2

Without 13,407,818 2,255,093 11,827,262 564,411

With 9,189,571 1,427,596 8,647,400 303,862

Symmetry	Random	Only Phase 1	Only Phase 2	Phase 1 and 2
Without	13,407,818	2,255,093	11,827,262	564,411
With	9,189,571	1,427,596	8,647,400	303,862

3.2. Game-theoretic results for the basic game

For San Jego, it can matter whether Black or White begins. Thus, it makes sense to distinguish between seven possible outcomes for a specified board position. The outcomes are denoted by F, Z, D, B, $B^{=}$ , W and $W^{=}$ and have the following meanings:

F: first player win,

B: Black win,

W: White win,

D: draw,

Z: second player win (Z like Zugzwang),

$B^{=}$ : Black achieves at least a draw,

$W^{=}$ : White achieves at least a draw.

The outcomes F, Z, D, B and W are independent of whether Black or White begins. For the outcomes

B^{=}

and

W^{=}

it depends on the first player if it is a win for her or a draw. An example for

B^{=}

is the

1 \times 7

board. If Black is the first player Black wins; if Black is the second player the game ends in a draw. So far, we found no board size with the opposite of this outcome (Black first player = draw, Black second player = Black wins).

Assume m and n arbitrary but fixed. By reasons of symmetry it is enough to look at the outcomes for boards with $m ⩽ n$ . Furthermore, it is sufficient to know the game value for Black to start if the board has an even number of cells. For an odd number of cells (for instance on a $3 \times 5$ board), the game values may differ because Black owns an extra tower in the beginning. A very special case is the $1 \times 5$ board. See the scores in Fig. 7 in the Appendix.

Figure 2 shows the outcomes for different small board sizes. For larger boards, the algorithm was not able to calculate the results in a reasonable amount of time. Even for the small $5 \times 5$ board it took several days. The more detailed scores (game values) can be found in Fig. 7 in the Appendix. Four of the seven outcomes occur for $1 \times n$ boards. If $2 ⩽ n ⩽ 6$ the first player always wins the game. This region is followed by a transition area ( $7 ⩽ n ⩽ 11$ ); here games occur with outcomes $B^{=}$ , F and D. For larger n, the games end in a draw except for $n = 17$ . This regularity was confirmed until $n = 27$ .

For boards with at least two rows, almost always the first player wins. The only two exceptions found are the $2 \times 4$ and $2 \times 10$ board. We believe that there are more exceptions for larger n. In contrast to the $1 \times n$ case we do not expect that all games end in a draw if n is significantly larger than m for all $m ⩾ 2$ . A reason might be that it is harder for the second player to defend, because more moves are needed to split the board.

Fig. 2.

Game-theoretic results of San Jego for various board sizes.

3.3. Other starting positions

Seven possible outcomes for a (basic) starting position were defined in Subsection 3.2. Here, our question is: What may happen for other starting positions? Exemplary answers are given for the $4 \times 4$ board.

The game values for all starting positions with eight black and eight white pieces were calculated. From each symmetry class we included only one representant in the investigation. In total, 1,674 such starting positions exist for the $4 \times 4$ board. In Fig. 3, these starting positions are classified with respect to the outcome (Win/Loss/Draw) or exact game value, respectively.

Approximately 60% of all these starting positions lead to a win for the starting player. However, for each of the other six outcomes (Z, D, B, $B^{=}$ , W, $W^{=}$ ) at least one starting position of this type exists. For the outcome Z we got exactly one starting configuration (cf. Fig. 4a). The numbers of positions with outcomes B or $B^{=}$ are by symmetry equal to the numbers of positions with outcomes W or $W^{=}$ .

Fig. 3.

Classification of all fair and unique starting positions for the $4 \times 4$ board.

Figure 3b shows the game values for all starting positions which do not end in a draw. For the classification with respect to the game values it does not matter if Black or White starts. Most of the starting positions are won by the first player with scores 1, 2, or 3. A win with game value 6 is the highest to occur. One of the two representatives can be found in Fig. 4b. There are only a few starting positions which can be won by the second player. The corresponding game values are relatively small, 3 being the maximal game value here (see the nice configuration in Fig. 4c).

Fig. 4.

Interesting starting positions.

4. Summary, discussion and open questions

4.1. Summary and discussion

San Jego is a new variant of Cannibal Clobber which itself is a variant of the semi-classic Clobber. The relation between San Jego and Cannibal Clobber is similar to the one between Emanuel Lasker’s “Lasca” and Checkers: In Lasca, also higher and higher towers of pieces are established during the course of the game (Lasker, 1931).

Whereas Clobber and Cannibal-Clobber are combinatorial games in the “traditional” sense, San Jego is different as the final score is not just win or loss, but a win by some margin. Unfortunately, the approach of Larsson et al. (2016, 2018) does not apply to San Jego as the final phase with moves by only one remaining active player is an essential part of San Jego.

We derived upper (and lower) bounds for the complexity of San Jego, in comparison with Clobber and Cannibal Clobber. The lower bounds are trivial in the sense that the complexities of Clobber and Cannibal Clobber on boards of the same size constitute these bounds.

We computed exact game-theoretic values for San Jego on small boards with the help of computer-based game tree search. Concerning slim boards, in particular with $1 \times n$ cells, we conjecture that on “all” long enough boards the game will end in a draw, if both sides play optimally. We also showed with computer help that the starting position, i.e. the distribution of pieces on the initial board, can make a huge difference in outcome.

On many small boards, the first player has a certain advantage. This finding is in agreement with our experience from many human test games. To make San Jego fair for play in practice, either pairs of games may be played with a change of colors after the first game, or a game may start with a komi bidding procedure where each players guesses the correct value to counterbalance an advantage for the side to move first.

For larger boards, computer analysis of San Jego may use versions of proof-number search (see Allis et al., 1994), table bases for “end games”, and more sophisticated heuristics in move ordering.

4.2. Open questions and new variants of San Jego

Complexity class: Is San Jego on $n \times n$ boards with arbitrary starting positions PSPACE complete? We think that the answer is “no”, at least for $1 \times n$ and $2 \times n$ boards, but do not have a proof so far.

Optimal strategy: Are there “simple” characterizations of perfect play in San Jego, like for instance Lehman’s algorithm in Shannon’s Switching game (Lehman, 1964)?

San Jego with non-equal numbers of pieces: For most board sizes in our analysis, the first player has a (small) advantage. This may be balanced by giving the second player extra pieces, on the cost of player 1. Fair or at least interesting values for settings have to be determined.

2-Phase San Jego: Starting position is the empty board. In Phase 1 the players alternate in placing own pieces on free cells of the board. When all cells are occupied, Phase 2 starts with the normal San Jego rules. In a subvariant, Phase 1 may take longer than $m \cdot n$ moves, to allow already nontrivial towers in this phase. Or, in a Phase 1 with $m \cdot n$ or less moves it may be allowed to place new pieces on own pieces that are already on the board.

ClobTower: This is the other possible intermediate step between Clobber and San Jego. Legal moves are to place own towers on top of neighboring foreign towers. At the end, the player with the highest tower is winner. ClobTower is the complement to Cannibal Clobber, so to say.

Fractional San Jego: Here also the pieces under the top of the towers play a role. Top pieces have value 1, the next one value $\frac{1}{2}$ , the third one $\frac{1}{4}$ and so on (geometric series). Pieces of top color get positive sign, pieces of the opponent negative sign. An example: A 6-floor tower with WWBBWB gets value $+ 1 + \frac{1}{2} - \frac{1}{4} - \frac{1}{8} + \frac{1}{16} - \frac{1}{32} = \frac{37}{32}$ . Each tower gets a value between 0 and 2. For each player the value of her highest tower are taken.

4.3. On human play

Experiments with dozens of human players during exhibitions in recent years indicate that “San Jego” as a game is much more suited for human play than Clobber or Cannibal Clobber. In particular, young people and children feel affected by stacking towers (for instance realized by LEGO^® bricks or GeoMag™ sticks).

Footnotes

Acknowledgements

We thank Mark Umnus, who validated some of the game theoretic results by independent computer calculations. We thank Richard Nowakowski for his hint on the Larsson et al. () paper. We want to thank three anonymous referees for their constructive reports.

Appendix

Table 5

Approximation of the central binomial coefficient via Stirling’s formula

m	n	$(\binom{m n}{⌈ \frac{m n}{2} ⌉}) / [\sqrt{\frac{2}{π}} \cdot \frac{2^{m n}}{\sqrt{m n}}]$
6	6	0.99308049
8	8	0.99610152
10	10	0.99750316
20	20	0.99937519
100	100	0.99997500
1000	1000	0.99999975

References

Allis, L.V., van der Meulen, M. & van den Herik, H.J. (1994). Proof-number search. Artif. Intell., 66(1), 91–124. doi:10.1016/0004-3702(94)90004-3.

Althöfer, I. (2015). San Jego. https://www.1000steine.de/de/gemeinschaft/forum/?entry=1&id=338936, last checked 02/06/2020.

Claessen, J. (2011). Combinatorial game theory in Clobber. Master’s thesis, Maastricht University. Supervised by Mark Winands.

Feller, W. (1970). An Introduction to Probability Theory and Its Applications (3rd ed., Vol. 1). New York: Wiley.

Larsson, U., Nowakowski, R.J., Neto, J.P. & Santos, C.P. (2016). Guaranteed scoring games. Electron. J. Comb., 23(3).

Larsson, U., Nowakowski, R.J. & Santos, C.P. (2018). Games with guaranteed scores and waiting moves. Int. J. Game Theory, 47(2), 653–671. doi:10.1007/s00182-017-0590-x.

Lasker, E. (1931). Brettspiele der Völker. Verlag August Scherl.

Lehman, A. (1964). A solution of the Shannon switching game. J. Soc. Indust. Appl. Math., 12(4), 687–725. doi:10.1137/0112059.

Reinefeld, A. (1983). An improvement of the scout tree search algorithm. ICCA Journal, 6(4), 4–14.

10.

Spivey, M.Z. (2019). The Art of Proving Binomial Identities. Chapman and Hall/CRC. doi:10.1201/9781351215824.

11.

Willemson, J. & Winands, M. (2005). MILA wins Clobber tournament. ICGA Journal, 28, 188–190. doi:10.3233/ICG-2005-28316.