On solving the 7,7,5-game and the 8,8,5-game
| Autor: | Chu-Ling Ko, Wei-Yuan Hsu, Ting-Han Wei, Jr-Chang Chen, Chu-Hsuan Hsueh, I-Chen Wu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
General Computer Science
Computer science Branching factor ComputingMilieux_PERSONALCOMPUTING 0102 computer and information sciences 02 engineering and technology 01 natural sciences Search tree Theoretical Computer Science 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm Combined method |
| Zdroj: | Theoretical Computer Science. 815:79-94 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2020.02.023 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect