Strategy optimization for deductive games

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

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

11 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)757-766
頁數10
期刊European Journal of Operational Research
183
發行號2
DOIs
出版狀態已發佈 - 2007 12月 1

ASJC Scopus subject areas

  • 一般電腦科學
  • 建模與模擬
  • 管理科學與經營研究
  • 資訊系統與管理

指紋

深入研究「Strategy optimization for deductive games」主題。共同形成了獨特的指紋。

引用此