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

Optimal Strategy
Guess
Branching
Game
Lower bound
Upper bound
Backtracking
Search Trees
Preprocessing
Speedup
Clustering
Estimate

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

Exact-bound analyzes and optimal strategies for mastermind with a lie. / Huang, Li Te; Chen, Shan Tai; Lin, Shun Shii.

Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers. 2006. p. 195-209 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4250 LNCS).

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

Huang, LT, Chen, ST & Lin, SS 2006, Exact-bound analyzes and optimal strategies for mastermind with a lie. in Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4250 LNCS, pp. 195-209, 11th International Conference on Advances in Computer Games, ACG 2005, Taipei, Taiwan, 05/9/6. https://doi.org/10.1007/11922155_15
Huang LT, Chen ST, Lin SS. Exact-bound analyzes and optimal strategies for mastermind with a lie. In Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers. 2006. p. 195-209. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11922155_15
Huang, Li Te ; Chen, Shan Tai ; Lin, Shun Shii. / Exact-bound analyzes and optimal strategies for mastermind with a lie. Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers. 2006. pp. 195-209 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{cf1446db787841cb86d2346f21691e83,
title = "Exact-bound analyzes and optimal strategies for mastermind with a lie",
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.",
author = "Huang, {Li Te} and Chen, {Shan Tai} and Lin, {Shun Shii}",
year = "2006",
month = "12",
day = "1",
doi = "10.1007/11922155_15",
language = "English",
isbn = "3540488871",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "195--209",
booktitle = "Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers",

}

TY - GEN

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

AU - Huang, Li Te

AU - Chen, Shan Tai

AU - Lin, Shun Shii

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70349351662&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349351662&partnerID=8YFLogxK

U2 - 10.1007/11922155_15

DO - 10.1007/11922155_15

M3 - Conference contribution

AN - SCOPUS:70349351662

SN - 3540488871

SN - 9783540488873

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 195

EP - 209

BT - Advances in Computer Games - 11th International Conference, ACG 2005, Revised Papers

ER -