1. 首頁
  2. 問答
  3. 國際象棋：高分支因子

國際象棋：高分支因子

2013-05-11 82 views
6

我想開發一個簡單的國際象棋引擎，但我正在努力與它的表現。我已經實施了alpha-beta修剪和迭代深化（沒有任何額外的啓發式）的Negamax，但我無法獲得超過第3-4層的合理搜索時間。下面是我的程序日誌摘錄從遊戲的開頭：國際象棋：高分支因子

2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 
2013-05-11 18:22:06,897 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 
2013-05-11 18:22:08,005 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 
2013-05-11 18:22:10,485 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6

它表明分支因子是10左右。我已經閱讀了正確的舉動排序我應該得到的東西約6，所以我懷疑我的訂購是錯誤的。它目前的工作方式如下：

  1. 遊戲樹節點有一個鏈接的子節點列表;最初，捕獲和促銷安靜的移動之前放置
  2. 在搜索中，孩子增加字母或導致截止放置在列表
  3. 關於深化PV的下一個迭代的開始要搜索的第一個

這是一個合適的方式來訂購移動和我得到的分支因素是可以預料的嗎？目前我正在使用一個簡單的靜態評估函數，它只考慮位置的材料差異 - 是否可以成爲低截止率的原因（如果還考慮數字的移動性，我會得到類似的結果）？諸如零移動減少或啓發式殺手這樣的技術是否會顯着幫助（不是10-15％，而是一個數量級）？我不希望我的引擎強大，但我希望分支因子大約爲6.

來源

2013-05-11 Matis

+0

這是您第一次搬家的日誌嗎？如果是這樣，那些PV對我來說不合法。 – TonyK 2013-05-11 19:19:07

+0

Claude Shannon是數學家，他在1950年代提出了第一種計算機胸部算法。他的論文是香農數字的基礎，據說是可能的國際象棋遊戲數量（大約10^120）。在他的工作中，他得出的結論是，如果一臺計算機可以每秒鐘評估10^6次可能的移動，那麼需要一臺計算機超過10^90年才能達到第一步（宇宙中的原子數目是估計在10^80左右）。 – scottb 2013-05-11 19:21:30

+1

這是第三步。以前是C2-> C4和D1-> A4。 – Matis 2013-05-11 19:22:09

回答

26

我在C＃中開發了一個象棋引擎，它的分支因子在2.5左右。絕對有可能通過許多個數量級來改進你的引擎。現在的總體策略是基於良好的移動排序使用非常積極的移動修剪。你爲了能夠看到一些深刻的戰術線路而犧牲了一些正確性。

下面是我發現最有效的技術概述。請注意，一些組件是互補的，其他組件是替代品，所以我給出的結果是一般指導原則。如果你沒有堅實的基礎，名單末尾的巨大收益是不可能的。

  1. 只是negamax與alpha-beta pruning：深度4在3秒內。

  2. 添加iterative deepening和null move heuristic：深度5.迭代加深在這一點上並沒有真正的幫助，但它很容易實現。無效 移動包括跳過你的回合，並看看你是否仍然可以通過淺搜索獲得beta測試截止日期 。如果可以，那麼它可能安全地修剪樹，因爲它幾乎總是有利於 移動。

  3. Killer heuristic：深度6.這涉及到存儲舉動， 原因公測截斷並首先嚐試他們，如果他們是合法的下一次 你是在同一深度。你似乎已經在做類似 了。

  4. MVV/LVA ordering：深度8.基本上，你想把他們 在移動 列表的頂部有大量的潛在材料淨收益的捕獲。所以如果一個棋子捕獲一個皇后，你應該首先搜索它。

  5. Bitboard representation：深度10.這不會改善分支 因子，但這是我在達到這一點時所做的。排列 陣列，改爲使用UInt64 s，並使用make/unmake而不是copy-make。如果你覺得困難，你不需要使用魔術貼紙;有更簡單的方法仍然非常快。位板極大地提高了性能 並且使編寫評估組件變得容易。我從 （6）分鐘到3秒。 （順便說一下，寫一個perft功能是確保移動代正確性的好方法）

  6. Transposition table：深度13.這提供了巨大的收益，但也 很難得到正確的。在執行表之前，請絕對確定您的位置散列 是正確的。大部分的好處都來自於 令人驚歎的表格，始終將最佳的 移動到表格中，並且每當您獲得匹配的位置時，首先嚐試 。

  7. Late move reductions：深度16.這極大地增加了您的搜索深度，但強度增益比其他技術更爲人爲的增加 。基本上，您訂購 的步驟現在非常好，您只需要完全搜索節點中的前幾個 移動，並且可以使用淺搜索來檢查其他移動。

  8. Futility pruning：深度17.葉節點通過跳過具有尋找潛在 材料增益時提高了節點的值的可能性較低移動 修整。如果移動的淨潛在收益+該頭寸的靜態評估低於該頭寸的當前值，則跳過該移動的 評估。

還有其他各種組件也有幫助，但大多數組件都很小，有些組件也是專有的。：D然而，並不是所有的高搜索深度和低分支因素。諸如quiescence search之類的東西會惡化搜索深度，但對於任何引擎來說都是非常必要的。沒有它，你的引擎將遭受巨大的戰術錯誤。你也可以考慮check extensions和single reply extensions。我還建議至少將piece-square tables引入您的評估功能。這是一個非常簡單的方法，可以大大提高程序的位置知識;你可能會看到你的引擎播放更多通用的開頭。國際象棋程序設計是一個有趣的愛好，我希望信息量不會阻止你！

來源

2013-05-20 04:50:54 Zong

+2

謝謝你提供了一個非常詳盡的答案。我特別希望通過不同的技術提供性能提升，並且一定會使用您的提示。 – Matis 2013-05-20 12:53:43

+0

我幾乎覺得這是一些強制性的閱讀，有關如何優化人工智能問題的一般想法。 – PascalVKooten 2016-01-20 22:32:21

2

您可以使用多種啓發式方法來減少分支因子。

首先，您應該使用transposition table (TT)來存儲位置結果，深度和最佳移動。在搜索移動之前，首先檢查它是否已經在深度≥=處搜索到要搜索的深度。如果是這樣，您可以簡單地使用表中的結果。如果不是這樣，您仍然可以將表中的動作用作搜索的第一步。

如果TT中沒有一個位置（搜索內部）匹配，則可以使用Iterative Deepening (ID)。而不是搜索深度爲N，您首先搜索的深度爲N-2。這將是非常快的，並會給你一個深度搜索N的動作。

還有Null Move Pruning。與Alpha-Beta結合使用（Negamax是Alpha-Beta的變體）將大大降低您的分支因子。這個想法是在搜索一個位置之前，你嘗試一個空移動（不是正在播放）並且執行縮減搜索（N-2或N-3）。減少搜索將非常快速。如果空移搜索的結果仍高於beta，則意味着位置非常糟糕，您不必再搜索它（不總是正確的，但大部分時間都是這樣）。

當然還有其他多種啓發式方法可以用來改善您的move ordering這些都可以提高您的分支因子。

來源

2013-05-16 12:49:03

相關問題

 相關問題