基於UCT的圍棋引擎的研究與實現

《基於UCT的圍棋引擎的研究與實現》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、摘要棋類博弈是人工智慧的重要研究主題之一。而在圍棋方面，由於圍棋的搜索空間太大、電腦難於處理模糊概念且難於設計學習演算法，目前最優(yōu)秀的圍棋程式的水準還處於業(yè)餘低段水準。電腦圍棋被認為是在繼國際象棋之後人工智慧領域中最困難的新挑戰(zhàn)之一。圍棋是檢驗人工智慧發(fā)展水準的良好環(huán)境，如何提高圍棋程式的棋力是人工智慧領域的一大難題。所以電腦圍棋研究具有重要的理論意義和實用價值。本論文將介紹如何基於UCT演算法設計和實現圍棋引擎。第一部分介紹了電腦圍棋研究背景及意義、研究狀況和關鍵技術，包括MonteCarlo方法和UCT演算法的理論。第二部分在圍棋引擎總體概述的基礎上說明其總體功能模組，並對各個子功

2、能模組進行描述，重點講解了交替下子的流程以及棋步產生模組。第三部分闡明了基於UCT演算法的圍棋引擎的設計，先設計圍棋引擎的總體流程，再依次說明UCT演算法流程、棋步合法性的判斷等模組的具體設計流程。第四部分探討了基於UCT演算法的圍棋引擎的實現，在分析圍棋引擎核心模組UCT演算法實現的基礎上，詳細說明了候選步的產生及管理機制，節(jié)點的UCT選擇，展開節(jié)點和棋局模擬，分析指出不同的因素和策略對電腦圍棋引擎的影響，其中棋局類比的著手庫模式匹配和其它圍棋知識對加強程式棋力有至關重要的作用。最後對主要工作做了總結，提出進一步的發(fā)展目標?；渡鲜鰞热?，實現了一個基於UCT演算法的圍棋引擎TaoGo

3、，支援GMP、GTP圍棋協(xié)定，SGF檔調試輸出和統(tǒng)計UCT類比棋局的資料，目前能正常與圍棋用戶端進行通信，實現人機和機機對弈。關鍵字：人工智慧電腦圍棋UCT演算法模式匹配目錄1緒論11.1研究背景及意義11.2研究狀況11.3關鍵技術21.3.1MonteCarlo方法21.3.2UCT演算法32基於UCT的圍棋引擎的概述52.1圍棋引擎的總體概述52.2圍棋引擎的總體功能模組52.3交替下子流程模組72.4棋步產生(UCT)模組82.5棋步合法性判斷模組102.6算氣模組102.7更新棋盤(提子)模組112.8勝負計算模組113基於UCT的圍棋引擎的設計123.1圍棋引擎總體流程設計

4、123.2UCT演算法具體流程設計133.3棋步合法性判斷模組設計163.4算氣模組設計183.5更新棋盤(提子)模組設計193.6勝負計算模組設計204基於UCT的圍棋引擎的實現224.1軟硬體開發(fā)環(huán)境224.2圍棋引擎的資料結構224.2.1棋局數據224.2.2UCTTree數據234.3圍棋引擎的UCT演算法實現234.3.1UCT演算法的核心實現234.3.2候選步的產生方式及管理機制264.3.3選擇節(jié)點(UCT選擇)284.3.4展開節(jié)點314.3.5棋局模擬334.4圍棋引擎運行效果414.4.1圍棋協(xié)議對弈測試414.4.2調試模式的SGF檔434.4.3UCT類比棋

5、局資料統(tǒng)計445工作總結及未來展望455.1工作總結455.2未來展望45致謝46參考文獻47英文摘要491緒論1.1研究背景及意義博弈是人工智慧的重要研究主題，人工智慧的發(fā)展在很大程度上得益於博弈研究的發(fā)展。1997年著名的深藍電腦戰(zhàn)勝國際象棋世界冠軍卡斯帕羅夫成為轟動一時的新聞事件[l]。可以說，作為博弈研究的主要內容之一，棋類博弈得到了滿意的解決，唯一的例外的是圍棋，目前最優(yōu)秀的圍棋程式還處於業(yè)餘低段水準。圍棋是博弈的一種，屬雙人零和博弈[2]。它起源於3000多年前的中國，充分體現了東方人的智慧，盛行于中日韓，逐漸在歐美流行。它比國際象棋複雜得多，正因為如此，很多人工智慧學家、

6、心理學家和數學家也投入到了電腦圍棋研究領域。電腦圍棋這個名稱來自於ComputerGo的直譯，略顯生硬。簡單地說，電腦圍棋就是結合人工智慧技術教電腦下圍棋，以達到與人類棋手相抗衡的目的。由於圍棋的搜索空間太大、電腦難於處理模糊概念且難於設計學習演算法，造成了電腦圍棋程式的棋力難於提高。圍棋是檢驗人工智慧發(fā)展水準的良好環(huán)境，如何提高圍棋程式的棋力是人工智慧領域的一大難題。同時，開發(fā)出與人類棋手水準相當的圍棋程式也有助於對人類認知能力的理解。所以電腦圍棋研究具有重要的理論意義和實用價值。1.2研究狀況電腦圍棋自Zobrist在1970年設計出第一個可與人對弈的程式以來[3]，至今已有約四十

7、年的歷史。由於圍棋本身的特質，使得電腦圍棋在繼西洋棋、象棋之後，成為人工智慧中一個相當引人注目的新挑戰(zhàn)。然而電腦圍棋的難點之一，便在於缺乏良好的局面評估函數[4]，使其不能跟國際象棋一樣，運用設計良好的局面評估函數、搜尋樹以及優(yōu)秀的剪枝法，即可獲得不錯的棋力；電腦圍棋大多借鑒一些經驗法則，以靜態(tài)的評估為主，而動態(tài)的搜尋則僅用於局部的、目標明確的棋串攻殺，較少的全域搜尋。因此，人類的經驗如何應運用於電腦圍棋，就成了設計的重點。自2003年起，Bo