An efficient approach to solve mastermind optimally

Li Te Huang, Shan Tai Chen, Shih Chieh Huang, Shun-Shii Lin

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The Mastermind game is well-known around the world. In recent decades, several approaches have been adopted for solving Mastermind in the worst case. An optimal strategy has finally been proposed by Koyoma and Lai in 1993 by using an exhaustive search for finding the optimal strategy in the expected case. In this paper, a more efficient backtracking algorithm with branch-and-bound pruning (BABBP) for Mastermind in the expected case is introduced, and an alternative optimal strategy is obtained eventually. Furthermore, the novel approach may be presumably applied to other games with some modifications in order to speed up the search.

Original languageEnglish
Pages (from-to)143-149
Number of pages7
JournalICGA Journal
Volume30
Issue number3
Publication statusPublished - 2007 Sep 1

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computational Mechanics
  • Human-Computer Interaction
  • Computer Graphics and Computer-Aided Design

Cite this

Huang, L. T., Chen, S. T., Huang, S. C., & Lin, S-S. (2007). An efficient approach to solve mastermind optimally. ICGA Journal, 30(3), 143-149.

An efficient approach to solve mastermind optimally. / Huang, Li Te; Chen, Shan Tai; Huang, Shih Chieh; Lin, Shun-Shii.

In: ICGA Journal, Vol. 30, No. 3, 01.09.2007, p. 143-149.

Research output: Contribution to journalArticle

Huang, LT, Chen, ST, Huang, SC & Lin, S-S 2007, 'An efficient approach to solve mastermind optimally', ICGA Journal, vol. 30, no. 3, pp. 143-149.
Huang LT, Chen ST, Huang SC, Lin S-S. An efficient approach to solve mastermind optimally. ICGA Journal. 2007 Sep 1;30(3):143-149.
Huang, Li Te ; Chen, Shan Tai ; Huang, Shih Chieh ; Lin, Shun-Shii. / An efficient approach to solve mastermind optimally. In: ICGA Journal. 2007 ; Vol. 30, No. 3. pp. 143-149.
@article{a8d73d613149420ca0a180f12d77660b,
title = "An efficient approach to solve mastermind optimally",
abstract = "The Mastermind game is well-known around the world. In recent decades, several approaches have been adopted for solving Mastermind in the worst case. An optimal strategy has finally been proposed by Koyoma and Lai in 1993 by using an exhaustive search for finding the optimal strategy in the expected case. In this paper, a more efficient backtracking algorithm with branch-and-bound pruning (BABBP) for Mastermind in the expected case is introduced, and an alternative optimal strategy is obtained eventually. Furthermore, the novel approach may be presumably applied to other games with some modifications in order to speed up the search.",
author = "Huang, {Li Te} and Chen, {Shan Tai} and Huang, {Shih Chieh} and Shun-Shii Lin",
year = "2007",
month = "9",
day = "1",
language = "English",
volume = "30",
pages = "143--149",
journal = "ICGA Journal",
issn = "1389-6911",
publisher = "Tilburg Centre for Cogination and Communication",
number = "3",

}

TY - JOUR

T1 - An efficient approach to solve mastermind optimally

AU - Huang, Li Te

AU - Chen, Shan Tai

AU - Huang, Shih Chieh

AU - Lin, Shun-Shii

PY - 2007/9/1

Y1 - 2007/9/1

N2 - The Mastermind game is well-known around the world. In recent decades, several approaches have been adopted for solving Mastermind in the worst case. An optimal strategy has finally been proposed by Koyoma and Lai in 1993 by using an exhaustive search for finding the optimal strategy in the expected case. In this paper, a more efficient backtracking algorithm with branch-and-bound pruning (BABBP) for Mastermind in the expected case is introduced, and an alternative optimal strategy is obtained eventually. Furthermore, the novel approach may be presumably applied to other games with some modifications in order to speed up the search.

AB - The Mastermind game is well-known around the world. In recent decades, several approaches have been adopted for solving Mastermind in the worst case. An optimal strategy has finally been proposed by Koyoma and Lai in 1993 by using an exhaustive search for finding the optimal strategy in the expected case. In this paper, a more efficient backtracking algorithm with branch-and-bound pruning (BABBP) for Mastermind in the expected case is introduced, and an alternative optimal strategy is obtained eventually. Furthermore, the novel approach may be presumably applied to other games with some modifications in order to speed up the search.

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

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

M3 - Article

AN - SCOPUS:37149052701

VL - 30

SP - 143

EP - 149

JO - ICGA Journal

JF - ICGA Journal

SN - 1389-6911

IS - 3

ER -