On solving the 7,7,5-game and the 8,8,5-game

Wei Yuan Hsu, Chu Ling Ko, Jr Chang Chen, Ting Han Wei, Chu Hsuan Hsueh, I. Chen Wu*

*Corresponding author for this work

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)79-94
Number of pages16
JournalTheoretical Computer Science
Volume815
DOIs
StatePublished - 2 May 2020

Keywords

  • k-in-a-row games
  • mnk-games
  • Pairing strategy
  • Positional games
  • Relevancy-zone

Fingerprint Dive into the research topics of 'On solving the 7,7,5-game and the 8,8,5-game'. Together they form a unique fingerprint.

Cite this