DTS演算法效能改良之研究

Abstract

電腦西洋棋在近年來已經大量使用平行搜尋演算法，目前表現最好的是使用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％左右的效能。