一個改良的對局樹搜尋演算法

Abstract

在對局樹的搜尋中，搜尋節點的多寡影響搜尋速度很大，而在眾多的對局樹搜尋演算 法中，SSS (State Space Search)演算法幾乎都可省略最多的節點，因此SSS 演算法 在對局樹的搜尋中佔了很重要的地位。 SSS 演算法最主要的兩大缺點就是需要龐大的記憶體及耗費很多時間在管理此龐大記 憶體。由于SSS 演算法花了太多時間在管理記憶體上，而且目前一般電腦很少配備那 麼大的記憶體，所以SSS 演算法目前並不適合實際的應用。 本文最主要的目的就是針對SSS 演算法的這兩個缺點做改進，使得SSS 演算法不再需 要太大的記憶體，並且在速度上也能有所改進。我們利用固定大小的OPEN LIST 及下 界雙數，減少了SSS 演算法所需的記憶體。再引進簡單的HASH函數，使改進後的SSS 演算法加快搜尋速度。最后我們以象棋的中盤局面為實驗資料，針對改進後的SSS 演算法跟其它的對局樹搜尋演算法做了一些比較。