簡易檢索 / 詳目顯示

回結果列表
研究生： 郭哲宇
論文名稱： 電腦象棋擴大空步剪裁演算法的設計及實作
指導教授： 林順喜
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 中文
論文頁數： 51
中文關鍵詞： 象棋 、空步搜尋 、人工智慧
論文種類： 學術論文
相關次數： 點閱：163  下載：17 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 目前大多數頂尖的象棋軟體都採用空步搜尋法，以增進搜尋效率，但這個方法有時會有水平效應的策略盲點。在本論文中我們設計一種改良的空步搜尋方法，可以增進搜尋速度且不會降低搜尋的正確性。且透過實驗分析結果，我們發現擴大空步搜尋的新方法，在平均狀態下可以展開較小的搜尋樹，且比單純使用標準空步搜尋有更佳的棋力。經對戰實戰，改良版和未改良版對戰之下，勝率逼近七成。

    第一章 緒論 1 第一節 前言 1 第二節 研究動機 2 第三節 論文架構 2 第二章 相關文獻及基礎理論 4 第一節 Min-Max搜尋演算法 4 第二節 Alpha-Beta搜尋演算法 5 第三節 NegaScout搜尋演算法 6 第四節 疊代加深搜尋(iterative deepening) 6 第五節 寧靜搜尋(quiescence search) 7 第六節 向前切捨法(forward pruning) 7 第七節 空步搜尋(null move) 8 第八節 適應性空步剪裁(adaptive null move) 8 第九節 帶驗證的空步剪裁 9 第三章 空步搜尋的改良 10 第一節 簡介 10 第二節 擴大空步搜尋演算法與流程圖 18 第三節 帶驗證擴大空步搜尋演算法與流程圖 28 第四章 系統測試分析 34 第五章 結論與未來研究方向 39 第一節 結論 39 第二節 未來研究方向 42 參考文獻 43

    [1] F. -H. Hsu, T. S. Anantharaman, M. S. Campbell, and A. Nowatzyk , “DEEP THOUGHT”, Computers, Chess, and Cognition, pp.55–78, 1990.
    [2] D. J. Slate and L. R. Atkin , “CHESS 4.5 – The Northwestern University chess program”, Chess Skill in Man and Machine, pp. 82–118, 1983.
    [3] D. F. Beal , “Experiments with the null move”, Advances in Computer Chess 5, pp.65–79, 1989.
    [4] H. J. Berliner , “Chess as problem solving: the development of a tactics analyzer”, Ph.D. thesis, Carnegie-Mellon University, Pittsburgh, PA, 1974.
    [5] A. L. Brudno ,“Bounds and valuations for abridging the search of estimates”, problems of cybernetics 10, pp.255-241. Translation of Russian original in Problemy Kibernetiki 10, pp.141-150, 1963.
    [6] G. Goetsch, and M. S. Campbell , “Experiments with the null-move heuristic”, Computers, Chess, and Cognition, pp.159–168, 1990.
    [7] R. D. Greenblatt , D. E. Eastlake and S. D. Crocker,“The Greenblatt chess program”, Fall Joint Computing Conf. Procs, Vol. 31, pp.801-810, 1967. Also in D. Levy (ed.), Computer Chess Compendium, Springer-Verlag, pp.56-66, 1988.
    [8] C. Donninger , “Null move and deep search: selective search heuristics for obtuse chess programs”, ICCA Journal, Vol. 16, No. 3, pp.137–143, 1993.
    [9] E. A. Heinz ,“Adaptive null-move pruning”, ICCA J. 22 , pp.123-132, 1999.
    [10] C. Ye and T. Marsland ,“Experiments in forward pruning with limiter extensions”, ICCA Journal, Vol.15, No.2, pp.55-66,1992.
    [11] D. E. Knuth and R. W. Moore ,“An analysis of alpha-beta pruning”, Artificial Intelligence 6, 4, pp.293-326, 1975.
    [12] B. Moreland , http://www.seanet.com/~brucemo/topics/quiescent.htm.
    [13] O. D. Tabibi and N. S. Netanyahu ,“Verified null-move pruning”, ICGA Journal, Vol.25 No.3, pp.153-161, 2002.
    [14] J. V. Neumann , http://library.thinkquest.org/26408/math/minimax.shtml.
    [15] C. E. Shannon , “Programming a computer for playing chess”, the National IRE Convention, 1949.
    [16] 王驕, 王濤 ,羅豔紅 ,徐心和, “中國象棋電腦博奕系統評估函數的自適應遺傳演算法實現”, 東北大學學報(自然科學版) Vol. 26, No. 10, 2005.
    [17] 李任軒, “電腦象棋知識庫切捨技術”,國立台灣師範大學資訊工程所碩士論文, 2006.
    [18] 涂志堅, “電腦象棋的設計與實現”,中山大學碩士論文, 2004.
    [19] 許舜欽, “電腦西洋棋和電腦象棋的回顧與前瞻”,電腦學刊, 第二卷, 第二期, 1-8頁, 1990.
    [20] 曹國明, “智慧型中國象棋程式的設計與實作”,國立台灣大學資訊工程所碩士論文, 1988.
    [21] 張躍騰, “人造智慧在電腦象棋的應用”, 國立台灣大學電機工程研究所碩士論文,1981.
    [22] 陳志昌, “電腦象棋開局知識庫系統之設計與製作”, 國立台灣大學資訊工程研究所碩士論文, 1998.
    [23] 黃少龍, “象棋教材”, 第四卷, 蜀蓉棋藝出版社, 1995.
    [24] 黃文樟, “電腦象棋深象中局程式的設計與實作”,國立台灣師範大學資訊工程所碩士論文, 2006.
    [25] 董昱驣, “電腦象棋程式達奕設計與製作”國立東華大學資訊工程研究所碩士論文,1992.
    [26] 廖家誠, “利用計算機下象棋之實驗”, 國立交通大學計算機工程研究所碩士論文,1982.

    QR CODE