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

Li Te Huang; Shun Shii Lin

doi:10.1007/978-3-642-12993-3_16

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

Li Te Huang^*, Shun Shii Lin

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers
Pages	170-181
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-12993-3_16
Publication status	Published - 2010
Event	12th International Conference on Advances in Computer Games, ACG 2009 - Pamplona, Spain Duration: 2009 May 11 → 2009 May 13

Publication series

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

Other

Other	12th International Conference on Advances in Computer Games, ACG 2009
Country/Territory	Spain
City	Pamplona
Period	2009/05/11 → 2009/05/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

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 proceeding › Conference 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, 2009/05/11. https://doi.org/10.1007/978-3-642-12993-3_16

@inproceedings{41654c472a4e4be59bbfd2a9a384f959,

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",

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",

note = "12th International Conference on Advances in Computer Games, ACG 2009 ; Conference date: 11-05-2009 Through 13-05-2009",

}

TY - GEN

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

AU - Huang, Li Te

AU - Lin, Shun Shii

PY - 2010

Y1 - 2010

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

T2 - 12th International Conference on Advances in Computer Games, ACG 2009

Y2 - 11 May 2009 through 13 May 2009

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this