Biểu diễn thế cờ và xử lý luật

Engine (động cơ cờ) không chỉ cần biết “quân đứng ở đâu”, mà còn cần biết đến lượt bên nào, quân nào đang chiếu và ván cờ đã đi đến đây thế nào. Bàn cờ, trạng thái lượt đi và lịch sử nước đi cùng hỗ trợ tìm kiếm; chỉ nhìn một bàn cờ không phải lúc nào cũng xác định được kết quả.

Bài viết được đối chiếu với official Pikafish tại commit 1c66b9b, tập trung giải thích cách các tệp cốt lõi phối hợp. Các phương pháp tìm kiếm được trình bày riêng trong Thuật toán 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 các kiểu cơ bản như quân cờ, màu quân, điểm trên bàn và nước đi.
bitboard.h	Biểu diễn một tập hợp điểm trên bàn và cung cấp các phép toán bit thường dùng.
attacks.h/.cpp	Tra phạm vi tấn công của quân theo vị trí và tình trạng bị cản.
position.h/.cpp	Lưu thế cờ hiện tại, xử lý việc đi quân, hoàn tác, tính hợp lệ và các quy định phụ thuộc lịch sử.
movegen.h/.cpp	Kết hợp các thông tin trên để sinh nước ứng viên hoặc nước hợp lệ theo nhu cầu.

Các tệp có nhiệm vụ riêng. Chẳng hạn, bảng tấn công trả lời “Mã có thể tới những điểm nào”, bộ sinh nước đi ghép điểm đầu và điểm cuối thành ứng viên, rồi kiểm tra tính hợp lệ loại những nước làm hở Tướng. Các kiểu cơ bản và Sinh và lọc nước đi là những chỗ có thể bắt đầu đọc.

Cùng một bàn cờ, vì sao lưu nhiều dạng thông tin?

Position đồng thời lưu board theo từng điểm, các bitboard chia theo loại và màu quân, cùng số lượng quân và những thông tin khác. Đây không phải lưu lặp nhiều bàn cờ, mà là chuẩn bị cách tra thuận tiện cho từng câu hỏi:

• Muốn biết “điểm này có quân gì”, tra thẳng board.
• Muốn biết “mọi Xe Đỏ ở đâu”, kết hợp bitboard màu quân và loại quân.
• Muốn biết “những quân địch nào nằm trong phạm vi tấn công”, lấy giao của hai tập hợp điểm.

Mỗi bit trong bitboard ứng với một điểm trên bàn. Pikafish dùng 128 bit để chứa 90 điểm; các hàng, cột, nửa bàn cờ và cung Tướng cũng có tập hợp tương ứng. Quy tắc tấn công xử lý vật cản của Xe và Pháo, chân Mã và mắt Tượng; bộ sinh nước đi không phải viết lại toàn bộ phép xét mỗi lần.

Về cách tra bảng tấn công và các nhánh Magic, PEXT/PDEP, xem Bitboard và bảng tấn công. Tra bảng làm cách tính nhanh hơn, không thay đổi cách quân di chuyển.

Mã nguồn: Các thành viên lưu thế cờ, Kiểu bitboard, Tập hợp điểm và phép toán bit, Tra phạm vi tấn công.

Đi quân và hoàn tác: lưu những gì cần để quay lại

Tìm kiếm liên tục “thử một nước — tính tiếp — quay về”. Nếu mỗi lần đều sao chép cả bàn cờ và tính lại mọi thông tin thì chi phí rất lớn.

Pikafish thực hiện nước đi ngay trên Position hiện tại, đồng thời tạo một StateInfo: lưu khóa hash, bộ đếm, thông tin chiếu, nước vừa đi, quân bị bắt và các dữ liệu khác; previous trỏ tới trạng thái trước. Đây không phải bản sao đầy đủ của bàn cờ: một số trường được chép từ bước trước, những trường khác được cập nhật theo thế cờ mới.

undo_move() đưa quân đã đi về chỗ cũ, khôi phục quân bị bắt rồi lùi con trỏ trạng thái về mục trước. Khóa hash, bộ đếm và các dữ liệu trong trạng thái cũ cũng được khôi phục theo. Hoàn tác phải trả lại toàn bộ trạng thái liên quan, không chỉ đưa các quân trên hình về chỗ cũ. Nếu không, lỗi sẽ ảnh hưởng sang các nhánh tìm kiếm khác về sau.

Cả các nước thực chiến đã cung cấp và những biến đi thử trong tìm kiếm đều phải giữ đúng quan hệ trước sau. Mỗi nút nhìn thấy lịch sử của chính đường đi đến nó; khi chuyển sang nhánh khác, không thể giữ lại thông tin chiếu và bộ đếm của nhánh vừa xét.

Mã nguồn: StateInfo, Cập nhật khi đi quân, Hoàn tác.

Hash Zobrist: nhận diện thế cờ nhanh, không phải lưu toàn bộ ván

Hash Zobrist chuẩn bị các số cho từng trường hợp “loại quân này ở điểm này”, rồi dùng phép XOR kết hợp những số ứng với các quân trên bàn và thông tin bên đến lượt đi thành một khóa. Khi đi một nước, chỉ cần bỏ vị trí cũ, thêm vị trí mới, xử lý bắt quân và đổi bên, không phải quét lại toàn bàn.

Việc cập nhật nhanh được là nhờ XOR cùng một số hai lần sẽ triệt tiêu nhau: có thể bỏ trực tiếp phần ứng với vị trí cũ của quân, không cần suy ngược toàn bàn từ kết quả.

Khóa cơ bản hiện tại st->key có 64 bit, chủ yếu tương ứng với bố trí quân và bên đến lượt đi. Nó không phải mã số tuyệt đối không thể trùng, cũng không chứa mọi nước đã đi trước đó. key() dùng cho bộ nhớ đệm còn điều chỉnh theo nhóm của bộ đếm luật 60 nước và thông tin lọc lặp lại, nhưng vẫn không thể thay thế lịch sử đầy đủ.

Vì vậy, “hash giống nhau” không có nghĩa “kết quả theo luật luôn giống nhau bất kể lịch sử”. Muốn thực sự xét chiếu liên tục, đuổi quân liên tục và các trường hợp tương tự, vẫn cần kiểm tra dọc chuỗi trạng thái. Xem Bảng chuyển vị để biết cách dùng lại bộ nhớ đệm.

Mã nguồn: Chuẩn bị bảng số Zobrist, Tạo khóa cơ bản, Cập nhật tăng dần, Điều chỉnh khóa bộ nhớ đệm.

Đi được nước này và đi rồi bị xử thế nào là hai việc khác nhau

Ứng viên giả hợp lệ đã đáp ứng cách di chuyển cơ bản của quân. Trên giả định đó, legal() chủ yếu kiểm tra Tướng bên mình có an toàn sau khi đi không, kể cả việc hai Tướng đối mặt. Nó không xét lại mọi quy định phụ thuộc lịch sử.

rule_judge() xử lý thế cờ lặp lại, chiếu liên tục, đuổi quân liên tục, luật 60 nước và các trường hợp hòa do lực lượng quân cụ thể. Mã dùng bộ lọc nhanh trước để giảm kiểm tra không liên quan, chỉ lần theo lịch sử và xét đuổi quân khi thực sự cần. Một số trường hợp lặp lại trong tìm kiếm chỉ cung cấp cận điểm, không trả ngay kết quả thắng thua cuối cùng.

Vì thế, không thể gộp “nước này không làm hở Tướng”, “biến này dẫn đến thua theo luật” và “biến này có điểm tìm kiếm rất kém” thành một chuyện. Lặp lại cũng không thể hiểu đơn giản là luôn hòa. Xem giải thích chi tiết hơn ở Luật cờ và tìm kiếm.

Mã nguồn: Nhiệm vụ của legal, Phán định theo luật.

FEN ghi thế cờ, không khôi phục cả lịch sử

FEN có thể ghi vị trí quân, bên đến lượt đi và các bộ đếm, nhưng không ghi từng nước trước đó ai chiếu, ai đuổi quân hay thế cờ đã lặp lại thế nào. Xuất thế cờ hiện tại thành FEN rồi chỉ đọc lại FEN đó không đồng nghĩa với khôi phục lịch sử nước đi ban đầu. set(fen) hiện tại khởi tạo lại thế cờ và trạng thái bắt đầu, rồi tính các thông tin liên quan từ bàn cờ.

Khi cần tái hiện vấn đề phụ thuộc lịch sử, nên giữ một điểm xuất phát đã biết cùng chuỗi nước đi sau đó. Lệnh UCI position … moves … chính là đặt điểm xuất phát trước, rồi thực hiện lần lượt các nước để dựng chuỗi trạng thái tương ứng. Nó cũng không thể bù lại phần lịch sử trước điểm xuất phát mà bạn chưa cung cấp.

Khi báo lỗi luật cờ cho nhà phát triển, tốt nhất nên cung cấp cả FEN ban đầu, các nước tiếp theo, phiên bản engine và phán định mong đợi. Chỉ gửi bàn cờ cuối thường không đủ để tái hiện vấn đề. Việc kiểm tra định dạng và thế cờ khi đọc FEN cũng không chứng minh rằng chắc chắn có một chuỗi nước hợp lệ từ khai cuộc dẫn tới thế cờ đó.

Mã nguồn: Khởi tạo từ FEN, Đi lại chuỗi nước từ điểm xuất phát; cú pháp lệnh nằm ở Giao thức UCI.

perft kiểm tra được gì và không kiểm tra được gì?

perft mở rộng theo các nước hợp lệ đến độ sâu dương được chỉ định, rồi đếm số chuỗi nước đi đạt tới độ sâu đó. Dù các thứ tự khác nhau dẫn tới cùng bàn cờ, chúng vẫn được tính riêng. perft không chọn nước tốt nhất, không dựa vào điểm NNUE và không dùng cắt tỉa tìm kiếm.

perft.h hiện tại dùng MoveList<LEGAL>, do_move() và undo_move(). Ở nút gốc, nó còn xuất số đếm riêng cho từng nước, giúp tìm nhánh nào sinh thiếu hoặc thừa nước.

Nó không gọi rule_judge(), nên không thể từ đó tuyên bố đã kiểm tra toàn bộ luật cờ tướng. Các phán định theo lịch sử như chiếu liên tục, đuổi quân liên tục và luật 60 nước cần kiểm thử riêng. perft cũng không xác minh nước tốt nhất, điểm số hay tìm kiếm có chọn lọc.

Kiểm thử	Câu hỏi chính được trả lời
perft	Sinh nước đi, lọc an toàn của Tướng, thực hiện và hoàn tác nước đi có cho số đếm đúng như dự kiến không?
Ca kiểm thử hồi quy về luật cờ	Với điểm xuất phát và lịch sử đã cho, mã có đưa ra phán định mong đợi vào đúng thời điểm không?
Kiểm thử hồi quy tìm kiếm và thử đấu	Hành vi tìm kiếm có bất thường không, thay đổi có cải thiện kết quả thực tế không?

Số đếm khớp là một kiểm tra có giá trị, nhưng không phải bằng chứng rằng “mọi chức năng của engine đều đúng”.

Mã nguồn: Cách triển khai perft.