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

Li Te Huang*, Shun Shii Lin

*Corresponding author for this work

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

1 Citation (Scopus)


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
Number of pages12
Publication statusPublished - 2010
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


Other12th International Conference on Advances in Computer Games, ACG 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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