學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
4 results
Search Results
Item 應用於電腦圍棋之蒙地卡羅樹搜尋法的新啟發式演算法(2011) 黃士傑; Shih-Chieh Huang電腦圍棋的研究開始於1970年，但圍棋程式卻從未曾被人們認為是強大的，直到2006年，當「蒙地卡羅樹搜尋」(Monte Carlo Tree Search)與「樹狀結構信賴上界法」(Upper Confidence bounds applied to Trees)出現之後，情況才開始完全不同。「蒙地卡羅樹搜尋」與「樹狀結構信賴上界法」所帶進的革命強而有力到一個地步，人們甚至開始相信，圍棋程式在10年或者20年之後，將能夠擊敗頂尖的人類棋手。 在本研究中，我們針對「蒙地卡羅樹搜尋」提出一些新的啟發式演算法，主要有兩方面的貢獻。第一個貢獻，是成功的將「模擬平衡化」(Simulation Balancing)應用到9路圍棋。「模擬平衡化」是一種用來訓練模擬的參數的演算法。Silver與Tesauro在2009年提出這個方法時，只實驗在比較小的盤面上，而我們的實驗結果首先證明了「模擬平衡化」在9路圍棋的有效性，具體方法是證明「模擬平衡化」超越了知名的監督式演算法Minorization-Maximization (MM)大約有90 Elo之多。第二個貢獻是針對19路圍棋，系統式的實驗了各種不同之時間控制的方法。實驗結果清楚的指明，聰明的時間控制方案可以大大的提高棋力。所有的實驗都是執行在我們的圍棋程式ERICA，而ERICA正是得益於這些啟發式演算法與實驗結果，成功取得了2010年電腦奧林匹亞的19路圍棋金牌。Item 電腦圍棋打劫的最佳策略之研究(2010) 詹傑淳; Chieh-Chun Chan打劫問題在圍棋裏佔據了一個十分重要的位置。在過去圍棋的打劫問題研究上，由於雙方各種走法的組合過於繁複，因此並未能考慮到所有可能獲得更大利益的情況。本論文重新的探討在本劫的條件下圍棋的打劫策略。首先，我們在打劫過程中將所有可能發生的情況都納入考慮，來確保不會有可能獲得更大利益的情況被忽略，利用MiniMax的搜尋原則建構出打劫的流程圖。接下來利用bottom up的方法來比較雙方的利益差，將不可能走到的分支砍掉，來找到正確決策的判斷式，因此我們可以得到在不同劫爭價值、有價值棋步、雙方劫材下最佳的決策。Item 電腦圍棋中考慮使用損劫之打劫策略研究(2007) 林玉祥在圍棋中，劫爭是個重要且有趣的問題，同時也是電腦圍棋程式提昇棋力的關鍵之一。劫爭與劫材的使用有密不可分的關係，也可以說，劫爭的複雜性與樂趣就建築在劫材的使用上。損劫是圍棋實戰中經常出現且被使用的一種劫材，由於損劫本身的性質，使得找劫材時的利益考量更複雜了許多。我們延續了先前師大資工所黃士傑的劫爭研究，納入使用損劫的考量，透過minimax搜尋原則以及打劫流程圖，找出打劫的策略。目標是當電腦圍棋程式遇上劫爭，可以迅速的計算出在這個局部能夠得到的利益，以及選擇正確的劫材來打劫。目前在損劫的損值相同時能夠迅速地獲得最佳解，而損值不同時，透過我們的方法來搜尋，平均能夠在七分鐘左右處理雙方各16個劫材的數量。另透過測試得知，使用經驗法則可以在平均誤差0.1目以內逼近最佳解所求之值。Item 電腦圍棋打劫的策略(2003) 黃士傑打劫在圍棋裏佔據了十分重要的位置，然而目前大部分的電腦圍棋程式都不具備打劫的能力。我們利用最大最小搜尋法的原則，得出本劫最佳的打劫策略，使得電腦圍棋程式在處理本劫時，能在局部求得獲利最大或損失最小的下法。我們根據形勢判斷的定義，精確的定義了棋步、劫爭與劫材的價值，作為探討打劫策略的基礎。我們也詳細探討了打劫過程中劫材的使用策略。