Optimal analyses for 3×n AB games in the worst case

Li Te Huang, Shun Shii Lin

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

1 Citation (Scopus)

Abstract

The past decades have witnessed a growing interest in research on deductive games such as Mastermind and AB game. Because of the complicated behavior of deductive games, tree-search approaches are often adopted to find their optimal strategies. In this paper, a generalized version of deductive games, called 3×n AB games, is introduced. However, traditional tree-search approaches are not appropriate for solving this problem since it can only solve instances with smaller n. For larger values of n, a systematic approach is necessary. Therefore, intensive analyses of playing 3×n AB games in the worst case optimally are conducted and a sophisticated method, called structural reduction, which aims at explaining the worst situation in this game is developed in the study. Furthermore, a worthwhile formula for calculating the optimal numbers of guesses required for arbitrary values of n is derived and proven to be final.

Original languageEnglish
Title of host publicationAdvances in Computer Games - 12th International Conference, ACG 2009, Revised Papers
Pages170-181
Number of pages12
DOIs
Publication statusPublished - 2010 Jun 25
Event12th International Conference on Advances in Computer Games, ACG 2009 - Pamplona, Spain
Duration: 2009 May 112009 May 13

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6048 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Advances in Computer Games, ACG 2009
CountrySpain
CityPamplona
Period09/5/1109/5/13

Fingerprint

Game
Search Trees
Guess
Optimal Strategy
Necessary
Arbitrary

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Huang, L. T., & Lin, S. S. (2010). Optimal analyses for 3×n AB games in the worst case. In Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers (pp. 170-181). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6048 LNCS). https://doi.org/10.1007/978-3-642-12993-3_16

Optimal analyses for 3×n AB games in the worst case. / Huang, Li Te; Lin, Shun Shii.

Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers. 2010. p. 170-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6048 LNCS).

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

Huang, LT & Lin, SS 2010, Optimal analyses for 3×n AB games in the worst case. in Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6048 LNCS, pp. 170-181, 12th International Conference on Advances in Computer Games, ACG 2009, Pamplona, Spain, 09/5/11. https://doi.org/10.1007/978-3-642-12993-3_16
Huang LT, Lin SS. Optimal analyses for 3×n AB games in the worst case. In Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers. 2010. p. 170-181. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-12993-3_16
Huang, Li Te ; Lin, Shun Shii. / Optimal analyses for 3×n AB games in the worst case. Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers. 2010. pp. 170-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{e2329a1b4d284284bf6fafb50dab3f4c,
title = "Optimal analyses for 3×n AB games in the worst case",
abstract = "The past decades have witnessed a growing interest in research on deductive games such as Mastermind and AB game. Because of the complicated behavior of deductive games, tree-search approaches are often adopted to find their optimal strategies. In this paper, a generalized version of deductive games, called 3×n AB games, is introduced. However, traditional tree-search approaches are not appropriate for solving this problem since it can only solve instances with smaller n. For larger values of n, a systematic approach is necessary. Therefore, intensive analyses of playing 3×n AB games in the worst case optimally are conducted and a sophisticated method, called structural reduction, which aims at explaining the worst situation in this game is developed in the study. Furthermore, a worthwhile formula for calculating the optimal numbers of guesses required for arbitrary values of n is derived and proven to be final.",
author = "Huang, {Li Te} and Lin, {Shun Shii}",
year = "2010",
month = "6",
day = "25",
doi = "10.1007/978-3-642-12993-3_16",
language = "English",
isbn = "3642129927",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "170--181",
booktitle = "Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers",

}

TY - GEN

T1 - Optimal analyses for 3×n AB games in the worst case

AU - Huang, Li Te

AU - Lin, Shun Shii

PY - 2010/6/25

Y1 - 2010/6/25

N2 - The past decades have witnessed a growing interest in research on deductive games such as Mastermind and AB game. Because of the complicated behavior of deductive games, tree-search approaches are often adopted to find their optimal strategies. In this paper, a generalized version of deductive games, called 3×n AB games, is introduced. However, traditional tree-search approaches are not appropriate for solving this problem since it can only solve instances with smaller n. For larger values of n, a systematic approach is necessary. Therefore, intensive analyses of playing 3×n AB games in the worst case optimally are conducted and a sophisticated method, called structural reduction, which aims at explaining the worst situation in this game is developed in the study. Furthermore, a worthwhile formula for calculating the optimal numbers of guesses required for arbitrary values of n is derived and proven to be final.

AB - The past decades have witnessed a growing interest in research on deductive games such as Mastermind and AB game. Because of the complicated behavior of deductive games, tree-search approaches are often adopted to find their optimal strategies. In this paper, a generalized version of deductive games, called 3×n AB games, is introduced. However, traditional tree-search approaches are not appropriate for solving this problem since it can only solve instances with smaller n. For larger values of n, a systematic approach is necessary. Therefore, intensive analyses of playing 3×n AB games in the worst case optimally are conducted and a sophisticated method, called structural reduction, which aims at explaining the worst situation in this game is developed in the study. Furthermore, a worthwhile formula for calculating the optimal numbers of guesses required for arbitrary values of n is derived and proven to be final.

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

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

U2 - 10.1007/978-3-642-12993-3_16

DO - 10.1007/978-3-642-12993-3_16

M3 - Conference contribution

AN - SCOPUS:77953801681

SN - 3642129927

SN - 9783642129926

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

SP - 170

EP - 181

BT - Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers

ER -