演繹競局及相關問題最佳化演算法之研究

Abstract

在資訊科技快速發展的今日，仍有許多複雜的組合最佳化問題(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.