Optimal algorithms for 2 × n mastermind games - A graph-partition approach

Shan Tai Chen, Shun-Shii Lin

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

This paper presents new and systematic methodologies for analyzing deductive games and obtaining optimal algorithms for 2 × n Mastermind games, where n ≥ 2. We have developed a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n Mastermind games in the expected and worst cases and are able to derive the following new results: (i) ⌊n/2⇔ + 2 guesses are necessary and sufficient for 2 × n Mastermind games in the worst case. (ii) The minimum number of guesses required for 2 × n Mastermind games in the expected case is (8n3 + 51n2 - 74n + 48)/24n2 if n is even and (8n3 + 51n2 - 80n + 69)/24n2 if n is odd. The optimization of this problem bears a resemblance to other computational problems such as circuit testing, differential cryptanalysis, on-line models with equivalent queries and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.

Original languageEnglish
Pages (from-to)602-611
Number of pages10
JournalComputer Journal
Volume47
Issue number5
DOIs
Publication statusPublished - 2004 Sep 21

Fingerprint

Combinatorial optimization
Networks (circuits)
Testing

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Optimal algorithms for 2 × n mastermind games - A graph-partition approach. / Chen, Shan Tai; Lin, Shun-Shii.

In: Computer Journal, Vol. 47, No. 5, 21.09.2004, p. 602-611.

Research output: Contribution to journalArticle

@article{b3078204d7f14047b51b97c5b72c8910,
title = "Optimal algorithms for 2 × n mastermind games - A graph-partition approach",
abstract = "This paper presents new and systematic methodologies for analyzing deductive games and obtaining optimal algorithms for 2 × n Mastermind games, where n ≥ 2. We have developed a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n Mastermind games in the expected and worst cases and are able to derive the following new results: (i) ⌊n/2⇔ + 2 guesses are necessary and sufficient for 2 × n Mastermind games in the worst case. (ii) The minimum number of guesses required for 2 × n Mastermind games in the expected case is (8n3 + 51n2 - 74n + 48)/24n2 if n is even and (8n3 + 51n2 - 80n + 69)/24n2 if n is odd. The optimization of this problem bears a resemblance to other computational problems such as circuit testing, differential cryptanalysis, on-line models with equivalent queries and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.",
author = "Chen, {Shan Tai} and Shun-Shii Lin",
year = "2004",
month = "9",
day = "21",
doi = "10.1093/comjnl/47.5.602",
language = "English",
volume = "47",
pages = "602--611",
journal = "Computer Journal",
issn = "0010-4620",
publisher = "Oxford University Press",
number = "5",

}

TY - JOUR

T1 - Optimal algorithms for 2 × n mastermind games - A graph-partition approach

AU - Chen, Shan Tai

AU - Lin, Shun-Shii

PY - 2004/9/21

Y1 - 2004/9/21

N2 - This paper presents new and systematic methodologies for analyzing deductive games and obtaining optimal algorithms for 2 × n Mastermind games, where n ≥ 2. We have developed a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n Mastermind games in the expected and worst cases and are able to derive the following new results: (i) ⌊n/2⇔ + 2 guesses are necessary and sufficient for 2 × n Mastermind games in the worst case. (ii) The minimum number of guesses required for 2 × n Mastermind games in the expected case is (8n3 + 51n2 - 74n + 48)/24n2 if n is even and (8n3 + 51n2 - 80n + 69)/24n2 if n is odd. The optimization of this problem bears a resemblance to other computational problems such as circuit testing, differential cryptanalysis, on-line models with equivalent queries and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.

AB - This paper presents new and systematic methodologies for analyzing deductive games and obtaining optimal algorithms for 2 × n Mastermind games, where n ≥ 2. We have developed a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n Mastermind games in the expected and worst cases and are able to derive the following new results: (i) ⌊n/2⇔ + 2 guesses are necessary and sufficient for 2 × n Mastermind games in the worst case. (ii) The minimum number of guesses required for 2 × n Mastermind games in the expected case is (8n3 + 51n2 - 74n + 48)/24n2 if n is even and (8n3 + 51n2 - 80n + 69)/24n2 if n is odd. The optimization of this problem bears a resemblance to other computational problems such as circuit testing, differential cryptanalysis, on-line models with equivalent queries and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.

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

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

U2 - 10.1093/comjnl/47.5.602

DO - 10.1093/comjnl/47.5.602

M3 - Article

AN - SCOPUS:4444355453

VL - 47

SP - 602

EP - 611

JO - Computer Journal

JF - Computer Journal

SN - 0010-4620

IS - 5

ER -