今日的資訊科學領域日新月異、發展迅速，許多相關應用領域的重要關鍵技術，如：容錯通信（fault-tolerant communication）、電路測試（circuit testing）、附加條件搜尋（additive search problem胝）以及密碼學中的差分密碼分析(differential cryptanalysis)等組合計算最佳化問題皆與演繹競局最佳化問題相關。
在本論文中，我們提出嶄新且有系統的演算法解決著名的Mastermind和AB game等兩個演繹競局問題之變形“容許e次錯誤回應的Mastermind演繹競局問題”與“容許e次錯誤回應的AB game演繹競局問題”。首先我們使用k分支演算法（KWB）針對不同的e值求得此類問題所需猜測次數的上限。藉由分群技巧，KWB演算法能有效且有效率的求得接近最佳的結果。另一方面，我們根據鴿籠原理的觀念，發展出一個以鴿籠原理為基礎的快速式回溯驗證演算法（PPBFB）來求出所需猜測次數的下限。這是一種電腦輔助驗證演算法，在搜尋過程中它能估計競局樹的高度，且當高度超過我們欲驗證的值時，就回溯並繼續驗證其他分支。此外我們更進一步提出「容量更新」和「預先處理」二種創新的技術，能更有效的提升下限估計的準確度和搜尋的速度。
我們提出的KWB演算法與PPBFB演算法可推廣到任意次數錯誤回應之演繹競局問題，而且若使用KWB演算法時，在空間與時間允許的情況下，我們可以增加k值，以求出更好的策略。目前我們使用KWB演算法和PPBFB演算法得到以下的成果：
(1) 對容許一次錯誤回應的Mastermind，我們求得此問題所需的猜測次數之上限和下限皆為7。因此我們完整的解決此問題而且求出在最差情況下最佳的猜測次數為7。
(2) 對容許一次錯誤回應的AB game，我們得到此問題所需的猜測次數之上限為9、下限為8。
(3) 對容許二次錯誤回應的Mastermind，我們求得上限與下限分別為10和7，而對容許二次錯誤回應的AB game，得到的上限與下限分別為15和8。
此外，針對容許一次錯誤回應的Mastermind與容許一次錯誤回應的AB game，我們將找到的競局策略表示成遞迴表示法，並實作成線上對局系統，供作後續驗證及研究之用。

The field of computer science changes with each passing day and many key techniques in the related fields of computational problems, such as fault-tolerant communication, circuit testing, additive search problem, and differential cryptanalysis, are related to the optimization of deductive games.
In this thesis, we present novel and systematic algorithms to solve variants of the Mastermind and the AB game, which are called “Mastermind with e lies” and “AB game with e lies”, respectively. Firstly, we use the k-way-branching algorithm (KWB) to get the upper bounds of the number of guesses for the problems with different values of e separately. With the help of clustering technique, the KWB algorithm is able to obtain near-optimal results effectively and efficiently. Secondly, we propose a fast backtracking algorithm (PPBFB) based on the pigeonhole principle to get the lower bounds of the number of guesses. That is a computer-aided approach, which is able to estimate the depth of the game tree and to backtrack when the depth is larger than a predefined value. Moreover, we also develop two novel methods, named “volume-renewing” and “preprocessing”. They can improve the precision in the estimation of the lower bounds and speed up the game tree search.
The KWB algorithm and the PPBFB algorithm can be applied to the deductive games with multiple lies. We will obtain better strategies by using the KWB algorithm with larger k if time and space are available. As a result of applying the KWB algorithm and the PPBFB algorithm, we have derived the following new results.
(1) For “Mastermind with a lie”, we show that the upper bound is 7 and that is also the lower bound. Thus, the problem is solved completely and the exact bound of the number of guesses for the problem is 7.
(2) For “AB game with a lie”, we exhibit that the upper bound and the lower bound are 9 and 8 respectively.
(3) For “Mastermind with 2 lies”, its upper bound and the lower bound are 10 and 7 respectively. On the other hand, the upper bound is 15 and the lower bound is 8 for “AB game with 2 lies”.
Furthermore, we represent the strategies for “Mastermind with a lie” and “AB game with a lie” as a recursive expression and have also implemented an online gaming system for further verifications and studies.

[1] E. R. Berlekamp, “Block coding for the binary symmetric channel with noiseless, delayless feedback,” in: H.B. Mann (Ed.), Error-Correcting Codes, Wiley, New York, 1968, pp. 61–85.
[2] Z. Chen and C. Cunha, “Finding a hidden code by asking questions,” Second Annual International Computing and Combinatorics Conference, 1996, pp. 50-55.
[3] S. T. Chen and S. S. Lin, “Novel algorithms for deductive games,” Proceedings of the 2004 International Computer Symposium on Artificial Intelligence, TA-E1, 2004.
[4] S. T. Chen, S. S. Lin, and L. T. Huang, “Two-phase optimisation algorithm for hard-combinatorial problems,” Proceedings of the Fifteenth Australasian Workshop on Combinatorial Algorithms, 2004, pp. 248–259.
[5] F. Cicalese and U. Vaccaro, “An improved heuristic for the Ulam–Renyi game,” Information Processing Letters 73, 2000, pp. 119–124.
[6] J. Czyzowicz, D. Mundici, and A. Pelc, “Solution of Ulam’s problem on binary search with two lies,” Journal of Combinatorial Theory Series A 49, 1988, pp. 384–388.
[7] J. Czyzowicz, D. Mundici, and A. Pelc, “Ulam’s searching game with lies,” Journal of Combinatorial Theory Series A 52, 1989, pp. 62–76.
[8] C. Deppe, “Solution of Ulam’s searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes,“ Discrete Mathematics 224, 2000, pp. 79–98.
[9] R. L. Dobrushin, “Information transmission in a channel with feedback,” Theory of Probability and its Applications 34, 1958, pp. 367–383.
[10] M. M. Flood, “Sequential search strategies with Mastermind variants — Part 1,” Journal of Recreational Mathematics, 20:2, 1988, pp. 105-126.
[11] W. Guzicki, “Ulam’s searching game with two lies,” Journal of Combinatorial Theory Series A 54, 1990, pp. 1–19.
[12] R. W. Hamming, “Error detecting and error correcting codes,” Bell System Technical Journal 29, 1950, pp. 147–160.
[13] R. Hill and J. P. Karim, “Searching with lies: the Ulam problem,” Discrete Mathematics 106/107, 1992, pp. 273–283.
[14] R. Hill, J. Karim, and E. Berlekamp, “The solution of a problem of Ulam on searching with lies,” Proceedings of IEEE International Symposium on Information Theory (ISIT’98), MIT, August 1998, pp. 244.
[15] L. T. Huang, S. T. Chen, and S. S. Lin, “Exact-bound analyses and optimal strategies for Mastermind with a lie,” to appear in The Eleventh Conference on Advances in Computer Games, 2005.
[16] R. W. Irving, “Towards an optimum Mastermind strategy,” Journal of Recreational Mathematics, 11:2, 1978-79, pp. 81-87.
[17] G. Kabatianski and V. Lebedev, “The Mastermind game and the rigidity of the Hamming space,” in Proceedings of the International Symposium on Information Theory IEEE, 2000, pp. 375-375.
[18] D. E. Knuth, “The computer as Mastermind,” Journal of Recreational Mathematics, 9:1, 1976, pp. 1-6.
[19] K. I. Ko and S. C. Teng, “On the number of queries necessary to identify a permutation,” Journal of Algorithms, 7, 1986, pp. 449-462.
[20] K. Koyama and T. W. Lai, “An optimal Mastermind strategy,” Journal of Recreational Mathematics, 25, 1993, pp. 251-256.
[21] E. L. Lawler and S. Sarkissian, “An algorithm for “Ulam’s Game” and its application to error correcting codes,” Information Processing Letters 56, 1995, pp. 89–93.
[22] J. J. Merelo, J. Carpio, P. Castillo, V. M. Rivas, and G. Romero (GeNeura Team), “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, 1999, pp. 184-192.
[23] A. Negro and M. Sereno, “Solution of Ulam’s problem on binary search with three lies,” Journal of Combinatorial Theory Series A 59, 1992, pp. 149–154.
[24] A. Negro and M. Sereno, “Ulam’s searching game with three lies,” Advanced in Applied Mathematics 13, 1992, pp. 404–428.
[25] E. Neuwirth, “Some strategies for Mastermind,” Zeitschrift fur Operations Research 26, 1982, pp. 257-278.
[26] A. Pelc, “Solution of Ulam’s problem on searching with a lie,” Journal of Combinatorial Theory Series A 44, 1987, pp. 129–140.
[27] A. Renyi, “On a problem of information theory,” MTA Mat. Kut. Int. Kozl. 6B, 1961, pp. 505–516.
[28] R. L. Rivest, A. R. Meyer, D. J. Kleitman, K. Winklmann, and J. Spencer, “Coping with errors in binary search procedures,” Journal of Computer and System Sciences 20, 1980, pp. 396–404.
[29] S. Seiden, “A manifesto for the computational method,” Theoretical Computer Science 282, 2002, pp. 381–395.
[30] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal 27, 1948, pp. 379–423 and 623–656.
[31] C. E. Shannon, “Zero-capacity of noisy channels,” IEEE Transactions on Information Theory IT 2, 1956, pp. 8–19.
[32] S. M. Ulam, “Adventures of a mathematician,” Scribner, New York, 1976, pp. 281.