Yahari wins Chinese dark chess tournament

Abstract

The Chinese dark chess tournament was held as part of the 22^nd Computer Olympiad, which took place in Macau from August 10^th to August 16^th, 2019. Four teams from the USA and Taiwan participated this year, as listed in Table 1 in alphabetical order.

Table 1
The participants

1. The game and tournament rules

Chinese dark chess is a two-player zero-sum non-deterministic game played on a 4 × 8 board. Initially, 32 pieces are face-down and randomly placed on the board. The first player flips one piece and owns the color. Two players alternatively makes a legal action, which is flipping a face-down piece, moving his/her piece to an empty square, or capturing the opponent’s piece. The player who captures all of the opponent’s pieces wins the game. A game is judged as a draw when the same position repeats three times, or when no piece is flipped or captured within 180 plies. The rules in detail can be referred to Chen et al. (2010).

The tournament adopted the round-robin system this year. Each program played two games against each of other programs, one game as the first player and the other as the second player. General speaking, the second player owns a little advantage in Chinese dark chess. To facilitate the progress of the tournament, all games were played via the game-playing platform, which has been developed by Jr-Chang Chen since 2011 (Tseng et al., 2013). The participants could download the Linux and MS Windows versions of client programs on the website (http://web.ntpu.edu.tw/~jcchen/index.html#competitions). For each match, two programs were connected to the platform and two games were automatically played. The server judged and recorded the outcome of each game. For a game, the time limit was 15 minutes for each player.

2. The results

Table 2 lists the cross table of the final results. For a game, the winner obtained 1 point, the loser obtained 0 point, and both obtained 0.5 point in case of a draw. The strengths of the two programs, Yahari and PupilDarkChess, were very close, which obtained 2.5 and 2 points respectively. Yanyu obtained 1.5 points. Deep Nikita was a newcomer. Since the program could not utilize the game-playing platform, the matches it had to play were cancelled under the author’s agreement.

Table 2
The final results

Congratulation to Yahari that received the gold medal. The program has been developed since 2013, and continued to improve its strength each year after it won the silver medals in the Computer Olympiad 2015/2016 and TAAI 2017/2018. The program includes a search engine and endgame databases. Its search engine is based on alpha-beta search, enhanced by chance node search. The data structure adopted bitboard and transposition table. The evaluation function is designed according to the material combinations during the midgame phase (Chang et al., 2018). The 6-piece endgame databases are built, and the sizes are reduced by equivalence classes (Chen et al., 2015, 2018).

PupilDarkChess won the silver medal. The program achieved the second place in the Computer Olympiad 2017/2018 and the gold medals in TAAI 2018/2019. The former version of PupilDarkChess is named NewbieDarkChess. It is also an alpha-beta-based search program, and adopts the method of Ballard (1983) to cope with chance nodes. The evaluation function contains a table in which the values of pieces and positions are trained by supervised learning. The 6-piece endgame databases are used.

Yanyu won the bronze medal, which was at the fifth place last year. The former version is named Lemon developed since 2016. The program is based on NegaScout search. The evaluation function considers the unique food chain relations of the chess spices in Chinese dark chess (Hsieh, 2010). The techniques including bitboard, transposition table, quiescence search and ponder are also implemented. To save computational time, Yanyu searches the deterministic actions (move and capture) and the nondeterministic action (flip) separately.

Fig. 1.

From left to right. H.J. van den Herik, Hsuan-Yu Wang (Yanyu), Po-Hsin Chen (PupilDarkChess) and Jr-Chang Chen (Yahari).

3. Selected games

We list two games: one is the game that Yahari defeated PupilDarkChess, and the other played by PupilDarkChess and Yanyu ended in a draw due to repeated positions. The notations of squares on a 4 × 8 board are letters a to d for columns and numbers 1 to 8 for rows. The letters K/k, G/g, M/m, R/r, N/n, C/c, and P/p denote kings, guards, ministers, rooks, knights, cannons, and pawns respectively. Uppercase letters and lowercase letters represent the red and black pieces, respectively.

Game 1: PupilDarkChess vs. Yahari 0:1

1. b3(R) d3(g) 2. d5(P) c3(k) 3. d1(G) c3-b3 4. c1(p) d4(p) 5. d5-d4 d3-d4 6. d7(r) c5(C) 7. a5(R) d4-d5 8. c4(p) d5-c5 9. a4(n) c6(C) 10. c6-c4 c5-c4 11. d1-c1 a7(m) 12. b1(N) b6(r) 13. a2(P) b3-c3 14. a5-a4 c3-d3 15. b8(p) d3-d4 16. c1-d1 b4(n) 17. d8(G) b4-b3 18. c8(P) b8-c8 19. d8-c8 c4-b4 20. b7(P) b4-a4 21. b7-b8 a7-b7 22. c7(K) b7-b8 23. c8-b8 a3(M) 24. a3-b3 a4-a3 25. a8(g) a8-b8 26. c7-b7 b8-a8 27. b7-a7 a3-b3 28. a7-a8 b3-a3 29. a8-b8 a3-a2 30. b8-b7 a1(M) 31. b7-b6 a2-a1 32. d1-c1 d7-d8 33. b6-c6 b5(c) 34. c6-c5 a1-b1 35. c1-d1 b5-b4 36. d2(p) d2-d3 37. c2(P) b4-b3 38. d1-d2 b1-c1 39. b2(c) b2-d2 40. c2-b2 d3-c3 41. a6(m) c3-c2 42. b2-c2 c1-c2 43. c5-b5 a6-b6 44. b5-b4 b6-c6 45. b4-b5 d4-d5 46. b5-b6 d5-c5 47. d6(N) c6-d6 48. b6-b7 c5-c6 49. b7-b8 c6-c7 50. b8-a8 c7-b7 51. a8-b8 b7-b8

Game 2: PupilDarkChess vs. Yanyu 0.5:0.5

1. b3(r) b1(G) 2. d1(n) b2(g) 3. b2-b1 d3(p) 4. d2(P) d2-d3 5. d1-d2 d5(P) 6. d2-d3 a4(k) 7. d4(M) d4-d3 8. d6(n) c4(c) 9. a5(P) d3-d4 10. b5(N) d4-c4 11. c6(R) c6-d6 12. a7(R) a5-a4 13. b1-b2 a8(c) 14. c7(G) a7-a8 15. a2(K) a2-b2 16. c2(p) b2-b3 17. c2-b2 c4-d4 18. b2-b3 d4-d3 19. a6(p) d3-d2 20. c3(P) c3-b3 21. a6-a5 a4-a5 22. a3(N) c7-c6 23. d7(g) d2-c2 24. d8(p) c2-b2 25. b8(C) a8-a7 26. c8(C) b2-c2 27. b7(m) b8-d8 28. d7-d8 c6-c7 29. b7-b8 c7-b7 30. d8-c8 c2-d2 31. c1(M) c1-d1 32. c5(P) d1-c1 33. b8-a8 c1-d1 34. a8-b8 a1(m) 35. a1-a2 c5-c4 36. b8-a8 d2-c2 37. c8-d8 d1-c1 38. d8-d7 d6-c6 39. d7-d6 a7-a6 40. d6-c6 b7-a7 41. a8-b8 a7-b7 42. b8-a8 b7-a7 43. a8-b8 b6(p) 44. c6-c7 b5-b6 45. b4(r) b6-c6 46. b4-b5 a7-a8 47. c7-b7 a3-a4 48. b8-c8 c1-b1 49. c8-c7 c6-d6 50. c7-c6 b1-c1 51. c6-b6 c1-d1 52. b6-a6 d6-d7 53. a2-a3 b3-b2 54. a3-b3 a4-a3 55. a6-b6 d1-d2 56. b6-c6 d2-d1 57. c6-b6 d1-d2 58. b6-c6 c2-c1 59. c6-c5 c1-d1 60. c5-c6 d2-c2 61. c6-b6 d1-d2 62. b6-c6 d2-d1 63. c6-b6 d1-d2 64. b6-c6 c2-c1 65. c6-c5 c1-d1 66. c5-c6 d2-c2 67. c6-b6 d1-d2 68. b6-c6 d2-d1 69. c6-b6 d1-d2 70. b6-c6 c2-c1 71. c6-c5 c1-d1 72. c5-c6 d2-c2 73. c6-b6 d1-d2

Footnotes

Acknowledgements

This work was supported in part by the Ministry of Science and Technology of Taiwan under contracts 108-2221-E-305-008-MY3, 108-2221-E-003-011-MY3, 109-2634-F-009-019- and 109-2634-F-259-001- through Pervasive Artificial Intelligence Research (PAIR) Labs, Taiwan. We are grateful to the National Center for High-performance Computing for computer time and facilities.

References

Ballard, B.W. (1983). The *-minimax search procedure for trees containing chance nodes. Artificial Intelligence, 21(3), 327–350. doi:10.1016/S0004-3702(83)80015-0.

Chang, H.-J., Chen, J.-C., Fan, G.-Y. & Hsu, T.-s. (2018). Using Chinese dark chess endgame databases to validate and fine-tune game evaluation functions. ICGA Journal, 40(2), 45–60. doi:10.3233/ICG-180048.

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., Fan, G.-Y., Chang, H.-J. & Hsu, T.-s. (2018). Compressing Chinese dark chess endgame databases by deep learning. IEEE Transactions on Games, 10(4), 413–422. doi:10.1109/TG.2018.2802484.

Chen, J.-C., Lin, T.-Y. & Hsu, T.-s. (2015). Equivalence classes in dark chess endgames. IEEE Transactions on Games, 7(2), 109–122. doi:10.1080/0740817X.2014.892230.

Hsieh, C.-H. (2010). The study and implementation of food chain relations of the chess spices in Chinese dark chess. Master thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University, Taiwan (in Chinese).

Tseng, W.-J., Chen, J.-C., Chen, L.-P., Yen, S.-J. & Wu, I.-C. (2013). TCGA 2013 computer game tournament report. ICGA Journal, 36(3), 166–168. doi:10.3233/ICG-2013-36310.