隨著眾多領域中最佳化問題的逐步探索，發現許多重要的問題都能被轉換成演繹競局問題(deductive game)的模型，例如編碼理論(coding theory)、電路測試(circuit testing)、密碼系統破解(differential cryptanalysis)、附加條件搜尋(additive search problem)等問題。換言之，在演繹競局問題上的研究將使其他相關領域問題的求解露出希望曙光，因此發展有效解決演繹競局問題的方法變得不容遲緩。
在過去數十年間，有許多針對演繹競局問題的研究產生。Mastermind與AB game(或稱為Bulls and Cow)是最有名的兩種演繹競局問題，知名的電腦科學家Donald E. Knuth在1976年於論文中介紹此二者並針對Mastermind做相關研究。在本論文中，我們提出一系列理論剪裁(theoretical-pruning)的最佳化方法與數學證明來解決這兩種問題。
在運用這些新方法到欲解決的問題後，我們得到下列新的成果：
(1)我們提出一個適用於各種演繹競局問題的admissible heuristic。同時，我們根據此admissible heuristic，提出一個更有效率的演算法來解決Mastermind，最後亦得到Mastermind在平均狀況下的最佳策略。
(2)針對AB game，我們提出一個更精緻的剪裁演算法(pruning algorithm)來處理它。很幸運地，最後我們得到AB game在平均狀況下的最佳策略且其平均猜測次數為5.213。
(3)我們針對在最差狀況下3×n AB games的最佳策略做理論性的分析。最後我們成功地導出一個計算最差狀況下的最佳猜測次數之公式。
(4)我們研究一個AB game的變型，稱為容許一次錯誤回應之AB game。最終我們求得其最佳猜測次數為8。

With the increasing exploration of optimization problems in numerous fields, many critical issues, such as coding theory, circuit testing, differential cryptanalysis, and additive search problem, can be modeled as deductive games. In other words, the research of these games has led to the hope that the fruitful solutions of problems in related areas may be obtained. Thus, it becomes urgent to develop efficient mechanisms for deductive games.
Over the last few decades, considerable concern has arisen in solving a number of deductive games. Mastermind and AB game (or “Bulls and Cows”), which were introduced by the famous scientist, Donald E. Knuth, in 1976, are the most well-known ones. In this dissertation, we aim to present a series of theoretical-pruning optimization approaches and mathematical proofs to solve both of the two.
As a result of applying these novel methods, the following new results have been obtained.
(1)An admissible heuristic for deductive games is presented. Meanwhile, a more efficient algorithm based on it is introduced to solve Mastermind and an alternative optimal strategy in the expected case is gained eventually.
(2)A refined pruning algorithm is demonstrated to address AB game. Fortunately, an optimal strategy for AB game in the expected case is acquired finally and its expected number of queries is 5.213.
(3)Analyses of playing 3×n AB games in the worst case optimally are conducted. Furthermore, a worthwhile formula for calculating the optimal numbers of queries in the worst case is derived successfully.
(4)A variation of AB game, AB game with an unreliable response, is surveyed. Finally, an exact bound of the number of queries for the game is achieved and its value is 8.

[1] Allen, J. (1989), “A Note on the Computer Solution of Connect-Four,” Heuristic Programming in Artificial Intelligence 1: The First Computer Olympiad, pp. 134–135.
[2] Allis, L. V. (1988), A knowledge-based approach of Connect-Four—the game is solved: white wins, Master's thesis, Vrije Universiteit, Amsterdam, The Netherlands.
[3] Allis, L. V. (1994), Searching for solutions in artificial intelligence, PhD Dissertation, Universiteit Maastricht, Maastricht, The Netherlands.
[4] Appel, K., and Haken, W. (1977), “Every planar map is four colorable part I: discharging,” Illinois Journal of Mathematics, Vol. 21, pp. 429–490.
[5] Appel, K., Haken, W., and Koch, J. (1977), “Every planar map is four colorable part II: reducibility,” Illinois Journal of Mathematics, Vol. 21, pp. 491–567.
[6] Barteld, K. (2005), “Yet another Mastermind strategy,” ICGA Journal, Vol. 28, No. 1, pp. 13–20.
[7] Bento, L., Pereira, L., and Rosa, A. (1999), “Mastermind by evolutionary algorithms,” Proceedings of the 1999 ACM symposium on Applied computing, San Antonio, Texas, USA, 28 February-2 March, pp. 307–311.
[8] Berghman, L., Goossensa, D., and Leus, R. (2009), “Efficient solutions for Mastermind using genetic algorithms,” Computers and Operations Research, Vol. 36, No. 6, pp. 1880–1885.
[9] Bernier, J. L., Herráiz, C. I., Merel, J. J., Olmeda, S., and Prieto, A. (1996), “Solving Mastermind using GAs and simulated annealing: a case of dynamic constraint optimization,” Parallel Problem Solving from Nature (PPSN IV), Lecture Notes in Computer Science, Vol. 1141, pp. 554–563.
[10] Billings, D., Papp, D., Peña, L., Schaeffer, J., and Szafron, D. (1999), “Using selective-sampling simulations in poker,” Proceedings of AAAI Spring Symposium on Search Techniques for Problem Solving under Uncertainty and Incomplete Information, Stanford, CA, USA, March, pp. 13–18.
[11] Bjornsson, Y., and Marsland, T. A. (2001), “Multi-cut alpha-beta pruning in game-tree search,” Theoretical Computer Science, Vol. 252, No. 1, pp. 177–196.
[12] Blum, C., and Roli, A. (2003), “Metaheuristics in combinatorial optimization: overview and conceptual comparison,” ACM Computing Surveys, Vol. 35, No. 3, pp. 268–308.
[13] Bresina, J. L. (1996), “Heuristic-biased stochastic sampling,” Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, Oregon, Portland, 4-8 August, pp. 271–278.
[14] Chen, S. T. (2004), On the Study of Optimization Algorithms for Deductive Games and Related Problems. PhD Dissertation, National Taiwan Normal University, Taipei, Taiwan.
[15] Chen, S. T., Hsu, S. H., and Lin, S. S. (2004), “Optimal algorithms for 2×n AB games - a graph-partition approach,” Journal of Information Science and Engineering, Vol. 20, No. 1, pp. 105–126.
[16] Chen, S. T., Hsu, S. H., and Lin, S. S. (2004), “Optimal algorithms for 2×n Mastermind games - a graph-partition approach,” Computer Journal, Vol. 47, No. 5, pp. 602–611.
[17] Chen, S. T., Lin, S. S., and Huang, L. T. (2007), “A two-phase optimization algorithm for Mastermind,” Computer Journal, Vol. 50, No. 4, pp. 435–443.
[18] Chen, S. T., Lin, S. S., Huang, L. T., and Hsu, S. H. (2007), “Strategy optimization for deductive games,” European Journal of Operational Research, Vol. 183, No. 2, pp. 757–766.
[19] Colorni, A., Dorigo, M., Maffioli, F., Maniezzo, V., Righini, G., and Trubian, M. (1996), “Heuristics from nature for hard combinatorial optimization problems,” International Transactions in Operational Research, Vol. 3, No. 1, pp. 1–21.
[20] Coulom, R. (2006), “Efficient selectivity and backup operators in Monte-Carlo tree search,” Proceedings of the 5th Conference on Computers and Games, Turin, Italy, 29-31 May, pp. 72–83.
[21] Donninger, C. (1993), “Null move and deep search: selective-search heuristics for obtuse chess programs,” ICCA Journal, Vol. 16, No. 3, pp. 137–143.
[22] Dorigo, M., and Gambardella, L. M. (1997), “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53–66.
[23] Drakard, K. (1998), “Mastermind: WebGames,” Internet: http://www.irt.org/ games/js/mind/.
[24] Feo, T. A., and Resende, M. G. C. (1995), “Greedy randomized adaptive search procedures,” Journal of Global Optimization, Vol. 6, No. 2, pp. 109–133.
[25] Flood, M. M. (1988), “Sequential search strategies with Mastermind variants — Part 1,” Journal of Recreational Mathematics, Vol. 20, No. 2, pp. 105–126.
[26] Glover, F. (1986), “Future paths for integer programming and links to artificial intelligence,” Computers and Operations Research, Vol. 13, No. 5, pp. 533–549.
[27] Glover, F. (1990), “Tabu search Part II,” ORSA Journal on Computing, Vol. 2, No. 1, pp. 4–32.
[28] Goddard, W. (2004), “Mastermind revisited,” Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 51, pp. 215–220.
[29] Goddard, W. (2003), “Static Mastermind,” Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 47, pp. 225–236.
[30] Goodrich, M. T. (2009), “On the algorithmic complexity of the Mastermind game with black-peg results,” Information Processing Letters, Vol. 109, No. 13, pp. 675–678.
[31] Greenwell, D. (1999-2000), “Mastermind,” Journal of Recreational Mathematics, Vol. 30, pp. 191–192.
[32] Hales, T. C. and Ferguson, S. P. (2006), Discrete and Computational Geometry, Vol. 36, No. 1.
[33] Harvey, W. D., and Ginsberg, M. L. (1995), “Limited discrepancy search,” Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, Montréal, Québec, Canada, 20-25 August, pp. 607–613.
[34] Heinz, E. A. (2000), “AEL Pruning,” ICGA Journal, Vol. 23, No. 1, pp. 21–32.
[35] Helmstetter, B., and Cazenave, T. (2003), “Searching with analysis of dependencies in a solitaire card game,” van den Herik, H. J. Iida, H. and Heinz, E. A. (eds), Advances in Computer Games 10, Kluwer Academic Publishers, Netherlands.
[36] Holland, J. H. (1975), Adaptation in natural and artificial systems. University of Michigan Press. Ann Arbor.
[37] Huang, L. T. (2005), On the study of deductive games with lies, Master's thesis, National Taiwan Normal University, Taipei, Taiwan.
[38] Huang, L. T., Chen, S. T., and Lin, S. S. (2006), “Exact-bound analyses and optimal strategies for Mastermind with a lie,” Lecture Notes in Computer Science, Advances in Computer Games 11, Vol. 4250, pp. 195–209.
[39] Irving, R. W. (1978-79), “Towards an optimum Mastermind strategy,” Journal of Recreational Mathematics, Vol. 11, No. 2, pp. 81–87.
[40] Jäger, G., and Peczarski, M. (2009), “The number of pessimistic guesses in generalized Mastermind,” Information Processing Letters, Vol. 109, No. 12, pp. 635–641.
[41] Juill´e, H., and Pollack, J. B. (1998), “A sampling-based heuristic for tree search applied to grammar induction,” Proceedings of the Fifteenth National Conference on Artificial Intelligence, Madison, Wisconsin, USA, 26-30 July, pp. 776–783.
[42] Kabatianski, G., and Lebedev, V. (2000), “The Mastermind game and the rigidity of the Hamming space,” Proceedings of the 2000 IEEE International Symposium on Information Theory, Sorrento, Italy, 25-30 June, pp. 375–375.
[43] Kalisker, T., and Camens, D. (2003), “Solving Mastermind using genetic algorithms,” Genetic and Evolutionary Computation — GECCO 2003, Lecture Notes in Computer Science, Vol. 2724, pp. 1590–1591.
[44] Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983), “Optimization by simulated annealing,” Science, Vol. 220, No. 4598, pp. 671–680.
[45] Knuth, D. E. (1976), “The computer as Mastermind,” Journal of Recreational Mathematics, Vol. 9, No. 1, pp. 1–6.
[46] Ko, K. I., and Teng, S. C. (1986), “On the number of queries necessary to identify a permutation,” Journal of Algorithms, Vol. 7, No. 4, pp. 449–462.
[47] Koyama, K., and Lai, T. W. (1993), “An optimal Mastermind strategy,” Journal of Recreational Mathematics, Vol. 25, No. 4, pp. 251–256.
[48] Labat, J. M., and Pomerol, J. C. (2003), “Are Branch and Bound and A* Algorithms Identical,” Journal of Heuristics, Vol. 9, No. 2, pp. 131–143.
[49] Land, A. H., and Doig, A. G. (1960), “An automatic method of solving discrete programming problems,” Econometrica, Vol. 28, No. 3, pp. 497–520.
[50] McKay, B. D. (1998), “Isomorph-free exhaustive generation,” Journal of Algorithms, Vol. 26, No. 2, pp. 306–324.
[51] Merelo-Guervos, J. J., Castillo, P., and Rivas, V. M. (2006), “Finding a needle in a haystack using hints and evolutionary computation: the case of evolutionary MasterMind,” Applied Soft Computing, Vol. 6, No. 2, pp. 170–179.
[52] Neapolitan, R. and Naimipour, K. (2004), Foundations of Algorithms Using C++ Pseudocode. 3rd edn. Jones and Bartlett Publishers.
[53] Neuwirth, E. (1982), “Some strategies for Mastermind,” Mathematical Methods of Operations Research, Vol. 26, No. 1, pp. 257–278.
[54] Norvig, P. (1984), “Playing Mastermind optimally,” ACM SIGART Bulletin, No. 90, pp. 33–34.
[55] Pitsoulis, L. S., and Resende, M. G. C. (2002), “Greedy randomized adaptive search procedure,” In P. Pardalos, and M. Resende, (eds), Handbook of Applied Optimization. Oxford University.
[56] Prieditis, A., and Davis, R. (1995), “Quantitatively relating abstractness to the accuracy of admissible heuristics,” Artificial Intelligence, Vol. 74, No. 1, pp. 165–175.
[57] PYVA-NET (2000), “Pyva net!,” Internet: http://pyva.net/eng/play/bk.html.
[58] Roche, J. R. (1997), “The value of adaptive questions in generalized Mastermind,” Proceedings of the 1997 IEEE International Symposium on Information Theory, Ulm, Germany, 29 June- 4 July, pp. 135–135.
[59] Rosu, R. (1999), Mastermind, Master's thesis, North Carolina State University, Raleigh, North Carolina.
[60] Ruiz, R., and StÄutzle, T. (2007), “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” European Journal of Operational Research, Vol. 177, No. 3, pp. 2033–2049.
[61] Ruml, W. (2001), “Incomplete tree search using adaptive probing,” Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, Seattle, Washington, USA, 4-10 August, pp. 235–241.
[62] Russell, S. and Norvig, P. (2002), Artificial Intelligence: A Modern Approach. 2nd edn. Prentice-Hall.
[63] Schaeffer, J., Burch, N., Björnsson, B., Kishimoto, A., Müller, M., Lake, R., Lu, P., and Sutphen, S. (2007), “Checkers is solved,” Science, Vol. 317, No. 5844, pp. 1518–1522.
[64] Sedgewick, R. (1988), Algorithms. 2nd edn. Addison-Wesley.
[65] Seiden, S. (2002), “A manifesto for the computational method,” Theoretical Computer Science, Vol. 282, No. 2, pp. 381–395.
[66] Seiden, S. (2001), “Can a computer proof be elegant,” ACM SIGACT News, Vol. 32, No. 1, pp. 111–114.
[67] Shapiro, E. (1983), “Playing Mastermind logically,” ACM SIGART Bulletin, No. 85, pp. 28–29.
[68] Singley, A. (2005), Heuristic solution methods for the 1-dimensional and 2-dimensional Mastermind problem, Master's thesis, University of Florida.
[69] Spencer, J. (1983), “Short theorems with long proofs,” American Mathematical Monthly, No. 90, pp. 365–366.
[70] Stuckman, J., and Zhang, G. Q. (2006), “Mastermind is NP-complete,” INFOCOMP - Journal of Computer Science, Vol. 5, No. 2, pp. 25–28.
[71] Swaszek, P. (1999), “The mastermind novice,” Journal of Recreational Mathematics, No. 30, pp. 193–198.
[72] Temporel, A., and Kovacs, T. (2003), “A heuristic hill climbing algorithm for Mastermind,” UKCI ’03, Proceedings of the 2003 UK Workshop on Computational Intelligence, pp. 189–196.
[73] Ugurdag, H., Sahin, Y., and Baskirt, O. (2006), “Population-based FPGA solution to Mastermind game,” AHS, Proceedings of the first NASA/ESA conference on Adaptive Hardware and Systems, pp. 237–246.
[74] Zobrist, A. L. (1970), “A new hashing method with applications for game playing,” Technical Report 88, Department of Computer Science, University of Wisconsin, Madison, USA. Also in ICGA Journal (1990), Vol. 13, No. 2, pp. 69–73.