2010 | OriginalPaper | Buchkapitel
Optimal Analyses for 3×n AB Games in the Worst Case
verfasst von : Li-Te Huang, Shun-Shii Lin
Erschienen in: Advances in Computer Games
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.