容許多次錯誤回應之演繹競局問題之研究

Abstract

今日的資訊科學領域日新月異、發展迅速，許多相關應用領域的重要關鍵技術，如：容錯通信（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.