A two-phase optimization algorithm for mastermind

Shan Tai Chen, Shun Shii Lin, Li Te Huang

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

This paper presents a systematic model, two-phase optimization algorithms (TPOA), for Mastermind. TPOA is not only able to efficiently obtain approximate results but also effectively discover results that are getting closer to the optima. This systematic approach could be regarded as a general improver for heuristics. That is, given a constructive heuristic, TPOA has a higher chance to obtain results better than those obtained by the heuristic. Moreover, it sometimes can achieve optimal results that are difficult to find by the given heuristic. Experimental results show that (i) TPOA with parameter setting (k, d) = (1, 1) is able to obtain the optimal result for the game in the worst case, where k is the branching factor and d is the exploration depth of the search space. (ii) Using a simple heuristic, TPOA achieves the optimal result for the game in the expected case with (k, d) = (180, 2). This is the first approximate approach to achieve the optimal result in the expected case.

Original languageEnglish
Pages (from-to)435-443
Number of pages9
JournalComputer Journal
Volume50
Issue number4
DOIs
Publication statusPublished - 2007 Jul 1

Keywords

  • Algorithm
  • Deductive game
  • Mastermind
  • Search strategies

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

A two-phase optimization algorithm for mastermind. / Chen, Shan Tai; Lin, Shun Shii; Huang, Li Te.

In: Computer Journal, Vol. 50, No. 4, 01.07.2007, p. 435-443.

Research output: Contribution to journalArticle

Chen, Shan Tai ; Lin, Shun Shii ; Huang, Li Te. / A two-phase optimization algorithm for mastermind. In: Computer Journal. 2007 ; Vol. 50, No. 4. pp. 435-443.
@article{f0681a1d1cfb4c63adc8249240979ac7,
title = "A two-phase optimization algorithm for mastermind",
abstract = "This paper presents a systematic model, two-phase optimization algorithms (TPOA), for Mastermind. TPOA is not only able to efficiently obtain approximate results but also effectively discover results that are getting closer to the optima. This systematic approach could be regarded as a general improver for heuristics. That is, given a constructive heuristic, TPOA has a higher chance to obtain results better than those obtained by the heuristic. Moreover, it sometimes can achieve optimal results that are difficult to find by the given heuristic. Experimental results show that (i) TPOA with parameter setting (k, d) = (1, 1) is able to obtain the optimal result for the game in the worst case, where k is the branching factor and d is the exploration depth of the search space. (ii) Using a simple heuristic, TPOA achieves the optimal result for the game in the expected case with (k, d) = (180, 2). This is the first approximate approach to achieve the optimal result in the expected case.",
keywords = "Algorithm, Deductive game, Mastermind, Search strategies",
author = "Chen, {Shan Tai} and Lin, {Shun Shii} and Huang, {Li Te}",
year = "2007",
month = "7",
day = "1",
doi = "10.1093/comjnl/bxm006",
language = "English",
volume = "50",
pages = "435--443",
journal = "Computer Journal",
issn = "0010-4620",
publisher = "Oxford University Press",
number = "4",

}

TY - JOUR

T1 - A two-phase optimization algorithm for mastermind

AU - Chen, Shan Tai

AU - Lin, Shun Shii

AU - Huang, Li Te

PY - 2007/7/1

Y1 - 2007/7/1

N2 - This paper presents a systematic model, two-phase optimization algorithms (TPOA), for Mastermind. TPOA is not only able to efficiently obtain approximate results but also effectively discover results that are getting closer to the optima. This systematic approach could be regarded as a general improver for heuristics. That is, given a constructive heuristic, TPOA has a higher chance to obtain results better than those obtained by the heuristic. Moreover, it sometimes can achieve optimal results that are difficult to find by the given heuristic. Experimental results show that (i) TPOA with parameter setting (k, d) = (1, 1) is able to obtain the optimal result for the game in the worst case, where k is the branching factor and d is the exploration depth of the search space. (ii) Using a simple heuristic, TPOA achieves the optimal result for the game in the expected case with (k, d) = (180, 2). This is the first approximate approach to achieve the optimal result in the expected case.

AB - This paper presents a systematic model, two-phase optimization algorithms (TPOA), for Mastermind. TPOA is not only able to efficiently obtain approximate results but also effectively discover results that are getting closer to the optima. This systematic approach could be regarded as a general improver for heuristics. That is, given a constructive heuristic, TPOA has a higher chance to obtain results better than those obtained by the heuristic. Moreover, it sometimes can achieve optimal results that are difficult to find by the given heuristic. Experimental results show that (i) TPOA with parameter setting (k, d) = (1, 1) is able to obtain the optimal result for the game in the worst case, where k is the branching factor and d is the exploration depth of the search space. (ii) Using a simple heuristic, TPOA achieves the optimal result for the game in the expected case with (k, d) = (180, 2). This is the first approximate approach to achieve the optimal result in the expected case.

KW - Algorithm

KW - Deductive game

KW - Mastermind

KW - Search strategies

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

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

U2 - 10.1093/comjnl/bxm006

DO - 10.1093/comjnl/bxm006

M3 - Article

AN - SCOPUS:34447499942

VL - 50

SP - 435

EP - 443

JO - Computer Journal

JF - Computer Journal

SN - 0010-4620

IS - 4

ER -