爲什麼Faile比簡單國際象棋程序（TSCP）快得多？ （國際象棋引擎優化）

Question

我希望這不是太大的任意問題的，但我一直在尋找通過Faile和TSCP的源代碼，我一直在玩他們反目成仇。據我可以看到引擎有很多共同點，但Faile每秒搜索約130萬個節點，而TSCP每秒僅搜索300k個節點。

爲faile的源代碼可以在這裏找到：http://faile.sourceforge.net/download.php。 TSCP源代碼可以在這裏找到：http://www.tckerrigan.com/Chess/TSCP。

通過查看它們之後，我看到一些相似之處：兩者都使用陣列板表示（儘管Faile使用144尺寸板），兩者都使用帶有某種轉置表的alpha beta搜索，兩者都具有非常相似的評估函數。我能找到的主要區別是，Faile通過具有片段位置的陣列來使用板的冗餘表示。這意味着當移動產生時（通過兩個程序的非常相似的功能），Faile必須循環更少的壞塊，同時維護這個數組的成本要少得多。

我的問題是：爲什麼會出現在這兩個方案的速度4倍的差異？另外，爲什麼Faile會一直擊敗TSCP（我只是通過觀察他們的動作估計大約200個ELO差異）？對於後者，這似乎是因爲Faile正在深入尋找幾層。

Answer 1

TSCP沒有哈希表（-75 ELO）。 TSCP沒有殺手爲了訂購（-50 ELO）。 TSCP不爲空（-100 ELO）。 TSCP有一個壞的攻擊功能設計（-25 ELO）。

在這4件事情你有250點ELO的差異。這會增加每秒節點的數量，但不能在不同引擎上每秒比較節點，因爲程序員可以對節點的不同解釋使用不同的解釋。

Answer 2

簡短的回答： TSCP很簡單（因爲你可以從它的名字猜測）。 Faile更先進，開發人員花費了一些時間來優化它。所以Faile要更快，這意味着更深層次的搜索和更高的ELO也是合理的。

龍答：至於我記得，該計劃中最重要的部分，採用α+β搜索（其中一部分影響性能的最），是移動發電機。 TSCP的移動生成器不會以任何特定順序生成移動。 Faile的生成器（如您注意到的）使用片段列表，該列表按照片段值遞減的順序排序。這意味着它首先會產生更重要的舉動。這允許alpha-beta修剪切割更多不需要的移動，並使搜索樹減少分枝。較少分支樹可能更深，並且仍然具有相同數量的節點，這允許更深入的搜索。

下面是一個非常簡單的例子，說明移動順序如何實現更快的搜索。假設，上屆白人的舉動是愚蠢的 - 他們將一些棋子移到了無保護的位置。如果我們發現一些黑棋移除了這塊棋子，我們可以忽略所有其他棋子，但尚未估算棋步並返回到處理白棋的移動列表。女王控制的空間比棋子多得多，所以它有更多的機會去除這塊棋子，所以如果我們先看皇后的棋步，我們更有可能跳過更多不必要的棋步。

我沒有比較這些程序的其他部分。但最有可能的是，Faile也更好地優化它們。諸如alpha-beta算法本身，搜索樹的可變深度，靜態位置分析等可能也會得到優化。