應用於象棋開局庫之工作層級AB-DUAL*搜尋演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：15

、訪客IP：3.143.168.172

姓名

林伯翰(Po-Han Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

應用於象棋開局庫之工作層級AB-DUAL*搜尋演算法
(Job-Level AB-DUAL* for Chinese Chess Opening)

相關論文

★ 行程邀約郵件的辨識與不規則時間擷取之研究	★ NCUFree校園無線網路平台設計及應用服務開發
★ 網際網路半結構性資料擷取系統之設計與實作	★ 非簡單瀏覽路徑之探勘與應用
★ 遞增資料關聯式規則探勘之改進	★ 應用卡方獨立性檢定於關連式分類問題
★ 中文資料擷取系統之設計與研究	★ 非數值型資料視覺化與兼具主客觀的分群
★ 關聯性字組在文件摘要上的探討	★ 淨化網頁：網頁區塊化以及資料區域擷取
★ 問題答覆系統使用語句分類排序方式之設計與研究	★ 時序資料庫中緊密頻繁連續事件型樣之有效探勘
★ 星狀座標之軸排列於群聚視覺化之應用	★ 由瀏覽歷程自動產生網頁抓取程式之研究
★ 動態網頁之樣版與資料分析研究	★ 同性質網頁資料整合之自動化研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

電腦象棋目前研究主要使用被動式開局庫，其建構方式為收集棋譜並統計整理勝敗等數據。其主要的問題是，使用時若依照統計數據來當作選擇依據，可能選到統計數據顯示為優秀的盤面，但盤面評估程式判斷為不佳。開局庫為保有與評估程式的一致性，避免遭遇上述情況，除了使用統計資料以外，還必須要對開局庫內的葉節點進行盤面評估，然而這是非常大量的計算，因此本論文使用Job Level System來加速運算效率。
一般的Job Level Search是利用平行化發送工作至遠端運算，來加速電腦遊戲程式的運算，因為各個工作能獨立運算，故非常適合分散式運算架構。而本論文提出的方法，是將Job Level Search與AB-DUAL*合併，該演算法由Alpha-Beta Search衍生而來。AB-DUAL*不同於Alpha-Beta Search沒有限制搜尋的分數範圍，其使用了Zero-Window來加速搜尋時的剪裁，因此需要的計算較少，更加適合利用來縮短計算時間。最後在實驗結果中，展示演算法的效能及速率均有大幅改善。

摘要(英)

Constructing a passive opening book for Chinese Chess requires the collection of thousands of expert games played on the Internet and filtering and ranking of all positions in the opening book based on factors such as the number of wins/draws/losses. A major issue here is the consistency between the opening book and the game-playing program. That is, the “statistical good” positions could be “weak spots” for game-playing program. In this paper, we evaluate all positions with game-playing program under job-level system to speed up the computation and maintain the consistency for the construction of the Chinese Chess opening book.
Generic job-level search was proposed to solve computer game applications by dispatching jobs to remote workers for parallel processing. This approach leverages game-playing programs and encapsulates them as jobs. Such an approach is well suited for a distributed computing environment, since these jobs can be run independently by remote processors in a job-level system. This paper applies job-level search to AB-DUAL*, which is an extension of Alpha-Beta Search but uses zero-window to increase pruning. In our experiments, the results demonstrate significant performance improvement and speedups.

關鍵字(中)

★ 工作層級系統
★ 最大最小搜尋
★ 開局庫
★ 象棋

關鍵字(英)

★ Job Level System
★ Alpha-Beta Search
★ Opening Book

論文目次

摘要 i
Abstract ii
目錄 iii
表目錄 iv
圖目錄 v
第一章緒論 1
1.1. 研究動機 2
1.2. 論文結構 4
第二章背景 5
2.1. MiniMax Search 5
2.2. Alpha-Beta Search 6
2.3. SSS* 7
2.4. AB-SSS* 7
2.4.1. AB-DUAL* 9
2.5. Job Level System 11
第三章研究方法 13
3.1. Single Worker Job Level AB-DUAL* 13
3.1.1. 符號定義 13
3.1.2. 演算法 15
3.2. Multi-Worker Job Level AB-DUAL* 17
3.2.1. 符號定義 17
3.2.2. 演算法 17
3.2.3. Abortion 18
3.2.4. Hard Abortion 20
3.2.5. Soft Abortion 20
第四章實驗及結果 21
第五章結論與未來展望 23
參考資料 24

參考文獻

[1] Aske Plaat; Jonathan Schaeffer; Wim Pijls; Arie de Bruin; (1994). SSS* = a-b + TT. Technical Report TR-CS-94-17, Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
[2] Aske Plaat; Jonathan Schaeffer; Wim Pijls; Arie de Bruin; (1995). A Minimax Algorithm Better than Alpha-Beta? No and Yes. Technical Report TR-95-15, Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
[3] Aske Plaat; Jonathan Schaeffer; Wim Pijls; Arie de Bruin; (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence 87(1-2): 255-293.
[4] Donninger, C. and Lorenz, U., (2006). Innovative Opening-Book Handling. Advances in Computer Games, 11th International Conference (ACG 2005), volume 4250 of Lecture Notes in Computer Science, pp. 1-10. Springer.
[5] George Stockman; (1979). A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence 12(2):179-196.
[6] Guillaume M.J-B. Chaslot; Jean-Baptiste Hoock; Julien Perez; Arpad Rimmel; Olivier Teytaud; and Mark H.M.Winands; (2009). Meta Monte-Carlo Tree Search for Automatic Opening Book Generation. Proceedings of the IJCAI’09 Workshop on General Intelligence in Game Playing Agents: 7–12.
[7] I-Chen Wu; Hung-Hsuan Lin; Der-Johng Sun; Ping-Hung Lin; Yi-Chih Chan; and Bo-Ting Chen; (2010). Job-Level Proof-Number Search for Connect6. The International Conference on Computers and Games , Kanazawa, Japan, and also the IEEE Transactions on Computational Intelligence and AI in Games, DOI: 10.1109/TCIAIG.2012.2224659.
[8] I-Chen Wu; Hung-Hsuan Lin; Der-Johng Sun; Kuo-Yuan Kao; Ping-Hung Lin; Yi-Chih Chan; Bo-Ting Chen; (2013). Job-Level Proof Number Search. IEEE Trans. Comput. Intellig. and AI in Games 5(1): 44-56
[9] James R. Slagle; John E. Dixon; (1969). Experiments with some programs that search game trees, JACM 16, 2 189-207.
[10] John P. Fishburn (1983). Another optimization of alpha-beta search, SIGART Bulletin, Issue 84.
[11] Jr-Chang Chen (2005). Design and Implemantation of Knowledge-base System for Computer Chinese Chess.
[12] Knuth, D.E., and Moore, R.W. (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6:293-326.

[13] Lung-Ping Chen; I-Chen Wu; Chih-Wei Hsieh; Der-Johng Sun; Hung-Hsuan Lin. (2013). The Development of the Resource Broker of Desktop Grid Federation for Tree Search Applications. Japanese Society for Artificial Intelligence 2013.
[14] Michael Buro; (1999). Toward Opening Book Learning. ICGA Journal 22(2):98-102.
[15] Thomas R. Lincke; (2000). Strategies for the Automatic Construction of Opening Books. International Conference on Computers and Games.

指導教授

張嘉惠、陳志昌

審核日期

2013-8-13

推文