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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal analyses for 3×n AB games in the worst case'. Together they form a unique fingerprint.

  • 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