Design and implementation aspects of a Surakarta program

Abstract

In this paper, we present the techniques, such as bitboard, iterative-deepening aspiration search algorithm, endgame tablebase, used in our Surakarta program Fuchou. A bijective function similar to Schadd’s is developed to map a Surakarta board position to a unique address of the endgame tablebase. The function is one-to-one and onto and can be computed very quickly using some techniques compared to conventional methods. We have implemented it on our Surakarta program FuChou. Experimental results show that we have gotten advantages of speedup as well as accuracy on the endgame boards.

Keywords

endgame tablebase alpha-beta search bitboard iterative-deepening aspiration search computer games Surakarta

1. Introduction

In the area of computer games, many researchers studied and presented many useful techniques, such as the alpha-beta pruning (Knuth and Moore, 1975) and MCTS (Coulom, 2006; Kocsis and Szepesvári, 2006), in order to promote their programs’ strengths. Among them, the policy network (Silver et al., 2016) used in AlphaGo by DeepMind team, or many parallel search algorithms are developed to increase the search depth and to get more accurate evaluation scores about the board positions. However, in many endgames, one player usually needs a long sequence of moves to beat his/her opponent. If we only use the game search algorithms, it will be very difficult to find a winning path within a short period of game-playing time.

The endgame tablebase (Chess Programming) is a possible technique to relieve the above problem. We can apply the retrograde method (Ströhlein, 1970) in advance to find the best move for a large amount of endgames, and store the results in a tablebase. In the game playing time, if the board is entering into the endgame state, then we can directly access the information in the tablebase and quickly get the best move to play. Hence, it is very favorable to have a large endgame tablebase to help the program to beat its opponent in advantage positions or to postpone the possible losses or even to reverse the victory in disadvantage positions.

Surakarta is a two-player game, named after the ancient city of Surakarta in central Java. It is also named Permainan or Roundabouts. The game is also a competition item in many computer competitions, such as Computer Olympiad (ICGA), Technologies and Applications of Artificial Intelligence (TAAI), Taiwan Computer Game Association (TCGA), University Computer Games Championship, and National Computer Games Tournament.

Surakarta is still an unsolved game. Our objective is to develop a program with a high strength. The rest of this paper is organized as follows. Section 2 goes through the related work in Surakarta programs and related techniques, such as bitboard, search algorithms, and endgame tablebases. Section 3 presents our approach for developing the Surakarta agent. A bijective function similar to Schadd (2011) for fast indexing the board is used in our program and is introduced in Section 4. Sections 5 and 6 show the implementation details of the DTC (Distance To Conversion) endgame tablebases and experimental results. Section 7 concludes the paper and provides some remarks.

2. Surakarta and related work

2.1. Pieces and chessboard

The Surakarta board has 6 horizontal and 6 vertical lines resulting in 36 intersections and 8 circular arcs. The two players, Black and White, begin the game with 12 isotype pieces each, located at both sides, as shown in Fig. 1(a).

2.2. The rules of moves and captures

Players make moves alternate. On a turn, a player either moves one of his pieces to an unoccupied point in any one of the 8 directions (4 diagonal and 4 orthogonal directions) as shown in Fig. 1(b) and (c) or makes a capturing move as shown in Fig. 1(d). A capturing move consists of traversing along an inner or outer circuit around at least one of the eight corner loops of the board, and then finally followed by landing on an enemy piece, capturing it. Any number of unoccupied points may be traveled over, before or after traversing a corner loop. An unoccupied point may be traveled over more than once during the capturing piece’s journey. Only unoccupied points may be traveled over; jumping over pieces is not permitted. Captured piece is removed from the board.

Basically, pieces that occupied the center of the board are more powerful, where they are in one or two loops. On the other hand, pieces on the corner are difficult to move, as the spaces next to the corner can be attacked by the opponent. Due to the special property of Surakarta, it is a challenging problem for creating a program with a high strength.

Fig. 1.

(a) the initial state of Surakarta, (b) non-capturing moves, (c) non-capturing moves, (d) capturing moves.

2.3. Winning condition

The player capturing all 12 of the opponent’s pieces wins the game. Winands’s (2016) paper and recent ICGA Surakarta tournaments further apply the threefold repetition rule or the 50-move rule, which states that the game is ended if the same board position occurs three time or no captures in the past 50 moves. When the game is ended, the player with more pieces remaining on the board than the opponent wins the game. Otherwise, it is a draw for both sides.

Here we review some research results about the design of agent programs, bitboard, and aspiration search. Zhang and Ding (2011) implemented a Surakarta program using arrays to store the board information, where 0 indicates empty position, 1 and 2 indicate Black and White pieces respectively. They created two circular queues to store the intersection positions of two loops. When touching these intersections, the program needs to search the loops to check if capturing move is available.

Winands (2016) developed a Surakarta agent program named SIA which performs an $α β$ depth-first iterative-deepening search in the PVS framework. A two-level transposition table is applied to prune a subtree or to narrow the $α β$ window. In the Surakarta engine SIA, the following techniques are employed: quiescence search, multi-cut, and realization probability search. At the leaf nodes of the regular search, a quiescence search is performed to get more accurate evaluations. In SIA an extended version of quiescence search is implemented. This type of a quiescence search limits the set of moves to be considered and uses the evaluations of interior nodes as lower/upper bounds of the resulting search value. Most importantly, all endgame tablebases up to 8 pieces have been generated. SIA won the gold medal at the 12^th, 13^th, 15^th, 17^th, and 18^th ICGA Computer Olympiad. It did not lose a single game in each tournament it participated. This shows that SIA has a very high level of strength.

Adelson-Velsky et al. (1970) used bitboard techniques on games. They introduced many bitboard operations such as XOR, AND, OR. Those are adopted in many later developed programs.

Kaindl et al. (1991) compared the minmax algorithm with the alpha-beta using aspiration window. They used the number of bottom positions (NBP) as an evaluation item, and analyzed the details of their aspiration window method.

Allis et al. (1994a; 1994b) applied the threat-space search and the PN search to prove that free-style Gomoku is a first-player win game. However, at the present time, Surakarta is still unsolved. Hence, we can construct the endgame tablebases to promote the program’s strength.

Basically, there are two kinds of endgame tablebases: DTM (Distance To Mate) and DTC (Distance To Conversion). The goal of DTM is to find a shortest path to beat its opponent. On the other hand, the goal of DTC is to find a shortest path to capture its opponent’s piece in order to reduce the number of remaining pieces and to get an advantage over its opponent. Our Surakarta program applied DTC for implementation.

An endgame tablebase is used in querying a position for getting its best move. We need a function to map a board position to an identification number which is the address for storing its best move. The function must be one-to-one because we cannot let two different board positions refer to the same address in the endgame tablebase. Furthermore, we prefer to reduce the total amount of space used in the endgame tablebase.

Among the researches of the Chess endgame tablebases, most researches used 6 bits to reference the 64 squares of Chess board. For an endgame with n pieces, it needs $6 n$ bits for referencing, and hence this will totally have $2^{6 n} = 64^{n}$ combinations. In Thompson (1991; 1996), taking advantage of the fourfold symmetry of the chessboard, Ken Thompson confined the white king to the a8-d8-d5 octant by horizontal, vertical, or diagonal reflections, and further reduced the size of the endgame tablebase to one eighth (more accurately, 10/64) of the original size. For other kinds of games, such as Chinese chess (Chen et al., 2014) or Chinese Dark Chess (Chen et al., 2018), most researchers also used this idea to implement their endgame tablebases.

Unfortunately, this kind of encoding may waste lots of space for some other games, such as Surakarta. For a Surakarta board with n pieces, the total number of possible board positions is $(\begin{matrix} 36 \\ n \end{matrix}) \times 2^{n}$ . Hence, for 6-piece Surakarta board, the total number of possible board positions is $(\begin{matrix} 36 \\ 6 \end{matrix}) \times 2^{6} = 124, 658, 688$ . If we directly apply the method used in Chess, there will totally have $36^{6} = 2, 176, 782, 336$ combinations, which is about 17.5 times. Even if we take advantage of the fourfold symmetry of the chessboard (Thompson, 1991; 1996), it does still need lots of space. Although there are many encoding enhancements (Endgame Tablebases) proposed later in order to reduce space, it still cannot effectively narrow the gap. In Computer Chess Club (Nalimov, 1998), Eugene Nalimov mentioned that it will get the same board position if we exchange two isotype pieces and this is a reason for the waste of the space. In Surakarta, since each player has 12 isotype pieces, it will get much severe waste of space if we use the encoding scheme of Chess.

3. Our Surakarta agent

FuChou is our Surakarta program developed with C++. It is based on the bitboard data structure and Iterative-Deepening Aspiration Search in the PVS framework (Marsland and Campbell, 1982).

3.1. BitBoard and bit operation

Bitboard is a popular technique that is used in many kinds of games for a long time. But, at the present, there are not so many research papers utilizing bitboard in Surakarta program. Bitboard is a numeric variable representing a board state. For a board size under $8 \times 8$ , such as Surakarta, we usually use two unsigned integers to represent two players’ pieces respectively as shown in Fig. 2(a) and (b). Each bit of the bitboard can have the value 1 or 0 to indicate whether that position is occupied with a player’s piece.

We map each bit of the bitboard to a position of the Surakarta board shown in Fig. 2(c). The Bit Manipulation Instruction Sets (BMI 1) have specified functions to extract a piece, get its position number, and then convert the number to its board state. The non-capturing moves of Surakarta means moving a piece to an unoccupied point in any one of the 8 directions. The masks for each position is established in advance. When we want to generate the non-capturing moves, we just get a piece and “exclusive or” the bitboard of non-empty positions with the corresponding mask to find all its legal non-capturing moves. Figure 3 shows this process. Figure 3(a) gets a piece to move. Figure 3(b) is its mask. Now the non-empty positions (including White and Black pieces) are indicated as a bitboard in Fig. 3(c). We can xor Fig. 3(b) with Fig. 3(c) to get Fig. 3(d) which removes the non-empty positions and reserves the empty positions in the 8 directions. Hence Fig. 3(d) represents all the non-capturing moves of the piece shown in Fig. 3(a). The above process just takes logic operations to get the final results with a very efficient way. This bitboard data structure is surely better than the arrays from the performance point of view.

Fig. 2.

(a) the bitboard of White pieces, (b) the bitboard of Black pieces, (c) the mapped position number for each bit.

Fig. 3.

Use bitboards to generate non-capturing moves: (a) the moving piece, (b) the mask of the moving piece, (c) non-empty positions, (d) final non-capturing moves.

3.2. Iterative-deepening aspiration search

We use Iterative-Deepening Aspiration Search in the PVS framework (Marsland and Campbell, 1982) in our Surakarta program, where the values of alpha and beta are not fixed values $- \infty$ and ∞ respectively. Instead, they are in a guessed range which is expected to catch the final exact values. Common approach is to apply shallow search to get a value and use it as a window for the next deeper search. Note that if the derived value is less than or equal to alpha, then it is called Fail low and it needs to search again where beta is changed to alpha, and alpha is changed to $- \infty$ . On the other hand, if the derived vale is greater than or equal to beta, then it is called Fail high and it also needs to search again where alpha is changed to beta, and beta is changed to ∞. Algorithm 1 depicts the pseudo code of the Iterative-Deepening Aspiration Search in the PVS framework.

FuChou was written based on the algorithm. Now we introduce how to set the window size Δ, which has a dynamic range. Initially, the center of the aspiration window is set as the value of previous search level as follows. $\begin{matrix} (1) & Δ = | \frac{value}{10} | + 20 \end{matrix}$

Algorithm 1
Iterative-deepening aspiration search

1. Set start and end.

2. Set lastVal as 0.

3. for depth from start to end

4. Set Δ.

5. alpha ← lastVal − Δ

6. beta ← lastVal + Δ

7. value ← $α β$ (alpha, beta, depth)

8. if value ⩽ alpha

9. value ← $α β$ ( $- \infty$ , alpha, depth)

10. else if value ⩾ beta

11. value ← $α β$ (beta, ∞, depth)

12. lastVal ← value

13. end for

We think that the board is more unstable when the absolute function of value is larger. Hence we set a larger window size. Furthermore, when the value equals 0, we add an extra quantity 20 in order to prevent Δ from being 0.

3.3. Quiescence search

When $α β$ search reaches a depth limit, the leaf nodes are usually judged with an evaluation function to indicate the advantages of the nodes. However, the leaf nodes may have an unstable state that the exchanges of pieces can occur in the subsequent moves. Immediate evaluations at the leaf nodes are very inaccurate and the results are problematic. Hence, we should continuously search the game tree until a calm state. In FuChou, when it searches to a depth limit, it will continue to perform a deeper search considering only the capturing moves. Usually, this extension will end up with 0 possible captures a few ply down.

3.4. Parallel computing in PVS

The number of legal moves of a Surakarta board is around 20 to 40. Most programs used a single thread to search the game tree. In Marsland and Campbell (1982), PVS is introduced. They also describe how to implement the parallel version of PVS. FuChou also applies the same technique. After searching the first branch using PVS, it uses the OpenMP library to parallelize the execution of the remaining branches according to the available cores and store the search results in an array.

4. A bijective function for fast indexing

In this section, we refer to the Formula 4.1 in Schadd (2011), which was used to construct the endgame tablebase of Fanorona game. We develop a similar bijective function for fast indexing a board position. We design the mapping function for Surakarta. The board of Surakarta has 36 positions. Firstly, we encode the non-empty positions as 1 and the empty positions as 0, as shown in Fig. 4. For the 1-piece endgame, row 1 in Fig. 4(a) means the only one piece is put at the first position of the Surakarta board which has 36 positions. We encode this board as 0. Row 2 in Fig. 4(a) means the only one piece is put at the second position of the Surakarta board. We encode this board as 1. And so on. We can see that there will have totally 36 rows in Fig. 4(a) and the encoding numbers are $0, 1, 2, \dots, 35$ , respectively. Now, let us take a look at the 2-piece endgame shown in Fig. 4(b). Row 1 means the two pieces are put at positions 1 and 2, and this board is encoded as 0. Row 2 means the right piece is put at position 1 and the left piece is put at position 3, and this board is encoded as 1. Row 3 means the right piece is put at position 2 and the left piece is put at position 3, and this board is encoded as $2 = 1 +$ 1, which can be realized as an offset 1 for the left piece plus the encoded number of the 1-piece endgame for the right piece. Similarly, Rows 4 to 6 are 2-piece endgame where the left piece is put at position 4 that is encoded with an offset 3 and the right piece is put at positions 1, 2, or 3, and is encoded as 0, 1, or 2, just the same with the 1-piece endgame shown in Fig. 4(a). Similarly, Fig. 4(c) shows the 3-piece endgame where the left piece is encoded with an offset and the remaining two pieces are encoded with the 2-piece endgame shown in Fig. 4(b). Now the problem is how to derive the offset value for the leftmost piece.

Let $(\begin{matrix} i \\ j \end{matrix})$ be the number of combinations of putting j 1s in i positions. For example, as shown in rows 1 to 10 of Fig. 4(c), there are $(\begin{matrix} 5 \\ 3 \end{matrix}) = 10$ possible combinations for putting three 1s in 5 positions. Since $(\begin{matrix} i \\ j \end{matrix})$ is the combination number, we have $(\begin{matrix} i \\ j \end{matrix}) = (\begin{matrix} i - 1 \\ j \end{matrix}) + (\begin{matrix} i - 1 \\ j - 1 \end{matrix})$ .

Fig. 4.

The encoding of non-empty board positions: (a) 1-piece endgame, (b) 2-piece endgame, (c) 3-piece endgame.

Let $F (i, j)$ be the offset for the leftmost piece of the j-piece endgame in which the leftmost piece is put at position i. From Fig. 4, we can see that the encoded values will be 0 if all the j pieces are all put at the right-hand side, that is, positions 1 to j. Therefore, $F (i, j) = 0$ if $i = j$ . Now, if $i > j > 0$ , the distance from $F (i - 1, j)$ to $F (i, j)$ will be $(\begin{matrix} i - 2 \\ j - 1 \end{matrix})$ , which equals the number of combinations for putting $j - 1$ 1s in $i - 2$ positions, as illustrated in Fig. 5. Hence, we have $\begin{matrix} F (i, j) = F (i - 1, j) + (\begin{matrix} i - 2 \\ j - 1 \end{matrix}) \end{matrix}$

For the 3-piece endgame shown in Fig. 4(c), row 2 depicts $F (4, 3) = F (3, 3) + (\begin{matrix} 2 \\ 2 \end{matrix}) = 0 + 1 = 1$ , row 5 depicts $F (5, 3) = F (4, 3) + (\begin{matrix} 3 \\ 2 \end{matrix}) = 1 + 3 = 4$ , and row 11 depicts $F (6, 3) = F (5, 3) + (\begin{matrix} 4 \\ 2 \end{matrix}) = 4 + 6 = 10$ . Furthermore, $\begin{array}{l} F (i, j) = & F (i - 1, j) + (\begin{matrix} i - 2 \\ j - 1 \end{matrix}) \\ = & F (i - 1, j) + (\begin{matrix} i - 3 \\ j - 1 \end{matrix}) + (\begin{matrix} i - 2 \\ j - 1 \end{matrix}) \\ ⋮ \\ = & F (j, j) + (\begin{matrix} j - 1 \\ j - 1 \end{matrix}) + (\begin{matrix} j \\ j - 1 \end{matrix}) + \dots + (\begin{matrix} i - 3 \\ j - 1 \end{matrix}) + (\begin{matrix} i - 2 \\ j - 1 \end{matrix}) \\ = & (\begin{matrix} j - 1 \\ j - 1 \end{matrix}) + (\begin{matrix} j \\ j - 1 \end{matrix}) + \dots + (\begin{matrix} i - 3 \\ j - 1 \end{matrix}) + (\begin{matrix} i - 2 \\ j - 1 \end{matrix}) \\ = & (\begin{matrix} i - 1 \\ j \end{matrix}) \end{array}$

Fig. 5.

The scheme for computing the offsets.

The last step can be proven by induction. Due to the page limit, we omit it here.

From previous derivations, we can compute and store the values of $F (i, j)$ beforehand by using the dynamic programming method as follows. In practical applications, we don’t consider 0-piece endgame and it will not happen in real games. So we can let $F (i, j)$ be 1 when $j = 0$ . Now we can derive the formula $F (i, j)$ as follows which does not depend on the value of $(\begin{matrix} i \\ j \end{matrix})$ and can be computed only by itself. $\begin{matrix} F (i, j) = \{\begin{matrix} 0, & if i = j \\ 1, & if i \neq 0 but j = 0 \\ F (i - 1, j) + F (i - 1, j - 1), & if i > j > 0 \\ undefined, & otherwise . \end{matrix} \end{matrix}$

Now suppose that a Surakarta endgame board has n pieces located at positions $p_{1}, p_{2}, \dots, p_{n}$ , where $p_{k} \in {1, 2, \dots, 36}, \forall k \in {1, 2, \dots, n}$ . Without loss of generality, assume $p_{1} < p_{2} < \dots < p_{n}$ and $nonEmpty = black ∣ white$ , then the $index$ value for the endgame board can be calculated as follows: $\begin{matrix} index = (\sum_{k = 1}^{n} F (p_{k}, k)) ≪ n ∣ pext (black, nonEmpty) \end{matrix}$

This method uses the patterns of the n non-empty positions to accumulate the values $F (p_{k}, k)$ of each piece and then quickly computes its offset as well as the patterns of both players’ pieces. Because each non-empty position has only two possibilities (i.e. White or Black), we can just take the pattern of the Black player and ignore the White player to uniquely determine the pattern of both sides. Then, the pext (Parallel bits extract) instruction in the BMI2 instruction set of the modern CPU is masked with Black to get the pattern of the Black player. The above function can map an n-piece Surakarta endgame board onto a value in the range $[0, 2^{n} \times (\begin{matrix} 36 \\ n \end{matrix}))$ . This function also preserves the properties of one-to-one and onto, and therefore is a bijective function. Furthermore, we can also derive the original board configuration from the index value for this is necessary in the construction process of retrograde method.

As mentioned earlier, Schadd (2011) has used the similar function to construct the endgame tablebase of Fanorona game. He got rid of all-black and all-white configurations and reduced slightly the space used. If we want to get the same effect, we can replace the above formula with the following one. $\begin{matrix} index = (\sum_{k = 1}^{n} F (p_{k}, k)) \times (2^{n} - 2) ∣ (pext (black, nonEmpty) - 1) \end{matrix}$

However, the ratio of all-black and all-white configurations in an endgame tablebase is quite small. Hence we didn’t apply his idea in our implementation for saving the computation time.

5. DTC endgame tablebases

We used the retrograde method to establish the DTC endgame tablebases starting from 1-piece. At the present time, 1-piece to 6-pieces endgame tablebases have already been constructed. The number of boards for 1-piece to 6-pieces are 72, 2529, 57120, 942480, 12063744, and 124658688, respectively. Their construction time are 0, 0.01, 0.65, 6.07, 84.39, 1264.88 seconds, respectively.

The 6-pieces DTC endgame tablebase is combined with the aspiration search. When the search reaches the depth limit and the number of pieces is less than or equal to 6, the board will be given a value according to the tablebase. If the DTC value is positive, it means how far the player will win the game. In this case, the board will be given a value of winValue–(DTC_value $- 1$ ), where winValue is a very large number such as $10^{6}$ . On the other hand, if the DTC value is negative, it means how far the player will lose the game. In this case, the board will be given a value of loseValue–(DTC_value $+ 1$ ), where loseValue is a very small number such as $- 10^{6}$ . If the DTC value is 0, it means a draw game. In this case, the board will be given a value of 0. Algorithm 2 presents the pseudo code of the DTC evaluation.

Algorithm 2
DTC_Evaluation (board)

1. idx ← FindDtcIndex(board);

2. state ← dtcTable[idx];

3. if (state == 0)

4. return 0;

5. else if (state > 0)

6. return winValue − weight×(state − 1);

7. else

8. return loseValue − weight×(state + 1);

6. Experiments and results

The experimental environment of the development of our program Fuchou is as follows: CPU: INTEL i7-6700K 4.0 GHz, GPU: NVIDIA GeForce GTX 1080Ti, RAM: 24 GB DDR4 2400 MHz, Hard Drives: INTEL SSD 535 Series 240 GB.

We designed two experiments. In Experiment 1, we randomly generate 1000 10-pieces Surakarta boards. In order to test the performance of the DTC endgame tablebase, we let FuChou with the endgame tablebase play with FuChou without the endgame tablebase starting from those generated boards, alternating Black or White first, taking turns, and totally derive 4000 game results of win, lose or draw. In addition, we also want to know whether more pieces boards will have different performance since we only have the 5-pieces endgame tablebase. Hence in Experiment 2, we randomly generate 1000 12-pieces Surakarta boards for testing.

Although we generate the boards randomly, in order to avoid the boards having an obvious advantage for one side, we only generate the boards with the condition that the difference of the number of pieces between two sides is not more than 4. So Experiment 1 only generates boards with a ratio of 3:7, 4:6, 5:5, 6:4, or 7:3 for both sides. Experiment 2 only generates boards with a ratio of 4:8, 5:7, 6:6, 7:5 or 8:4 for both sides.

Besides, we used the following manner to run all the experiments. Starting from the initial board, the two programs will execute the Aspiration Search with a depth of 8 to 10 to play with each other until the game is ended.

The player capturing all of the opponent’s pieces wins the game. We apply the threefold repetition rule to check the end of the game. Experiment 1 took about 9 hours to play the 4000 games, and Experiment 2 took about 28 hours to play the 4000 games.

6.1. Experiment 1: The effect of DTC tablebase

In this experiment, we use 1000 boards to let FuChou with DTC tablebase play 4000 games with FuChou without DTC tablebase. The number of wins, draws, and loses of FuChou with DTC tablebase are 2115, 12, and 1873, respectively.

We see that the version with DTC tablebase has more number of wins and has a win rate of 52.88% due to the fact that many boards take advantage of the DTC tablebase to select more correct moves. The version without DTC tablebase suffers from lacking the information, and therefore gets more number of loses.

6.2. Experiment 2: The effect of different number of pieces

This experiment want to check if the boards with more pieces are less likely to use the DTC tablebase and the performance will degrade. Similarly, we let the two versions play the 12-pieces boards for 4000 games. The number of wins, draws, and loses of FuChou with DTC tablebase are 2129, 14, and 1857, respectively.

The DTC version gets 53.23% win rate and is close to the results of Experiment 1. These experiments present the obvious advantages of using endgame tablebase because the value of endgame board is accurate and the evaluation of the endgame board is not needed.

7. Concluding remarks

In this paper, a bijective function is developed to map a Surakarta board position to a unique address of the endgame tablebase. The function is one-to-one and onto and can be computed very quickly compared to conventional methods. Our method can also be applied to other kinds of games such as Checkers and Breakthrough where both players have only one kind of pieces. At the present, we don’t deal with the fourfold symmetry of the board. If we apply Thompson’s (1991; 1996) method to confine one particular piece to a specified area by horizontal, vertical, or diagonal reflections, then it seems that we can further reduce the size of the endgame tablebase to one sixth (6/36) of the original size. However, this is not true because Thompson’s method can only save the time to generate lots of symmetric boards and cannot save the total space used. On the other hand, Thompson’s method needs extra computation cost and should be taken into account in the implementation.

When to use the endgame tablebase? Basically, there are two situations. The first is when the board has only n or less pieces, then the program can always access the endgame tablebase to optimally play the game. In this case, the computation cost for dealing with the fourfold symmetry is minor.

The second is when using game search algorithm a piece is captured and the board has only n pieces, then it is the time to access the endgame tablebase. In this case, the total computation cost for dealing with the fourfold symmetry for all the searched boards is quite huge.

Finally, we would like to thank all the reviewers for their detailed comments and suggestions. One reviewer suggests the following idea: “It is still possible to exploit some form of symmetry. Without loss of generality you can only consider positions in which white has equal or more pieces than black. If in the actual game black has more pieces, you can just switch the colors around and look up the value. This might conflict with the current turn though.” For this insightful suggestion, our reply is this can only deal with the cases of the first player (white) having more pieces than the second player (black). If in the actual game the first player is black and black has more pieces, we surely can just switch the colors around and look up the value. However, if in the actual game the first player is black and black has less pieces, indeed we cannot just switch the colors around and look up the value. This will let the second player become the first player and will result in a wrong decision.

The review also suggests the following idea: “You can also save a little bit of space by assuming that the pieces on the highest position number (Fig. 5) is always white, and switch the colors around if this is not the case. This halves your size.” For this suggestion, our reply is as follows. Assume that the pieces on the highest position number (Fig. 5) is always white and the first player is white to look up the value. Then for a board being not the case, we switch the colors and the second player will become the first player and will also result in a wrong decision.

Since 2016, our program FuChou attended many Surakarta tournaments and won the silver medal at TAAI 2016, ICGA 2017, TAAI 2017, ICGA 2018 and the gold medal at TCGA 2017.

Footnotes

Acknowledgements

This research was supported in part by a grant MOST 106-2221-E-003-027-MY2 from Ministry of Science and Technology, R.O.C.

References

Adelson-Velsky, G., Arlazarov, V., Bitman, A., Zhivotovsky, A. & Uskov, A. (1970). Programming a computer to play chess. Russian Mathematical Surveys, 25, 221–262. doi:10.1070/RM1970v025n02ABEH003792.

Allis, L.V., van den Herik, H.J. & Huntijens, M.P.H. (1994a). Go-Moku and Threat-Space Search. Interview Questions.

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

Chen, B.N., Chang, H.J., Hsu, S.C., Chen, J.C. & Hsu, T.S. (2014). Advanced meta-knowledge for Chinese chess endgame knowledge bases. ICGA Journal, 37(1), 17–24. doi:10.3233/ICG-2014-37103.

Chen, J.C., Fan, G.Y., Chang, H.J. & Hsu, T.S. (2018). Compressing Chinese dark chess endgame databases by deep learning. IEEE Transactions on Games. doi:10.1109/TG.2018.2802484.

Coulom, R. (2006). Efficient selectivity and backup operators in Monte-Carlo tree search. In 5 ^th International Conference on Computers and Games (pp. 72–83).

Endgame Tablebases, chessprogramming, URL: https://chessprogramming.wikispaces.com/Endgame+Tablebases.

Kaindl, H., Shams, R. & Horacek, H. (1991). Minimax search algorithms with and without aspiration windows. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(12), 1225–1235. doi:10.1109/34.106996.

Knuth, D.E. & Moore, R.W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6, 293–326. doi:10.1016/0004-3702(75)90019-3.

10.

Kocsis, L. & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In 15 ^th European Conference on Machine Learning (pp. 282–293).

11.

Marsland, T. & Campbell, M. (1982). A Study of Parallel Tree Search Algorithms. Technical Report TR 82-4, Computing Science Department, University of Alberta.

12.

Nalimov, E. (1998). Nalimov’s TBs: One question by Eugene Nalimov, Computer Chess Club, November 18, 1998. URL: https://www.stmintz.com/ccc/index.php?id=33351.

13.

Schadd, M.P.D. (2011). Selective Search in Games of Different Complexity. Ph.D. Thesis, Department of Knowledge Engineering, Maastricht University, Maastricht, The Netherlands.

14.

Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Graepel, T., Lillicrap, T., Leach, M., Kavukcuoglu, K. & Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529, 484–489. doi:10.1038/nature16961.

15.

Ströhlein, T. (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich, German.

16.

Thompson, K. (1991). Chess endgames. ICCA Journal, 14(1), 22.

17.

Thompson, K. (1996). 6-piece endgames. ICCA Journal, 19(4), 215–226.

18.

Winands, M.H.M. (2016). The Surakarta bot revealed. In

Cazenave ,

Winands ,

Edelkamp ,

Schiffel,

Thielscher and

Togelius (Eds.), Computer Games. CGW 2015, GIGA 2015. Communications in Computer and Information Science (Vol. 614). Cham: Springer.

19.

Zhang, L. & Ding, L. (2011). A storage structure and capture judging algorithm of realizing the computer game program of Surakarta chess. In Proc. 23 ^th Chinese Control and Decision Conference , Mianyang (pp. 3442–3445).

1.	Set start and end.
2.	Set lastVal as 0.
3.	for depth from start to end
4.	Set Δ.
5.	alpha ← lastVal − Δ
6.	beta ← lastVal + Δ
7.	value ← $α β$ (alpha, beta, depth)
8.	if value ⩽ alpha
9.	value ← $α β$ ( $- \infty$ , alpha, depth)
10.	else if value ⩾ beta
11.	value ← $α β$ (beta, ∞, depth)
12.	lastVal ← value
13.	end for

1.	idx ← FindDtcIndex(board);
2.	state ← dtcTable[idx];
3.	if (state == 0)
4.	return 0;
5.	else if (state > 0)
6.	return winValue − weight×(state − 1);
7.	else
8.	return loseValue − weight×(state + 1);