較高維度演繹競局問題最佳演算法之設計與分析

The Design and Analysis of Optimal Algorithms for Deductive Games with Higher Dimensions

黃立德(Li-Te Huang)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/博士(2009年)

摘要

隨著眾多領域中最佳化問題的逐步探索，發現許多重要的問題都能被轉換成演繹競局問題(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.

並列關鍵字

branch-and-bound ； deductive game ； game tree ； search algorithm ； theoretical pruning ； unreliable response

參考文獻

[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.

[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.

[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.