A two-phase optimization algorithm for mastermind

Shan Tai Chen, Shun Shii Lin*, Li Te Huang


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

14 引文 斯高帕斯(Scopus)


This paper presents a systematic model, two-phase optimization algorithms (TPOA), for Mastermind. TPOA is not only able to efficiently obtain approximate results but also effectively discover results that are getting closer to the optima. This systematic approach could be regarded as a general improver for heuristics. That is, given a constructive heuristic, TPOA has a higher chance to obtain results better than those obtained by the heuristic. Moreover, it sometimes can achieve optimal results that are difficult to find by the given heuristic. Experimental results show that (i) TPOA with parameter setting (k, d) = (1, 1) is able to obtain the optimal result for the game in the worst case, where k is the branching factor and d is the exploration depth of the search space. (ii) Using a simple heuristic, TPOA achieves the optimal result for the game in the expected case with (k, d) = (180, 2). This is the first approximate approach to achieve the optimal result in the expected case.

頁(從 - 到)435-443
期刊Computer Journal
出版狀態已發佈 - 2007 7月

ASJC Scopus subject areas

  • 一般電腦科學


深入研究「A two-phase optimization algorithm for mastermind」主題。共同形成了獨特的指紋。