簡易檢索 / 詳目顯示

回結果列表
研究生： 方裕欽
論文名稱： UCT算法的適用性及改進策略研究－以黑白棋為例
Research on Applicabilities and Improved Strategies of the Upper Confidence Bounds Applied to Trees Algorithm on Othello
指導教授： 林順喜
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2008
畢業學年度： 96
語文別： 中文
論文頁數： 55
中文關鍵詞： 電腦黑白棋 、UCT演算法 、人工智慧
論文種類： 學術論文
相關次數： 點閱：351  下載：58 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 電腦棋類在人工智慧領域中，一直是引人關注的，而電腦黑白棋在1997年時，由Logistello打敗當時的人類冠軍Takeshi Murakami，可以說是電腦黑白棋的一個里程碑。而在2007年，MoGo圍棋程式以UCT演算法在9路圍棋的比賽中取得良好的成績，使人們開始注意到UCT演算法。而目前相關文獻中，尚未有任何文獻提出應用UCT演算法於黑白棋上的研究。
    本論文首度將UCT演算法實作於黑白棋中，除了探討UCT演算法在黑白棋中的適用性外，並根據黑白棋的特性，提出部分改進策略。

    摘 要 ii ABSTRACT iii 誌 謝 v 目 錄 vi 附圖目錄 viii 第一章 緒論 1 第一節 前言 1 第二節 研究動機 4 第三節 論文架構 6 第二章 相關文獻及基礎理論 7 第一節 電腦黑白棋發展回顧 7 1. Logistello 7 2. WZebra 7 3. 相關研究成果 8 第二節 電腦對局理論基礎 8 1. 位棋盤 8 2. 對局樹 9 3. 極大極小搜尋演算法 9 4. 同形表 11 5. UCT演算法 13 第三章 實作程式基本架構 16 第一節 盤面資料結構 16 1. 位棋盤 16 2. 邊界判斷 20 3. 計算棋子數目 22 第二節 走子 23 1. 走子順序 23 2. 合法走步的產生 25 第三節 同形表 31 第四節 UCT演算法實作 33 1. 決策樹資料結構 33 2. 更新分數與pass狀況處理 35 3. 決策樹的刪除 38 第四章 實驗分析及改進策略 40 第一節 實驗與分析 40 第二節 UCT演算法改進策略 45 第五章 結論與未來研究方向 51 附錄 戰績表 54 參考著作 55

    [1] A. L. Zobrist, "A Hashing Method with Applications for Game Playing," Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1969.
    [2] C. E. Shannon, "Programming a Computer for Playing Chess," Philosophical Magazine, Ser. 7, Vol. 41, No. 314, Mar. 1950.
    [3] L. Kocsis and C. Szepesvari, "Bandit based Monte-Carlo planning", European Conference on. Machine Learning, pp. 282–293, 2006.
    [4] L. V. Allis, van der Meulen M., van den Herik H. "Alpha-Beta Conspiracy-Number Search," Advances in Computer Chess 6, pp. 73-95, 1991.
    [5] J. Kloetzer, H. Iida, and B. Bouzy, "The Monte-Carlo Approach in Amazons," Computer Games Workshop, Amsterdam, The Netherlands, pp. 185-192, 2007.
    [6] M. Buro, "The Othello Match of the Year: Takeshi Murakami vs. Logistello," ICCA Journal Vol. 20, No. 3, pp. 189-193, 1997.
    [7] M. Buro, "From Simple Features to Sophisticated Evaluation Functions," First Int'l Conf. Computers and Games (CG'98), Lecture Notes in Computer Science, Springer-Verlag, New York, Vol. 1558, 1998.
    [8] M. Buro, "Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello," NECI Tech. Report #96, Princeton, N.J., 1997.
    [9] M. Buro, "Toward Opening Book Learning," ICCA Journal, Vol. 22, No. 2, pp. 98-102, 1999.
    [10] M. Buro, "Improving Heuristic Mini-Max Search by Supervised Learning , "Artificial Intelligence, Vol. 134, No.1-2 , pp. 85-99, 2002.
    [11] R. D. Greenblatt , D. E. Eastlake and S. D. Crocker,“The Greenblatt Chess Program," Fall Joint Computing Conf. Procs., San Francisco, Vol. 31, pp. 801-810, 1967. Also in D. Levy (ed.), Computer Chess Compendium, Springer-Verlag, pp. 56-66, 1988.
    [12] S. Iwata and T. Kasai , "The Othello game on an n*n board is pspace-complete, " Theoretical Computer Science, Vol. 123, No. 2, pp. 329–340, 1994.
    [13] The perfect play line in 6x6 Othello, http://www.feinst.demon.co.uk/Othello/6x6sol.html.
    [14] The possible perfect outcome of the ANTI 8x8 Othello game, http://www.tothello.com/html/reversed_othello_games.html.
    [15] Y. Wang, , S. Gelly, "Modifications of UCT and sequence-like simulations for Monte-Carlo go, "CIG 2007, Honolulu, USA, pp. 175–182, 2007.

    QR CODE