如何使用轉置表與MTD（f）

Question

我正在爲紙牌遊戲編寫人工智能，經過一些測試後，我發現在我的alpha測試版算法中使用MTD（f） - 一系列零窗口搜索 - 比單獨使用alpha-beta更快。

的MTD（F）算法以及這裏http://people.csail.mit.edu/plaat/mtdf.html

我的問題是，在MTD（F）搜索每遍（每猜測），我不重用任何先前位置的描述我已經存儲了，即使寫在鏈接上表明我應該（實際上在迭代之間清除表格加速了算法）。

我的問題是，當我在換位表中存儲一個位置和一個值時，我還存儲了它的有效alpha和beta值。因此，用不同的猜測（因此alpha和beta）通過樹的第二遍不可能重用任何信息。這是預期的還是我缺少一些基本的東西？

例如，如果對於alpha = 3 beta = 4，我們應該得到7的結果（顯然是截斷值），我應該在表中存儲它作爲α= 3到β= 6有效嗎？或者beta = 7？

Answer 1

您的問題歸結爲如何在alpha測試搜索旁邊使用換位表的概念性理解。這也是我遇到的一個巨大問題，在四處看後，我發現this discussion這比我關於該主題閱讀的任何文章都更自然地向我解釋了這個概念。

基本上你不能把所有的alpha-beta結果都視爲相同的，因爲當發生截斷時，結果只表示一個界限，而不是真正的minimax值。已經證明，使用邊界仍然會始終給你相同的最佳狀態，但可能沒有確切的分數。當你從截止狀態存儲狀態時，你需要把它作爲一個界限，並在下一個階段嘗試改進。這通常會多次評估同一個節點，但它會根據需要不斷改進實際分數。

Here is a good example更完整地實現了前面鏈接文章中列出的概念。滾動到第14頁。