Strategy optimization for deductive games

Shan Tai Chen, Shun Shii Lin, Li Te Huang, Sheng Hsuan Hsu

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

This paper presents novel algorithms for strategy optimization for deductive games. First, a k-way-branching (KWB) algorithm, taking advantage of a clustering technique, can obtain approximate results effectively. Second, a computer-aided verification algorithm, called the Pigeonhole-principle-based backtracking (PPBB) algorithm, is developed to discover the lower bound of the number of guesses required for the games. These algorithms have been successfully applied to deductive games, Mastermind and "Bulls and Cows." Experimental results show that KWB outperforms previously published approximate strategies. Furthermore, by applying the algorithms, we derive the theorem: 7 guesses are necessary and sufficient for the "Bulls and Cows" in the worst case. These results suggest strategies for other search problems.

Original languageEnglish
Pages (from-to)757-766
Number of pages10
JournalEuropean Journal of Operational Research
Volume183
Issue number2
DOIs
Publication statusPublished - 2007 Dec 1

Keywords

  • Algorithm
  • Bulls and cows
  • Mastermind
  • Pigeonhole principle
  • Search strategies

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Strategy optimization for deductive games'. Together they form a unique fingerprint.

  • Cite this