An investigation of strength analysis metrics for game-playing programs: A case study in Chinese dark chess

Abstract

For developers of game-playing programs, it is an important but non-trivial task to measure the strengths of the programs, especially with respect to the theoretically optimal players. The optimal players are hard to obtain in practice since many real-world games are too hard to solve entirely. In this paper, a reduced version of Chinese dark chess (CDC), $2 \times 4$ CDC, which has been solved, is used as a testbed to analyze the strengths of game-playing programs for CDC, a non-deterministic game. Absolute strength is then defined to be the win rates against the optimal player. Experiment results show that win rates against designated baseline programs are a good metric, since these win rates are highly correlated to absolute strengths. The stronger the designated baseline programs are, the higher the correlations of win rates are to the absolute strengths. In addition, it is shown that prediction rates and mean squared errors are other good metrics and have high correlations to the absolute strengths. The experiment results also show that the win rates obtained in $2 \times 4$ CDC have a high correlation to those in the original $4 \times 8$ CDC, except for those using the technique of progressive bias.

Keywords

Chinese dark chess strength analysis optimal player game-playing program

1. Introduction

When developing game-playing programs, one important thing is to measure the strengths of the programs. Assuming that an optimal player exists, a program’s absolute strength can be measured by the win rate playing against the optimal player. However, it is impractical to expect access to such optimal players in many real-world games since these games are too complex to solve entirely (Kishimoto & Mueller, 2015; van den Herik et al., 2002). Thus, for the strength analysis of game-playing programs of these games in practice, many researchers used win rates as well as some other metrics such as prediction rates and mean squared errors to measure their strengths.

The first goal of this paper is to analyze the correlation between these practically measured strengths and absolute strengths for the game of Chinese dark chess (CDC), a non-deterministic game normally played on a $4 \times 8$ board, as a case study. A strong correlation implies that the practically measured strengths can be used to represent the absolute strengths. The analysis was done on the solved $2 \times 4$ CDC (Chang & Hsu, 2014), a reduced version of CDC. The experiment results showed that for MCTS-based programs that utilized techniques such as early playout terminations, implicit minimax backups, quality-based rewards, and progressive bias (Hsueh et al., 2016), the win rates playing against available baseline players indeed had high correlations to their absolute strengths in $2 \times 4$ CDC. The stronger the designated baseline player (with respect to the optimal player), the higher the correlation coefficient was. Thus, it can be concluded that the win rates playing against a reasonably strong player can reflect the absolute strengths. The experiments also showed that prediction rates to expert moves and mean squared errors of values of positions were also good metrics of the programs’ strengths, though these metrics were less accurate compared with win rates against designated players.

The second goal is to investigate whether the win rates obtained in reduced and small-sized games can be used to predict those in the full-sized games, since games with smaller sizes usually share similar properties to the original ones. A strong correlation in this case implies that new algorithms can be tested in small-sized games instead of full-sized games to save time. The experiment results showed that most of the win rates of the MCTS-based programs (Hsueh et al., 2016) obtained in $2 \times 4$ CDC can be used to predict those in $4 \times 8$ CDC, except for the variations that used the technique of progressive bias.

The rest of the paper is structured as follows. Sect. 2 describes background knowledge including the game of CDC, the reduced $2 \times 4$ CDC and how it was solved, and Monte-Carlo tree search. Sect. 3 illustrates in more detail three metrics: win rates against a designated player, prediction rates to expert moves, and mean squared errors of values of positions. Sect. 4 then contains the experiment results and discussions on the three metrics in $2 \times 4$ CDC. Sect. 5 analyzes projecting the win rates obtained in $2 \times 4$ CDC to those in $4 \times 8$ CDC. Finally, Sect. 6 makes concluding remarks. Detailed experiment results are included in Appendix A, and simple linear regression is described in Appendix B.

2. Background

2.1. Chinese dark chess (CDC)

Chinese dark chess (CDC) (B.-N. Chen et al., 2010; Hsueh et al., 2016; Yen et al., 2015) is a two-player zero-sum non-deterministic game which uses the same set of pieces as Chinese chess. The two players, red and black, respectively own one king (K/k), two guards (G/g), two ministers (M/m), two rooks (R/r), two knights (N/n), two cannons (C/c), and five pawns (P/p). The uppercase and lowercase letters are abbreviations for red and black pieces respectively.

The game is played on a $4 \times 8$ square board. At the start of the game, all 32 pieces are randomly shuffled, then placed face-down in the squares, as shown in Fig. 1(a). Pieces are referred to as unrevealed pieces if they are faced-down, or revealed pieces when they are facing up. The first player begins by revealing any unrevealed piece. The revealed piece, and the set of pieces with the same color as this piece, is now owned by the first player. The second player owns the other set. Information conveyed by the revealed pieces are observable by both players. Both players in their own turn can either reveal an unrevealed piece, which is called a flipping action, or move one of their own revealed pieces, which is called a moving action. Note that it is possible for a player to flip and reveal enemy pieces, which the player’s opponent can move immediately in the proceeding turn. A flipping action is denoted by S(?) where S is the source square. For example, c4(?) indicates a flipping action at c4 in Fig. 1(b). A moving action is denoted by S–D where S and D are source and destination squares.

Fig. 1.

(a) The initial position and (b) an example of position for CDC.

All pieces can be moved to any of its adjacent empty squares. Pieces other than cannons can be moved to an adjacent square to capture an opponent piece. Whether a piece can capture another piece depends on its and its opponent piece’s ranks, which, from the highest to the lowest, are kings, guards, ministers, rooks, knights, cannons, and pawns. Generally, pieces can capture opponent pieces with equal or lower ranks. Three exceptions are illustrated as follows. First, kings cannot capture pawns. Second, pawns can capture kings. Third, cannons can capture all types of opponent pieces but need to jump over exactly one piece in the same row or the same column, which is called one-step-jump. An example for one-step-jump is shown in Fig. 1(b), where the black cannon (c) at d4 can capture the red rook (R) at a4 or the red minister (M) at d8. Finally, when one player captures all the opponent pieces or when the opponent has no legal move, the player wins. When both players neither capture nor reveal any piece within 40 moves or repeat the same position three times, the game ends as a draw.

CDC is one of the games played in the Computer Olympiad since 2010 (Hsueh & Wu, 2015; Tseng et al., 2017; van den Herik et al., 2012; Yen et al., 2010, 2013). Many programs were developed based on alpha-beta search (Chang et al., 2017; B.-N. Chen et al., 2010; J.-C. Chen et al., 2018; Yen et al., 2010). MCTS was first applied to CDC by Yen et al. (2015). Hsueh et al. (2016) further improved an MCTS-based game-playing program by incorporating four techniques, described in more detail in Sect. 2.3.

2.2. The solved

2 \times 4

CDC

A reduced version of CDC, $2 \times 4$ CDC, has been devised and solved by Chang & Hsu (2014). The major difference between $2 \times 4$ CDC and the original version lies in the board size and the set of used pieces. In addition to the board size, the used pieces in $2 \times 4$ CDC only considered 24 fair and equivalent material combinations (combinations of pieces) as listed in Table 1. By fair, both players have the same set of pieces at the beginning of a game. For example, “KGGM vs. kggr” is not listed in Table 1 since two players have different sets of pieces. By equivalent (J.-C. Chen et al., 2015), material combinations with the same relations between pieces are only counted once. For example, “KGGR vs. kggr” is not listed in Table 1 since it has the same piece relations as “KGGM vs. kggm.”

All legal positions were assigned theoretical values from retrograde analysis (Chang & Hsu, 2014). In their work, expected win rates were used as theoretical values. If a position does not contain any unrevealed piece or only one unrevealed piece type remains, the game becomes deterministic. Thus, the theoretical value is 1, 0, or $- 1$ which represents a win, a draw, or a loss respectively from the view point of the player to move. An example position is shown in Fig. 2(a), where the result is a win for the black player. Since CDC is actually a non-deterministic game – a flipping action with different piece types may result in different game outcomes – for each position, the theoretical value ranges from $- 1$ to 1 where $- 1$ and 1 were 100% losses and 100% wins respectively from the view point of the player to move. For example, assuming that it is the red player’s turn in the position in Fig. 2(b), the theoretical value is 0.0958 according to Chang & Hsu (2014), which shows a slight advantage toward the red player. Note that a theoretical value of 0 does not represent a necessary draw, it may also represent the situation with 50% wins and 50% losses.

Table 1
24 fair and equivalent material combinations in $2 \times 4$ CDC

KGGM vs. kggm KGGC vs. kggc KGGP vs. kggp KGMM vs. kgmm

KGMR vs. kgmr KGMC vs. kgmc KGMP vs. kgmp KGCC vs. kgcc

KGCP vs. kgcp KCCP vs. kccp KCPP vs. kcpp KPPP vs. kppp

GGMM vs. ggmm GGMR vs. ggmr GGMC vs. ggmc GGCC vs. ggcc

GGCP vs. ggcp GMCP vs. gmcp GCCP vs. gccp GCPP vs. gcpp

GPPP vs. gppp CCPP vs. ccpp CPPP vs. cppp PPPP vs. pppp

Fig. 2.

Examples of positions in $2 \times 4$ CDC from a game of “KGCP vs. kgcp” (a) without and (b) with chance events.

2.3. Monte-Carlo tree search (MCTS)

Monte-Carlo tree search (MCTS) (Browne et al., 2012) is a kind of best-first search where states are evaluated by Monte Carlo simulations. One popular implementation in practice is upper confidence bounds applied to trees (UCT) (Kocsis & Szepesvári, 2006) which applies upper confidence bounds (UCB) (Auer et al., 2002) at selection phase, one of the four phases in MCTS. The UCB function is shown as follows: $\begin{matrix} (1) & {UCB}_{i} = Q_{i} + C \sqrt{\frac{ln N}{n_{i}}}, \end{matrix}$ where $Q_{i}$ is the estimated value of node i which is usually a win rate or a mean value of rewards for the position corresponding to node i, C the coefficient balancing exploration and exploitation, N the visit count of the parent of node i, and $n_{i}$ the visit count of node i.

To generate a move, MCTS usually consists of several iterations (or simulations). Each iteration contains four phases, selection, expansion, playout, and backpropagation. The selection phase follows the above UCB formula to traverse UCT until a leaf is reached. During the expansion phase, one or more children from the leaf is expanded. A playout policy is then used to play the game to the end, obtaining a game outcome in the process. Backpropagation then refers to the process of updating this outcome of the playout to all nodes traversed during selection. As for playout policies, the simplest one is to randomly select a move. More sophisticated playout policies were used to make the playouts cleverer for CDC (Hsueh et al., 2016; Yen et al., 2015). They used piece weights, as an example listed in Table 2, to calculate scores for moves when captures and/or escapes happened. Roulette-wheel selections were then applied to select moves according to their scores.

Hsueh et al. (2016) further incorporated four techniques into an MCTS-based CDC program to improve the playing strength. The four techniques were early playout terminations, implicit minimax backups, quality-based rewards, and progressive bias, respectively introduced in the following four subsections.

2.3.1. Early playout terminations

The technique of early playout terminations (EPT) terminates playouts before the end of games. For CDC, Hsueh et al. (2016) terminated playouts immediately and returned the corresponding outcomes whenever a material combination of a position is very likely to win (e.g., the player has a king and a guard while the opponent has only two ministers), or very likely to draw (e.g., the player has only one guard while the opponent has two ministers). In their article, all material combinations were analyzed manually for EPT, and labeled as likely wins, likely draws, likely losses, or unknown.

The advantages of EPT were to speed up and make the outcomes of playouts more accurate. In their experiments, they also reversed the outcomes for those positions with likely wins and likely losses with a probability of ε to show the importance of the accuracy of the outcomes of playouts. Clearly, when ε was 0, EPT performed best and obtained a win rate of 60.75% (± 2.76%) against the original program. Note that these programs were run with 30,000 simulations per move, and the same for all experiments mentioned in the rest of this section.

2.3.2. Implicit minimax backups

The technique of implicit minimax backups (IMB) was proposed by Lanctot et al. (2014). The objective was to help MCTS deal with tactical positions by introducing minimax scores from heuristic evaluations of positions. The $Q_{i}$ in the UCB formula (Formula (1)) was modified as $\begin{matrix} (2) & Q_{i}^{IMB} = (1 - α) Q_{i} + α m_{i}, \end{matrix}$ where $m_{i}$ is the minimax score of node i which is mapped to the same range of $Q_{i}$ , and α the weight of the minimax score.

The heuristic evaluation function for CDC used by Hsueh et al. (2016) was the weighted material sum, namely the difference of the total piece weights between the player and the opponent. The piece weights were also the ones in Table 2. The minimax scores of chance nodes were weighted according to visit counts instead of probabilities of unrevealed pieces. The experiment results showed that with $α = 0.3$ , IMB had a win rate of 70.90% (± 2.42%) against the original program.

Table 2
Piece weights for CDC used by Hsueh et al. (2016)

Piece type K/k G/g M/m R/r N/n C/c P/p

Weight 55 50 25 10 8 30 8

2.3.3. Quality-based rewards

The technique of quality-based rewards was proposed by Pepels et al. (2014). The rewards of wins and losses obtained in simulations were adjusted according to simulation lengths (SL) or terminal state qualities (TSQ) collected online. Simulation length was the length of the game in the simulation from the root to the end. Terminal state quality used by Hsueh et al. (2016) for CDC was the remaining number of pieces with considering piece weights, $\begin{matrix} (3) & | S | + c_{w} \sum_{i \in S} ω_{i}, \end{matrix}$ where S is the set of remaining pieces of the winner, $| S |$ the number of remaining pieces of the winner, $c_{w}$ the coefficient representing the importance of piece weights, and $ω_{i}$ the weight of piece i as listed in Table 2. The adjusted rewards were then calculated by $\begin{matrix} (4) & R^{new} = R + sign (R) \times a \times b (λ), \end{matrix}$ where R is the original reward (1 for a win and $- 1$ for a loss), a the coefficient deciding the largest range of adjustment, and $b (λ) = - 1 + 2 / (1 + e^{- k λ})$ a function scaling the value of λ to $[- 1, 1]$ where k is a parameter. In Formula (4), λ, normalized values, for SL and TSQ are $λ_{SL} = (μ_{SL}^{p} - l) / σ_{SL}^{p}$ and $λ_{TSQ} = (t - μ_{TSQ}^{p}) / σ_{TSQ}^{p}$ respectively where $μ_{SL}^{p}$ , $σ_{SL}^{p}$ , $μ_{TSQ}^{p}$ and $σ_{TSQ}^{p}$ are sample means and sample standard deviations of simulation lengths and terminal state qualities for player p, and l and t the length and the terminal state quality of the simulation. The experiments by Hsueh et al. (2016) showed that SL ( $a = 0.25$ and $k = 7$ ) and TSQ ( $a = 0.3$ , $k = 11$ and $c_{w} = 0.02$ ) had win rates of 57.50% (± 2.77%) and 59.00% (± 2.78%) against the original program.

2.3.4. Progressive bias

The technique of progressive bias (PB) was proposed by several researchers with different forms (Chaslot et al., 2008; Ikeda & Viennot, 2014; Nijssen & Winands, 2011). The idea was to use available heuristics to guide selections among nodes with few simulations. Hsueh et al. (2016) extended the UCB formula (Formula (1)) to: $\begin{matrix} (5) & Q_{i} + C \sqrt{\frac{ln N}{n_{i}}} + c_{p} \times \frac{H_{i}}{{count}_{i}}, \end{matrix}$ where $H_{i}$ is the heuristic score of the move to node i, $c_{p}$ the coefficient representing the influence of the heuristics, and ${count}_{i}$ a counter corresponding to node i. Hsueh et al. (2016) experimented six forms of ${count}_{i}$ , including $n_{i}$ , $\sqrt{n_{i}}$ , $ln (n_{i} + 1)$ , $l_{i}$ , $\sqrt{l_{i}}$ , and $ln (l_{i} + 1)$ where $l_{i}$ is the loss count of node i.

The heuristic scores of moves designed by Hsueh et al. (2016) for CDC used some basic heuristics including capturing opponent pieces, escaping the player’s pieces, and suiciding the player’s pieces. These basic heuristics are collectively referred to in the remainder of this paper as $H^{B}$ . In addition, they also used advanced heuristics including curbing opponent pieces, which will be referred to as $H^{C}$ , and calculating scores for flipping actions, referred to as $H^{F}$ . The heuristics were experimented incrementally as follows, denoted by $H^{B}$ , $H^{B} + H^{C}$ , and $H^{B} + H^{C} + H^{F}$ . The experiment results showed that with $H^{B} + H^{C} + H^{F}$ and the settings, ${count}_{i} = \sqrt{n_{i}}$ and $c_{p} = 0.1$ , PB had a win rate of 82.10% (± 1.98%) against the original program.

3. Investigated strength analysis metrics

3.1. Win rates playing against a designated player

For game-playing programs, win rates against designated players are commonly used as a metric to measure the strengths of the programs. It is usually claimed that the higher the win rate obtained, the stronger the program is (Tesauro, 1995). Playing against human players is also a way (Campbell et al., 2002; Silver et al., 2016, 2017; Tesauro, 1995); however, since it is too slow to obtain statistically significant results (Tesauro, 1995), usually, the designated players are computer programs, often called baseline programs.

Baseline programs in practice can be a random player (randomly make a move), an early version of the tested program, or other available programs. Usually, random players are weak and are easily defeated. In the past, when demonstrating the strengths of new algorithms or heuristics, usually they were made to play against early versions of the tested programs (Chaslot et al., 2008; B.-N. Chen et al., 2010; Gelly & Silver, 2007; Hsueh et al., 2016; Lanctot et al., 2014; Nijssen & Winands, 2011; Pepels et al., 2014; Runarsson & Lucas, 2014; Silver et al., 2016, 2017; Tian & Zhu, 2016; Yen et al., 2015). Sometimes, they were made to play against other openly available programs (Chaslot et al., 2008; Coulom, 2007; Gelly & Silver, 2007; Ikeda & Viennot, 2014; Lanctot et al., 2014; Silver et al., 2016, 2017; Tian & Zhu, 2016; Yen et al., 2015).

However, it is still a question whether and how much the win rates can reflect the absolute strengths of the tested programs. In the solved $2 \times 4$ CDC, since theoretical values of all positions are known, there exists an optimal player which always selects best moves, defined as the moves leading to the highest theoretical value. This optimal player can serve as the baseline program. More specifically, theoretical values of moves are determined as follows. For a moving action, the theoretical value directly comes from the position after moving. For a flipping action, the theoretical value is the weighted average for unrevealed pieces based on the probability distribution of these unrevealed pieces. For example, the move b1(?) in Fig. 3 has a theoretical value of 0.000 which is the weighted average of the theoretical values of the three possibilities G ( $0.167 \times 2 / 4$ ), k ( $0.333 \times 1 / 4$ ), and p ( $- 0.667 \times 1 / 4$ ).

Fig. 3.

A partial tree with theoretical values of positions in the red player’s view from a game of “KGGP vs. kggp” where one of the two g’s as well as the P are captured and it is the red player’s turn at the root position.

Note that, for deterministic positions with wins or losses, the theoretical values did not provide information of distances to win or loss (Chang & Hsu, 2014). Thus, the optimal player does not take into consideration shortest wins and longest losses. In addition, the optimal player does not take into consideration whether a move is risky or not. For the example in Fig. 3, the move b1(?) has a theoretical value of 0.000 from the red player’s view, which is as good as the move a2–a1. Thus, the optimal player just randomly chooses from the two moves. However, the move b1(?) is riskier since the red player has a probability of ¼ to flip the p at b1 which will lead to a highly disadvantageous situation.

3.2. Prediction rates to expert moves

Assuming that a set of positions with moves played by experts (optimal players at best) are available, prediction rates to those expert moves are commonly used to analyze and measure strengths of programs (Chang et al., 2015; Coulom, 2007; Lai, 2015; Liskowski et al., 2018; Runarsson & Lucas, 2014; Silver et al., 2016, 2017; Tian & Zhu, 2016). The prediction rate of a program is the probability that the moves selected by the program match expert moves. For example, moves from game records played by human players were used as expert moves in the game of Go (Coulom, 2007; Silver et al., 2016, 2017; Tian & Zhu, 2016) and Othello (Liskowski et al., 2018; Runarsson & Lucas, 2014). In some cases, the moves generated by a program with much deeper search also served as expert moves. For example, Lai (2015) used the moves from a program with time-limited searches as expert moves in chess.

In $2 \times 4$ CDC, since theoretical values of all positions are known, best moves can be used to derive the prediction rate. It is possible that a position has more than one best move. An example is shown in Fig. 3 where the moves a2–a1 and b1(?) are all best moves. In this case, selecting any of these moves is said to match the best moves. As explained in Sect. 3.1, the theoretical values cannot distinguish shorter wins or longer losses from wins or losses. Thus, if more than one move leads to a win, all are considered as best moves. Prediction rates of best moves were measured by Chang et al. (2015) for a basic MCTS program in $2 \times 4$ CDC. However, only positions within the first two moves of a game were tested.

If a program has a high prediction rate to the expert moves, it can be said that the strength of the program is close to the experts’ and thus can be inferred as a strong program. However, any moves not matching expert moves do not necessarily indicate sub-optimal plays for the following two reasons. First, the expert moves (from human players or programs) may not be the theoretically best moves. Second, it is possible that there exist several equally good moves given a position, but only the one selected by the expert is counted as an expert move. An example that stronger programs have lower prediction rates is shown by Silver et al. (2017) for the game of Go, where AlphaGo Zero had much higher win rates but lower prediction rates to moves by professional players (cf. Figs 3 and 4 by Silver et al. (2017)).

3.3. Mean squared errors of values of positions

Assuming that a set of positions with ground-truth values (theoretical values under best circumstances) are available, mean squared errors between the given ground-truth values and the values estimated by game-playing programs can be used to analyze the strengths of the programs (Gelly & Silver, 2007; Silver et al., 2016, 2017). The mean squared error of a program on a given set of positions P and the corresponding ground-truth values ${v_{p}}_{p \in P}$ is calculated as $\begin{matrix} (6) & MSE = \frac{1}{| P |} \sum_{p \in P} {({\hat{v}}_{p} - v_{p})}^{2}, \end{matrix}$ where $| P |$ is the number of positions in P and ${\hat{v}}_{p}$ the value of position p estimated by the program.

In $2 \times 4$ CDC, theoretical values of all positions are known and can be used to serve as the ground-truth values. However, since it is hard for many games to obtain their theoretical values, usually the outcomes of the games played by experts or reasonably strong programs were used instead (Silver et al., 2016, 2017; Takeuchi et al., 2010). Using the outcomes of the games meant that $v_{p}$ for all positions in a game were set to the outcome of the game. In addition, Takeuchi et al. (2010) labeled the values of positions by the theoretical values if exhaustive search can be finished in a reasonable time.

If a program has a low mean squared error of values of positions, it means that the program understands the positions better and thus is usually stronger. Mean squared errors were shown to have a strong correlation to the strengths of programs (Gelly & Silver, 2007; Silver et al., 2017).

4. Experiments for $2 \times 4$ CDC

In the experiments, all analyzed CDC programs were based on MCTS with different techniques or different parameters (Hsueh et al., 2016). Although the programs were originally written to play $4 \times 8$ CDC, it was generalized to different board sizes. All techniques incorporated by Hsueh et al. (2016) for $4 \times 8$ CDC were directly applied to $2 \times 4$ CDC. In total, the strengths of 129 program settings, as listed in Table 3, were analyzed. The program settings generally followed the experiments by Hsueh et al. (2016). All of the experiments were run on machines equipped with Intel (R) Core(TM) i5-3570K CPU 3.40 GHz with 8 GB memory.

In the following subsections, for each of the settings of MCTS above, win rates are collected given five different baseline programs in Sect. 4.1, prediction rates are collected given three different sets of expert moves in Sect. 4.2, and mean squared errors are collected given three different sources of ground-truth values in Sect. 4.3. All the detailed values of win rates, prediction rates, and mean squared errors are presented in Appendix A.

Table 3
Details of the 129 analyzed program settings for $2 \times 4$ CDC

Incorporated technique Number of simulations per move Settings of parameters

None 1, 10, 100, 500, 1,000, 2,000, 5,000, 10,000, 20,000, 30,000, 50,000, 100,000, 200,000 None

EPT 1,000
30,000 $ε \in {0, 0.05, 0.1, 0.2, 0.3, 0.4}$

IMB $α \in {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}$

SL $(a, k) \in {0.2, 0.25, 0.3} \times {3, 5, 7, 9, 11}$

TSQ $a = 0.3$ , $k = 11$ , $c_{w} \in {0, 0.01, 0.02, 0.03, 0.04}$
$a = 0.3$ , $c_{w} = 0.02$ , $k \in {7, 9, (11,) 13, 15}$
$k = 11$ , $c_{w} = 0.02$ , $a \in {0.2, 0.25, (0.3,) 0.35}$

PB $H^{B}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$
$H^{B} + H^{C}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$
$H^{B} + H^{C} + H^{F}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$

Incorporated technique	Number of simulations per move	Settings of parameters
None	1, 10, 100, 500, 1,000, 2,000, 5,000, 10,000, 20,000, 30,000, 50,000, 100,000, 200,000	None
EPT	1,000 30,000	$ε \in {0, 0.05, 0.1, 0.2, 0.3, 0.4}$

IMB	$α \in {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}$

SL	$(a, k) \in {0.2, 0.25, 0.3} \times {3, 5, 7, 9, 11}$

TSQ	$a = 0.3$ , $k = 11$ , $c_{w} \in {0, 0.01, 0.02, 0.03, 0.04}$ $a = 0.3$ , $c_{w} = 0.02$ , $k \in {7, 9, (11,) 13, 15}$ $k = 11$ , $c_{w} = 0.02$ , $a \in {0.2, 0.25, (0.3,) 0.35}$

PB	$H^{B}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$ $H^{B} + H^{C}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$ $H^{B} + H^{C} + H^{F}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$

4.1. Win rates

This subsection investigates whether the win rates against practical and available baseline programs are correlated to the win rates against the optimal player (absolute strengths). In the experiments, the win rate of a program against a designated baseline program was obtained in the following way. The program played against the designated baseline program 1,000 games, with altering turns playing first, in each of the 24 combinations as listed in Table 1. Its win rate was the average score of the 24,000 games where a win was counted as 1, a draw as 0.5, and a loss as 0.

In $2 \times 4$ CDC, five baseline programs were considered. The first was the optimal player (OPT) as described in Sect. 3.1. The second was a four-ply1

¹
Six-ply EMM ran about 150 times slower than that of four-ply. Due to time constraints, experiments on EMM with more plies were not conducted.

expectiminimax player (EMM) (Russell & Norvig, 2009) using weighted material sum (as described in Sect. 2.3.2) as heuristic evaluation. EMM had a win rate of 35.22% (± 0.57%) against OPT. The remaining three baseline programs were the original MCTS with 1,000, 5,000, and 30,000 simulations per move (MCTS-1k, MCTS-5k, and MCTS-30k), which had win rates of 37.67% (± 0.57%), 43.41% (± 0.57%), and 46.78% (± 0.58%) against OPT respectively. The five baseline programs from the weakest to the strongest were EMM, MCTS-1k, MCTS-5k, MCTS-30k, and OPT. In the experiments, EMM was intentionally included to have a baseline program not based on MCTS but also practically available.

In order to analyze the correlation between win rates against practical and available baseline programs and those against OPT, each of the 129 program settings (listed in Table 3) played against the five baseline programs respectively. For these program settings, let WR_OPT, WR_EMM, WR_1k, WR_5k and WR_30k be the win rates respectively against OPT, EMM, MCTS-1k, MCTS-5k, and MCTS-30k. Figure 4(a)–(d) show respectively WR_EMM, WR_1k, WR_5k, and WR_30k with respect to the absolute strength WR_OPT for all program settings. These plots show very highly positive correlations whose correlation coefficients r (Asuero et al., 2006; Lane et al., 2014), described in more detail in Appendix B, were 0.9633, 0.9790, 0.9880, and 0.9922 respectively. The stronger the baseline program was, the higher the correlation coefficient obtained. The sample standard errors (Lane et al., 2014) with respect to the predicted lines (the dotted lines in Fig. 4) were 1.57%, 1.19%, 0.90%, and 0.73% respectively. Appendix B describes more on the sample standard errors and the predicted lines. The above observations suggested that the baseline program should be as strong as possible in order to obtain accurate strengths of game-playing programs when the optimal player was not available. However, this would be a tradeoff between the accuracy of the metric and the time needed to perform experiments, since a stronger baseline program usually implies more computation time.

Fig. 4.

Scatter plots for (a) WR_EMM, (b) WR_1k, (c) WR_5k, and (d) WR_30k to WR_OPT.

4.2. Prediction rates

This subsection investigates whether the prediction rates to practical and available expert moves are correlated to those to the best moves (moves by OPT), and whether all of these prediction rates are correlated to the absolute strengths (win rates against OPT). A set of 2,400 games, 100 in each of the 24 material combinations listed in Table 1, were collected and about 47,000 positions in the game set were used for experiments on prediction rates.

Three sets of expert moves were considered, the best moves as described in Sect. 3.2, the moves by MCTS-1k, and the moves by MCTS-1M (the original MCTS with 1,000,000 simulations per move). MCTS-1k and MCTS-1M had win rates of 37.67% (± 0.57%) and 49.21% (± 0.58%) against OPT respectively. Note that MCTS-1k was intentionally included to investigate the cases where the quality of the collected expert moves was low. To obtain the prediction rate of a program, the program played moves for the positions in the selected game set. In the experiment, both MCTS-1k and MCTS-1M obtained prediction rates respectively to the best moves with 84.46% (± 0.33%) and 93.31% (± 0.23%). The results clearly showed that MCTS-1M played the best moves more often than MCTS-1k.

In order to analyze the correlation of prediction rates, each of the 129 program settings (listed in Table 3) played moves for the positions in the selected game set. For these program settings, let PR_BEST, PR_1k and PR_1M be the prediction rates respectively to the best moves, the moves by MCTS-1k, and the moves by MCTS-1M. Figure 5(a) and (b) show respectively PR_1k and PR_1M with respect to PR_BEST for all program settings. Note that the values in PR_BEST tended to be higher than those in PR_1k and PR_1M, for the reason that it was easier to match best moves since a position may have multiple best moves as described in Sect. 3.2. From the experiment results, as expected, PR_1k could not reflect PR_BEST well, which only had a correlation coefficient of 0.3938. On the contrary, PR_1M had a highly positive correlation to PR_BEST, which had a correlation coefficient of 0.8998. The sample standard errors with respect to the predicted lines were 3.29% and 1.56%. The results showed that the quality of expert moves influenced the results of prediction rates greatly, and that prediction rates to moves by a stronger program can be used to approximate those to the best moves.

Fig. 5.

Scatter plots for (a) PR_1k and (b) PR_1M to PR_BEST.

Next, the correlation between the prediction rates and the absolute strengths (win rates against OPT) was investigated. Figure 6(a)–(c) show the prediction rates, PR_1k, PR_1M and PR_BEST, with respect to WR_OPT. Similar to those shown in Fig. 5, PR_1k was not a good metric to the absolute strengths either, which only had a correlation coefficient of 0.5159. PR_1M had a very highly positive correlation coefficient of 0.9167 to the absolute strengths. The sample standard errors with respect to the predicted lines were 5.00% and 2.33%. These suggested that when expert moves with high quality were available, prediction rates to those expert moves were good metrics to the strengths of game-playing programs, though not as good as win rates playing against a baseline program as shown in Sect. 4.1. In addition, PR_BEST had a higher correlation to absolute strengths than both PR_1k and PR_1M. Namely, the correlation coefficient of PR_BEST to WR_OPT was 0.9802, and the sample standard error with respect to the predicted line was 1.16%. The analyses showed that the strengths of game-playing programs had strong correlations to the ability to select the best moves.

Fig. 6.

Scatter plots for (a) PR_1k, (b) PR_1M, and (c) PR_BEST to WR_OPT.

4.3. Mean squared errors

For $2 \times 4$ CDC, it is straightforward to use the theoretical values (as described in Sect. 3.3) as the ground-truth values to analyze mean squared errors of given programs. In addition to this set, let the moves played by MCTS-1M be regarded as expert moves, and thus the outcomes of these games be another source of the ground-truth values. The correlation of mean squared errors with different sources of ground-truth values is then analyzed. In addition, this subsection also studies whether all of these mean squared errors are correlated to the absolute strengths (win rates against OPT).

In the experiments, the same set of about 47,000 positions as in Sect. 4.2 was used. Two sources of ground-truth values for these positions were considered, the theoretical values and the outcomes of games from self-plays by MCTS-1M. Namely, a self-play game was performed by MCTS-1M from a given position to the end of the game. The game outcomes, consisting of wins, draws, and losses, were converted to 1’s, 0’s and $- 1$ ’s respectively, and subsequently used as a source of ground-truth values of the positions. Without loss of generality, all of the values were from the red player’s point of view. To obtain a mean squared error of a program, the program ran MCTS on each of the positions in the game set. The value of position p estimated by the program, ${\hat{v}}_{p}$ , was $Q_{i}$ in Formula (1) where i was the root of the search tree corresponding to p. Mean squared errors were then calculated based on the given ground-truth values and the collected ${{\hat{v}}_{p}}$ . Note that mean squared errors were scaled by a factor of ¼ to the range of $[0, 1]$ in this paper. To investigate whether game outcomes with a lower quality influenced the results of mean squared errors, those from self-plays by MCTS-1k were included as the third source of ground-truth values.

In order to analyze the correlation of mean squared errors, each of the 129 program settings (listed in Table 3) ran MCTS on all positions in the game set. For these programs, let MSE_TH, MSE_GO-1k and MSE_GO-1M be the mean squared errors respectively with theoretical values, game outcomes from self-plays by MCTS-1k, and game outcomes from self-plays by MCTS-1M. Figure 7(a) and (b) show respectively MSE_GO-1k and MSE_GO-1M with respective to MSE_TH for all program settings. Note that the values in MSE_TH tended to be lower than those in MSE_GO-1k and MSE_GO-1M, for the reason that the granularity of theoretical values was lower than that of game outcomes. The experiment results showed very highly positive correlation coefficients, 0.9971 and 0.9999, and the sample standard errors with respect to the predicted lines were 0.0008 and 0.0002. These showed that mean squared errors with different sources of game outcomes could predict those with respect to theoretical values well even when the expert had a lower quality such as MCTS-1k.

Fig. 7.

Scatter plots for (a) MSE_GO-1k and (b) MSE_GO-1M to MSE_TH.

Next, the correlation between the mean squared errors and the absolute strengths (win rates against OPT) was investigated. Figure 8(a)–(c) show the mean squared errors MSE_GO-1k, MSE_GO-1M, and MSE_TH with respect to WR_OPT. All showed highly negative correlations, which had correlation coefficients of $- 0.8881$ , $- 0.9080$ , and $- 9078$ respectively, and the sample standard errors with respect to the predicted lines were 2.68%, 2.45%, and 2.45%. Note that the results here showed negative correlations since stronger game-playing programs tended to have lower mean squared errors. Generally, mean squared errors were good metrics to the strengths of game-playing programs, though not as good as win rates playing against a baseline program as shown in Sect. 4.1. However, it was a relatively stable metric compared to prediction rates, since game outcomes with a lower quality did not influence this metric too much.

5. Experiments on predicting win rates in

4 \times 8

CDC from

2 \times 4

CDC

In this section, the absolute strengths of game-playing programs in $2 \times 4$ CDC were used to help analyze the strengths of game-playing programs in $4 \times 8$ CDC. Since games with different board sizes may have similar properties, it is worth investigating whether the experiment results obtained in smaller sizes can be used to predict those in the original size or a bigger size.

The details of the 66 program settings for both $2 \times 4$ and $4 \times 8$ CDC are listed in Table 4. For each program setting, let the two win rates ${WR}_{2 \times 4}$ and ${WR}_{4 \times 8}$ be obtained as follows. ${WR}_{2 \times 4}$ was the win rate against OPT (the optimal player) in $2 \times 4$ CDC which was the average score of 24,000 games as described in Sect. 4.1. ${WR}_{4 \times 8}$ was the win rate against MCTS-30k (the original MCTS with 30,000 simulations per move), also a baseline program used by Hsueh et al. (2016). Most of the win rates in ${WR}_{4 \times 8}$ were presented by Hsueh et al. (2016), where each win rate in $4 \times 8$ CDC was the average score of 1,000 games.

Fig. 8.

Scatter plots for (a) MSE_GO-1k, (b) MSE_GO-1M, and (c) MSE_TH to WR_OPT.

Table 4

Details of the 66 analyzed program settings for both $2 \times 4$ and $4 \times 8$ CDC

Incorporated technique	Number of simulations per move	Settings of parameters
None	2,000, 5,000, 10,000, 20,000, 30,000, 50,000, 100,000, 200,000	None
EPT	30,000	$ε \in {0, 0.05, 0.1, 0.2, 0.3, 0.4}$

IMB		$α \in {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}$

SL		$(a, k) \in {0.2, 0.25, 0.3} \times {3, 5, 7, 9, 11}$

TSQ		$a = 0.3$ , $k = 11$ , $c_{w} \in {0, 0.01, 0.02, 0.03, 0.04}$ $a = 0.3$ , $c_{w} = 0.02$ , $k \in {7, 9, (11,) 13, 15}$ $k = 11$ , $c_{w} = 0.02$ , $a \in {0.2, 0.25, (0.3,) 0.35}$

PB		$H^{B}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$ $H^{B} + H^{C}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$ $H^{B} + H^{C} + H^{F}$ , ${count}_{i} = \sqrt{n_{i}}$ , $c_{p} \in {0.001, 0.01, 0.1, 1, 10}$

Figure 9 shows that ${WR}_{2 \times 4}$ were not highly correlated to ${WR}_{4 \times 8}$ for all program settings listed in Table 4. The correlation coefficient of 0.4552 showed a low positive correlation only, and the sample standard error with respect to the predicted line (the dot-dashed line in Fig. 9) was 14.51% which was high. In addition to a lower correlation coefficient, another reason that the sample standard error here was relatively higher than those in Sect. 4 was that the number of sample data were lower here (66 vs. 129). After checking the distribution of points in Fig. 9, the points at the top-left part (hollow points) were all from the program settings with PB. By removing those related to PB, a much higher correlation was obtained with a correlation coefficient of 0.9481. The sample standard error with respect to the new predicted line (the dotted line in Fig. 9) was 5.27%. In addition, the correlation coefficient for the program settings with PB was 0.7055. Although a high positive correlation was obtained, only 15 sample data were included. The sample standard error with respect to the predicted line (the dashed line in Fig. 9) was 10.15%, which was still high.

Fig. 9.

Scatter plot for ${WR}_{2 \times 4}$ to ${WR}_{4 \times 8}$ where the hollow points are related to program settings with PB.

In brief, ${WR}_{2 \times 4}$ can be roughly used to predict ${WR}_{4 \times 8}$ except for PB. In order to investigate the inconsistency of PB, the win rates from different program settings with PB, shown in Appendix A, were further analyzed. It was observed that PB in $2 \times 4$ CDC obtained higher win rates with $c_{p} = 0.01$ for all of the three experimented heuristics, $H^{B}$ , $H^{B} + H^{C}$ and $H^{B} + H^{C} + H^{F}$ . However, it was $c_{p} = 0.1$ for $4 \times 8$ CDC. Judging by this, it was speculated that heuristic scores of moves might not generalize well to different board sizes. Thus, the heuristics used in PB were further experimented. More specifically, in both $2 \times 4$ and $4 \times 8$ CDC, the strengths of the strongest heuristics $H^{B} + H^{C} + H^{F}$ were measured by the original MCTS with different numbers of simulations per move. In $2 \times 4$ CDC, the program using the heuristics without search had a playing strength approximate to the original MCTS with only 30 simulations per move, where the win rate was 50.41% (± 0.52%). In contrast, the program using the same heuristics without search had a playing strength approximate to the original MCTS with 1,800 simulations per move in $4 \times 8$ CDC, where the win rate was 50.30% (± 2.08%). The results showed that the advantages brought by heuristic scores of moves were much higher in $4 \times 8$ CDC than in $2 \times 4$ CDC. From the above, the inconsistency of PB was conjectured to be a result of the used heuristic scores of moves. However, this should be justified with further research, and therefore is left as an open problem in the future.

6. Conclusions

In this paper, three metrics measuring strengths of game-playing programs are analyzed in a solved game, $2 \times 4$ CDC. The commonly used metric, win rates playing against a baseline program, has been shown to have the highest correlation to the absolute strengths of programs (win rates against the optimal player). Moreover, using stronger baseline programs reflects the absolute strengths better. The analysis in this paper offers evidence that win rates against a baseline program – the stronger the better – can be used to approximate the absolute strengths of programs.

In addition, the second metric, prediction rates to expert moves, also has a high correlation to the absolute strengths, as long as expert moves with high qualities were collected. The third metric, mean squared errors of values of positions, also has a high correlation to the absolute strengths, which is influenced less by the quality of the collected data. The results show that the strengths of game-playing programs can be roughly measured by these two metrics.

In addition, the win rates for game-playing programs with the same settings in both $2 \times 4$ and $4 \times 8$ CDC are analyzed. Except for those related to PB, the win rates obtained in different board sizes also have a high correlation. A conjecture for the inconsistency of PB is related to the used heuristic scores of moves. Further research is needed to study the condition that the win rates obtained in smaller sizes can or cannot be used to predict those in the full or larger sizes. In the future, it is also worth applying the analysis presented in this paper to other solved games, even deterministic games such as Hex (Gao et al., 2017; Henderson et al., 2009; Pawlewicz & Hayward, 2014).

Footnotes

Acknowledgements

The authors would like to thank the Ministry of Science and Technology of the Republic of China (Taiwan) for financial support of this research under contract numbers MOST 106-2221-E-009-139-MY2, 106-2221-E-305-016-MY2, 106-2221-E-305-017-MY2, 107-2634-F-009-011, and 107-2634-F-259-001.

Detailed experiment results

Table A.1 lists the win rates of the 129 program settings against five $2 \times 4$ CDC baseline programs, OPT, EMM, MCTS-1k, MCTS-5k and MCTS-30k, in the five columns WR_OPT ( ${WR}_{2 \times 4}$ ), WR_EMM, WR_1k, WR_5k, and WR_30k, and the 66 program settings against MCTS-30k in $4 \times 8$ CDC in the column ${WR}_{4 \times 8}$ . The 95% confidence bounds for win rates in WR_OPT, WR_EMM, WR_1k, WR_5k, and WR_30k were less than 0.59%, and those in ${WR}_{4 \times 8}$ were less than 2.89%.

Table A.2 lists the prediction rates of the 129 program settings for $2 \times 4$ CDC with respect to the best moves, the moves played by MCTS-1k, and the moves by MCTS-1M in the columns PR_BEST, PR_1k, and PR_1M, the mean squared errors with respect to the theoretical values, the game outcomes from self-plays by MCTS-1k, and the game outcomes from self-plays by MCTS-1M in the columns MSE_TH, MSE_GO-1k, and MSE_GO-1M respectively. The 95% confidence bounds for prediction rates in PR_BEST were less than 0.42%, and those in PR_1k and PR_1M were less than 0.45%. The 95% confidence bounds for mean squared errors in MSE_TH were less than 0.0012, and those in MSE_GO-1k and MSE_GO-1M were less than 0.0017.

Simple linear regression

Simple linear regression, described in more detail by Lane et al. (2014), is a model to derive how two random variables are linearly correlated. This section illustrates it by the example of two random variables X and Y with sample data $(x, y) \in {(1, 4), (3, 6), (5, 10), (5, 12), (6, 13)}$ , as shown in Fig. B.1. In this paper, the Pearson’s correlation coefficient r is used, which is calculated by $\begin{matrix} (B.1) & r = \frac{\sum_{i = 1}^{N} (x_{i} - \overline{x}) (y_{i} - \overline{y})}{\sqrt{\sum_{i = 1}^{N} {(x_{i} - \overline{x})}^{2} \cdot \sum_{i = 1}^{N} {(y_{i} - \overline{y})}^{2}}}, \end{matrix}$ where N is the total number of the sample data, $x_{i}$ and $y_{i}$ the i^th data of x and y, and $\overline{x}$ and $\overline{y}$ the sample means of X and Y which are $\frac{1}{N} \sum_{i = 1}^{N} x_{i}$ and $\frac{1}{N} \sum_{i = 1}^{N} y_{i}$ respectively. The higher the absolute values of correlation coefficients are, the stronger the correlations between the two random variables. Correlation coefficients range from $- 1$ to 1, and the correlation coefficient of the given example is $r = \frac{30}{\sqrt{16 \times 60}} \approx 0.9682$ . A rule of thumb interprets the correlation coefficient as follows, though it depends on the purpose of the analysis and on the number of sample data. For the absolute value of r, $[0.9, 1]$ shows a very high correlation, $[0.7, 0.9)$ a high correlation, $[0.5, 0.7)$ a moderate correlation, $[0.3, 0.5)$ a low correlation, and $[0, 0.3)$ little if any correlation (Asuero et al., 2006). Thus, in the above example, X and Y are said to have a very highly positive correlation.

The regression line, the best-fitting straight line, is $\begin{matrix} (B.2) & y = \overline{y} + \frac{\sum_{i = 1}^{N} (x_{i} - \overline{x}) (y_{i} - \overline{y})}{\sum_{i = 1}^{N} {(x_{i} - \overline{x})}^{2}} (x - \overline{x}), \end{matrix}$ which predicts the values of y given x. Thus, the regression line of the given example is $y = 1.5 + 1.875 \cdot x$ , the dotted line shown in Fig. B.1. The sample standard error of the prediction on Y is then calculated by $\begin{matrix} (B.3) & s = \sqrt{\frac{\sum_{i = 1}^{N} {(y_{i} - y_{i}^{'})}^{2}}{N - 2}}, \end{matrix}$ where $y_{i}^{'}$ is the prediction on the regression line given $x_{i}$ . In the given example, the sample standard error is $s = \sqrt{\frac{3.75}{3}} \approx 1.1180$ . A small value of sample standard error shows that the prediction can be trusted.

References

Asuero, A.G., Sayago, A. & González, A.G. (2006). The correlation coefficient: An overview. Critical Reviews in Analytical Chemistry, 36(1), 41–59. doi:10.1080/10408340500526766.

Auer, P., Cesa-Bianchi, N. & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3), 235–256. doi:10.1023/A:1013689704352.

Browne, C.B., Powley, E., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P.et al. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43. doi:10.1109/TCIAIG.2012.2186810.

Campbell, M., Hoane, A.J. & Hsu, F.-h. (2002). Deep Blue. Artificial Intelligence, 134(1), 57–83. doi:10.1016/S0004-3702(01)00129-1.

Chang, H.-J., Fan, G.-Y., Chen, J.-C., Hsueh, C.-W. & Hsu, T.-s. (2017). Validating and fine-tuning of game evaluating functions using endgame databases. Paper presented at the 6th Workshop on Computer Games (CGW 2017), Held in Conjunction with the 26th International Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia.

Chang, H.-J. & Hsu, T.-s. (2014). A quantitative study of 2 × 4 Chinese dark chess. In

H.J.

van den Herik ,

Iida and

Plaat (Eds.), Computers and Games: 8th International Conference, CG 2013: Revised Selected Papers, Yokohama, Japan, August 13–15, 2013 (pp. 151–162). Cham: Springer.

Chang, H.-J., Hsueh, C.-W. & Hsu, T.-s. (2015). Convergence and correctness analysis of Monte-Carlo tree search algorithms: A case study of 2 by 4 Chinese dark chess. Paper presented at the 2015 IEEE Conference on Computational Intelligence and Games (CIG), Tainan, Taiwan.

Chaslot, G.M.J.B., Winands, M.H.M., van den Herik, H.J., Uiterwijk, J.W.H.M. & Bouzy, B. (2008). Progressive strategies for Monte Carlo tree search. New Mathematics and Natural Computation, 4(3), 343–357. doi:10.1142/S1793005708001094.

Chen, B.-N., Shen, B.-J. & Hsu, T.-s. (2010). Chinese dark chess. ICGA Journal, 33(2), 93–106. doi:10.3233/ICG-2010-33204.

10.

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, PP(99), 1. doi:10.1109/TG.2018.2802484.

11.

Chen, J.-C., Lin, T.-Y., Chen, B.-N. & Hsu, T.-s. (2015). Equivalence classes in Chinese dark chess endgames. IEEE Transactions on Computational Intelligence and AI in Games, 7(2), 109–122. doi:10.1109/TCIAIG.2014.2317832.

12.

Coulom, R. (2007). Computing Elo ratings of move patterns in the game of Go. In

H.J.

van den Herik ,

Mark ,

Jos and

Maarten (Eds.), Proceedings of the Computer Games Workshop 2007, Amsterdam, June 15–17, 2007 (pp. 113–124).

13.

Gao, C., Mueller, M. & Hayward, R.B. (2017). Focused depth-first proof number search using convolutional neural networks for the game of Hex. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) (pp. 3668–3674). doi:10.24963/ijcai.2017/513.

14.

Gelly, S. & Silver, D. (2007). Combining online and offline knowledge in UCT. In Proceedings of the 24th International Conference on Machine Learning (pp. 273–280). ACM.

15.

Henderson, P., Arneson, B. & Hayward, R.B. (2009). Solving 8 × 8 Hex. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI ’09) (pp. 505–510). AAAI Press.

16.

Hsueh, C.-H. & Wu, I.-C. (2015). DarkKnight wins Chinese dark chess tournament. ICGA Journal, 38(4), 249–251. doi:10.3233/ICG-2015-38411.

17.

Hsueh, C.-H., Wu, I.-C., Tseng, W.-J., Yen, S.-J. & Chen, J.-C. (2016). An analysis for strength improvement of an MCTS-based program playing Chinese dark chess. Theoretical Computer Science, 644, 63–75. doi:10.1016/j.tcs.2016.06.025.

18.

Ikeda, K. & Viennot, S. (2014). Efficiency of static knowledge bias in Monte-Carlo tree search. In

H.J.

van den Herik ,

Iida and

Plaat (Eds.), Computers and Games: 8th International Conference, CG 2013: Revised Selected Papers, Yokohama, Japan, August 13–15, 2013 (pp. 26–38). Cham: Springer.

19.

Kishimoto, A. & Mueller, M. (2015). Game solvers. In

Nakatsu ,

Rauterberg and

Ciancarini (Eds.), Handbook of Digital Games and Entertainment Technologies (pp. 1–20). Singapore: Springer Singapore.

20.

Kocsis, L. & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In

Fürnkranz ,

Scheffer and

Spiliopoulou (Eds.), Machine Learning: ECML 2006: 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006 (pp. 282–293). Berlin: Springer. doi:10.1007/11871842_29.

21.

Lai, M. (2015). Giraffe: Using deep reinforcement learning to play chess. CoRR. abs/1509.01549.

22.

Lanctot, M., Winands, M.H.M., Pepels, T. & Sturtevant, N.R. (2014). Monte Carlo tree search with heuristic evaluations using implicit minimax backups. Paper presented at the 2014 IEEE Conference on Computational Intelligence and Games, Dortmund, Germany.

23.

Lane, D.M., Scott, D., Hebl, M., Guerra, R., Osherson, D. & Zimmer, H. (2014). Introduction to Statistics. Houston, TX: Rice University.

24.

Liskowski, P., Jaśkowski, W.M. & Krawiec, K. (2018). Learning to play Othello with deep neural networks. IEEE Transactions on Games, PP(99), 1. doi:10.1109/TG.2018.2799997.

25.

Nijssen, J.A.M. & Winands, M.H.M. (2011). Enhancements for multi-player Monte-Carlo tree search. In

H.J.

van den Herik ,

Iida and

Plaat (Eds.), Computers and Games: 7th International Conference, CG 2010: Revised Selected Papers, Kanazawa, Japan, September 24–26, 2010 (pp. 238–249). Berlin: Springer. doi:10.1007/978-3-642-17928-0_22.

26.

Pawlewicz, J. & Hayward, R.B. (2014). Scalable parallel DFPN search. In

H.J.

van den Herik ,

Iida and

Plaat (Eds.), Computers and Games: 8th International Conference, CG 2013: Revised Selected Papers, Yokohama, Japan, August 13–15, 2013 (pp. 138–150). Cham: Springer.

27.

Pepels, T., Tak, M.J.W., Lanctot, M. & Winands, M.H.M. (2014). Quality-based rewards for Monte-Carlo tree search simulations. In

Schaub ,

Friedrich and

O’Sullivan (Eds.), Proceedings of the Twenty-First European Conference on Artificial Intelligence, ECAI 2014 (pp. 705–710). IOS Press.

28.

Runarsson, T.P. & Lucas, S.M. (2014). Preference learning for move prediction and evaluation function approximation in Othello. IEEE Transactions on Computational Intelligence and AI in Games, 6(3), 300–313. doi:10.1109/TCIAIG.2014.2307272.

29.

Russell, S. & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

30.

Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G.et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489. doi:10.1038/nature16961.

31.

Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A.et al. (2017). Mastering the game of Go without human knowledge. Nature, 550(7676), 354–359. doi:10.1038/nature24270.

32.

Takeuchi, S., Kaneko, T. & Yamaguchi, K. (2010). Evaluation of game tree search methods by game records. IEEE Transactions on Computational Intelligence and AI in Games, 2(4), 288–302. doi:10.1109/TCIAIG.2010.2102022.

33.

Tesauro, G. (1995). Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3), 58–68. doi:10.1145/203330.203343.

34.

Tian, Y. & Zhu, Y. (2016). Better computer Go player with neural network and long-term prediction. Paper presented at the 4th International Conference on Learning Representations (ICLR 2016), San Juan, Puerto Rico.

35.

Tseng, W.-J., Chen, J.-C. & Wu, I.-C. (2017). DarkKnight wins Chinese dark chess tournament. ICGA Journal, 39(3), 163–165. doi:10.3233/ICG-170023.

36.

van den Herik, H.J., Plaat, A. & Hellemons, J. (2012). The 16th Computer Olympiad. ICGA Journal, 35(1), 50. doi:10.3233/ICG-2012-35111.

37.

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

38.

Yen, S.-J., Chen, J.-C., Chen, B.-N. & Tseng, W.-J. (2013). DarkKnight wins Chinese dark chess tournament. ICGA Journal, 36(3), 175–176. doi:10.3233/ICG-2013-36315.

39.

Yen, S.-J., Chiu, S.-Y. & Wu, I.-C. (2010). MoDark wins the Chinese dark chess tournament. ICGA Journal, 33(4), 230–231. doi:10.3233/ICG-2010-33410.

40.

Yen, S.-J., Chou, C.-W., Chen, J.-C., Wu, I.-C. & Kao, K.-Y. (2015). Design and implementation of Chinese dark chess programs. IEEE Transactions on Computational Intelligence and AI in Games, 7(1), 66–74. doi:10.1109/TCIAIG.2014.2329034.

KGGM vs. kggm	KGGC vs. kggc	KGGP vs. kggp	KGMM vs. kgmm
KGMR vs. kgmr	KGMC vs. kgmc	KGMP vs. kgmp	KGCC vs. kgcc
KGCP vs. kgcp	KCCP vs. kccp	KCPP vs. kcpp	KPPP vs. kppp
GGMM vs. ggmm	GGMR vs. ggmr	GGMC vs. ggmc	GGCC vs. ggcc
GGCP vs. ggcp	GMCP vs. gmcp	GCCP vs. gccp	GCPP vs. gcpp
GPPP vs. gppp	CCPP vs. ccpp	CPPP vs. cppp	PPPP vs. pppp

An investigation of strength analysis metrics for game-playing programs: A case study in Chinese dark chess

Abstract

Keywords

1. Introduction

2. Background

2.1. Chinese dark chess (CDC)

2.3.1. Early playout terminations

2.3.2. Implicit minimax backups

Table 2 Piece weights for CDC used by Hsueh et al. (2016) Piece type K/k G/g M/m R/r N/n C/c P/p Weight 55 50 25 10 8 30 8

2.3.4. Progressive bias

3. Investigated strength analysis metrics

3.1. Win rates playing against a designated player

3.3. Mean squared errors of values of positions

4. Experiments for 2 × 4 CDC

1 Six-ply EMM ran about 150 times slower than that of four-ply. Due to time constraints, experiments on EMM with more plies were not conducted.

Footnotes

Acknowledgements

Detailed experiment results

Simple linear regression

References

Table 2
Piece weights for CDC used by Hsueh et al. (2016)

Piece type K/k G/g M/m R/r N/n C/c P/p

Weight 55 50 25 10 8 30 8

4. Experiments for $2 \times 4$ CDC

¹
Six-ply EMM ran about 150 times slower than that of four-ply. Due to time constraints, experiments on EMM with more plies were not conducted.