Name
Abstract | ||
|---|---|---|
An mnk-game is a kind of k-in-a-row game played on an m×n board, where two players alternatively mark empty squares with their own colors and the first player who gets k-consecutive marks (horizontally, vertically, or diagonally) wins. In this paper, we present an AND/OR search tree algorithm specifically for proving mnk-games. We first propose three novel methods to reduce the branching factor of AND/OR search trees. We also propose a new method to find pairing strategies, which further accelerate the proof of mnk-games. The combined methods drastically speed up the proof for the 7,7,5-game, which is solved in 2.5 seconds. Moreover, this paper is the first to solve the 8,8,5-game, which is proven as a draw within 17.4 hours. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.tcs.2020.02.023 | Theoretical Computer Science |
Keywords | DocType | Volume |
k-in-a-row games,mnk-games,Positional games,Pairing strategy,Relevancy-zone | Journal | 815 |
Issue | ISSN | Citations |
C | 0304-3975 | 1 |
PageRank | References | Authors |
0.39 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei-Yuan Hsu | 1 | 1 | 0.72 |
| Chu-Ling Ko | 2 | 1 | 0.72 |
| Jr-Chang Chen | 3 | 42 | 15.19 |
| Ting-Han Wei | 4 | 9 | 1.65 |
| Chu-Hsuan Hsueh | 5 | 11 | 4.21 |
| I.-C. Wu | 6 | 41 | 14.29 |