在資訊科技快速發展的今日，仍有許多複雜的組合最佳化問題(combinatorial
optimization problems)無論對演算法的設計或計算機的速度都是重大的挑戰，例如：編碼
問題(coding problems)、電路測試(circuit testing)、附加條件搜尋(additive search problem),
資料庫的線上查詢(on-line models with equivalent queries)，與密碼系統破解(differential
cryptanalysis)。而這些問題的都與演繹競局最佳化相關聯。亦即：在演繹競局最佳化問題
中得到的任何結論或成果，皆可能應用到上述重要科技領域的發展，可說是現今電腦科
學領域中的ㄧ門重要的課題。
一般而言，競局問題的計算複雜度相當高，通常皆為Pspace、Exptime 或者是Expspace
的問題，因為其計算複雜度會隨著問題大小(problem size)的增大而呈指數成長，對於較
大的問題而言，幾乎是不可能在多項式時間(polynomial time)內找到確定性(deterministic)
的最佳策略。在本研究中，我們首先針對著名的電腦科學家Knuth 提出的演繹競局最佳
化問題：Mastermind 和AB game (在歐洲叫做"bulls and cows")及其變化做深入的研究。
其次，對於更一般化的最佳化問題，我們不但深入的分析與探討機率演算法(probabilistic
algorithm)、近似演算法(approximate algorithm)及平行演算法(parallel algorithm)等技術的
特性與效能，更利用這些演算法的優點與特性，提出了一系列嶄新且有系統的最佳化演
算法，應用這些演算法來有效的解決更複雜的演繹競局及相關組合最佳化問題，此研究
中提出的演算法有：(1)圖形分割演算法(graph-partition, GP)，(2) k 分支逼近演算法
(k-way-branching, KWB) ， (3) 應用鴿籠定理的回溯搜尋法(pigeonhole-principle-based
backtracking, PPBB)，(4)菁英演化式演算法(elitism-based evolutionary algorithm, EBEA)，
以及其平行分散式的演算法(5) DEBEA。
首先，我們利用競局樹(Game tree)的一些特性：例如樹的外部路徑長度(external path
length)與高度(height)來具體描述整個問題的架構；除此之外，以競局圖(Game graph)來表
示競局過程中的每ㄧ個狀態。圖形分割演算法(GP)就是建立在這個架構上，藉由此架構，
我們發現競局圖中一些對稱(symmetric)、全等(equivalent)和遞迴(recursive)的特性，利用這些特性，不但減少了整個問題的搜尋空間，更幫助我們有效率的尋找最佳策略。也因
此發展出在平均狀況(expected case)和最差狀況(the worst case)下解決這類型問題的最佳
策略，我們得到了以下的最佳化結果：
(1) 2×n AB game 在最差狀況下，最多必須要猜n/2+1 次。
(2) 2×n AB game 在平均狀況下，當n 是偶數時平均猜測次數為(4n3+21n2 -76n+72)/ 12n(n-1)
次；而當n 是奇數時為(4n3+21n2 -82n+105)/12n(n-1)次。
(3) 2×n Mastermind 在最差情況下，最多必須要猜n/2+2 次。
(4) 2×n Mastermind 在平均狀況下，當n 是偶數時需要猜(8n3+51n2-74n+48)/24n2 次；當n
是奇數時要猜(8n3+51n2-80n+69) / 24n2 次。
其次，我們提出k 分支近似演算法(KWB)，KWB 已成功的應用於找尋4×10 AB game
的最佳策略。此演算法可以獲得在最差狀況下的最佳策略，以及在平均情況下接近最佳
(near-optimal)的策略；而且如果在執行時間和空間允許的情況下，我們可以增加參數k
的值而使得所得的策略更接近最佳解。另外，我們提出了擴展鴿籠定理(extended
pigeonhole principle)，並利用其發展一套電腦輔助驗證的演算法PPBB 來證明在4×10 AB
game 在最差情況下所需猜測次數的下限(lower bound)，藉此可證明在最差狀況下，我們
所獲得的策略為最佳化策略。利用這KWB 與PPBB 演算法，我們得到以下新的結果：
(1) 在4×6 Mastermind 競局的期望情況下，當k=1 時，近似演算法的結果是97.385 %接
近最佳解；當k=40 時，結果是99.487 %接近最佳解，此結果較先前所有文獻中最好
的heuristic 策略為佳。
(2) 在4×10 AB Game 最差情況下，我們得到了最佳策略，其中至多只需要猜7 次；在平
均狀況下也得到了一個平均猜測次數為5.268 次的策略。
(3) 為了將成果提供各界參考運用，本研究在演繹競局上所提出的最佳化演算法已在網頁
上完成系統實作。網址如下：http://alg.csie.ntnu.edu.tw/deductive_game/
在此研究的最後部分，我們探討演化式演算法來處理較複雜的演繹競局及相關的組
合最佳化問題；其中，我們提出了菁英演化式演算法(EBEA)，EBEA 很成功的應用於一
個NP-complete 問題：二元決策圖(BDD)最佳化問題。我們也在叢集電腦(PC cluster)上發展了一套有效率的分散式演算法(DEBEA)，並比較與分析其平行化的效能。應用EBEA
與DEBEA 於BDD 最佳化問題，可獲致以下新的結果：
(1) 在EBEA 中，我們提出了ㄧ個演化式演算法的終止機制：stable function，並推導出
該機制一些很好的特性，這些特性能幫助我們選擇終止條件，而有效的減少程式的執
行時間。
(2) 在BDD 基準測試電路LGSynth91 中，EBEA 能夠很有效率的將所有最佳解已知
(exact-size-known)的測試電路(benchmarks)求出最佳解。
(3) 藉由多處理器的合作，對LGSynth91 中較大的測試電路而言，DEBEA 都能有效的求
得甚而超越目前文獻已知的最佳解。

Abstract
With the rapid development of information technologies, many state-of-the-art combinatorial
optimization problems— such as coding, circuit testing, additive search, online models with
equivalent queries and differential cryptanalysis— are related to solutions for deductive games.
In other words, any conclusion drawn from this kind of game may be applied, although probably
not directly, to any of these problems as well as to any other combinatorial optimization problem.
The optimization problems mainly considered in this study are two kinds of well-known
deductive games: Mastermind and AB games (or "bulls and cows"), the optimization problems of
which were proposed by the renowned scientist Donald E. Knuth. To analyze and solve the
games, we propose a series of novel and systematic optimization algorithms and approaches,
including graph-partition (GP), pigeonhole-principle-based backtracking (PPBB), and
k-way-branching (KWB) approaches. Moreover, evolutionary algorithms are investigated for
solving the games with larger sizes and related hard-combinatorial problems.
The graph-partition approach, which takes advantage of properties of game trees and a
graphic model for representing the game-guessing process, has been successfully applied to
completely solve 2×n AB games and 2×n Mastermind games. With this novel approach, we find
some symmetric, isomorphic, and recursive structures in the game-guessing 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 the games in both the
expected and the worst cases. We summarize the optimal results for the games as follows:
(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.
(3) n/2+2 guesses are necessary and sufficient for 2×n Mastermind games in the worst case.
(4) The minimum number of guesses required for 2×n Mastermind games in the expected case is
(8n3+51n2 -74n+48)/24n2 if n is even, and (8n3+51n2 -80n+69)/24n2 if n is odd.
Abstract
With the rapid development of information technologies, many state-of-the-art combinatorial
optimization problems— such as coding, circuit testing, additive search, online models with
equivalent queries and differential cryptanalysis— are related to solutions for deductive games.
In other words, any conclusion drawn from this kind of game may be applied, although probably
not directly, to any of these problems as well as to any other combinatorial optimization problem.
The optimization problems mainly considered in this study are two kinds of well-known
deductive games: Mastermind and AB games (or "bulls and cows"), the optimization problems of
which were proposed by the renowned scientist Donald E. Knuth. To analyze and solve the
games, we propose a series of novel and systematic optimization algorithms and approaches,
including graph-partition (GP), pigeonhole-principle-based backtracking (PPBB), and
k-way-branching (KWB) approaches. Moreover, evolutionary algorithms are investigated for
solving the games with larger sizes and related hard-combinatorial problems.
The graph-partition approach, which takes advantage of properties of game trees and a
graphic model for representing the game-guessing process, has been successfully applied to
completely solve 2×n AB games and 2×n Mastermind games. With this novel approach, we find
some symmetric, isomorphic, and recursive structures in the game-guessing 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 the games in both the
expected and the worst cases. We summarize the optimal results for the games as follows:
(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.
(3) n/2+2 guesses are necessary and sufficient for 2×n Mastermind games in the worst case.
(4) The minimum number of guesses required for 2×n Mastermind games in the expected case is
(8n3+51n2 -74n+48)/24n2 if n is even, and (8n3+51n2 -80n+69)/24n2 if n is odd.

[Alb02a] Alba, E. (2002). “Parallel evolutionary algorithms can achieve super-linear
performance,” Information Processing Letters, 82, pp. 7-13.
[Alb02b] Alba, E. and Tomassini, M. (2002). “Parallelism and Evolutionary Algorithms,” IEEE
Trans. on Evolutionary Computation, Vol. 6, No. 5, pp. 443-462.
[App77] Appel, K. and Jaken, W. (1977). “Every Planar Map is Four Colorable: Part I;
Discharging,” Illinois J. Math., 21, 429-490.
[Ben99] Bento, L. Pereira, L. Rosa, A. (1999). “Mastermind by evolutionary algorithms,” in
Proceedings of the International Symposium on Applied Computing, pp. 307-311.
[Ber96] Bernier, J. L. Herraiz, C. I., Merelo, J. J., Olmeda, S., and Prieto, A. (1996). “Solving
Mastermind using Gas and simulated annealing: a case of dynamic constraint
optimization,” in Proceedings PPSN, Parallel Problem Solving from Nature IV, in
Computer Science, 1141, pp. 554-563.
[Blu03] Blum, C. and Roli, A. 2003. Metaheuristics in Combinatorial Optimization: Overview
and Conceptual Comparison. ACM Computing Surveys, Vol. 35, No. 3, pp. 268-308.
[Bol96a] Bolling, B. and I. Wegener. (1996). “Improving the variable ordering of OBDDs is
NP-complete,” IEEE Trans. Computer., vol. 45, pp 993-1002.
[Bol96b] Bolling, B. M. Löbbing, and I. Wegener. (1996). “On the effect of local changes in the
variable ordering of ordered decision diagrams,” Inform. Processing Lett., vol. 59, pp.
233-239.
[Box57] Box, G. (1957). “Evolutionary operation: A method for increasing industrial
productivity,” Journal of the Royal Statistic Society, 6(2), 81-101.
[Bra84] Brayton, R. K., G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni- Vincentelli,
(1984). Logic Minimization Algorithms for VLSI Synthesis. Boston: Kluwer AcademicPublishers.
[Bra96] Brassard, G. and Bratley, P. (1996). Fundamentals of Algorithmics. Prentice-Hall, Inc.
[Bry86] Bryant, R. E. (1986). “Graph-based algorithms for Boolean function manipulation,” IEEE
Trans. Comput., vol. 35, pp. 677-691.
[Bry92] Bryant, R. E. (1992). “Symbolic Boolean Manipulation with Ordered Binary-Decision
Diagrams,” ACM, Comp. Surveys, vol. 24, 293-318.
[Che96] Chen, Zhixiang and Cunha, Carlos (1996). “Finding a hidden code by asking questions,”
COCOON’96, Computing and Combinatorics, pp. 50-55.
[Cul93] Culberson J. (1993). Crossover versus mutation: fueling the debate: TGA versus GIGA.
In Proceedings of the 5th International Conference on Genetic Algorithms ICGA-93,
632.
[Dav85] Davis, L. (1985). ”Applying Adaptive Algorithms To Epistatic Domains,” in
Proceedings of the International Joint Conference on Artificial Intelligence, 162-164.
[Dre97] Drechsler, R. and N. Gockel. (1997). ”Minimization of BDDs by Evolutionary
Algorithms,” International Workshop on Logic Synthesis (IWLS'97).
[Dre00] Drechsler, R. Drechsler, N., and Günther, W. (2000). “Fast exact minimization of BDDs,”
IEEE Trans. Computer-Aided Designs, vol. 19, pp. 384-389.
[Dre01a] Drechsler, R., W. Günther, and F. Somenzi. (2001). “Using lower bounds during
dynamic BDD minimization,” IEEE Trans. Computer-Aided Designs, vol. 20, pp. 51-57.
[Dre01b] Drechsler, R. and W. Günther. (2001). “History-based dynamic BDD minimization,” the
VLSI journal, vol. 31, pp. 51-63.
[Esh91] Eshelman, L. J. (1991). “The CHC adaptive search algorithm: how to have safe search
when engaging in nontraditional genetic recombination.” Foundations of Genetic
Algorithms, FOGA-I, pp. 265-283.
[Fer99] Ferber, Jacques. (1999). Multi-Agent Systems - An Introduction to Distributed Artificial
Intelligence, Addison-Wesley.
[Flo88] Flood, M. M. (1988). “Sequential search strategies with Mastermind variants — Part 1,”
Journal of Recreational Mathematics, 20:2, pp. 105-126.
[Fog88] Fogel, D. B. (1988). “An Evolutionary Approach to the Traveling Salesman Problem.”
Biological Cybernetics 60, 139–144.
[Fog90] Fogel, D. B. (1990). “A Parallel Processing Approach to a Multiple Traveling Salesman
Problem Using Evolutionary Programming.” In Canter, L. (ed.) Proceedings on the
Fourth Annual Parallel Processing Symposium, 318–326.
[Fog93] Fogel, D. B. (1993). “Applying Evolutionary Programming to Selected Traveling
Salesman Problems.” Cybernetics and Systems 24, 27–36.
[Fri90] Friedman, S. J. and K. J. Supowit. (1990). “Finding the optimal variable ordering for
binary decision diagrams,” IEEE Trans. Comput., pp. 710-713, May.
[Fuj91] Fujita, M., Y. Matsunaga, and T. Kakuda. (1991). ”On variable ordering of binary
decision diagrams for the application of multi-level synthesis,” in European Conf.
Design Automat., 50-54.
[Gol85] Goldberg, D.E. and Lingle, R. Jr. (1985). “Alleles, loci, and the traveling salesman
problem.” In Proceedings of the 1st International Conference on Genetic Algorithms
ICGA-85, pp. 154-159.
[Gun99] Günther, W. and R. Drechsler. (1999). “Minimization of Free BDDs,” Design
Automation Conference, Proceedings of the ASP-DAC '99. Asia and South Pacific vol.1,
pp. 323 -326.
[Hol75] Holland, J. H. (1975). Adaptation in Natural and Artificial Systems, University of
Michigan Press.
[Hun02] Hung, N. N. William, Xiaoyu Song, El Mostapha Aboulhamid, and Michael A. Driscoll.
(2002). “BDD Minimization by Scatter Search,” IEEE Trans. CAD, vol. 21, No. 8, pp.
974-979.
[Irv78] Irving, R. W. (1978-79). “Towards an optimum Mastermind strategy,” Journal ofRecreational Mathematics, 11:2, pp. 81-87.
[Ish91] Ishiura, N., H. Sawada, and S. Yajima. (1991). “Minimization of binary decision diagrams
based on exchange of variables,” in Proc. Int. Conf. Computer-Aided Design, pp.
472-475.
[Jeo93] Jeong, S.-W., T.-S. Kim, and F. Somenzi. (1993). “An efficient method for optimal BDD
ordering computation,” in Proc. Int. Conf. VLSI and CAD.
[Kab00] Kabatianski, G. and Lebedev, V. (2000). “The Mastermind game and the rigidity of the
Hamming space,” in Proceedings of the International Symposium on Information
Theory IEEE, pp. 375-375.
[Kal03] Tom Kalisker and Doug Camens (2003). “Solving Mastermind Using Genetic
Algorithms,” GECCO 2003, LNCS 2724, pp. 1590-1591, 2003.
[Kan02] Kantard, M. (2002). Data Mining: Concepts, Models, Methods and Algorithms,
Wiley-IEEE Press.
[Keb92] Kebschull, U., E. Schubert, and W. Rosenstiel. (1992). “Multilevel logic synthesis based
on functional decision diagrams,” in Proc. European Design Automation Conf. pp
43-47.
[Knu76] Knuth, D. E. (1976). “The computer as Mastermind,” Journal of Recreational
Mathematics, 9:1, pp. 1-6.
[Knu98] Knuth, D. E. (1998). The art of computer programming- sorting and searching, volume
3, second edition.
[Ko86] Ko, K.-I. Teng, S.-C.. (1986). “On the number of queries necessary to identify a
permutation,” Journal of Algorithms, 7, pp. 449-462.
[Koy93] Koyama, K. Lai, T. W. (1993). “An optimal Mastermind strategy,” Journal of
Recreational Mathematics, 25, pp. 251-256.
[Kum94] Kumar V., A. Grama, A. Gupta, and G. Karypis. (1994). Introduction to Parallel
Computing: Design and Analysis of Algorithms. Redwood City, California:Benjamin/Cummings Publishing Co.
[Lin01] Lin, S. S. and C. J. Wei. (2001). “Improved Algorithm for Binary Decision Diagram
Minimization Problem,” National Computer Symposium, pp. A068-A079.
[Lin04] Lin, S. S. (2004). Web site: http://csie.ntnu.edu.tw/~linss/.
[Lyn96] Lynch, N. A. (1996). Distributed algorithms, Morgan Kaufmann Publishers, Inc.
[Mer99] Merelo, J. J. Carpio, J. Castillo, P. Rivas, V. M. Romero, G. GeNeura Team. (1999).
“Finding a needle in a haystack using hints and evolutionary computation: the case of
Genetic Mastermind,” Genetic and Evolutionary Computation Conference late
breaking papers books, pp. 184-192.
[Mic99] Michalewicz, Z., Genetic algorithms + Data structures = Evolution Programs, Springer,
Berlin: Germany, 1999.
[Mit97] Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
[Mol94] Möller, D. and R. Drechsler. (1994). “Symmetry based variable ordering for ROBDD’s,”
in Proc. IFIP Workshop on Logic and Architecture Synthesis, pp. 47-53.
[Neu82] Neuwirth, E. (1982) “Some strategies for Mastermind,” Zeitschrift fur Operations
Research, 26, pp. 257-278.
[Oli87] Oliver, I. M., Smith, D. J., and Holland, J. R. C. (1987). “A study of permutation
crossover operators on the traveling salesman problem.” In Proceedings of the 2nd
International Conference on Genetic Algorithms, ICGA-87, pp. 224–230.
[Pan95] Panda, S. and F. Somenzi. (1995). “Who are the variables in your neighborhood,” in Int.
Conf. Computer-Aided Design, pp. 74-77.
[Pap82] Papadimitriou, C. H. and Steiglitz, K. (1982). Combinatorial Optimization) Algorithms
and complexity. Dover Publications, Inc., New York.
[Pel02] Pelc, A. (2002). “Searching games with errors) fifty years of coping with liars,”Theoretical Computer Science, 270, pp. 71-109.
[Roc97] Roche, J. R. (1997). “The value of adaptive questions in generalized Mastermind,” in
Proceedings of the International Symposium on Information Theory IEEE, pp. 135-135.
[Rud93] Rudell, R. (1993). “Dynamic variable ordering for ordered binary decision diagrams,” Int.
Conf. Computer-Aided Design, pp. 42-47.
[Rus03] Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach,
Prentice-Hall.
[Sch99] Scholl, C., D. Möller, and P. Molitor. (1999). “BDD minimization Using Symmetries,”
IEEE Trans. Computer-Aided Designs of Integrated Circuits and Systems, vol. 18, no 2.
pp. 81-99.
[Sed88] Sedgewick, R. (1988). Algorithms, second edition, Addison-Wesley.
[Som01a] Somenzi, F. (2001). CUDD: CU Decision Diagram Package – Release 2.3.1 Technical
report, Dept. of Electrical and Computer Engineering, University of Colorado, Boulder,
Colorado.
[Som01b] Somenzi, F. (2001). Web site: http://vlsi.colorado.edu/~fabio.
[Thi94] Thierens, D., and Goldberg, D. E. (1994). “Elitist recombination: an integrated selection
recombination GA.” In Proceedings of the 1st IEEE World Congress on Computational
Intelligence, 508–512.
[Ula76] Ulam, S. M. (1976). Adventures of a Mathematician, Scribner, New York, p. 281.
[Whi89] Whitley, D., Starkweather, T., and Fuquay, D’A. (1989). “Scheduling problems and
traveling salesman: the genetic edge recombination operator.” In Proceedings of the
3rd International Conference on Genetic Algorithms ICGA-89, pp. 133–140.
[Wil99] Wilkinson, B. and Allen, M. (1999). Parallel Programming: Techniques and
Applications Using Networked Workstations, Prentice Hall.
[Yan00] Yang, J. M. and Kao, C. Y. (2000). “Integrating adaptive mutation and familycompetition into genetic algorithms as function optimizer,” Soft Computing, vol. 4, pp.
89-102.