跳到主要內容

臺灣博碩士論文加值系統

(44.201.94.236) 您好!臺灣時間:2023/03/25 01:09
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔡心迪
研究生(外文):Tsai, Hsin-Ti
論文名稱:六子棋時序差異學習之研究
論文名稱(外文):Temporal Difference Learning in Connect6
指導教授:吳毅成
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學與工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:99
語文別:中文
論文頁數:45
中文關鍵詞:六子棋時序差異學習alpha-beta搜尋迫著空間搜尋
外文關鍵詞:Connect6temporal difference learningalpha-beta searchthreat-space search
相關次數:
  • 被引用被引用:0
  • 點閱點閱:264
  • 評分評分:
  • 下載下載:22
  • 收藏至我的研究室書目清單書目收藏:0
六子棋是吳毅成教授2005年發表的一個棋類遊戲,近年來已經發展成為世界性的遊戲。而NCTU6則是一個六子棋的AI程式,曾獲得兩屆電腦奧林匹亞賽局競賽六子棋組金牌,以及在人機賽中擊敗許多棋士。
這篇論文的目的是研究如何應用時序差異學習(Temporal Difference Learning)於六子棋程式上。由於六子棋的一些遊戲特性和其他遊戲不同,因此這篇同時也討論了時序差異學習在六子棋上有哪些值得注意的議題。
根據我們的實作經驗,時序差異學習演算法能讓新的程式對上原本的程式NCTU6有57.95% 的勝率,顯示NCTU6確實增加了棋力。新的程式也在2011 TCGA六子棋組獲得了金牌的好成績。

The Connect6 game, first introduced by Professor I-Chen Wu in 2005, now becomes one of the popular games in the world. NCTU6 is a Connect6 AI program developed by our team, has won gold medal in ICGA tournaments twice and defeated many professional players in Man-Machine Connect6 championship.
The main purpose of this thesis is to research temporal difference learning in Connect6. Some characteristics of Connect6 are different from other games, so we also discuss the issues of temporal difference learning in Connect6.
According to our practical experience, the new program with temporal difference learning reaches a 57.95% win percentage against original program. This shows that the new method successfully improves NCTU6. The new program has also won gold medal in 2011 TCGA tournaments.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章、介紹 1
1.1 六子棋 1
1.2 NCTU6 3
1.3 研究目的 4
1.4 貢獻 4
1.5 論文組織 5
第二章、研究背景 6
2.1 迫著空間搜尋 6
2.2 Alpha-Beta Search 9
2.2.1 Mini-Max Search 10
2.2.2 評估函數(Evaluation Function) 10
2.2.3 特徵(Feature) 11
2.2.4 Alpha-Beta Search 12
2.3 NCTU6的搜尋 12
2.3.1 NCTU6的迫著空間搜尋 13
2.3.2 NCTU6的Alpha-Beta Search 13
2.4 時序差異學習 13
2.4.1 策略(Policy) 14
2.4.2 回饋 15
2.4.3 模型 16
2.4.4 TD(λ) 16
2.4.5 TD(0)和TD(1) 19
第三章、研究方法 21
3.1 簡單的時序差異學習 21
3.2 虛擬程式碼 25
3.2.1 TD Learning 25
3.2.2 SelfPlay 26
3.2.3 Greedy 27
3.2.4 Eval 28
3.3 實作議題 28
3.3.1 特徵的選擇 28
3.3.2 特徵標準化 30
3.3.3 迫著空間搜尋 31
3.3.4 讀高手棋譜訓練 32
第四章、實驗 33
4.1 實作細節 33
4.1.1 更新比例 33
4.1.2 選點策略 33
4.1.3 更新標準化 34
4.1.4 分數標準化 34
4.1.5 回饋(Reward) 35
4.1.6 兩層更新 35
4.2 實驗環境 36
4.3 區分階段 37
4.4 特徵標準化 39
4.5 迫著空間搜尋 39
4.6 讀高手棋譜訓練 41
第五章、結論與未來展望 43
參考文獻 44
[1] Connect6-六子棋網站. Available at http://www.connect6.org/
[2] D.E. Knuth and R.W. Moore, “An analysis of alpha-beta pruning,“ Artificial Intelligence, 6:293–326, 1975.
[3] D. Silver, “Reinforcement learning and simulation-based search in computer Go,” Ph.D. dissertation, Dept. Comput. Sci., Univ. Alberta, Edmonton, AB, Canada, 2009.
[4] H.J. van den Herik, J.W.H.M. Uiterwijk and J.V. Rijswijck, “Games solved: Now and in the future,” Artificial Intelligence, vol. 134 (1-2), pp. 277–311, 2002.
[5] I.-C. Wu and D.-Y. Huang, “A New Family of K-in-a-row Games,” Advances in Computer Games Conference (ACG2005), Taipei, Taiwan, 2005.
[6] I.-C. Wu and P.-H. Lin, “Relevance-Zone-Oriented proof search for Connect6,” IEEE Trans. Comput. Intell. AI Games, vol. 2, no. 3, Sep. 2010.
[7] I.-C. Wu, D.-Y. Huang and H.-C. Chang, “Connect6,” ICGA Journal, vol. 28(4), pp. 234–242, 2006.
[8] J.R. Slagle and J.K. Dixon, “Experiments with some programs that search game trees,” JACM 16, 2 189-207, 1969.
[9] L.V. Allis, H.J. van den Herik and M.P. H. Huntjens, “Go-Moku Solved by New Search Techniques,” Computational Intelligence, Vol. 12, pp. 7–23, 1996.
[10] L.V. Allis, “Searching for solutions in games and artificial intelligence,” Ph.D. Thesis, University of Limburg, Maastricht, 1994.
[11] Little Golem website. Available at http://www.littlegolem.net/
[12] Ludoteka website. Available at http://www.ludoteka.com/
[13] Pente website. Available at http://pente.org/
[14] R.S. Sutton and A.G. Barto, “Reinforcement Learning: An Introduction,” MIT Press, Cambridge, MA, 1998.
[15] T. Thomsen, ”Lambda-search in game trees - with application to Go,” ICGA Journal, Vol. 23 203–217, 2000.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top