局面表示與規則
引擎儲存棋子位置、行棋方、將軍資訊和走棋歷史。局面價值由當前盤面與到達它的路徑共同決定,長將、長捉和自然限招尤其依賴歷史。
本文核對 official Pikafish 提交 1c66b9b。下文解釋這份原始碼的實際流程;不同版本及規則選項應結合各自實現閱讀。搜尋方法見搜尋演算法。
幾個檔案分別管什麼?
| 檔案 | 主要職責 |
|---|---|
types.h | 定義棋子、顏色、格點和走法。 |
bitboard.h | 用位運算表示、組合一組格點。 |
attacks.h/.cpp | 根據位置與阻擋關係,查詢攻擊範圍。 |
movegen.h/.cpp | 把起點、可達終點與目標集合組合成走法。 |
position.h/.cpp | 儲存局面,處理落子撤銷、將帥安全與歷史規則。 |
例如馬的攻擊查詢先處理馬腿;生成器將可達點組成候選;legal() 再檢查走後將帥安全。原始碼入口:基礎種類、生成與過濾、攻擊查詢。
同一張棋盤,為什麼要存幾份資訊?
Position 同時維護按格點排列的 board、按棋子種類和顏色劃分的位棋盤,以及棋子數量。三者服務於不同查詢:查某點是什麼子,訪問陣列;取全部紅車,組合顏色和棋子種類集合;找攻擊範圍內的敵子,對兩個集合求交集。
位棋盤每一位對應一個格點,Pikafish 用 128 位容納 90 個格點。行、列、半邊棋盤和九宮也有相應集合。走棋和撤銷時,這些表示必須同步更新,搜尋才能繼續使用它們。
車炮線路、馬腿和象眼的攻擊查詢可用預先建立的表加速,Magic 與 PEXT/PDEP 是其中的索引計算路徑,詳見位棋盤與攻擊表。
具體怎樣生成一步棋?
generate_moves() 先取出行棋方某類棋子的位棋盤,用 pop_lsb() 逐個取出起點,再計算攻擊範圍並與 target 求交集。結果集合中每個終點都組成一個 Move(from, to)。
| 請求 | target 的含義 |
|---|---|
CAPTURES | 對方棋子所在的格點。 |
QUIETS | 空格點;生成的非吃子著法仍可能將軍。 |
PSEUDO_LEGAL | 己方棋子以外的格點。 |
EVASIONS | 根據將軍線路收窄目標,並補充特殊解將方式。 |
炮在這裡分兩路處理:吃子查詢炮的隔子攻擊範圍,再與敵子求交集;非吃子查詢車的直線範圍,再與空點求交集。
例如,只看 e 列,炮在 e2,己方棋子在 e5,敵子在 e8,中間其餘點為空。向這一方向的非吃子候選為 e2e3、e2e4;吃子候選為 e2e8,e5 充當炮架。e6、e7 在炮架之後,炮無法跳過去停在空點上。
馬在 e4 時,向上兩條候選是 e4d6、e4f6;如果 e5 有子,這兩個點都會被馬腿阻擋。兵卒的攻擊查詢還接收顏色,處理前進方向與過河後的橫走;士、將帥和象的表處理九宮、半邊棋盤及象眼等限制。
被單子將軍時,生成器先考慮吃掉將軍子、墊入線路和移動將帥;炮將還補上「移走己方炮架」的候選。遇到多個將軍子,則生成全部偽合法候選交給安全檢查。最後,generate<LEGAL>() 用 pos.legal() 過濾;過濾時以列表末項覆蓋非法項,縮短列表。
這些候選的棋理優劣隨後由排序和搜尋判斷。原始碼:逐類生成、炮的兩路生成和應將分支。
落子與撤銷:儲存返回所需的資訊
搜尋反覆試走一步、遞迴計算,再退回原處。Pikafish 直接修改當前 Position,並建立一個 StateInfo:儲存雜湊鍵、計數、將軍資訊、剛走的棋和被吃的子,previous 指向上一狀態。部分欄位複製,另一些增量更新。
undo_move() 將移動的棋子放回,恢復被吃的子,並讓狀態指標退回上一項。恢復棋盤、雜湊和歷史計數必須成套完成,這樣下一條分支才會從相同起點計算。實戰著法和搜尋中的臨時著法都沿各自的狀態鏈組織。
Zobrist 雜湊:快速定位局面
Zobrist 為「某種棋子在某個點」準備數值,再把盤面對應項和行棋方用異或組合成鍵。走棋時異或掉起點、異或進終點,吃子時再移除被吃子的項;同一個數異或兩次抵消,所以更新只涉及發生變化的部分。
基本鍵 st->key 為 64 位,主要對應佈局與行棋方,存在雜湊碰撞的可能。用於快取的 key() 還結合限招計數的分組和重複過濾資訊作調整。重複檢測以基本鍵追查狀態鏈,長將與長捉的具體結果由鏈中的將軍和走棋資訊決定。
相同佈局可以來自不同的將捉歷史,因此讀快取程式碼時,還要核對規則檢查和快取保護。詳見置換表。
原始碼:準備 Zobrist 數表、建立基本鍵、增量更新、快取鍵調整。
走法合法性與歷史裁決
legal() 以候選已滿足基本走法為前提。它先構造走後的佔用集合 (pieces() ^ from) | to:移除起點,保留或加入終點。將帥移動時檢查目的地受攻擊情況;其他棋子移動時檢查己方將帥的原位置,吃子還要排除已被吃掉的攻擊者。維護的牽制與阻擋資訊允許部分著法走快速路徑。
checkers_to() 在新佔用關係下檢查兵卒、馬、車、炮及將帥照面。移動炮架可能使炮將出現或消失,移動馬腿可能開啟馬將,所以檢查會使用走後的阻擋關係。
歷史裁決交給 rule_judge():搜尋走入新節點後,結合之前的將軍、捉子、重複和限招資訊處理勝負或和棋。有些搜尋內重複只提供分數界限,供搜尋收窄視窗。
原始碼:legal 與將帥攻擊查詢、規則判定。相關概覽見規則與搜尋。
怎樣找到並裁決一段循環?
這份實現先計算可回看長度:考慮吃子後的計數、額外將軍步和距最近搜尋空步的距離。至少有四步可回看,且 Bloom 過濾器提示可能存在重複時,才沿 previous 鏈每次回退兩步,比較同一行棋方的基本鍵。過濾器節省無關檢查,命中後仍會逐項比較雜湊鍵。
回退時分別累計兩方是否步步將軍。一方長將,就用決定性勝負分處理;雙方長將,結果為和。雙方都沒有步步將軍時,再在局面副本上呼叫 detect_chases() 檢查長捉。
本版本還區分實戰歷史與根節點之後的搜尋路徑:在根節點及以前找到兩次先前出現,或在根之後符合條件地找到一次先前出現,會進入相應重複分支。三次出現及已確定的循環和棋可直接返回;部分搜尋內第二次出現的勝負預判繼續檢查是否可能轉為和棋。此時 rule_judge() 可留下 result 而返回 false,搜尋據此調整 alpha 或 beta 後繼續。
這描述的是本頁固定提交中的搜尋實現。實際對局應使用與平臺匹配的棋規;比較其他規則版本時,還要核對重複次數、捉的定義和雙方違規的裁決方式。
原始碼:歷史回看與重複分支、搜尋如何使用未終結的重複結果。
捉子怎麼認,怎樣確認一直捉同一子?
chased() 返回一個棋子身份集合,每一位對應一個被捉棋子。函式先篩選攻擊者與目標:這份實現允許將帥、兵卒長捉,目標中的未過河兵卒和對將帥的攻擊也有專門排除;受到牽制的攻擊者只保留相應牽制者目標。
候選攻擊通過 chase_legal() 檢查以後,程式碼按棋種分支處理。馬或炮攻擊車,以及士象攻擊符合條件的更強棋子,進入直接記捉分支。其他候選則臨時模擬吃子,查詢目標點的回吃者,逐個檢查回吃是否使將帥安全;若存在合法回吃,這個分支就排除該候選捉。相同棋種之間的互攻,還要處理對稱攻擊與牽制的例外。
detect_chases() 給雙方現存棋子分配身份編號,並在回退時讓編號隨棋子移動,確保跟蹤的是同一枚棋子。每步比較走前、走後的被捉集合,取 after & ~before 得到該步新造成的捉,再不斷與此前集合求交集。
例如兩步新捉的目標集合分別是 {馬 A, 炮 B} 和 {炮 B, 車 C},交集留下 {炮 B}。如果每步換捉物件,最終交集可能為空。遍歷結束,一方仍有共同目標、另一方沒有時,前者因長捉判負;雙方都有或都沒有共同目標,則返回和棋。遍歷遇到將軍的情況還另有分支,不能直接套用這個集合例子。
原始碼:輕量吃子模擬、捉子篩選與身份交集。棋規背景見象棋棋規疑雲。
自然限招與特定子力和局
do_move() 維護自然限招計數。這份程式碼中,吃子會清零計數和雙方將軍次數;每方超過十次的將軍及對應應將有計數豁免。到 rule60 >= 120 時,rule_judge() 先看是否還有合法走法:有則判和,沒有則按無合法著法判負,保留最後一步造成勝負的情況。
隨後還有特定子力組合的和局識別。程式碼先要求盤上無兵卒,再依據車馬炮、士象配置分為直接和局或需要檢查終局的情況。後一類先檢查當前是否已無合法著法,再逐步檢查是否存在一步使對手無合法著法的路線。這些條件對應原始碼列出的組合,適用範圍應逐項核對。
用 FEN 與著法序列重建歷史
FEN 儲存棋子、行棋方和計數。set(fen) 據此建立新的起始狀態,逐著將捉和之前的重複需要另行提供。復現歷史相關問題時,應儲存起始 FEN 與後續著法,再用 position … moves … 逐步建立狀態鏈。
報告規則問題時,提供起始 FEN、後續著法、版本、規則設定和預期裁決。FEN 解析負責格式與局面條件檢查;若要確認某盤面從開局可達,還需要相應棋譜或另外的可達性分析。
原始碼:FEN 初始化、從起點重放著法;命令形式見 UCI 協議。
perft 與規則迴歸各怎樣測試?
perft 用 MoveList<LEGAL>、do_move() 和 undo_move() 展開至指定正深度,統計到達這一深度的走法路徑。不同順序即使到達同一盤面,也分別計數。根節點還輸出每步的計數,幫助定位少生成或多生成的分支。
perft 的遞迴只列舉走法,完整歷史規則由獨立迴歸用例驗證。兩者覆蓋範圍如下:
| 測試 | 主要回答的問題 |
|---|---|
| perft | 走法生成、將帥安全過濾和落子撤銷是否符合預期計數? |
| 棋規迴歸 | 給定起點與歷史後,是否在正確時點作出預期裁決? |
| 搜尋迴歸與對弈測試 | 搜尋是否異常,改動對實戰結果有何影響? |
perft 不呼叫 rule_judge();長將、長捉和限招需要包含完整歷史的測試,棋力變化需要對弈統計。原始碼:perft 實現。
