Exact-bound analyzes and optimal strategies for mastermind with a lie

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

*此作品的通信作者

研究成果: 書貢獻/報告類型會議論文篇章

3 引文 斯高帕斯(Scopus)

摘要

This paper presents novel and systematic algorithms to solve a variant of the Mastermind game, which is called "Mastermind with a Lie". Firstly, we use the k-way-branching(KWB) algorithm to get an upper bound of the number of guesses for the problem. With the help of clustering technique, the KWB algorithm is able to obtain near-optimal results effectively and efficiently. Secondly, we propose a fast backtracking(PPBFB) algorithm based on the pigeonhole principle to get the lower bounds of the number of guesses. That is a computer-aided approach, which is able to estimate the depth of the game tree and to backtrack when the depth is larger than a predefined value. Moreover, we also develop two novel methods, named "volume-renewing" and "preprocessing". They can improve the precision in the estimation of the lower bound and speed up the game tree search. As a result of applying the KWB algorithm and the PPBFB algorithm, we are able to show that the upper bound is 7 and that is also the lower bound. Thus, the problem is solved completely and the exact bound of the number of guesses for the problem is 7.

原文英語
主出版物標題Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers
頁面195-209
頁數15
DOIs
出版狀態已發佈 - 2006
事件11th International Conference on Advances in Computer Games, ACG 2005 - Taipei, 臺灣
持續時間: 2005 九月 62005 九月 9

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
4250 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

其他

其他11th International Conference on Advances in Computer Games, ACG 2005
國家/地區臺灣
城市Taipei
期間2005/09/062005/09/09

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「Exact-bound analyzes and optimal strategies for mastermind with a lie」主題。共同形成了獨特的指紋。

引用此