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

Li Te Huang, Shan Tai Chen, Shun Shii Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAdvances in Computer Games - 11th International Conference, ACG 2005, Revised Papers
Pages195-209
Number of pages15
DOIs
Publication statusPublished - 2006 Dec 1
Event11th International Conference on Advances in Computer Games, ACG 2005 - Taipei, Taiwan
Duration: 2005 Sep 62005 Sep 9

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4250 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Conference on Advances in Computer Games, ACG 2005
CountryTaiwan
CityTaipei
Period05/9/605/9/9

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Huang, L. T., Chen, S. T., & Lin, S. S. (2006). Exact-bound analyzes and optimal strategies for mastermind with a lie. In Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers (pp. 195-209). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4250 LNCS). https://doi.org/10.1007/11922155_15