搜尋演算法
皮卡魚不會把所有變化都算到同樣深。它會先試更有希望的走法,把關鍵變化算得更深;對希望較小的分支少算,或提前停下。NNUE 負責給局面打分,搜尋負責比較「走下去會怎樣」。
本文以 official Pikafish 的提交 1c66b9b 為核對基準。下文列出的方法均能在這份程式碼中找到;具體閾值會隨版本調整,因此重點解釋用途,不把調參常數當成固定規則。文末附原始碼入口及 Chessprogramming Wiki 等延伸資料。
相關內容:原始碼導讀、局面評估與 NNUE、局面表示與規則、引擎執行與通訊。
先看整體:一次搜尋在做什麼
可以把搜尋理解為不斷重複下面幾件事:
- 看當前局面是否已經觸發勝負、和棋或重複局面等規則。
- 查快取,看看以前是否算過,能否複用結果或好走法。
- 生成候選走法,優先試更有希望的,排除走後露將等非法著法。
- 走一步,換對方思考,再把結果傳回來;算完後撤銷這一步。
- 根據結果繼續深算、補搜,或停止某些分支。
這是一次搜尋的概覽。實際實現會交錯進行評估、剪枝和深度調整,下文按各方法解決的問題展開。
| 需要解決的問題 | Pikafish 使用的方法 |
|---|---|
| 雙方都選對自己有利的棋,怎麼比較? | Negamax 形式的 Alpha-Beta、主要變例搜尋(PVS) |
| 時間有限,先算多深? | 迭代加深、期望視窗(Aspiration Windows)、時間管理 |
| 先看哪步,算過的能否複用? | 走法排序、歷史啟發、靜態交換評估(SEE)、置換表(TT) |
| 深度到了,但吃子還沒算完怎麼辦? | 靜態搜尋(Quiescence Search) |
| 哪些地方少算,哪些地方多算? | 空步剪枝、ProbCut、無望剪枝、LMR、IIR、奇異延伸等 |
| 象棋走法與棋規怎麼處理? | 位棋盤與攻擊表、合法性檢查、將軍/長捉/重複與限招判定 |
Minimax 與 Negamax:換個角度看分數
先假設所有分數都從紅方看:越大越利紅,越小越利黑。紅方走時選最大值,黑方走時選最小值,這就是 Minimax(極小化極大)。引擎不能只看「我能吃到什麼」,還要考慮對手會選最讓自己難受的回應。
Negamax 把兩套處理統一起來:分數始終從當前行棋方看,換一方就取負號。 如果走完一步後,對手看到的分數是 -80,對自己就是 +80。於是雙方都只需「取最大值」,遞迴時寫成 score = -search(...)。
這裡的一層(ply)指一方走一步,紅黑各走一步是兩層。示例分數只用於說明比較關係,不代表某個棋子的固定價值。
Alpha-Beta:已經不會改變選擇,就不必算完
假設紅方已有一條路線,面對黑方的最佳回應也能得到 +50。再檢查另一條路線時,只要發現黑方有一個回應能把分數壓到 +30,這條路線就不可能比前者更好。黑方是否還能把它壓到 +10,已不影響紅方的選擇,可以省下後續計算。
Alpha-Beta 用 alpha 和 beta 表示本次搜尋關心的分數視窗:
alpha:需要超過的門檻;不超過它,就不能改善當前選擇。beta:達到它便已足以讓上層排除這條路線,無須繼續求精確分數。
視窗規定本次搜尋關心的分數門檻。 結果不高於原來的 alpha 叫 fail-low,給出上界;達到或超過 beta 叫 fail-high,給出下界;落在視窗內,得到該深度、該評估方式下的確切值。fail-soft 允許返回視窗外的分數,解釋結果時仍要保留相應界限種類。
只使用基本 Alpha-Beta,在相同搜尋樹和葉子評估下,可以得到與完整 Minimax 相同的結果。後面介紹的空步、無望剪枝和減深加入了經驗判斷,不能一概套用這個保證。
展開:一個只展示基本原理的 Negamax / Alpha-Beta 例子
下面用教學虛擬碼展示 Negamax 和 Alpha-Beta 的骨架。terminal_score() 先處理終局與規則,包含象棋中無合法著法判負;分數從當前行棋方看。示例在深度用完時直接評估,Pikafish 的對應路徑會進入後文的靜態搜尋。
int search(int depth, int alpha, int beta) {
if (auto result = terminal_score(); result.has_value())
return *result;
if (depth <= 0)
return evaluate_side_to_move();
int best = -INF;
for (Move move : ordered_legal_moves()) {
make_move(move);
int score = -search(depth - 1, -beta, -alpha);
undo_move(move);
best = std::max(best, score);
alpha = std::max(alpha, score);
if (alpha >= beta)
break;
}
return best;
}負號不僅作用於返回分數,也會把子節點視窗變成 (-beta, -alpha)。INF 應選用足夠大的安全常量,不能直接對最小整數取負,以免溢位。
PVS:其他走法先問「能不能更好」
PVS(Principal Variation Search,主要變例搜尋)建立在好走法往往排在前面的基礎上:在主變化節點,先用完整視窗搜尋第一步,建立一個較可靠的候選;後面的走法先用很窄的視窗試探,問「它能不能超過當前最佳?」有希望時,再按需要用完整視窗補搜。
對於整數分數,(alpha, alpha + 1) 這樣的視窗通常叫零視窗。它主要回答是否超過門檻,不能在這個窗口裡求出一個嚴格介於兩端的整數分數。
Pikafish 將 PVS 與 LMR 組合:後面的候選先淺搜,結果有希望再補深。視窗寬窄決定要問多精確,深度多少決定往後看多遠。 零視窗搜尋仍執行真實走法;空步搜尋則臨時交換行棋方,檢驗讓一手後的結果。
原始碼:PVS 與 LMR 的遞迴搜尋。
用具體視窗看一次 PVS 試探
假設第一著已經得到 +50,後面的著法先用 (50, 51) 試探:
| 返回情況 | 得到的資訊 | 下一步 |
|---|---|---|
| 不高於 50 | 這次搜尋給出上界,候選沒有超過門檻。 | 繼續取下一候選。 |
| 達到或超過 51 | 得到超過門檻的下界。 | 在滿足補搜條件時擴大視窗、恢復相應深度。 |
比如 fail-soft 返回 65,仍要結合下界種類閱讀,再通過補搜判斷它究竟多好。PVS 與 LMR 的實際組合見遞迴搜尋。
迭代加深與期望視窗:先有答案,再逐步改進
皮卡魚從較淺的深度開始,一輪輪提高目標深度。這叫迭代加深。淺層搜尋得到的最佳走法、主變化、分數和快取,會幫助下一輪更快找到重點;時間用完時,也有已經得到的結果可用。
根節點的期望視窗圍繞候選近期平均評分設定較小範圍,並參考分數波動。結果明顯超出範圍時,程式碼擴大相應一側的視窗再搜,使搜尋在穩定候選上節省工作、在異常變化上補充計算。
介面的 depth 20 是迭代的目標深度。減深、延伸和靜態搜尋使各條分支的實際深度不同。主變化(PV)展示當前搜尋認為雙方會選擇的主要路線,可隨後續計算改變。
原始碼:迭代循環與視窗調整。
走法生成:列出候選,再檢查能不能真走
生成、合法性檢查和排序各管一件事:有哪些候選、能不能走、先算哪步。
生成器可按需要列出吃子(CAPTURES)、非吃子(QUIETS)、應將(EVASIONS)或全部偽合法走法(PSEUDO_LEGAL)。偽合法的意思是基本走法符合要求,但還可能走後露將;主搜尋取出候選後,會呼叫 pos.legal() 檢查。需要直接拿到完整合法列表時,LEGAL 生成也會進行過濾。
這裡的 quiet 常譯作「靜著」,但它只是不吃子的走法,仍然可能將軍。
象棋中特別需要處理的情況
- 炮:不吃子時沿無阻擋的直線走,吃子時必須隔一個炮架。被炮將軍時,移走己方炮架也可能解將。
- 馬與象:要處理馬腿、象眼和象不過河;兵卒過河後的橫走、將帥和士的九宮範圍也由對應攻擊規則限制。
- 將帥安全:走後不能讓己方將帥受攻擊,包括將帥照面。
- 多子將軍:不能照抄國際象棋的「雙將只能動王」。當前實現遇到多個將軍棋子,會生成全部偽合法走法,再篩出合法應對。
在候選已符合基本走法的前提下,legal() 主要檢查走後將帥是否安全;長將、長捉等依賴歷史的判定由後面的規則邏輯處理。
位棋盤與攻擊表:一次處理一組格點
位棋盤把一組格點表示成二進位制位,例如「所有紅子的位置」或「這枚馬能攻擊的位置」。交、並等位運算就能同時處理一批格點。Pikafish 使用 128 位位棋盤容納象棋的 90 個格點,同時保留按格點查詢棋子的陣列。
車、炮、馬、象等攻擊範圍利用預先建立的表來查詢。普通編譯路徑用 magic 乘法和移位計算索引;啟用 USE_PEXT 的路徑使用 PEXT / PDEP 指令。具體採用哪條路徑取決於編譯版本,不能據此認定某種指令在所有 CPU 上都更快。
搜尋走入一個分支時落子,返回時撤銷。局面狀態和雜湊鍵隨走法增量更新,省去每一步重新掃描整盤的工作。
走法排序與歷史啟發:先試最有希望的棋
好的排序能更早找到強著,讓 Alpha-Beta 更快停止其他分支。常規主搜尋中的取著順序大致為:
- 置換表裡留下的候選走法(TT move)。
- 經 SEE 等快速判斷較好的吃子。
- 歷史評分較好的非吃子走法。
- 較差的吃子。
- 較差的非吃子走法。
MovePicker 按階段生成、評分並取出候選,應將、靜態搜尋和 ProbCut 各有對應流程。階段中的「較好」「較差」表示優先順序,較差吃子仍可進入搜尋。當前順序允許高歷史分非吃子先於較差吃子,主要依靠 TT、吃子歷史和各類非吃子歷史來排序。
歷史啟發(History Heuristic)記錄走法在搜尋中的效果。 經常產生有效截斷或其他有用結果的走法會提高後續優先順序,反覆表現差則降低優先順序。統計記錄在引擎的歷史表中。
程式碼同時使用主歷史、吃子歷史、連續著歷史(結合前面走過什麼)、兵卒結構歷史,以及靠近根節點的歷史。吃子評分會結合被吃子的價值與吃子歷史;非吃子還會參考將軍、躲避或進入低價值棋子的攻擊範圍等資訊。
原始碼:MovePicker 階段與評分、歷史表定義。
SEE:先粗算一下換子是否吃虧
SEE(Static Exchange Evaluation,靜態交換評估)快速估計一個落點上的連續換子能否達到收益門檻:我吃過去,對方吃回來,我還能不能再吃,大致是賺是虧?Pikafish 的 see_ge() 回答的是「是否至少達到給定門檻」。
SEE 用於吃子排序和部分剪枝,也可篩查非吃子後是否容易丟子。它集中計算落點附近的交換收益;棄子引出的遠處威脅與後續配合,需要搜尋繼續驗證。
原始碼:靜態交換評估。
置換表:算過的局面儘量複用
不同的走棋順序可能到達同一局面。置換表(Transposition Table,TT)用雜湊鍵查詢先前的搜尋記錄,儲存候選走法、深度、分數、分數的界限種類及靜態評估等資訊。
記錄的界限對應產生它的搜尋深度、評估和選擇性策略,複用時需要檢查這些條件。
| 記錄種類 | 表示什麼 |
|---|---|
EXACT | 在那次搜尋條件下得到的確切返回值 |
LOWER | 下界:已知至少有這麼好,常見於 fail-high |
UPPER | 上界:已知不超過這個值,常見於 fail-low |
只有深度、節點種類、界限等條件合適時,才可直接複用分數並停止搜尋;否則,快取中的走法仍可拿來優先嚐試。EXACT 也不代表已經從數學上解出了這盤棋的最終勝負。
象棋的局面價值還會受走棋歷史與限招影響。當前實現有相應的規則檢查和部分快取保護,不能簡單認為「棋子擺放相同,任何歷史下都可無條件使用同一結果」。
原始碼:TT 資料結構、主搜尋讀取與截斷。設定記憶體大小可參見 Hash 說明。
靜態搜尋:不要在換子只算一半時停下
假設搜尋剛好在「我吃了對方一個子」後到達目標深度。如果立刻打分,卻沒看到對方下一步能吃回來,就會誤以為賺了子。靜態搜尋(Quiescence Search,qsearch)在常規深度用完後繼續處理部分戰術變化,減少這種「停在半截」的誤判。
當前 Pikafish 通常繼續搜尋吃子;被將軍時改用應將候選,不能只生成吃子。
- 未被將軍時,可把當前靜態評估作為 stand pat 的基準,再看值得搜尋的吃子能否改善它。stand pat 是搜尋中的近似基準,實戰仍須走出合法著法。
- 被將軍時,不能使用 stand pat,必須考慮應將;若無合法應對,就是敗局。
- qsearch 自己也使用置換表、無望剪枝和 SEE 等篩選,並不會窮盡所有吃子或所有將軍。
- 象棋中無合法走法,即使沒被將軍也是困斃判負;當前程式碼對這種情況也有檢查,不能照搬國際象棋的困斃和棋。
「靜態搜尋」仍然在走棋遞迴;「靜態評估」才是給當前局面打分,兩者要區分。
原始碼:qsearch。
剪枝:把算力留給更可能影響結果的分支
下面這些選擇性方法都能在當前 Pikafish 中找到。它們結合靜態評估、深度、歷史和分數視窗決定哪裡可以少算。它們帶有經驗假設,可能誤判;適用條件、餘量和補搜用來控制風險。 表中只解釋用途,不省略成「滿足一句話就總會觸發」。
| 方法 | 用直白的話解釋 |
|---|---|
| Razoring | 靜態分已經遠低於 alpha 等條件滿足時,轉交靜態搜尋,檢查眼前戰術,而不繼續原來的深層搜尋。 |
| 反向無望剪枝(Reverse Futility) | 靜態分減去餘量仍足夠高時,某些節點可提前返回,省去後續搜尋。 |
| 空步剪枝(Null-move Pruning) | 內部假設自己讓一手,淺搜後若仍夠好,就可能無需把真實走法逐個算完。詳見下文。 |
| ProbCut | 對有希望的吃子先做靜態搜尋,再按需做較淺搜尋;若越過一個比 beta 更高的門檻,就可能提前停止當前子樹。 |
| Small ProbCut | 利用置換表中足夠深、明顯超過額外門檻的下界,提前返回;不再重複完整的試吃子流程。 |
| 著法數量剪枝(Move-count Pruning / LMP) | 已經試了足夠多候選且條件合適時,跳過後續非吃子走法;數量門檻會變化。 |
| 候選走法的無望剪枝(Futility) | 結合靜態分、可能吃到的子力、歷史和預計深度,跳過看起來難以追上 alpha 的候選。 |
| 歷史剪枝(History Pruning) | 某些非吃子走法的連續著/兵卒結構歷史太差時,不再投入搜尋。 |
| SEE 剪枝 | 快速換子估計損失過大時,跳過某些候選;門檻隨深度等因素改變。 |
這些判斷會受節點種類、是否被將軍、將殺分、子力和歷史等條件限制,不能把每一項理解成適用於所有局面。
另外,**殺棋距離剪枝(Mate-distance Pruning)**利用當前距根節點的層數,收緊可能的殺棋分上下界,排除不可能改善殺棋距離的搜尋。它屬於分數界限推導,應與上面的經驗判斷區分。
空步為何有用,又會在哪裡出錯?
空步剪枝採用「讓對手先走,局面仍足夠好」的經驗判斷:臨時交換行棋方,以減小的深度檢驗這一假設。空步僅用於搜尋內部。
輪到自己走反而變壞的局面稱為 zugzwang(楚茨文克),會破壞上述假設。因此程式碼要求未被將軍、己方仍有車馬炮等條件,較深搜尋還可能回到原局面驗證。減深量隨條件變化,驗證搜尋用來降低誤判風險。
減深與延伸:關鍵分支值得算得更深
剪枝是省掉某些搜尋;減深是先少算;延伸是多算。 Pikafish 會根據搜尋過程動態調整深度。
| 方法 | 當前實現的作用 |
|---|---|
| LMR(Late Move Reductions,後著減深) | 排在後面、希望較小的著法先淺搜;若結果超過 alpha,再視結果補深。減深量參考歷史、節點種類等,也可能用於吃子。 |
| IIR(Internal Iterative Reductions,內部迭代減深) | 缺少 TT 候選等條件成立時,降低當前節點的搜尋深度。IID 則通過一輪淺搜尋找好候選,兩者採用不同處理。 |
| 奇異延伸(Singular Extension) | 暫時排除一個合格的 TT 候選,淺搜其餘走法;如果其他走法都明顯差一截,就給這個候選更多深度。 |
| Multi-cut 與負延伸 | 在上述排除候選的檢查中,其他走法仍足夠好時,可能直接截斷;另一些條件下則減少 TT 候選的深度。 |
奇異延伸判斷的是 TT 候選與其他走法在一次受限搜尋中的差距。即使有多個合法著法,一個明顯突出的候選也可能獲得延伸。其餘深度調整還結合節點種類、歷史和搜尋結果共同決定。
NNUE 與評估修正:打分也會影響搜尋方向
搜尋經常需要一個不繼續走棋的局面估分。Pikafish 呼叫 NNUE 評估,再結合搜尋中的修正資訊使用這個分數;它既幫助葉子評分,也會影響某些剪枝和深度分配。
評估修正歷史(Correction History)記錄靜態估分與後續搜尋結果的偏差。 程式碼按兵卒、其他子力佈局和前序著法等資訊組織統計,用於修正相關局面的靜態分。統計儲存在搜尋歷史表中,NNUE 權重由載入的網路檔案提供。
因此,要把三件事分開:NNUE 提供局面估分,歷史表幫助排序或修正,搜尋比較後續變化。這幾部分配合決定引擎把時間花在哪裡。
原始碼:評估修正的計算與更新、搜尋中的評估入口。
象棋規則:相同盤面,不一定是同一個問題
搜尋中不僅要檢查將軍和無合法著法,還要處理長將、長捉、重複局面及自然限招等情況。相同盤面再次出現,不代表必然和棋。
rule_judge() 先用快速過濾判斷是否值得追查歷史,再沿狀態鏈檢查將軍與捉子。已確定的裁決可直接返回;部分搜尋內重複給出分數界限,供搜尋收窄視窗後繼續。
判斷時要分別核對走法是否合法、歷史是否觸發裁決、快取結果是否適用。具體生成步驟、循環回看與被捉棋子身份的交集,見局面表示與規則。
多執行緒、MultiPV 與時間:怎樣分配這次思考
多執行緒讓工作執行緒推進各自的搜尋,並共享置換表;部分歷史資訊按 NUMA 節點共享。執行緒既會重複工作,也會利用其他執行緒留下的資訊,收益取決於局面、硬體和搜尋條件。
MultiPV為多個根候選保留主要變化,需要額外的根搜尋。它適合比較備選棋;在相同時間內,候選增加會分攤單條主線的計算預算。
時間管理先根據剩餘時間、加秒、待走步數和 Move Overhead 等計算預算,再參考分數下降、最佳走法是否穩定等情況調整。固定時間、節點數等限制也會影響何時停止。迭代加深讓引擎能在這些限制下逐步改進已有答案。
原始碼:執行緒啟動與結果選擇、時間預算、搜尋中的時間調整。相關設定見 UCI 選項。
原始碼與延伸閱讀
從哪裡讀 Pikafish 原始碼
以下連結全部固定到本文核對的提交,避免以後程式碼變化後行號對應不上:
search.cpp:迭代加深、PVS、各類剪枝、減深、延伸和靜態搜尋。movepick.cpp與history.h:取著階段、排序評分與歷史統計。movegen.cpp與attacks.h:走法生成及攻擊範圍。position.cpp:合法性、落子撤銷、SEE 和象棋規則。tt.h、thread.cpp、timeman.cpp:快取、執行緒和時間分配。
繼續理解演算法
Chessprogramming Wiki 適合查術語和通用思路;其中很多例子針對國際象棋。閱讀時應區分通用搜索方法與具體棋規,Pikafish 是否實際採用某個方法,以本頁對應原始碼為準。
