Optimal algorithms for 2 × n mastermind games - A graph-partition approach

Shan Tai Chen*, Shun Shii Lin

*此作品的通信作者

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

14 引文 斯高帕斯(Scopus)

摘要

This paper presents new and systematic methodologies for analyzing deductive games and obtaining optimal algorithms for 2 × n Mastermind games, where n ≥ 2. We have developed a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n Mastermind games in the expected and worst cases and are able to derive the following new results: (i) ⌊n/2⇔ + 2 guesses are necessary and sufficient for 2 × n Mastermind games in the worst case. (ii) The minimum number of guesses required for 2 × n Mastermind games in the expected case is (8n3 + 51n2 - 74n + 48)/24n2 if n is even and (8n3 + 51n2 - 80n + 69)/24n2 if n is odd. The optimization of this problem bears a resemblance to other computational problems such as circuit testing, differential cryptanalysis, on-line models with equivalent queries and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.

原文英語
頁(從 - 到)602-611
頁數10
期刊Computer Journal
47
發行號5
DOIs
出版狀態已發佈 - 2004

ASJC Scopus subject areas

  • 電腦科學(全部)

指紋

深入研究「Optimal algorithms for 2 × n mastermind games - A graph-partition approach」主題。共同形成了獨特的指紋。

引用此