Analysis and efficient solutions for 2 × 4 Chinese dark chess 1

Abstract

This paper considers the $2 \times 4$ variation of a popular 2-player imperfect information game Chinese dark chess (CDC). The $2 \times 4$ version is solved by computing the game-theoretical value of each position for all possible material combinations with at most four red pieces and four black pieces. The experimental results show that where to make the first move, which must be a flip, is the most important factor to affect the outcome of a game. We find that choosing a square to flip that has the best-expected outcome may not be the best strategy. Instead, a square that has the best-expected difference before and after the first move is made should be chosen. We also discover that $2 \times 4$ CDC is unfair and it is favorable to the second player, but some openings are fair. We believe observations and techniques made here can be used to improve the performance of programs for playing the original $4 \times 8$ full version of CDC.

Keywords

Chinese dark chess endgame database imperfect information game 2 × 4 game board

1. Introduction

For stochastic games, such as Backgammon (Tesauro, 1995), bridge (Scott, 1991), Mahjong (Lin et al., 2011) and Chinese dark chess (CDC) (Chen et al., 2010), a critical problem during searching is how to deal with chance nodes. A better understanding of how chance nodes affect the behavior of searching can lead to the development of better algorithms.

This paper uses CDC as the research object. Since it is currently infeasible to completely solve the $4 \times 8$ full version of CDC, we study a smaller version of the game. Solving the $2 \times 4$ version completely can provide insight that may help solve the full version. By reducing the size of the game board from $4 \times 8$ to $2 \times 4$ , there are 8 squares instead of 32 on the board and each player holds only 4 pieces. We evaluate all 1,790 possible material combinations in our experiments. Figure 1(a) shows the initial position of $2 \times 4$ CDC. Figure 1(b) shows the coordinates and the ID assignments to each square, which are between 0 and 7.

The remainder of this paper is organized as follows. Section 2 introduces the rules of CDC, and Section 3 introduces the indexing function of positions and the method used to completely solve the game. Section 4 describes the experiment environment and shows the experiment results, while Section 5 considers implementation issues and discusses experiment results. Section 6 provides concluding remarks.

Fig. 1.

The initial board.

2. Background

2.1. Chinese dark chess

Chinese dark chess (CDC) is a popular version of Banqi (Chen et al., 2010), which is a variation of Chinese chess. CDC uses the same set of pieces as Chinese chess, but only requires half of the game board and places pieces inside the squares instead of at the intersections. There are 32 pieces: 16 red and 16 black. In this paper, the red pieces and the black pieces are denoted by upper-case letters and lower-case letters, respectively. Each color has one king (K or k), two guards (G or g), two ministers (M or m), two rooks (R or r), two knights (N or n), two cannons (C or c) and five pawns (P or p). Each piece has two sides, dark and revealed. A piece’s type is marked on the revealed side, and the dark sides of all the pieces are identical. A piece is unrevealed if its dark side is facing up, and it is revealed if its marked side is facing up. At the beginning of a game, all the pieces are unrevealed so players do not know the type of any piece. The first player flips one of the unrevealed pieces and then owns the color of that piece, which means the second player owns the other color. In each turn, a player can either flip an unrevealed piece to reveal its identity, or to move one of his/her own revealed pieces. A revealed piece can be moved to an adjacent empty square or be used to capture a lower-ranked or same-ranked revealed opponent piece in the adjacent square with the exception that a cannon cannot capture the opponent’s cannon by moving. There is a special capture rule for cannons which will be described later. A player loses the game if he/she cannot make any legal move. Let $x > y$ denotes that x’s rank is higher than y’s rank. The pieces are ranked by two rules: (1) $K > G > M > R > N > C$ and (2) $G, M, R, N > P$ and $P > K$ . Notice that there is no ranking order between cannons and pawns, and except for cannons, every piece is of the same order as itself. The cannon can make a special jump move in the following circumstances. On a straight line, if there is exactly one piece, revealed or unrevealed, between the cannon and a revealed opponent piece, the cannon can capture this piece, no matter its rank, by jumping to its square.

2.2. Game solving and fair game

In the domain of computer games, a game can be solved at three different levels, ultra-weakly solved, weakly solved, and strongly solved (van den Herik et al., 2002). If a game is ultra-weakly solved, the game-theoretical value of the initial position is determined. If a game is weakly solved, an optimal strategy from the beginning of the game is provided. If a game is strongly solved, the optimal moves of all legal positions are provided. Note that in imperfect information games and stochastic games, an optimal move does not mean 100% win, lose or draw. Instead, an optimal move in imperfect information games or stochastic games is the move having the maximum expected value of either the winning chance, the winning plus the drawing chance, or the difference between the winning and the losing chance. In this paper, we solve $2 \times 4$ CDC strongly in the sense of calculating the maximum expected value of the difference between the winning and the losing chance of each position. Furthermore, a position is fair if the winning chance and the losing chance of this position are equal. That is, this position is not biased toward any player. For example, a position with 50% of chance to win and 50% of chance to lose and a position with 100% of chance to draw are both fair.

2.3. Retrograde analysis

The retrograde analysis methods are widely used in solving games (Thompson, 1986). In the process of retrograde analysis, it is important to determine the set of next positions and the set of previous positions of a given position (Sturtevant and Saffidine, 2017). In the imperfect information games, one chance node has multiple possible next positions, therefore a backward propagation method is not feasible. A top-down search method is usually used for these imperfect information games (Bonnet and Viennot, 2017). Note that although Kriegspiel (Ciancarini and Favini, 2010) is also an imperfect information game, it is different from other imperfect information games. A position in Kriegspiel does not only contain the pieces’ locations of the current player but also the “partial information” of the opponent’s pieces’ locations.

2.4. Related works

In stochastic games and imperfect information games, chance nodes are involved in the search tree. In dice games, such as Backgammon (Tesauro, 1995) and “EinStein würfelt nicht!” (Althöfer and Voigt, 2014), legal moves are determined by dice rolls. At the beginning of each turn, the player first rolls the dice and then chooses one of the legal moves decided by the outcome of the dice roll. In other games, such as Mahjong and CDC, the legal moves are separated into deterministic moves and stochastic moves. The state transitions of deterministic moves are fixed. On the other hand, the state transition of stochastic moves is not fixed. For a stochastic move, there are multiple possible outcomes. In the search tree of a stochastic game, every node is a chance node. In the search tree of an imperfect information game, only the nodes related to the stochastic moves are chance nodes.

Previous work on CDC (Chang et al., 2010, 2012, 2015; Yen et al., 2015) has mainly focused on how to deal with the uncertainty caused by flip moves. Because a player knows neither the type nor the color of an unrevealed piece until it is revealed unless the remaining pieces are all of the same type, the game is stochastic, and the probability distribution of a flip move changes over the course of the game. Several games involve probability behavior, e.g., Backgammon, bridge (Scott, 1991), Mahjong (Lin et al., 2011) and Kriegspiel (Ciancarini and Favini, 2010). However, in contrast to Backgammon, the probability distribution of a flip move in CDC changes during the game (Tesauro, 1995). This dynamic behavior of CDC is more like that in bridge and Mahjong, which are normally played by 4 players, making them more difficult to analyze than 2-player games. On the other hand, CDC is not like Kriegspiel, which a player only knows part of the information of his/her opponent. In CDC, both players know the locations of revealed pieces of both sides but have no information about the exact type of any unrevealed piece. In Kriegspiel, a player can use deterministic moves to gain more information and to reduce the uncertainty. In CDC, a player can never gain any information of an unrevealed piece, unless he/she makes a flip move to reduce the number of unrevealed pieces. That is, a player cannot gain extra information without making a stochastic move in CDC. As a research topic, CDC contains the following important properties: (1) it is a 2-player game; (2) it is a stochastic game and the probability distribution of a flip move changes during the course of playing the game; and (3) at the endgame stage, when all pieces are revealed it becomes a deterministic game.

3. Methods

In this section, we describe a bottom-up approach similar to the retrograde analysis method used in (Thompson, 1986) to solve $2 \times 4$ CDC.

3.1. $2 \times 4$ CDC

Similar to $4 \times 8$ CDC, an unrevealed piece’s type in $2 \times 4$ CDC is unknown until it is revealed or all unrevealed pieces are of the same type. For each unrevealed piece on the board, the players only know what types it can possibly be. Hence, the value of each position is recorded as a probability distribution with 3 possible outcomes: win, draw or loss. Note that two probability distributions cannot be compared as we usually do on comparing single numerical values. For example, a position with 100% of chance to have a draw and a position with 15% of chance to win and 20% of chance to lose, cannot be compared directly. This paper uses the expected value of the difference between the winning probability and the losing probability as the representative value of a position. When two positions are compared, we compare their representative values.

Indexing function. Before explaining how $2 \times 4$ CDC is solved, we describe the indexing function used in mapping positions to a continuous range of integers starting from 0. The index of a position consists of two parts: the locations of the pieces and whether a piece is revealed or not. In this paper, we use an ordering of “KGMRNCPkgmrncp” to list the pieces in a given material combination. For example, the material combination consisting of a red king, a red minister, a black guard and a black pawn is “KMgp”.

We start with a basic indexing function, which is easy to use but lacks optimization. The basic indexing function contains two parts, the locations of the pieces and whether a piece is revealed or not. We use a $2 n$ -tuple to record the locations and the revealed states of a position with n pieces. Consider the position of “KMgp” in Fig. 2(a), there is one red king, one red minister, one black guard and one black pawn. The red king and the black pawn are revealed, and the red minister and the black guard are unrevealed. Figure 2(b) and Fig. 2(c) show the two possibilities of this position. In Fig. 2, a prefix “d” before a letter means this piece is unrevealed. For example, “dM” means an unrevealed red minister. The unrevealed red minister can be located either in B2 or C2. If the red minister is located in B2, then this position is recorded as $(7, 1, 2, 0, 0, 1, 1, 0)$ where the first four elements denote the locations of K, M, g, and p, respectively. And the last four elements denote the revealing status, where 0 means revealed and 1 means unrevealed, respectively. If the unrevealed red minister is located at C2, then it is the position of Fig. 2(c), and the corresponding index is $(7, 2, 1, 0, 0, 1, 1, 0)$ . Comparing the index of positions in Fig. 2(b) and Fig. 2(c), only the second and third digits are different since only the locations of the red minister and the black guard are exchanged. There are two issues with the above basic indexing function. First, the mapping between a position and its index is not unique. As we show in Fig. 2, the same position has two different indexes. Second, this index function does not exclude illegal positions. For example, the index $(0, 0, 0, 0, 0, 1, 1, 0)$ of “KMgp“ puts all 4 pieces in the same square. In order to resolve the two issues above, we propose a highly improved indexing function.

Fig. 2.

Illustration of the basic indexing function. The material combination is “KMgp”. The prefix “d” of a letter denotes that piece is unrevealed. In Fig. 2(b) and (c), there are an unrevealed red minister, “dM”, and an unrevealed black guard, “dg”.

Before we describe the details of our indexing function, we first introduce two basic operators in our indexing function: a function to calculate the i^thcombination and a function to calculate the i^thpermutation. We start with defining the i^th combination of an ordered set. For a given set with n distinct elements, there are $(\binom{n}{k})$ different ways to pick k different elements from this set. There exists a 1–1 mapping from an integer in the range of $[0, (\binom{n}{k}) - 1]$ to one of the ways to pick k elements. For example, if we want to pick 2 elements from the ordered set ${1, 2, 3}$ , then there are $(\binom{3}{2}) = 3$ different ways: ${1, 2}$ , ${1, 3}$ and ${2, 3}$ . If we list the 3 possible results in a unique lexicographical order, then we can map 0 to ${1, 2}$ , 1 to ${1, 3}$ and 2 to ${2, 3}$ . That is, for a given number i, we can calculate the i^th combination of an ordered set; conversely, for a given combination of the ordered set, we can calculate its combination order, i.

Now we consider the case of the i^th permutation. Similar to the i^th combination, there are $n!$ possible permutations of an ordered set with n elements. Once again, we map any integer, j, in the range of $[0, n! - 1]$ to a unique permutation and calculate the permutation order, j. For example, we can map 0 to the permutation 0, 1 and 1 to the permutation 1, 0 for the ordered set ${0, 1}$ . And we can find that the permutation order of 0, 1 and 1, 0 are 0 and 1, respectively.

Now we describe how to construct our indexing function using the method proposed by Knuth (Knuth, 2008) to calculate the i^th combination and the i^th permutation of an ordered set and their inverse functions. First, we present six attributes that can encode a position uniquely. A position with a given material combination can be recorded by the following six attributes: (1) TPIECE: the total number of pieces on the board; (2) LPIECE: the number of revealed pieces on the board; (3) SQUAREID: the combination order of the occupied squares as a subset of all squares; (4) LSQUAREID: the combination order of the squares occupied by the revealed pieces as a subset of the occupied squares; (5) LSET: the combination order of the revealed pieces as a subset of the material combination; and (6) LPER: the permutation order of the set of revealed pieces, ordered according to their occupied squares’ IDs. The range and notation of each attribute are listed in Table 1.

In Fig. 3, the total number of pieces is 4 and the number of revealed pieces is 2. The squares occupied by the pieces are 0, 1, 2 and 7; hence the combination order equals $(\binom{0}{1}) + (\binom{1}{2}) + (\binom{2}{3}) + (\binom{7}{4}) = 35$ . The revealed pieces occupy squares 0 and 7, which are the first and fourth occupied squares, so the combination order equals $(\binom{0}{1}) + (\binom{3}{2}) = 3$ . The red king and the black pawn are the first piece and the fourth piece, respectively, in the “KMgp” combination, so the combination order equals $(\binom{0}{1}) + (\binom{3}{2}) = 3$ . The square ID of the red king is 7 and the square ID of the black pawn is 0, so the order of revealed pieces according to the square ID is “pK”, which is the second permutation of the set ${K, p}$ . This means its index is 1, so the six attributes of the position in Fig. 3 are $(4, 2, 35, 3, 3, 1)$ .

Table 1

The attributes of a position

		Range

Attribute	Description	From	To
TPIECE	Total number of pieces	1	8
LPIECE	Total number of revealed pieces	0	TPIECE
SQUAREID	The i^th subset of all squares with size TPIECE	0	$(\binom{8}{TPIECE}) - 1$
LSQUAREID	The i^th subset of occupied square with size LPIECE	0	$(\binom{TPIECE}{LPIECE}) - 1$
LSET	The i^th subset of combination of pieces with size LPIECE	0	$(\binom{TPIECE}{LPIECE}) - 1$
LPER	The i^th permutation of revealed pieces with size LPIECE	0	$LPIECE! - 1$

The representative values of the red turned positions and the black turned positions are saved separately, so the turn information is not used in the indexing function. Because there is a 1–1 mapping between the i^th combination and integers as well as a 1–1 mapping between i^th permutation and integers, each index represents a unique valid position.

Fig. 3.

Index of the position shown is $(4, 2, 35, 3, 3, 1)$ if the material combination “KMgp” is considered.

Bottom-up method. We use a bottom-up method to solve $2 \times 4$ CDC. For a given material combination, all its proper subsets are generated before the given one can be generated. For example, before “KGkg” can be generated, we need to first generate “KGk”, “KGg”, “Kkg” and “Gkg”. Figure 4 shows all the dependency relations starting from “KGkg”. Note that although “Gg” is a proper subset of both “Gkg” and “KGg”, “Gkg” and “KGg” cannot be transferred into “Gg” since the red (black, respectively) king cannot be captured by the black (red, respectively) guard.

Top-down method. We use a top-down method to calculate the representative value of each $2 \times 4$ CDC position when the material combination is given. The values of positions in $2 \times 4$ CDC are representative values, instead of exact ones, namely the value of each position is a real number ranging from $- 1$ to 1. Thus, the representative value of a sure-to-win position is 1 and that of a sure-to-lose position is $- 1$ . The updating strategy used in the original retrograde analysis (Sturtevant and Saffidine, 2017) cannot be used to solve $2 \times 4$ CDC because most of the positions have representative values between $- 1$ and 1 rather than being equal to $- 1$ or 1. In this case, instead of using a bottom-up method, we use a top-down method to determine the representative value of each position.

Fig. 4.

Dependency graph of “KGkg”.

For each material combination, we determine the representative value of positions from the case of having no unrevealed pieces to the case of having only unrevealed pieces. Because flipping an unrevealed piece is a non-reversible move, the number of unrevealed pieces cannot increase during the course of a game. Hence, the representative values of positions consisting of k unrevealed pieces depend on those consisting of $k - 1$ unrevealed pieces. When the number of unrevealed pieces is zero or the piece types of all unrevealed pieces are the same, then the corresponding position contains no chance move, and the representative value can only be 1, 0 or $- 1$ . To determine the representative values of positions that have more than one type of unrevealed pieces, we use an iterative deepening depth-first search strategy (Korf, 1985). We use the Procedure DFS as the basic component of our algorithm. The search depth increases by 2 in each iteration of Algorithm 1.

Procedure

DFS(state s, depth d)

Algorithm 1:

CDC database updates

4. Experiments

This section describes the experimental settings and discusses the experimental results.

4.1. Experimental settings

In the experiments, we calculate all 1,790 equal-piece-number (4 red pieces and 4 black pieces) material combinations of $2 \times 4$ CDC. There are 24 material combinations with identical red and black pieces. Therefore we call those 24 material combinations symmetric. The remaining 1,766 material combinations are called nonsymmetric.

In a position with n unrevealed pieces, there are $n!$ possible outcomes if we reveal all the unrevealed pieces. Each outcome is a winning event if this outcome is a “Win” position and it is a losing event if it is a “Loss” position. The representative values of win, draw and lose are 1, 0 and $- 1$ , respectively. Note that some of the results may have the same representative value, but the original distribution may not be the same. For example, if the total number of events is 2, then 1 win and 1 loss (1W1L) and 2 draws (2D) have the same representative value of 0. The experiments were run on a server with an Intel Xeon CPU E5-2690 2.90 GHz and 96 GB DDRIII 1333 memory.

4.2. Observations hold on symmetric material combinations

In $2 \times 4$ CDC, the pieces are shuffled and the game board is symmetric. So there are only two choices for the first move, namely, “Flip A2” (flip piece in square 0), abbreviated as “A2” and “Flip B2” (flip piece in square 1), abbreviated as “B2”. Therefore, we can reduce the choices of where to make the first move to two. Furthermore, the first move is followed by seven possible second moves.

Table 2 lists the experimental results of symmetric material combinations. Column 1 and 2 show the index and the material combination of pieces, columns 3 to 6 show the experimental results. Columns 3 and 4 show the representative value and the standard deviation when the first move is “A2”; Columns 5 and 6 show the representative value and the standard deviation when the first move is “B2”. Results show that the first player is disadvantageous for most material combinations. The only exceptions are “KGCPkgcp”, “KGGCkggc” and “GCPPgcpp”. The standard deviation is 0.9; that is, although the expected result favors the second player, the first player also has a good chance to win.

Table 3 lists the results of the second move of “KGCPkgcp” if the first move is “B2.” There are four possible outcomes, that is, either a king, a guard, a cannon or a pawn is revealed. Each subtable has eight columns. Column 1 shows the square ID which is chosen by the second move, and columns 2 to 8 list the corresponding expected difference of each remaining unrevealed piece. Under the mini-max assumption, the second player plays “Flip C2” if the first player reveals a cannon; otherwise, the second player plays “Flip D2”.

Table 2
Experimental results of symmetric material combinations: the results of choosing different first moves

Index Material combination “A2” “B2”

$E [x]$ $σ$ $E [x]$ $σ$

1 CCPP v.s. ccpp −0.061 0.847 −0.044 0.843

2 CPPP v.s. cppp −0.125 0.846 −0.030 0.871

3 GCCP v.s. gccp −0.106 0.941 −0.042 0.951

4 GCPP v.s. gcpp −0.075 0.933 0.010 0.942

5 GGCC v.s. ggcc −0.177 0.944 −0.091 0.951

6 GGCP v.s. ggcp −0.123 0.941 −0.034 0.946

7 GGMC v.s. ggmc −0.136 0.924 −0.030 0.938

8 GGMM v.s. ggmm −0.210 0.908 −0.137 0.909

9 GGMR v.s. ggmr −0.169 0.908 −0.088 0.915

10 GMCP v.s. gmcp −0.076 0.913 −0.015 0.920

11 GPPP v.s. gppp −0.195 0.890 −0.177 0.894

12 KCCP v.s. kccp −0.128 0.887 −0.044 0.891

13 KCPP v.s. kcpp −0.121 0.877 −0.012 0.885

14 KGCC v.s. kgcc −0.124 0.922 −0.044 0.932

15 KGCP v.s. kgcp −0.120 0.918 0.002 0.926

16 KGGC v.s. kggc −0.085 0.914 0.002 0.919

17 KGGM v.s. kggm −0.103 0.890 −0.078 0.886

18 KGGP v.s. kggp −0.192 0.919 −0.145 0.925

19 KGMC v.s. kgmc −0.090 0.893 −0.006 0.899

20 KGMM v.s. kgmm −0.096 0.876 −0.060 0.878

21 KGMP v.s. kgmp −0.134 0.920 −0.084 0.922

22 KGMR v.s. kgmr −0.075 0.879 −0.040 0.879

23 KPPP v.s. kppp −0.288 0.927 −0.225 0.933

24 PPPP v.s. pppp −0.543 0.840 −0.543 0.840

Index	Material combination	“A2”	“B2”
1	CCPP v.s. ccpp	−0.061	0.847	−0.044	0.843
2	CPPP v.s. cppp	−0.125	0.846	−0.030	0.871
3	GCCP v.s. gccp	−0.106	0.941	−0.042	0.951
4	GCPP v.s. gcpp	−0.075	0.933	0.010	0.942
5	GGCC v.s. ggcc	−0.177	0.944	−0.091	0.951
6	GGCP v.s. ggcp	−0.123	0.941	−0.034	0.946
7	GGMC v.s. ggmc	−0.136	0.924	−0.030	0.938
8	GGMM v.s. ggmm	−0.210	0.908	−0.137	0.909
9	GGMR v.s. ggmr	−0.169	0.908	−0.088	0.915
10	GMCP v.s. gmcp	−0.076	0.913	−0.015	0.920
11	GPPP v.s. gppp	−0.195	0.890	−0.177	0.894
12	KCCP v.s. kccp	−0.128	0.887	−0.044	0.891
13	KCPP v.s. kcpp	−0.121	0.877	−0.012	0.885
14	KGCC v.s. kgcc	−0.124	0.922	−0.044	0.932
15	KGCP v.s. kgcp	−0.120	0.918	0.002	0.926
16	KGGC v.s. kggc	−0.085	0.914	0.002	0.919
17	KGGM v.s. kggm	−0.103	0.890	−0.078	0.886
18	KGGP v.s. kggp	−0.192	0.919	−0.145	0.925
19	KGMC v.s. kgmc	−0.090	0.893	−0.006	0.899
20	KGMM v.s. kgmm	−0.096	0.876	−0.060	0.878
21	KGMP v.s. kgmp	−0.134	0.920	−0.084	0.922
22	KGMR v.s. kgmr	−0.075	0.879	−0.040	0.879
23	KPPP v.s. kppp	−0.288	0.927	−0.225	0.933
24	PPPP v.s. pppp	−0.543	0.840	−0.543	0.840

Table 3

Choices of the second move after the first move “Flip B2” is made for “KGCPkgcp”

	(a) First move reveals K

	G	C	P	k	g	c	p
A2	0.069	0.106	0.171	0.693	0.708	0.456	−0.642
C2	0.407	−0.018	0.365	0.826	0.790	0.628	−0.594
D2	0.158	0.106	0.078	0.140	0.008	−0.488	0.400
A1	−0.093	0.275	−0.036	0.204	0.215	0.086	0.268
B1	0.299	0.415	0.286	0.767	0.725	0.518	−0.636
C1	0.096	0.318	0.085	−0.022	−0.146	0.114	0.136
D1	0.132	0.024	0.063	0.260	−0.033	0.110	0.419

	(b) First move reveals G

	K	C	P	k	g	c	p
A2	0.171	−0.008	0.035	−0.635	0.665	0.457	0.601
C2	0.407	−0.108	0.303	−0.689	0.783	0.546	0.706
D2	0.065	0.150	0.079	0.293	0.110	−0.454	0.058
A1	−0.090	0.256	−0.033	0.210	0.186	0.056	0.206
B1	0.299	0.340	0.215	−0.635	0.731	0.478	0.618
C1	0.096	0.301	0.089	0.104	−0.024	0.092	−0.139
D1	0.058	0.024	0.007	0.388	0.235	0.103	−0.019

	(c) First move reveals C

	K	G	P	k	g	c	p
A2	0.361	0.322	0.206	−0.436	−0.411	0.075	0.282
C2	−0.018	−0.108	−0.083	−0.589	−0.503	0.422	−0.071
D2	−0.154	−0.138	−0.201	0.754	0.765	0.497	0.657
A1	0.133	0.163	0.139	0.210	0.219	0.004	0.167
B1	0.415	0.340	0.313	−0.463	−0.450	0.174	0.086
C1	0.318	0.301	0.333	0.015	0.050	0.003	−0.033
D1	−0.192	−0.156	−0.160	0.193	0.182	0.150	0.207

	(d) First move reveals P

	K	G	C	k	g	c	p
A2	0.075	0.131	0.044	0.725	−0.563	0.142	0.576
C2	0.365	0.303	−0.083	0.722	−0.592	0.199	0.721
D2	0.099	0.049	0.051	−0.017	0.293	−0.324	0.139
A1	−0.058	−0.008	0.272	0.183	0.138	0.114	0.174
B1	0.286	0.215	0.313	0.728	−0.544	0.272	0.663
C1	0.085	0.089	0.333	−0.188	0.114	0.174	−0.001
D1	0.029	0.014	0.024	−0.075	0.372	0.160	0.269

4.3. Observations hold on all material combinations

As we mention in Section 4.2, there are two possible first moves which are “A2” and “B2” for each material combination. For each material combination, there are eight possible outcomes $R_{x, i}$ after the first move is made, where $x =$ “A2” or “B2” and $1 ⩽ i ⩽ 8$ . We define ${\bar{R}}_{x} = \frac{\sum_{i = 1}^{8} R_{x, i}}{8}$ to be the average representative value over 8 different outcomes after x is played. Each first move has its own representative value, ${\bar{R}}_{x}$ , where x is “A2” or “B2”.

In Fig. 5, a point ( ${\bar{R}}_{A 2}$ , ${\bar{R}}_{B 2}$ ) corresponds to a material combination whose representative value is ${\bar{R}}_{A 2}$ (respectively, ${\bar{R}}_{B 2}$ ) if the first player chooses “A2” (respectively, “B2”) as his/her first move. If different choices of the first move make no significant difference on the resulting representative values, then the points of all material combinations should lie along the line $y = x$ . However, Fig. 5 shows that the choice of the first move does lead to different results.

Fig. 6 shows the representative values of choosing “A2” as the first move and separately choosing “B2” as the first move, for all material combinations. The x-axis is the expected winning probability and the y-axis is the expected losing probability. For example, the point $(0.5, 0.5)$ represents a material combination having 50% chance to win and 50% chance to lose after the first move is made. Figure 6(a) shows the resulting distribution among all possible material combinations if “A2” is the first move. Figure 6(b) shows the resulting distribution among all possible material combinations if “B2” is the first move. In Fig. 6(b), most of the points are along the line $y = x$ , which means that most material combinations have a similar winning probability and losing probability after choosing “B2” as the first move. On the other hand, in Fig. 6(a), many points are above the line $y = x$ , which means that when choosing “A2” as the first move, many material combinations have a negative representative value. This suggests that the resulting distribution of having “B2” as the first move is more stable than that of having “A2” as the first move. That is, “B2” is a better first move for most of the material combinations.

Fig. 5.

The distribution of $({\bar{R}}_{A 2}, {\bar{R}}_{B 2})$ among all material combinations.

Fig. 6.

Resulting distributions of two possible first moves “Flip A2” and “Flip B2”.

Although this experiment only shows the result for $2 \times 4$ CDC, we conjecture that $4 \times 8$ CDC may have the same characteristic for the following reason. In both versions of the game, the second player can use a similar strategy to counter the first player’s first move. That is, the second player can choose the next move according to the location and piece type which the first player has just revealed. For example, if the revealed piece is a highly valuable piece, such as a king or a guard, it is safe for the second player to flip the square where, if the piece in that square is a cannon, he/she can use a jump move to capture that highly valuable piece. The results suggest that 1) the choice of the first move is critical for CDC; and 2) picking one of the squares in the central area as the first move is better than picking from the corner area.

4.4. Stable strategy

We now consider a strategical consideration to decide where to make the first move.

For each initial position, there are eight possible outcomes after the first move is made. For a first move x and each possible outcome i, we compare the representative value $R_{x, i}$ of the position after the first move x is made with the original representative value R. Then we calculate the number of possible outcomes having a larger representative value, namely $# {R_{x, i} > R}$ , an equal representative value, namely $# {R_{x, i} = R}$ , and a smaller representative value, namely $# {R_{x, i} < R}$ . We define $Comp (R_{x}, R) = (n_{0}, n_{1}, n_{2})$ as a three-tuple where $n_{0}$ , $n_{1}$ and $n_{2}$ are $# {R_{x, i} > R}$ , $# {R_{x, i} = R}$ , and $# {R_{x, i} < R}$ , respectively.

Table 4 lists the changes of the representative value before and after the first move is made for all 1,790 possible material combinations. The first column shows $Comp (R_{x}, R)$ . The second and third columns show the number of material combinations having the given comparison result after choosing “A2” and “B2” as the first move, respectively. For example, for all material combinations, if we choose $x =$ “A2” as the first move, then the number of material combinations with $Comp (R_{x}, R) = (2, 0, 6)$ is 10. Note that $n_{0}$ , $n_{1}$ and $n_{2}$ are all non-negative integers and $n_{0} + n_{1} + n_{2} = 8$ . In theory, there are $\frac{10!}{8! 2!} = 45$ different values for $Comp (R_{x}, R)$ . However, for $2 \times 4$ CDC, we can only find 9 different $Comp (R_{x}, R)$ ’s as shown in the first column of Table 4. It is an interesting question for future work to find out the reason why this is the case. For a given material combination, we can compare $Comp (R_{A 2}, R)$ and $Comp (R_{B 2}, R)$ . We denote $C_{x} = # {R_{x, i} > R} - # {R_{x, i} < R}$ to be the number of outcomes having a larger representative value minus the number of outcomes having a smaller representative value after making the move x.

Here we define a “stable” first move to be one such that when it is played, the probability of having a better representative value equals the probability of having a worse one. Hence the game will likely remain as it was after the move is made. By using our definition, in Table 4, the material combinations achieving $Comp (R_{x}, R) = (4, 0, 4)$ and $Comp (R_{x}, R) = (0, 8, 0)$ are stable, i.e., $C_{x} = 0$ . If we want to find a “stable” first move, then we should choose a move x with $C_{x} = 0$ , that is, an x with $Comp (R_{x}, R) = (n_{0}, n_{1}, n_{0})$ such that $n_{2}$ equals $n_{0}$ . Under this model of comparison, 1,712 material combinations are stable when choosing “A2” and 1,645 material combinations are stable when choosing “B2” when $Comp (R_{x}, R) = (4, 0, 4)$ . However, there is only 1 stable material combination each for choosing “A2” or “B2” when $Comp (R_{x}, R) = (0, 8, 0)$ . We define the stable ratio as the number of stable material combinations over the number of all the material combinations. Hence, if we want to choose a move that is more stable, “A2”, with a stable ratio $1, 713 / 1, 790 = 0.957$ is more stable than “B2” with a stable ratio $1, 646 / 1, 790 = 0.920$ .

Table 4
Value of $Comp (R_{x}, R)$ where $x =$ “A2” or “B2” and the corresponding numbers of material combination (MC)

# of MC

$Comp (R_{x}, R)$ x =“A2” x =“B2”

(0, 8, 0) 1 1

(1, 0, 7) 0 2

(2, 0, 6) 10 19

(3, 0, 5) 34 33

(4, 0, 4) 1,712 1,645

(4, 1, 3) 0 1

(5, 0, 3) 23 85

(6, 0, 2) 9 4

(7, 0, 1) 1 0

Total 1,790 1,790

	# of MC
(0, 8, 0)	1	1
(1, 0, 7)	0	2
(2, 0, 6)	10	19
(3, 0, 5)	34	33
(4, 0, 4)	1,712	1,645
(4, 1, 3)	0	1
(5, 0, 3)	23	85
(6, 0, 2)	9	4
(7, 0, 1)	1	0
Total	1,790	1,790

4.5. Anomaly in comparing representative values

In Table 5, each row is separated into three categories according to the relationship between $C_{A 2}$ and $C_{B 2}$ , that is $C_{A 2} > C_{B 2}$ , $C_{A 2} = C_{B 2}$ and $C_{A 2} < C_{B 2}$ ; Each column is separated into three categories according to the relationship between ${\bar{R}}_{A 2}$ and ${\bar{R}}_{B 2}$ , that is ${\bar{R}}_{A 2} > {\bar{R}}_{B 2}$ , ${\bar{R}}_{A 2} = {\bar{R}}_{B 2}$ and ${\bar{R}}_{A 2} < {\bar{R}}_{B 2}$ . If we compare $C_{A 2}$ and $C_{B 2}$ and then choose the move x with the higher value, we are choosing x with a higher probability to increase the representative value after the move is made. On the other hand, if we compare ${\bar{R}}_{A 2}$ and ${\bar{R}}_{B 2}$ and choose a move with the higher value, we are choosing a move with a higher outcome representative value, not considering the actual chance to obtain that representative value. There are 5 material combinations with $C_{A 2} < C_{B 2}$ and ${\bar{R}}_{A 2} > {\bar{R}}_{B 2}$ , that is “KCPPggcc”, “KCPPggmc”, “KMPPggcc”, “KRPPggmc”, and “KRRNggmm”, and 97 material combinations with $C_{A 2} > C_{B 2}$ and ${\bar{R}}_{A 2} < {\bar{R}}_{B 2}$ .

A fundamental problem in the game tree search is how to compare two nodes with representative values in the form of distributions instead of exact numerical values. Traditionally, distributions are represented by their expected representative values which are ${\bar{R}}_{A 2}$ and ${\bar{R}}_{B 2}$ in our case. However, we have shown that if we only care about the expected representative values, then we may have a higher chance of lowering the expected value after the move is made. That is, the 5 material combinations with ${\bar{R}}_{A 2} > {\bar{R}}_{B 2}$ , but $C_{A 2} < C_{B 2}$ . On the other hand, if we choose a move that has a higher probability of increasing the expected representative value later on, then it might have a lower expected representative value. Those are the 97 material combinations with $C_{A 2} > C_{B 2}$ , but ${\bar{R}}_{A 2} < {\bar{R}}_{B 2}$ .

Table 5
Numbers of material combinations breaking down using the resulting distributions and representative values of playing “A2” and “B2”

$C_{A 2} > C_{B 2}$ $C_{A 2} = C_{B 2}$ $C_{A 2} < C_{B 2}$ Total

${\bar{R}}_{A 2} > {\bar{R}}_{B 2}$ 4 343 5 352

${\bar{R}}_{A 2} = {\bar{R}}_{B 2}$ 0 142 0 142

${\bar{R}}_{A 2} < {\bar{R}}_{B 2}$ 97 1,150 49 1,296

Total 101 1,635 54 1,790

	$C_{A 2} > C_{B 2}$	$C_{A 2} = C_{B 2}$	$C_{A 2} < C_{B 2}$	Total
${\bar{R}}_{A 2} > {\bar{R}}_{B 2}$	4	343	5	352
${\bar{R}}_{A 2} = {\bar{R}}_{B 2}$	0	142	0	142
${\bar{R}}_{A 2} < {\bar{R}}_{B 2}$	97	1,150	49	1,296
Total	101	1,635	54	1,790

4.6. Fair openings

In total, there are 131 possible symmetric material combinations consisting of 4 pieces for each player. Although the total number of symmetric material combinations is 131, some material combinations are equivalent (Chen et al., 2015), namely, they have the same capturing relationship between pieces. For example, “KGMPkgmp” and “KGRPkgrp” have the same relationship since the roles of K, G and P are the same in both material combinations. That is, both M and R are less than K and G, but greater than P. Hence if we treat M in the first material combination as R in the second material combination, the two material combinations are considered as equivalent (Chen et al., 2015). There are 24 symmetric material combinations consisting of 4 pieces that are not equivalent. Also, there are 1,790 non-equivalent material combinations consisting of 4 red pieces and 4 black pieces if we do not require the red side and the black side to have the same piece set.

Although the experimental results show the unfairness of the game due to where the first move is made, we discover conditions for it to become fair later on. Figure 7 shows the three fairest positions with two revealed pieces and where the next move should be in “KGMPkgmp” combination.

Fig. 7.

Fair positions after a sequence of flips in “KGMPkgmp”. All of the three positions are fair because the expected difference is 0.

5. Discussion

5.1. Implementation issues

Section 3 discusses the indexing function used in $2 \times 4$ CDC, and one benefit of this function is that it reduces the size of positions needed to be saved. In $2 \times 4$ CDC, there are at most 8 pieces. The number of saved positions with eight pieces is $2^{32} = 4, 294, 967, 296$ if the indexing function is not optimized. In our implementation, the size of an endgame database is $1, 441, 729$ which is only $0.03 %$ of the former one. This indexing function can also be used to improve the performance of database of $4 \times 8$ CDC.

To ensure the result of each position to be correct, each computed representative value is verified. There are two common verifying methods. First, each position’s representative value is obtained by the values returned from some of its children according to the properties of the search procedure, and for each position, there should be one child position causing the representative value of its parent position to be recorded as it is. Second, since the game board is symmetric, a position should have the same representative value after up-down flipping, left-right flipping, or clockwise rotation. We have verified our results using both methods.

5.2. Opponent model

In this paper, we use the difference of the winning chance and losing chance as the objective function. Here we show this objective function leads to the best score in a game tournament. In a tournament, a single win, draw and lose normally gain 2, 1 and 0 points, respectively. If the number of winning events, draw events and losing events of a nondeterministic state are $N_{W}$ , $N_{D}$ , and $N_{L}$ , respectively, then the total number of events is $N = N_{W} + N_{D} + N_{L}$ . We are finding the move with the maximum expected number of $N_{W} - N_{L}$ , which equals to $N_{W} \times 1 + N_{D} \times 0 + N_{L} \times (- 1)$ . Moreover, it is equivalent to finding the move with the maximum expected value of $\frac{N_{W}}{N} \times 2 + \frac{N_{D}}{N} \times 1 + \frac{N_{L}}{N} \times 0$ , which means our objective function finds a move with the maximum expected number of points in a tournament.

5.3. Possible usage of $2 \times 4$ CDC

In Section 1, we have mentioned that we want to gain insight into $4 \times 8$ CDC. One of the findings is shown in Section 4. We have discussed the possible opening strategy for $2 \times 4$ CDC and believe this strategy can be applied to the $4 \times 8$ version. Here we introduce another approach to help us better understanding the original $4 \times 8$ CDC. Recently, the neural network is widely used as part of the evaluation function in the game playing programs, such as Go (Silver et al., 2016), chess and Shogi (Silver et al., 2017). And we believe that the representative value of all legal positions of $2 \times 4$ CDC is a valuable data source for training, verifying or fine-tuning the evaluation function of the original $4 \times 8$ CDC (Chang et al., 2018; Hsueh et al., 2018). The game board of $4 \times 8$ CDC can be covered by several $2 \times 4$ boards, that is, we can use the representative values of the local $2 \times 4$ boards as a lower bound of the representative value of the whole $4 \times 8$ board, and using methods like convolution neural network (Silver et al., 2017) to approximate the representative value of the $4 \times 8$ board.

6. Conclusion

This paper considers CDC on a $2 \times 4$ game board and solves all material combinations consisting of an equal number of red pieces and black pieces. The implementation uses a highly improved indexing function to avoid ambiguity and as a result, saves $99.97 %$ of the storage space. We also solve $2 \times 4$ CDC for the 24 symmetric material combinations, where both players have 4 pieces of identical rank. The experimental results show that the choice of where to make the first move is a key factor affecting the game’s outcome, and most material combinations favor the second player. However, in some situations, the first player has a higher probability of revealing a piece that is good for him. Results also show that although the beginning of the game may not fair, in some specific openings, it is fair.

Footnotes

Acknowledgements

This work was supported in part by the Ministry of Science and Technology of Taiwan under contracts 104-2221-E-001-021-MY3, 106-2221-E-305-016-MY2, 106-2221-E-305-017-MY2, 107-2634-F-259-001- and 107-2634-F-009-011-.

References

Althöfer, I. & Voigt, R. (2014). Einstein würfelt nicht. In Spiele, Rätsel, Zahlen (pp. 41–47). Springer.

Bonnet, F. & Viennot, S. (2017). Toward solving “Einstein würfelt nicht!”. In In Advances in Computer Games (pp. 13–25). Springer. doi:10.1007/978-3-319-71649-7_2.

Chang, H.-J., Chen, J.-C., Fan, G.-Y., Hsueh, C.-W. & Hsu, T.-s. (2018). Using Chinese dark chess endgame databases to validate and fine-tune game evaluation functions. ICGA Journal, 40(2).

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. In Computational Intelligence and Games (CIG), 2015 IEEE Conference on (pp. 260–266). IEEE. doi:10.1109/CIG.2015.7317963.

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.

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.

Chen, J.-C., Lin, T.-Y., Hsu, S.-C. & Hsu, T. (2012). Design and implementation of computer Chinese dark chess endgame database. In Proceeding of TCGA Workshop (pp. 5–9).

Ciancarini, P. & Favini, G.P. (2010). Playing the perfect kriegspiel endgame. Theoretical Computer Science, 411(40–42), 3563–3577. doi:10.1016/j.tcs.2010.05.019.

Hsueh, C.-H., Wu, I-C., Hsu, T.-s. & Chen, J.-C. (2018). An investigation of strength analysis metrics for game-playing programs: A case study in Chinese dark chess. ICGA Journal, 40(2).

10.

Knuth, D.E. (2008). The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions (1st ed.). Addison-Wesley Professional.

11.

Korf, R.E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial intelligence, 27(1), 97–109. doi:10.1016/0004-3702(85)90084-0.

12.

Lin, C.-H., Shan, Y.-C. & Wu, I-C. (2011). Tournament framework for computer mahjong competitions. In Technologies and Applications of Artificial Intelligence (TAAI), 2011 International Conference on (pp. 286–291). IEEE. doi:10.1109/TAAI.2011.56.

13.

Scott, D. (1991). The problematic nature of participation in contract bridge: A qualitative study of group-related constraints. Leisure Sciences, 13(4), 321–336. doi:10.1080/01490409109513148.

14.

Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. nature, 529(7587), 484–489. doi:10.1038/nature16961.

15.

Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. Arxiv preprint. Available at arXiv:1712.01815.

16.

Sturtevant, N.R. & Saffidine, A. (2017). A study of forward versus backwards endgame solvers with results in Chinese checkers. In Workshop on Computer Games (pp. 121–136). Springer.

17.

Tesauro, G. (1995). Td-gammon: A self-teaching backgammon program. In Applications of Neural Networks (pp. 267–285). Springer. doi:10.1007/978-1-4757-2379-3_11.

18.

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

19.

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.

20.

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.

	# of MC

$Comp (R_{x}, R)$	x =“A2”	x =“B2”
(0, 8, 0)	1	1
(1, 0, 7)	0	2
(2, 0, 6)	10	19
(3, 0, 5)	34	33
(4, 0, 4)	1,712	1,645
(4, 1, 3)	0	1
(5, 0, 3)	23	85
(6, 0, 2)	9	4
(7, 0, 1)	1	0
Total	1,790	1,790