簡易檢索 / 詳目顯示

回結果列表
研究生： 白聖秋
論文名稱： DTS演算法效能改良之研究
指導教授： 林順喜
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 中文
論文頁數： 47
中文關鍵詞： 電腦西洋棋 、平行搜尋演算法 、人工智慧 、動態樹分割演算法
論文種類： 學術論文
相關次數： 點閱：235  下載：43 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 電腦西洋棋在近年來已經大量使用平行搜尋演算法，目前表現最好的是使用DTS（Dynamic Tree Splitting）搜尋演算法，該演算法的作者Robert M. Hyatt所設計出來的電腦西洋棋程式Crafty也在2004年第12屆World Computer Speed Chess Championship比賽獲得第二名。
    本篇論文主要研究DTS（Dynamic Tree Splitting）搜尋演算法，發現使用一些改良技巧，如改良方法一的控制CPU分配量與改良方法二的控制允許使用DTS搜尋演算法的最低層數，能將DTS（Dynamic Tree Splitting）搜尋演算法在電腦西洋棋程式中獲得更好的效能。我們也使用開放程式碼的Crafty20.14版做實驗，目前研究結果發現改良方法一能提升20％左右的效能，而改良方法二能提升35％左右的效能。

    摘 要 ii ABSTRACT iii 目錄 vi 附表目錄 vii 附圖目錄 viii 第一章 緒論 1 第一節 前言 1 第二節 研究動機及目的 2 第三節 論文架構 3 第二章 平行Alpha-Beta搜尋演算法 4 第一節 前言與Alpha-Beta搜尋演算法 4 第二節 三種節點分類 6 第三節 PVS搜尋演算法 7 第四節 EPVS搜尋演算法 9 第五節 DTS搜尋演算法 10 第三章 DTS搜尋演算法效能改良 13 第一節 過去的效能與實驗數據發現 13 第二節 改良方法一：橫向思考 15 第三節 改良方法二：縱向思考 18 第四章 效能分析 21 第一節 改良方法一的實驗結果 21 第二節 改良方法一簡易的分析及驗證方法 25 第三節 改良方法二的實驗結果 28 第五章 結論與未來研究方向 33 第一節 結論 33 第二節 未來研究方向 35 附錄 36 附錄A Crafty測試的12個盤面資訊 36 附錄B 深象測試的10個盤面資訊 32 參考文獻 47

    【1】Beal, D. F.,“Experiments with the Null-Move”, Advances in Computer Chess ,Vol. 5, pp.65-79, 1989.
    【2】Brudno, A. L., “Bounds and Valuations for Abridging the Search of Estimates”, Problems of Cybernetics, Vol. 10, pp.255-241, 1963.
    【3】Donninger, C.,“Null Move and Deep Search : Selective Search Heuristics for Obtuse Chess Programs”, ICCA Journal, Vol. 16, No. 3, pp.137-143, 1993.
    【4】Goetsch, G., and Campbell, M. S.,“Experiments with the Null-Move Heuristic”, Computers, Chess, and Cognition, pp. 159-168, 1988.
    【5】Greenblatt, R. D., Eastlake, D. E., and Crocker, S. D.,“The Greenblatt Chess Program”, Fall Joint Computing Conf. Procs. Vol. 31, pp.801-810, 1967.
    【6】Hyatt, R. M., Suter, B. W., and Nelson, H. L., “A Parallel Alpha/Beta Tree Searching Algorithm”, Parallel Computing , Vol. 10, No.3 , pp.299-308, 1989.
    【7】Hyatt, R. M., “The DTS High-Performance Parallel Tree Search Algorithm”, ICCA Journal , Vol. 20, No. 1, pp.3-19, 1997.
    【8】Kaindl, H.,“Dynamic Control of the Quiescence Search in Computer Chess”, Cybernetics and Systems Research, pp.973-977, 1982.
    【9】Knuth, D. E. and Moore, R. W., “An Analysis of Alpha-beta Pruning”, Artificial Intelligence, Vol. 6, No. 4, pp.293-326, 1975.
    【10】Marsland , T. A. and Campbell, M. S., “Parallel Search of Strongly Ordered Game Tree”, ACM Computing Surveys, Vol. 14, No. 4, pp.533-551, 1982.
    【11】Plaat, A., Schaeffer, J., Pijls, W., and Bruin, A. de,“Nearly Optimal Minimax Tree Search”, Technical Report ,Vol. 19, 1994.
    【12】 李任軒,“電腦象棋知識庫切捨技術”, 國立台灣師範大學資訊工程研究所碩士論文, 2006.
    【13】許舜欽,黃東輝,“中國象棋知識庫之設計與製作”, 全國計算機會議論文集, 頁505-509, 1985.
    【14】張躍騰,“人造智慧在電腦象棋的應用”,國立台灣大學電機工程研究所,碩士論文, 1981.
    【15】 黃文樟,“電腦象棋深象中局程式的設計與實作”, 國立台灣師範大學資訊工程研究所碩士論文, 2006.
    【16】 陳志昌,“電腦象棋開局知識庫系統之設計與製作”, 國立台灣大學資訊工程研究所碩士論文, 1998.

    QR CODE