Browsing by Author "Hsu, Wei-Yuan"

Now showing 1 - 2 of 2

On solving the 7,7,5-game and the 8,8,5-game
(2020-05-02)
Hsu, Wei-Yuan
;
Ko, Chu-Ling
;
Chen, Jr-Chang
;
Wei, Ting-Han
;
Hsueh, Chu-Hsuan
An mnk-game is a kind of k-in-a-row game played on an m x nboard, 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. (C) 2020 Elsevier B.V. All rights reserved.
Solving 7,7,5-game and 8,8,5-game
(2018-01-01)
Hsu, Wei-Yuan
;
Ko, Chu-Ling
;
Hsueh, Chu-Hsuan
;
Wu, I-Chen
;
資訊工程學系
An mnk-game is a kind of k-in-a-row game played on an m x n chess board, where two players alternatively mark empty squares with their own colors and the first one to get k-consecutive marks wins. This paper solves 7,7,5-game and 8,8,5-game as draws. In the proof, we propose some methods based on pairing strategies and potential weights, and then use a program implementing these methods to solve 7,7,5-game in about one minute and 8,8,5-game in about three days.