TY - JOUR

T1 - Optimal algorithms for 2 × n AB games - A graph-partition approach

AU - Chen, Shan Tai

AU - Lin, Shun Shii

PY - 2004/1

Y1 - 2004/1

N2 - This paper presents new and systematic methodologies to analyze deductive games and obtain optimal algorithms for 2 × n AB games, where n ≥ 2. We have invented a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space, but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n AB games in the expected and worst cases, and are able to derive the following new results: (1) ⌈n/2⌉ + 1 guesses are necessary and sufficient for 2 × n AB games in the worst case, (2) the minimum number of guesses required for 2 × n AB games in the expected case is (4n3 + 21n2-76n + 72)/12n(n - 1) if n is even, and (4n3 + 21n2 - 82n + 105)/12n(n - 1) if n is odd. The optimization of this problem bears resemblance with other computational problems, such as circuit testing, differential cryptanalysis, on-line models with equivalent queries, and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems, as well as to any other combinatorial optimization problem.

AB - This paper presents new and systematic methodologies to analyze deductive games and obtain optimal algorithms for 2 × n AB games, where n ≥ 2. We have invented a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space, but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n AB games in the expected and worst cases, and are able to derive the following new results: (1) ⌈n/2⌉ + 1 guesses are necessary and sufficient for 2 × n AB games in the worst case, (2) the minimum number of guesses required for 2 × n AB games in the expected case is (4n3 + 21n2-76n + 72)/12n(n - 1) if n is even, and (4n3 + 21n2 - 82n + 105)/12n(n - 1) if n is odd. The optimization of this problem bears resemblance with other computational problems, such as circuit testing, differential cryptanalysis, on-line models with equivalent queries, and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems, as well as to any other combinatorial optimization problem.

KW - AB game

KW - Algorithms

KW - Game tree

KW - Mastermind

KW - Search strategies

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

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

M3 - Article

AN - SCOPUS:0842290663

SN - 1016-2364

VL - 20

SP - 105

EP - 126

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

IS - 1

ER -