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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/61564

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/61564

Title:	應用於象棋開局庫之工作層級AB-DUAL搜尋演算法;Job-Level AB-DUAL for Chinese Chess Opening
Authors:	林伯翰;Lin,Po-Han
Contributors:	資訊工程學系
Keywords:	工作層級系統;最大最小搜尋;開局庫;象棋;Job Level System;Alpha-Beta Search;Opening Book
Date:	2013-08-13
Issue Date:	2013-10-08 15:22:23 (UTC+8)
Publisher:	國立中央大學
Abstract:	電腦象棋目前研究主要使用被動式開局庫，其建構方式為收集棋譜並統計整理勝敗等數據。其主要的問題是，使用時若依照統計數據來當作選擇依據，可能選到統計數據顯示為優秀的盤面，但盤面評估程式判斷為不佳。開局庫為保有與評估程式的一致性，避免遭遇上述情況，除了使用統計資料以外，還必須要對開局庫內的葉節點進行盤面評估，然而這是非常大量的計算，因此本論文使用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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	803	View/Open

社群 sharing

Loading...