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

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

*Corresponding author for this work

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
Event11th International Conference on Advances in Computer Games, ACG 2005 - Taipei, Taiwan
Duration: 2005 Sept 62005 Sept 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
Country/TerritoryTaiwan
CityTaipei
Period2005/09/062005/09/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Exact-bound analyzes and optimal strategies for mastermind with a lie'. Together they form a unique fingerprint.

Cite this