局面表示與規則
引擎不僅要知道「棋子擺在哪裡」,還要知道輪到誰走、哪些子正在將軍,以及這盤棋怎樣走到這裡。棋盤、行棋狀態和走棋歷史共同支撐搜尋,單看一張棋盤並不總能判斷結果。
本文核對 official Pikafish 提交 1c66b9b,重點解釋幾個核心檔案怎樣配合;搜尋方法另見搜尋演算法。
幾個檔案分別管什麼?
| 檔案 | 主要職責 |
|---|---|
types.h | 定義棋子、顏色、格點、走法等基礎種類。 |
bitboard.h | 提供一組格點的表示及常用位運算。 |
attacks.h/.cpp | 根據位置和阻擋關係,查詢棋子的攻擊範圍。 |
position.h/.cpp | 儲存當前局面,處理落子、撤銷、合法性與歷史規則。 |
movegen.h/.cpp | 結合上述資訊,按需生成候選走法或合法走法。 |
這些檔案各有分工。例如,攻擊表回答「馬能到哪些點」,走法生成器把起點和終點組成候選,合法性檢查再排除走後露將的著法。基礎種類、生成與過濾是相應入口。
同一張棋盤,為什麼要存幾份資訊?
Position 同時儲存按格點排列的 board、按棋子種類和顏色劃分的位棋盤,以及棋子數量等資訊。這不是重複儲存幾盤棋,而是為不同問題準備方便的查詢方式:
- 問「這個點是什麼子」,直接查
board。 - 問「全部紅車在哪裡」,組合顏色與棋子種類的位棋盤。
- 問「攻擊範圍內有哪些敵子」,把兩個格點集合求交集。
位棋盤中的每一位對應一個格點。Pikafish 用 128 位容納 90 個格點,行、列、半邊棋盤和九宮也有相應的集合。車炮的阻擋、馬腿和象眼交給攻擊規則;生成器不必每次重新編寫一套判斷。
攻擊範圍的查表實現及 Magic、PEXT/PDEP 路徑,見位棋盤與攻擊表。查表加快的是計算方式,並不改變棋子的走法。
落子與撤銷:儲存的是返回所需的資訊
搜尋會反覆「試走一步—繼續計算—退回原處」。如果每次都複製整盤棋並重算所有資訊,成本很高。
Pikafish 在當前 Position 上落子,同時建立一個 StateInfo:儲存雜湊鍵、計數、將軍資訊、這步走法和被吃的子等,並用 previous 指向前一個狀態。它不是一份完整棋盤副本;部分欄位從上一步複製,另一些按新局面更新。
undo_move() 把移動的棋子放回,恢復被吃的子,再讓狀態指標退回上一項。舊狀態中的雜湊鍵、計數等隨之恢復。撤銷必須恢復整個相關狀態,不能只把畫面上的棋子挪回去。 否則錯誤會汙染後面搜尋的其他分支。
實戰已提供的著法和搜尋中臨時走出的變化,都要保持正確的前後關係。每個節點看到的是自己的歷史路徑;換到另一個分支,不能沿用剛才分支的將軍資訊和計數。
Zobrist 雜湊:方便認局面,不是完整棋譜
Zobrist 雜湊為「某種棋子在某個點」準備一組數,再把棋盤上的這些數和行棋方資訊用異或組合成鍵。走一步時,只需去掉舊位置、加入新位置,並處理吃子和換邊,不必重新掃描整盤。
這裡能快速更新,是因為同一個數異或兩次會抵消:原來棋子所在位置的那項可以直接移除,不需要從結果反推整盤棋。
當前基本鍵 st->key 是 64 位,主要對應棋子佈局與行棋方。它不是絕對無碰撞的編號,也沒有把先前每步棋裝進去。用於快取的 key() 還結合限招計數的分組和重複過濾資訊作調整,但仍然不能代替完整歷史。
因此,「雜湊相同」不能被解釋為「任何歷史下規則結果都相同」。真正判斷長將、長捉等情況,還需要沿狀態鏈檢查。快取怎樣複用,見置換表。
原始碼:準備 Zobrist 數表、建立基本鍵、增量更新、快取鍵調整。
能走這一步,和走了會怎樣判,是兩件事
偽合法候選已經滿足棋子的基本走法。legal() 在這個前提下主要檢查走後己方將帥是否安全,包括將帥照面;它不會把每條依賴歷史的棋規都重新判斷一遍。
rule_judge() 則處理重複局面、長將、長捉、自然限招以及特定子力和局等情況。實現先用快速過濾減少無關檢查,確有需要時才追查歷史、判斷捉子。有的搜尋中重複情況只提供分數界限,並不立即返回最終勝負。
所以,「這步沒有露將」「這條變化觸發規則判負」「這條變化搜尋分數很差」不能混為一談。重複也不能簡化成一律判和。更詳細的說明見規則與搜尋。
FEN 是局面記錄,不能恢復整段歷史
FEN 能記錄棋子位置、行棋方和計數資訊,但沒有逐著記錄之前誰將軍、誰捉子、局面曾怎樣重複。把當前局面匯出為 FEN,再單獨讀回來,並不等於恢復了原先的走棋歷史。 當前 set(fen) 會重新初始化局面與起始狀態,再由棋盤計算相關資訊。
需要復現依賴歷史的問題時,應保留一個已知起點及之後的著法序列。UCI 的 position … moves … 正是先設定起點,再逐步走入這些著法,建立對應狀態鏈;它也不能補回起點以前未提供的歷史。
向開發者報告規則問題時,最好同時提供起始 FEN、後續著法、引擎版本和預期判定。只發最後一張棋盤,往往不足以重現問題。FEN 解析中的格式與局面檢查,也不等於證明該局面一定能從開局合法走到。
原始碼:FEN 初始化、從起點重放著法;命令形式見 UCI 協議。
perft 能測什麼,不能測什麼?
perft 按合法走法展開到指定正深度,統計到達該深度的走法序列數。不同順序即使到達同一盤面,也分別計數。它不挑最佳著法,不靠 NNUE 評分,也不使用搜索剪枝。
當前 perft.h 使用 MoveList<LEGAL>、do_move() 和 undo_move();根節點還分別輸出每步的計數,便於定位哪條分支少生成或多生成了走法。
它沒有呼叫 rule_judge(),不能據此宣稱驗證了全部象棋棋規。 長將、長捉、限招等歷史判定,需要另外的測試;最佳著法、評分與選擇性搜尋也不由 perft 驗證。
| 測試 | 主要回答的問題 |
|---|---|
| perft | 走法生成、王安全過濾及落子撤銷是否與預期計數一致? |
| 棋規迴歸用例 | 給定起點與歷史後,是否在正確時點作出預期判定? |
| 搜尋迴歸與對弈測試 | 搜尋行為是否出現異常,修改是否改善實際表現? |
計數一致是有價值的檢查,但不是「引擎所有功能均正確」的證明。
原始碼:perft 實現。
