Strategy research based on chess shapes for Tibetan JIU computer game

Abstract

JIU is a variant of traditional Tibetan chess which is mainly played in Tibetan Qiang Autonomous Prefecture of Ngawa, China. The JIU game process is divided into two sequential stages: preparation and battle. The layout of stones during the preparation stage strongly influences gameplay in the battle stage. Compared with Go, computer game research on JIU is almost non-existent. We collected data for 300 JIU games recorded in Tibetan Qiang Autonomous Prefecture of Ngawa. By analyzing the data, several important strategic shapes were extracted: triangles, trinities, diagonals and squares. A chess-shape pattern-matching method based on matrices was developed to recognize these shapes. Offensive and defensive strategies based on these shapes were proposed for the preparation stage, being ranked in terms of priority. Moving and capturing strategies based on these shapes were proposed for the battle stage. Human players of various skill levels were invited to play against the software, applying the proposed strategies, to evaluate its performance. The win rates of the software were 2%, 25% and 60%, against top, intermediate, and beginner players. These results demonstrate that the JIU game software using the proposed strategy performs slightly above the beginner level.

Keywords

Computer games pattern matching Tibetan JIU strategy evaluation chess shape SGF

1. Introduction

JIU is a variant of traditional Tibetan chess which is mainly played in the Tibetan area of Sichuan province, the Tibet Autonomous Region and other Tibetan areas (Liu, 2012). It possesses unique Tibetan cultural characteristics (Zhang and Gou, 2014; Shotwell et al., 1994). Cultural protection and inheritance of JIU is similar to those of dozens of other kinds of Tibetan board games (Dui, 2003). JIU means “square” or ”puzzle” in the Tibetan language. Tibetan JIU chess is well protected and inherited in the Tibetan Qiang Autonomous Prefecture of Ngawa. In 2015, it was listed on the Sichuan Province Intangible Cultural Heritage List in China. The game process comprises two sequential stages: preparation and battle. In the preparation stage, stones are placed at points on the board until none are empty. In the battle stage, players move stones or capture the opponent’s stones until someone wins the game. JIU is representative of multiple board games with similar rules: JIA chess in Qinghai “King and Minister” chess in Tibet, “Mongolian War Banner” chess in Inner Mongolia, Shui chess in Duyun, Guizhou, and “Wolf eating Lamb” chess of the Han nationality.

Research on computer games is one of the most challenging directions for the field of artificial intelligence (Xu et al., 2008). In 1997, IBM’s Deep Blue accomplished the astounding defeat of Kasparov in international chess competition. Google’s Alpha Go, which applies a deep-learning algorithm to Go, achieved excellent results with the defeat of the top master human player (Mnih et al., 2015; Silver et al., 2016). Facebook’s DarkForest combines convolutional neural networks with Monte Carlo tree search to yield a similarly high level of success (Tian and Zhu, 2016). Compared to international chess, Go, and other chess, research on the game of JIU is almost non-existent. Existing literature (Li and Guan, 2011; Dondrub, 2007) mainly focuses on Tibetan Go and other Tibetan board games. Furthermore, most discuss rules, history or their cultural value – few discussed the search or evaluation of algorithms for Tibetan board games. There is some literature (Chen, 2006; Xiabei, 2011; Pei, 2012; Duojie and Cairang, 2014; Fan, 2014) on software development for JIA, Palace Double chess, Dalian and JieBujieZeng. Xiabei (2011) studied Tibetan JIA and developed the first software version of the game. Pei (2012) discussed the key problems, such as state-space representation of an irregular chessboard and winning judgment tactics. Duojie and Cairang (2014) designed and developed computer software for Dalian chess, which is a simplified version suitable for children. Fan (2014) discussed the application of entropy rate in the Tibetan board game JieBuJieZeng. By comparing the entropy rates of both players, it was concluded that the player acting as the King is more likely to win. Wang (2015) studied a Monte Carlo searching algorithm for application in the Tibetan Go game and developed game software used to teach Tibetan Go.

In this work, we developed computer software for playing JIU. We carried out in-depth field visits in the Aba area and collected approximately 300 valid game records from 2015 to 2016. We extracted several common chess shapes in JIU, e.g., Triangle, Trinity, Twain, Diagonal, and Square. We preprocessed the data from these 300 games using smart game format (SGF), used finite automata machines to identify the current chessboard, and applied a simple chess-pattern–matching method based on matrices to recognize the chess shape. Based on these shapes, defensive, offensive and null strategies for the preparation stage were proposed. Based on the shapes from the battle stage, moving and capturing strategies were proposed. As a result, we have developed the first software version of JIU, which has the play modes of man vs. man, man vs. machine and automatic chess game records. We invited JIU players with differing skill levels to play against the software. Test results show that the software can work normally, but the skill of the machine needs further improvement.

2. Rules of JIU

The game is played by two players: White and Black. White uses white stones and Black uses black stones. Players take alternate turn. The public JIU board size is 14×14 (see Fig. 1).

Each intersection is called a point, including corners and interactions at the edge. The two points at the ends of one vertical or horizontal line are adjacent to each other. The central square, which is of special importance, is divided into two parts by a diagonal line. Players take alternating turns. The game starts with an empty board. The game process comprises two sequential stages: preparation and battle. In the preparation stage, White plays first by placing a stone on one vertex of the diagonal line of the central grid. Then, Black places a stone at the other vertex of this diagonal line. Next, White places a stone at a point adjacent to one of the placed stones.Then, Black places his stone at a point adjacent to one of the placed stones. They place stones by turn until stones are places on all points of the board. The preparation stage ends with there is no empty point on the board.

Fig. 1.

Tibetan JIU chess board.

In the battle stage, the game starts with the removal of the two stones on the vertices of the diagonal. Black plays first.The goal of this stage is for players to capture stones. The movements and capturing methods are similar to those international checkers, but additional shapes are relevant:

Move: Move a stone to an adjacent empty point

Jumping capture: when an opponent’s stone is adjacent to a player’s stone and there is an empty point adjacent to the opponent’s stone, the player’s stone can jump to this empty point and capture the opponent’s stone.

Continued Jumping Capture: in JIU, maximal captures are encouraged. If a player has more than one opportunity to capture the opponent’s pieces via jumping, they can take a path to capture most of the opponent’s pieces as long as there is no jumping opportunity.

Square Capture: during the battle stage, if a player constructs a square with four of their stones, i.e., each of the four stones is adjacent to two of the other stones, the player can capture one opponent’s stone located at any point on the board.

Dalian: the square is the basic shape, and it can evolve into the Dalian, which is the most important JIU shape. There are two different Dalian shapes (see Fig. 2). This shape comprises seven same-colour stones and one empty point. The stone adjacent to the empty point is called the “vital stone”. By moving the vital stone into the empty point to construct a square, they can capture one of the opponent’s stone located at any point. A player with the Dalian shape can capture the opponent’s stones by repeatedly moving the vital stone.

Winner: a player is declared the winner when they have constructed a fixed shape, such as the Dalian, and the opponent cannot construct any square shape or they have captured fewer than 14 stones.

Fig. 2.

Dalian shape.

3. Extracting JIU chess shape

We conducted an in-depth field investigation in the Aba area and collected 300 game records. By analyzing the gameplay, we found that special shapes have a great influence on the likelihood of winning. Thus, we extracted several common chess shapes and designed the strategies based on these chess shapes.

Triangle shape

The triangle shape is three stones placed in a right triangle (see Fig. 3). The countering strategy is to fill the empty space, preventing formation of a square.

Trinity shape

The trinity shape is three same-colour stones placed in a line (see Fig. 4). In this case, if White moves to the point which is adjacent to the central white stone, White can construct two squares. Therefore, the countering strategy is to place a black stone at the key point (see Fig. 4), which prevents White from constructing two triangle shapes.

Fig. 3.

Triangle shape and its countering strategy.

Diagonal shape

The diagonal shape is two same-colour stones clipping a differently coloured stone. For example, two black stones clip one white stone (see Fig. 5). In this case, in order to prevent Black from forming a square, White should place a stone at the diagonal of the clipped white stone.

Fig. 4.

Trinity shape and its countering strategy.

Square shape

The square shape is four same-colour stones forming a square (see Fig. 6). The square shape is a basic but very important shape for JIU chess. The Dalian shape evolves from this shape. When a player constructs a Square shape, they can capture one of the opponent’s stone located at any point on the board. Therefore, the player should make every effort to construct Square shapes and prevent the opponent from forming Square shapes.

Fig. 5.

Diagonal shape and its countering strategy.

Fig. 6.

Square shape.

4. Chess-shape pattern-matching method

For JIU chess, the layout of the stones on the board in the preparation stage has a great impact on the likelihood of winning during battle. The special shapes are important to winning the game. We proposed a pattern-matching method based on matrices to match chess shapes with the chessboard. Specifically, we preprocessed the data collected from 300 games using SGF and identified shapes on the chessboard using deterministic finite automatons (DFAs). SGF, which was originally created to store data from Go games, uses text and a tree structure – it easily stores records of played games and provides features for storing annotated and analyzed games (Kierulf et al., 1990).

4.1. DFAs for identifying shapes on the chessboard

DFAs recognize strings and make Accept or Reject decisions (Hong, 2007). There is dependency relationship over several consecutive chess moves, so we can use DFAs to recognize the chess shapes.

A chess board string is recognized through the process shown in Fig. 7. In this figure, $W [gg]$ , $B [hh]$ , $W [gh]$ and $B [hg]$ represent the state transitions, W represents white stones, B represents black stones, and the letters in the brackets indicate the coordinates of the stones.

Fig. 7.

Recognizing a typical chess board string.

4.2. Matrix-based matching method

The strategy evaluation designed in this paper is based on chess shapes. Therefore, pattern-matching between chess shapes and the chess board is the basis of strategy evaluation. We designed a simple and effective chess-shape pattern-matching method based on matrices.

The JIU chess board is represented by a 14×14 matrix, $T_{B}$ : $\begin{matrix} (1) & T_{B} = [\begin{matrix} a_{1, 1} & \dots & a_{1, 14} \\ ⋮ & ⋱ & ⋮ \\ a_{14, 1} & \dots & a_{14, 14} \end{matrix}], \end{matrix}$ where $a_{i, j}$ describes wether the point with two-dimensional coordinate i, j is occupied by a stone on the chess board. The value of $a_{i, j}$ can be −1, 0 or 1, where −1 means that the point is occupied by a black stone, 0 means that the point is empty and 1 means that the point is occupied by a white stone.

Each chess shape is represented by an $m \times n$ matrix, $T_{s}$ : $\begin{matrix} (2) & T_{s} = [\begin{matrix} b_{1, 1} & \dots & b_{1, n} \\ ⋮ & ⋱ & ⋮ \\ b_{m, 1} & \dots & b_{m, n} \end{matrix}], \end{matrix}$ where $b_{i, j}$ describes whether the point with two dimensional coordinate i, j is occupied by a stone in the chess shape. The value of $b_{i, j}$ has the same meaning as that of $a_{i, j}$ . For the trinity shape, $m = 2$ , $n = 3$ or $m = 3$ , $n = 2$ . For triangle, diagonal and square chess shapes, $m = n = 2$ .

The area of size $m \times n$ in matrix $T_{B}$ can be extracted in a convolutional manner as a new matrix, $T_{P}$ . The chess-shape matching process is similar to matrix convolution with a one step in a convolutional neural network. Instead of executing matrix convolution of $T_{B}$ and $T_{P}$ , the pair of elements $a_{i, j}$ in matrix $T_{s}$ are compared with $b_{i, j}$ in the corresponding position in $T_{P}$ . The pattern matching is successful when elements in each pair are equal.

5. Strategy based on chess shapes

The layout of stones in the preparation stage is very important for constructing shapes. Offensive and defensive strategies based on shapes are proposed for the preparation stage. Different scores are given for the different strategies. In the battle stage, players who construct important shapes, such as square, have a great advantage in winning the game. Moving and capturing strategies based on shapes are proposed for the battle stage. Different scores are given for the different shapes.

5.1. Strategies for the preparation stage

Constructing threatening chess shapes in the preparation stage has a strong influence of winning the game. Based on the shapes, we recognized defensive, offensive and null strategies. Defensive strategies are designed to prevent the opponent from constructing chess shapes. Offensive strategies are designed to construct chess shape. The null strategy, which is employed only when no offensive or defensive strategies are available, randomly selects a legal point for stone placement. The evaluation values for the various strategies are shown in Table 1.

The null strategy is employed outright when neither player can construct a shape. Defensive strategies are employed outright when the player cannot construct a shape but the opponent constructs a threatening shape. In this case, the particular strategy is selected to counter the most threatening shape. Offensive strategies are employed outright when the player can construct a shape but the opponent cannot construct a threatening shape. In this case, the particular strategy is selected to form the most threatening shape.

Table 1
Values for different strategies

Strategy Value Type

Destroy square 100 Defensive

Destroy trinity 6 Defensive

Destroy triangle 25 Defensive

Destroy diagonal 5 Defensive

Construct square 90 Offensive

Construct trinity 8 Offensive

Construct triangle 30 Offensive

Construct diagonal 7 Offensive

Null 1 Null

Strategy	Value	Type
Destroy square	100	Defensive
Destroy trinity	6	Defensive
Destroy triangle	25	Defensive
Destroy diagonal	5	Defensive
Construct square	90	Offensive
Construct trinity	8	Offensive
Construct triangle	30	Offensive
Construct diagonal	7	Offensive
Null	1	Null

When the both players can construct threatening shapes, stone placement is determined through the following process. For the player and the opponent, the total valuations of the threatening shapes are obtained. The two values are compared to determine the course of action: $\begin{matrix} (3) & m_{t 1} s_{a t 1} + m_{t 2} s_{a t 2} + m_{d} s_{a d} + m_{s} s_{a s} >^{?} n_{t 1} s_{d t 1} + n_{t 2} s_{d t 2} + n_{d} s_{d d} + n_{s} s_{d s}, \end{matrix}$ where $m_{t 1}$ , $m_{t 2}$ , $m_{d}$ and $m_{s}$ are the numbers of trinities, triangles, diagonals and squares, respectively, that have been constructed in the game already or can be constructed in the next turn by the player; $s_{a t 1}$ , $s_{a t 2}$ , $s_{a d}$ and $s_{a s}$ are the values of constructing trinities, triangles, diagonals and squares, respectively; $n_{t 1}$ , $n_{t 2}$ , $n_{d}$ and $n_{s}$ are the numbers of trinities, triangles, diagonals and squares, respectively, that have been constructed in the game already or can be constructed in the next turn by the opponent; and $s_{d t 1}$ , $s_{d t 2}$ , $s_{d d}$ and $s_{d s}$ are the values of destroying trinities, destroying triangles, destroying diagonals and squares, respectively.

An offensive strategy is selected when the player has the highest threatening shape evaluation value. A defensive strategy is selected when the opponent has the highest threatening shape evaluation value. Pseudo code for this process is shown as follows.

void preparation(){ ShapeGet(); //recognize the chess shape from the board if(no shape) Null strategy;//randomly select placement if no shapes can be constructed if(the player can construct a shape and the opponent cannot) Offensive(); //use offensive strategy if(the player cannot construct a shape and the opponent can) Defensive(); //use defensive strategy if(both the player and the opponent can construct shapes) { MaxscoreGet(); //get highest score of shape evaluation if (Maxscore belongs to the player) then Offensive(); else Defensive(); } } void Defensive(){ trinity(i,j); // recognize Trinity shape triangle(i,j); // recognize Triangle shape diagonal(i,j); // recognize Diagonal shape square(i,j) // recognize Square shape sortByDefensiveValue( ); // Sort the defensive strategies by the evaluation value defensiveaction( );// use the max value defensive strategy } void Offensive(){ trinity(i,j); // recognize Trinity shape triangle(i,j); // recognize Triangle shape diagonal(i,j); // recognize Diagonal shape square(i,j) // recognize Square shape sortByOffensiveValue(); // sort the offensive strategies by the evaluation value offensiveaction(); // use the max value offensive strategy } 5.2. Strategies for the battle stage

Moving and capturing strategies have been designed for the battle stage. Moving means that a stone is moved to an adjacent empty point. The evaluation value is determined by the shape, i.e., trinity, triangle, diagonal or square, which will be constructed by moving the stone. The evaluation values of the trinity, triangle, diagonal, and square shapes are shown in Table 2.

The evaluation value of the moving strategy, $s_{move}$ , equals the largest value of the available $\begin{matrix} (4) & s_{move} = Max (s_{t 1}, s_{t 2}, s_{d}, s_{s}), \end{matrix}$ where $s_{n}$ , $s_{t 1}$ , $s_{t 2}$ , $s_{d}$ and $s_{s}$ are the values of the trinity, triangle, diagonal and square shapes, respectively, if the corresponding shapes can be formed, but they are 0 otherwise. The evaluation value of the capturing strategy, $s_{c}$ , is obtained similarly: $\begin{matrix} (5) & s_{c} = m \times s_{j} + Max (s_{n}, s_{t 1}, s_{t 2}, s_{d}, s_{s}), \end{matrix}$ where m is the number of stones captured and $s_{j} = 2$ is the value of capturing a stone. The values of the moving strategy and capturing strategy are compared, and the strategy with the highest evaluation value for the battle stage is selected. Pseudo code for this process is shown as follows.

Table 2
Value of different shapes in the battle stage

Chess shape Value

Square 1000

Trinity 100

Triangle 500

Diagonal 80

Chess shape	Value
Square	1000
Trinity	100
Triangle	500
Diagonal	80

void battle() { activeshape(); //get all the shapes in the board getmovingscore( ; //calculate the scores of moving getjumpingscore();//calculate the scores of jump capturing getmaxscore(); // get the highest score of the strategies carryout(); // implement the highest score strategy } 6. Test and analysis

By applying the proposed strategies, JIU software was developed. The software was evaluated through play tests with human players. We invited three players of differing skill levels to play against the software: Mr. Kahya, Naota and Sonting. Mr. Kahya is a top JIU chess player who was the Chairman of the Tibetan Chess Association of Tibetan Qiang Autonomous Prefecture of Ngawa, Sichuan Province, China, from 2005 to 2015. Naota is an intermediate level player from Minzu University of China who won first prize in the JIU chess contest held by the computer games research group of Minzu University of China. Sonting is a JIU chess beginner who is a member of computer games research group of Minzu University of China.

Mr Kahya and JIU software took turns playing as White and Black. They played 100 games in total. The results are shown in Table 3.

Table 3 shows that the win rate of the software against a top player is very low. Therefore, there is much room for improvement in the software for it to be competitive with the top JIU chess player.

Table 3
Wins between Kahya (top level) and JIU software

Player White Black

JIU software 1 3

Kahya 47 49

Player	White	Black
JIU software	1	3
Kahya	47	49

Naota played against the JIU software for 100 games, taking turns as White and Black. The results are shown in Table 4.

Table 4 shows that the software is more competitive against an intermediate player, but it still underperforms with a 1:3 win ratio.

Table 4

Wins between Naota (intermediate level) and JIU software

Player	White	Black
JIU software	25	28
Naota	72	75

Songting played against the JIU software for 100 games, taking turns as White and Black. The results are shown in Table 5.

Table 5 shows that the software performs slightly above the beginner level with a win ratio of approximately 3:2. From the above test data, the proposed strategies for the JIU software are appropriate at the beginner level. Applying machine learning to JIU chess will be very beneficial for improving performance in the future. From these limited results, it is also interesting to note that Black has a slight advantage at all levels of play, i.e., all three players and the JIU software individually had more wins as Black than they did as White.

Table 5

Wins between Songting (beginner level) and JIU software

Player	White	Black
JIU software	56	63
Songting	37	44

7. Summary

In this work, we developed software strategies for JIU – one of the best preserved and inherited chess games of all Tibetan board games. Software players for Go has achieved excellent performance in games against human players, but computer game research of JIU chess is still in its infancy. As part of this work, the important chess shapes of JIU were extracted. A chess-shape pattern-matching algorithm based on matrices was proposed. Strategies based on shape were designed for both stages of play. Game software was developed. The software was tested in play against human players. The test results show that the software, with the proposed strategies, performs slightly above the beginner level. Using algorithms based on reinforcement learning, beyond human data, guidance or domain knowledge, Alpha Go Zero achieved superhuman performance (Silver et al., 2017). In future work, algorithms using deep neural networks based on reinforcement learning will be applied to improve performance of the JIU chess game software.

Footnotes

Acknowledgements

This paper was supported by the National Natural Science Foundation of China with the Grant No. 61602539, 61873291 and 61773416.

References

Chen, B. (2006). A comparison of the I-go cultures between the hAn and the Tibetan from the perspective of cultural philosophy. Journal of Yunnan Normal University (Humanities and Social Sciences), 38(2), 1–5.

Dondrub, J. (2007). Considerations for rescuing and protecting Tibetan folk chess. Tibetan Art Studies, 22(2), 78–82.

Dui, G. (2003). On the discovery of Tibetan chess (Mimang) and related traditional Tibetan chesses. Journal of Tibet University, 18(3), 44–48.

Duojie, R. & Cairang, A. (2014). The design and implementation of Tibetan chess – “Dalian”. China Computer & Communication, 21(8), 106–107.

Fan, Z. (2014). Entropy rate of chess game – Tibetan Jiebujiezeng. Journal of Tibet University (Natural Sciences Edition), 7(1), 67–70.

Hong, X. (2007). Fuzzy Finite Automata and Their Minimizations. Dissertation, Sichuan Normal University.

Kierulf, A., Chen, K. & Nievergelt, J. (1990). Smart game board and go explorer: A study in software and knowledge engineering. Communications of the ACM, 33(2), 152–166. doi:10.1145/75577.75581.

Li, D. & Guan, X. (2011). Exploration on traditional Tibetan sports. Journal of Shenyang Sport University, 30(6), 130–132&142.

Liu, Q. (2012). The status quo and promotion value of traditional Tibetan chess. Contemporary Sports Technology, 2(27), 83–84.

10.

Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529–533. doi:10.1038/nature14236.

11.

Pei, S. (2012). Study of key issues in the palace two-door chess game system. Microcomputer Information, 29(10), 461–462.

12.

Shotwell, P.

(author) & SuodaChucha, D. (translator) (1994). The research of Tibetan chess. TITEBEN STUDIES, 9(3), 153–157.

13.

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

14.

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

15.

Tian, Y. & Zhu, Y. (2016). Better computer go player with neural network and long-term prediction. https://arxiv.org/abs/1511.06410. last accessed 2016/11/21.

16.

Wang, X. (2015). Teaching Tibetan go system based on computer game. Bachelor thesis, Minzu University of China.

17.

Xiabei, J. (2011). The design and develop computer-game software of Tibetan chess. Bachelor thesis, Qinghai Nationalities University.

18.

Xu, X., Deng, Z., Wang, J., Xu, C., Liu, J. & Ma, Z. (2008). Challenging issues facing computer game research. CAAI Transactions on Intelligent Systems, 3(4), 288–293.

19.

Zhang, Y. & Gou, X. (2014). The attention to traditional Tibetan sports introduced in Tibet colleges and universities. Contemporary Sports Technology, 4(23), 130, 132.