Biểu diễn thế cờ và xử lý luật
Engine lưu vị trí quân, bên đến lượt, thông tin chiếu và lịch sử nước đi. Giá trị thế cờ phụ thuộc cả bàn cờ lẫn đường đi dẫn tới đó, nhất là khi xét chiếu dai, đuổi dai và giới hạn nước đi.
Bài viết đối chiếu commit 1c66b9b của official Pikafish, mô tả quy trình của mã này. Phiên bản và tùy chọn luật khác cần được đối chiếu với cách triển khai tương ứng. Xem Thuật toán tìm kiếm để tìm hiểu tìm kiếm.
Mỗi tệp phụ trách việc gì?
| Tệp | Nhiệm vụ chính |
|---|---|
types.h | Định nghĩa quân, màu, điểm trên bàn và nước đi. |
bitboard.h | Biểu diễn và kết hợp tập hợp điểm bằng phép toán bit. |
attacks.h/.cpp | Tra phạm vi tấn công theo vị trí và vật cản. |
movegen.h/.cpp | Ghép điểm đầu, điểm đến và tập mục tiêu thành nước đi. |
position.h/.cpp | Lưu thế cờ, đi và hoàn tác, kiểm tra an toàn của Tướng và luật theo lịch sử. |
Với Mã, phần tra tấn công xử lý chân Mã; bộ sinh nước đi tạo ứng viên; legal() kiểm tra Tướng sau khi đi. Mã nguồn: kiểu cơ bản, sinh và lọc nước, tra tấn công.
Vì sao lưu bàn cờ dưới nhiều dạng?
Position duy trì mảng board theo từng điểm, bitboard theo loại và màu quân, cùng số lượng quân. Tra quân tại một điểm dùng mảng; tìm tất cả Xe Đỏ kết hợp màu và loại; tìm quân địch đang bị tấn công lấy giao của hai tập hợp.
Mỗi bit ứng với một điểm; Pikafish dùng 128 bit cho 90 điểm. Hàng, cột, nửa bàn và cung Tướng cũng có tập riêng. Đi và hoàn tác phải cập nhật đồng bộ các dạng này.
Bảng dựng trước giúp tra nhanh đường Xe, Pháo, chân Mã và mắt Tượng. Magic và PEXT/PDEP là những cách tính chỉ mục, xem Bitboard và bảng tấn công.
Mã nguồn: thành viên của thế cờ, kiểu bitboard, tập điểm và phép toán.
Cụ thể một nước đi được sinh thế nào?
generate_moves() lấy bitboard của từng loại quân bên đến lượt, dùng pop_lsb() tách từng điểm đầu, tính phạm vi tấn công rồi lấy giao với target. Mỗi điểm đến còn lại tạo thành Move(from, to).
| Yêu cầu | Ý nghĩa của target |
|---|---|
CAPTURES | Những điểm có quân đối phương. |
QUIETS | Điểm trống; nước không bắt quân vẫn có thể chiếu. |
PSEUDO_LEGAL | Các điểm ngoài tập quân bên mình. |
EVASIONS | Thu hẹp theo đường chiếu, rồi bổ sung cách giải chiếu đặc biệt. |
Pháo được xử lý theo hai nhánh: bắt quân dùng phạm vi tấn công qua ngòi rồi lấy giao với quân địch; không bắt quân dùng đường thẳng kiểu Xe rồi lấy giao với điểm trống.
Chỉ xét cột e: Pháo ở e2, quân mình ở e5, quân địch ở e8, các điểm giữa còn lại trống. Theo hướng đó, nước không bắt quân là e2e3, e2e4; nước bắt quân là e2e8, với e5 làm ngòi. Pháo không thể nhảy qua ngòi để dừng ở điểm trống e6 hoặc e7.
Mã ở e4 có hai ứng viên đi lên là e4d6, e4f6; quân ở e5 cản chân cả hai. Phần tra Tốt nhận thêm màu quân để xét hướng tiến và đi ngang sau khi qua sông. Bảng Sĩ, Tướng và Tượng xử lý giới hạn cung, nửa bàn và mắt Tượng.
Khi bị một quân chiếu, bộ sinh xét bắt quân chiếu, chặn đường và di chuyển Tướng. Chiếu Pháo còn bổ sung nước chuyển ngòi thuộc bên mình. Nếu có nhiều quân chiếu, mã sinh mọi ứng viên giả hợp lệ rồi kiểm tra an toàn. Cuối cùng, generate<LEGAL>() dùng pos.legal() lọc; khi bỏ một ứng viên, nó lấy mục cuối thay vào và rút ngắn danh sách.
Chất lượng ứng viên được xét tiếp bằng sắp thứ tự và tìm kiếm. Mã nguồn: sinh theo loại quân, hai nhánh của Pháo và giải chiếu.
Đi quân và hoàn tác
Tìm kiếm liên tục thử nước, đệ quy rồi quay về. Pikafish sửa trực tiếp Position hiện tại và tạo StateInfo chứa khóa hash, bộ đếm, thông tin chiếu, nước vừa đi và quân bị bắt. previous nối với trạng thái trước; một số trường được chép, số khác cập nhật tăng dần.
undo_move() trả quân về, khôi phục quân bị bắt và lùi con trỏ trạng thái. Bàn cờ, hash và bộ đếm lịch sử phải được khôi phục cùng nhau, để nhánh tiếp theo bắt đầu từ đúng trạng thái cũ. Nước thực chiến và nước thử trong tìm kiếm đều theo chuỗi trạng thái của mình.
Mã nguồn: StateInfo, đi quân, hoàn tác.
Hash Zobrist: định vị thế cờ nhanh
Zobrist gán số cho từng cặp quân và điểm, rồi XOR các mục đang có với thông tin bên đến lượt. Đi quân bỏ đóng góp ở điểm đầu và thêm ở điểm cuối; bắt quân còn bỏ mục của quân bị bắt. XOR cùng một số hai lần triệt tiêu nhau, nên chỉ cần cập nhật phần thay đổi.
Khóa cơ bản st->key có 64 bit, chủ yếu biểu diễn bố trí và lượt đi, với khả năng va chạm hash. key() dùng cho bộ nhớ đệm còn điều chỉnh theo nhóm bộ đếm giới hạn và bộ lọc lặp lại. Phần xét lặp lần theo khóa cơ bản trong chuỗi trạng thái; thông tin chiếu và nước đi trong chuỗi quyết định kết quả chiếu dai, đuổi dai.
Cùng bố trí quân có thể đến từ những lịch sử chiếu và đuổi khác nhau. Vì vậy cần đọc mã bộ nhớ đệm cùng phần kiểm tra luật và bảo vệ kết quả đệm. Xem Bảng chuyển vị.
Mã nguồn: tạo bảng Zobrist, tạo khóa, cập nhật tăng dần, điều chỉnh khóa đệm.
Nước hợp lệ và phán định theo lịch sử
legal() giả định ứng viên đã đúng cách di chuyển cơ bản. Nó dựng tập chiếm chỗ sau nước đi bằng (pieces() ^ from) | to: bỏ điểm đầu, giữ hoặc thêm điểm cuối. Tướng di chuyển thì xét tấn công ở điểm đến; quân khác thì xét điểm Tướng đang đứng, đồng thời loại quân tấn công đã bị bắt khi cần. Thông tin ghim và vật cản được duy trì sẵn giúp một số nước đi dùng nhánh kiểm tra nhanh.
checkers_to() xét Tốt, Mã, Xe, Pháo và hai Tướng đối mặt theo tập chiếm chỗ mới. Di chuyển ngòi có thể tạo hoặc bỏ chiếu Pháo; chuyển quân cản chân có thể mở chiếu Mã, nên vật cản sau nước đi là dữ liệu cần thiết.
rule_judge() xử lý lịch sử khi tìm kiếm đi vào nút mới, kết hợp chiếu, đuổi, lặp và giới hạn nước để xét thắng, thua hoặc hòa. Một số lần lặp trong tìm kiếm chỉ cung cấp cận điểm để thu hẹp cửa sổ.
Mã nguồn: legal và tra quân chiếu, phán định luật. Tổng quan: Luật và tìm kiếm.
Tìm và phán định một chu kỳ ra sao?
Mã tính giới hạn nhìn lại từ bộ đếm sau bắt quân, các bước chiếu bổ sung và khoảng cách tới nước rỗng gần nhất trong tìm kiếm. Khi có ít nhất bốn bước để nhìn lại và bộ lọc Bloom báo khả năng lặp, nó theo previous, lùi hai bước mỗi lần và so khóa cơ bản của cùng bên đến lượt. Sau khi bộ lọc báo trúng, từng khóa vẫn được so riêng.
Trong lúc lùi, mã ghi nhận mỗi bên có chiếu ở mọi lượt hay không. Một bên chiếu dai thì nhận điểm thua quyết định; cả hai chiếu dai thì hòa. Nếu cả hai đều không chiếu liên tục, bản sao thế cờ gọi detect_chases().
Phiên bản này phân biệt lịch sử thực chiến với đường đi sau nút gốc tìm kiếm. Hai lần xuất hiện trước ở hoặc trước gốc, hoặc một lần xuất hiện trước thỏa điều kiện ở sau gốc, sẽ vào nhánh lặp tương ứng. Lần xuất hiện thứ ba và chu kỳ đã xác định hòa có thể trả về ngay. Một số dự đoán thắng thua ở lần xuất hiện thứ hai còn phải xét khả năng chuyển thành hòa: rule_judge() có thể đặt result nhưng trả false; tìm kiếm dựa vào đó điều chỉnh alpha hoặc beta rồi tiếp tục.
Đây là mô tả commit cố định của bài. Khi chơi thực tế cần chọn luật khớp nền tảng. Với phiên bản luật khác, hãy đối chiếu số lần lặp, định nghĩa đuổi và cách xử khi cả hai cùng vi phạm.
Mã nguồn: nhìn lại lịch sử và nhánh lặp, tìm kiếm dùng kết quả lặp tạm thời.
Nhận diện đuổi và theo dõi cùng một quân
chased() trả một tập định danh quân, mỗi bit ứng với một quân bị đuổi. Trước tiên nó lọc quân tấn công và mục tiêu. Cách triển khai này cho phép Tướng, Tốt đuổi liên tục, đồng thời có nhánh loại Tốt địch chưa qua sông và tấn công vào Tướng. Quân đang bị ghim chỉ giữ các mục tiêu ghim tương ứng.
Sau kiểm tra chase_legal(), mã phân nhánh theo loại quân. Mã hoặc Pháo tấn công Xe, cùng Sĩ hoặc Tượng tấn công quân mạnh hơn thỏa điều kiện, được ghi nhận trực tiếp. Các ứng viên khác được thử bắt quân tạm thời: mã tìm quân có thể bắt lại tại điểm đến rồi kiểm tra từng nước có giữ an toàn cho Tướng không. Nếu có nước bắt lại hợp lệ, ứng viên đó bị loại khỏi tập đuổi của nhánh này. Hai quân cùng loại tấn công lẫn nhau còn có quy định về đối xứng và ghim.
detect_chases() gán định danh cho quân còn trên bàn của hai bên và di chuyển định danh cùng quân khi lùi lịch sử. Mỗi bước so tập bị đuổi trước và sau, lấy after & ~before để tìm đuổi mới do bước đó tạo ra, rồi lấy giao với tập đang tích lũy.
Ví dụ hai tập mục tiêu mới là {Mã A, Pháo B} và {Pháo B, Xe C} thì giao còn {Pháo B}. Đổi mục tiêu mỗi lượt có thể khiến giao cuối cùng rỗng. Sau khi xét xong, nếu chỉ một bên còn mục tiêu chung thì bên đó thua vì đuổi dai; cả hai còn hoặc cả hai đều hết thì hòa. Khi gặp chiếu trong lúc lùi, mã có nhánh riêng, nên ví dụ tập hợp này áp dụng cho nhánh đuổi vừa mô tả.
Mã nguồn: thử bắt quân nhẹ, lọc đuổi và giao định danh. Kiến thức nền: Những điểm tranh luận về luật cờ tướng.
Giới hạn nước đi và hòa theo lực lượng
do_move() duy trì bộ đếm giới hạn. Trong mã này, bắt quân đặt lại bộ đếm và số lần chiếu của cả hai bên; chiếu vượt mười lần mỗi bên cùng nước đáp chiếu tương ứng có miễn tính. Khi rule60 >= 120, rule_judge() xét nước hợp lệ: còn nước thì hòa, hết nước thì thua, giữ kết quả quyết định nếu bước cuối đã tạo thắng thua.
Sau đó mã xét hòa theo lực lượng khi bàn không còn Tốt, dựa trên những cấu hình cụ thể của Xe, Mã, Pháo, Sĩ và Tượng. Một số cấu hình hòa trực tiếp; số khác cần kiểm tra kết thúc. Nhóm sau xét bên hiện tại đã hết nước chưa, rồi thử từng nước xem có làm đối phương hết nước không. Phạm vi áp dụng là những tổ hợp được liệt kê rõ trong mã.
Mã nguồn: cập nhật bộ đếm, giới hạn nước và hòa theo lực lượng.
Dựng lại lịch sử bằng FEN và chuỗi nước
FEN lưu quân, lượt và bộ đếm. set(fen) dựng trạng thái bắt đầu mới từ đó; chiếu, đuổi và lặp trước đó cần chuỗi nước riêng. Muốn tái hiện lỗi theo lịch sử, hãy giữ FEN ban đầu cùng các nước tiếp theo rồi dùng position … moves … dựng chuỗi.
Báo lỗi luật nên có FEN đầu, các nước, phiên bản, tùy chọn luật và phán định mong đợi. Phân tích FEN kiểm tra định dạng cùng điều kiện thế cờ; muốn chứng minh thế đó tới được từ khai cuộc cần biên bản ván hoặc phân tích tính đạt tới riêng.
Mã nguồn: khởi tạo FEN, đi lại chuỗi nước. Cú pháp: Giao thức UCI.
Perft và kiểm thử hồi quy luật
Perft dùng MoveList<LEGAL>, do_move(), undo_move() mở rộng tới độ sâu dương được chỉ định và đếm đường đi đạt tới đó. Các thứ tự khác nhau vẫn tính riêng dù đến cùng bàn cờ. Số đếm từng nước ở gốc giúp tìm nhánh sinh thiếu hoặc thừa.
Perft liệt kê nước đi; ca hồi quy riêng kiểm tra đầy đủ luật theo lịch sử:
| Kiểm thử | Câu hỏi chính |
|---|---|
| Perft | Sinh nước, lọc an toàn của Tướng, đi và hoàn tác có đúng số đếm dự kiến? |
| Hồi quy luật | Với điểm đầu và lịch sử đã cho, phán định có đúng vào thời điểm cần thiết? |
| Hồi quy tìm kiếm và thử đấu | Tìm kiếm có bất thường, thay đổi ảnh hưởng kết quả đối kháng thế nào? |
Perft không gọi rule_judge(). Chiếu dai, đuổi dai và giới hạn cần kiểm thử đầy đủ lịch sử; thay đổi sức cờ cần thống kê đối kháng. Mã nguồn: triển khai perft.
