Name
Abstract | ||
|---|---|---|
Chinese Dark Chess, a nondeterministic two-player game, has not been studied thoroughly. State-of-the-art programs focus on using search algorithms to explore the probability behavior of flipping unrevealed pieces in the opening and the midgame phases. There has been comparatively little research on opening books and endgame databases, especially endgames with nondeterministic flips. In this paper, we propose an equivalence relation that classifies the complex piece relations between the material combinations of each player, and derive a partition for all such material combinations. The technique can be applied to endgame database compression to reduce the number of endgames that need to be constructed. As a result, the computation time and the size of endgame databases can be reduced substantially. Furthermore, understanding the piece relations facilitates the development of a well-designed evaluation function and enhances the search efficiency. In Chinese Dark Chess, the number of nontrivial material combinations comprised of only revealed pieces is 8 $,$497 $,$176, and the number that contain at least one unrevealed piece is 239$,$980 $,$775 $,$397. Under the proposed method, the compression rates of the above material combinations reach 28.93% and 42.52%, respectively; if the method is applied to endgames comprised of three to eight pieces, the compression rates reach 5.82% and 5.98%, respectively. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TCIAIG.2014.2317832 | Computational Intelligence and AI in Games, IEEE Transactions |
Keywords | Field | DocType |
board game,chinese dark chess,endgame database,equivalence class,game of chance,material combination,search algorithms,materials,algorithm design and analysis,equivalence classes,games,probability,law,databases | Equivalence relation,Combinatorics,Search algorithm,Nondeterministic algorithm,Evaluation function,Chess endgame,Theoretical computer science,Equivalence class,Partition (number theory),Mathematics,Computation | Journal |
Volume | Issue | ISSN |
7 | 2 | 1943-068X |
Citations | PageRank | References |
11 | 0.81 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jr-Chang Chen | 1 | 42 | 15.19 |
| Ting-Yu Lin | 2 | 16 | 5.65 |
| Bo-Nian Chen | 3 | 40 | 4.91 |
| Tsan-sheng Hsu | 4 | 737 | 101.00 |