Engine cờ vua minimax 2-ply được triển khai bằng 84.688 biểu thức chính quy

• Regex Chess là một engine 2-ply minimax chỉ bằng cách chạy tuần tự 84.688 phép thay thế biểu thức chính quy để chọn một nước đi hợp lệ và “không đến mức quá tệ” trên bàn cờ
• Trạng thái được đặt chung trong một chuỗi duy nhất với stack và biến, và các lệnh như push, pop, tra cứu/gán biến được xử lý bằng các phép thay thế biểu thức chính quy
• Phân nhánh điều kiện được mô phỏng bằng cách đổi marker %% biểu thị trạng thái đang hoạt động, và nhờ thay thế toàn cục nên có thể thực thi song song kiểu SIMD để xử lý nhiều trạng thái cùng lúc
• Engine tạo mọi nước đi hợp lệ dưới dạng các trạng thái song song và đánh giá cả phản hồi của đối thủ, nhưng không thực hiện tìm kiếm depth-3 để kiểm chứng hoàn toàn tính hợp lệ của cả phản hồi đối thủ
• Ban đầu, mỗi nước phản hồi mất khoảng 30 phút, nhưng sau khi xóa biến trung gian, tối ưu khớp mẫu, thêm lệnh chuyên dụng và song song hóa, bản triển khai cuối cùng giảm xuống còn 1–10 giây tùy vị trí

---

Cấu trúc cơ bản của Regex Chess

• Regex Chess cấu thành toàn bộ engine cờ vua bằng một danh sách 84.688 biểu thức chính quy
• Cấu trúc thực thi khá đơn giản
  • Duyệt danh sách biểu thức chính quy theo thứ tự
  • Áp dụng từng mẫu và chuỗi thay thế lên chuỗi trạng thái bàn cờ hiện tại
  • Hiển thị trạng thái cuối cùng ra màn hình
• Đầu vào không phải PGN mà là định dạng tọa độ nối ô xuất phát và ô đích như e2e4
• Mã dự án được công khai trên GitHub

CPU bằng biểu thức chính quy

• Thay vì viết trực tiếp luật cờ vua bằng biểu thức chính quy, tác giả trước tiên tạo ra một máy tính nhỏ hoạt động bằng biểu thức chính quy
• Máy tính này dùng một tập lệnh có thực thi điều kiện không phân nhánh, thực thi một lệnh trên nhiều dữ liệu, cùng thao tác stack và biến
• Trạng thái hiện tại được biểu diễn bằng một chuỗi duy nhất
  • %% biểu thị điểm bắt đầu của trạng thái thực thi đang hoạt động
  • Bên dưới #stack: là các phần tử stack được xếp chồng
  • Biến được lưu ở dạng #tên_biến: giá_trị

• Thao tác stack và biến

  • push tìm header %%\n#stack:\n rồi chèn giá trị vào ngay bên dưới để đặt lên đỉnh stack
  • pop xóa một dòng ngay dưới #stack: để loại bỏ giá trị ở đỉnh stack
  • Tra cứu biến tìm #tên_biến: trong chuỗi trạng thái, sao chép giá trị rồi thêm nó lên đỉnh stack
  • Gán biến xử lý cả trường hợp biến đã tồn tại lẫn chưa tồn tại
    • Nếu đã tồn tại thì thay giá trị cũ bằng giá trị đang có trên stack
    • Nếu chưa có thì thêm mới dòng biến
  • Các marker tạm như dấu backtick được dùng để ngăn cùng một lệnh bị áp dụng lại sai thứ tự

Thực thi điều kiện không phân nhánh và giới hạn vòng lặp

• Thực thi có điều kiện được triển khai bằng cond(tag) và reactivate(tag)
• Nếu giá trị ở đỉnh stack là False, marker hoạt động %% sẽ được đổi thành dạng %tag, khiến các lệnh sau đó không còn áp dụng lên trạng thái đó
• Về sau, reactivate(tag) đổi %tag trở lại thành %% để kích hoạt lại trạng thái tương ứng
• Cách này mô phỏng thực thi có điều kiện mà không cần phân nhánh tường minh
• Vì chương trình là một danh sách tuần tự các biểu thức chính quy nên không thể chạy vòng lặp trực tiếp
  • Nó không thể thực hiện tính toán đầy đủ Turing
  • Tuy vậy, các bài toán có giới hạn như tính nước đi tiếp theo trong cờ vua vẫn có thể được xử lý bằng cách trải phẳng vòng lặp

Thực thi song song bằng thay thế toàn cục

• Do phép thay thế biểu thức chính quy được áp dụng toàn cục trên toàn bộ chuỗi, nếu đặt nhiều trạng thái thực thi %% trong cùng một chuỗi trạng thái thì cùng một lệnh sẽ được áp dụng đồng thời lên nhiều trạng thái
• Ví dụ, nếu hai stack mỗi cái chứa hai số nguyên, khi chạy binary_add() thì hai phép cộng sẽ được thực hiện cùng lúc
• fork_inactive(tag) sao chép trạng thái đang hoạt động hiện tại và đặt bản sao vào trạng thái gắn tag không hoạt động
• fork_bool(variable) tách một trạng thái thành hai trạng thái, một mang giá trị True và một mang giá trị False
• Cấu trúc này được dùng để đánh giá đồng thời nhiều trạng thái bàn cờ khả dĩ thay vì lặp xử lý từng trạng thái một

Macro assembler và symbolic execution

• Engine không được viết hoàn toàn thủ công bằng biểu thức chính quy, mà dùng một macro assembler để chuyển chương trình kiểu Python thành các chuỗi lệnh nhỏ
• Mã kiểu Python như fib() được chuyển thành danh sách lệnh như push, lookup, binary_add, assign_pop
• Thay vì parser và code generation truyền thống, hệ thống dùng symbolic execution
  • Đối tượng biến không phải dictionary thật mà là đối tượng đặc biệt ghi lại các phép toán đã thực hiện
  • a = b + 1 được ghi thành lookup('b'), push(1), binary_add(), assign_pop('a')
• Câu lệnh if ghi lại cả nhánh điều kiện đúng lẫn sai rồi gộp chúng lại
  • Khi gặp rẽ nhánh điều kiện, hệ thống tạo hai đường đi trong cây gọi hàm
  • Qua nhiều lần truy vết, nó chọn nhánh ít được thăm hơn để hoàn thiện cả hai phía
  • Điểm hợp nhất được chuyển thành lệnh reactivate

Cách sinh nước đi cờ vua

• Bản thân việc viết engine cờ vua khá giống với engine trong ngôn ngữ thông thường, nhưng điểm mấu chốt là xử lý nhiều trạng thái song song
• Việc sinh nước đi của tốt gồm luồng như sau
  • Tìm mọi vị trí tốt trắng
  • Tạo trạng thái song song cho từng quân tốt
  • Tạm dừng trạng thái chính ban đầu và kích hoạt các trạng thái theo từng quân tốt
  • Kiểm tra đồng thời trên tất cả trạng thái quân tốt các ứng viên đi thẳng một ô, hai ô và bắt chéo
  • Gộp lại danh sách các nước ứng viên của từng trạng thái
• Ví dụ minh họa xử lý trực tiếp chuỗi FEN, nhưng trong triển khai thực tế bàn cờ được mở rộng thành các biến theo 64 ô để đọc và ghi
• Các quân trượt như tượng, xe, hậu cùng nhập thành và bắt tốt qua đường cũng được triển khai riêng
• Chi tiết triển khai có trong chess_engine.py

Xử lý một lượt và kiểm chứng nước đi

• Một lượt diễn ra theo thứ tự: đọc nước đi người chơi nhập, kiểm tra tính hợp lệ của nước đó, rồi sinh nước đáp trả của máy
• from_pretty_utf8_to_fen() chuyển hiển thị bàn cờ Unicode thành ký pháp FEN và trích ra ô đi và ô đến từ đầu vào
• Tính hợp lệ của nước người chơi không được kiểm tra bằng mã luật riêng, mà bằng cách sinh tất cả các bàn cờ hợp lệ tiếp theo rồi so sánh
  • make_move tạo bàn cờ sau khi áp dụng nước nhập
  • compute_legal_boards sinh mọi bàn cờ hợp lệ từ vị trí hiện tại
  • fork_on_list tách từng bàn cờ thành các trạng thái song song
  • Những trạng thái khác với kết quả áp dụng nước nhập sẽ bị loại bằng destroy_active_thread()
• Nếu không có nước hợp lệ, toàn bộ đầu ra sẽ bị thay bằng chuỗi hardcode "Illegal Move"
• Nước đáp trả của máy được tạo bằng cách sinh các bàn cờ phản hồi khả dĩ của quân đen và điểm số tương ứng, sau đó chỉ giữ lại bàn cờ có điểm tốt nhất bằng keep_best_scoring_board(score)

2-ply minimax và sự đơn giản hóa có chủ đích

• compute_and_score_legal_boards đóng vai trò cốt lõi của tìm kiếm minimax depth-2
• Trước hết engine sinh các nước ứng viên mà máy có thể đi, rồi sinh tiếp các nước đáp của đối thủ để kiểm tra xem vua có thể bị bắt hay không
• Vì phải kiểm chứng trạng thái chiếu nên việc sinh cả nước đáp của đối thủ đã tạo nên cấu trúc tìm kiếm depth-2
• Mỗi vị trí ứng viên được chấm điểm theo phản hồi tốt nhất của đối thủ
• Tuy nhiên đây không phải minimax depth-2 hoàn chỉnh
  • Engine không kiểm tra đến cùng xem nước đáp của đối thủ có phải là nước bất hợp lệ vì tự đặt vua mình vào thế bị chiếu hay không
  • Muốn xử lý đầy đủ việc này sẽ cần tìm kiếm depth-3 và chi phí tăng mạnh
• Bản thân các nước đáp mà máy sinh ra không phải là nước bất hợp lệ, nhưng trong một số trường hợp engine có thể xét đến những nước mà đối thủ thực tế không thể đi, từ đó chọn phản hồi yếu hơn thực tế

Tối ưu hiệu năng

• Bản triển khai ban đầu mất khoảng 30 phút để sinh nước đáp cho một nước đi của người chơi
• Bản cuối cùng trên máy của tác giả chỉ mất khoảng 1–10 giây tùy vị trí
• Mức tăng tốc khoảng 100 lần là kết quả của nhiều tối ưu hóa

• Xóa biến trung gian

  • Tra cứu biến phải tìm giá trị trong toàn bộ chuỗi trạng thái nên tốn chi phí O(n)
  • Khi fork trạng thái thực thi, các biến cũng bị sao chép theo, làm tăng mức dùng bộ nhớ
  • Việc chủ động xóa các biến không còn cần thiết và tái sử dụng tên biến giúp giảm thời gian lẫn bộ nhớ
  • Trạng thái nội bộ khi đánh giá một nước đi giảm từ 10GB xuống khoảng 300MB trước và sau tối ưu

• Tối ưu khớp biểu thức chính quy

  • Chỉ cần thêm ký tự xuống dòng ở đầu vào biểu thức chính quy dọn dẹp của lệnh điều kiện đã khiến hiệu quả của lệnh đó tăng khoảng 2 lần
  • Do trong trạng thái có rất nhiều chuỗi True và False, mẫu cần được giới hạn để chỉ nhanh chóng tìm đúng giá trị ở đỉnh stack
  • Những khác biệt nhỏ trong mẫu để giảm các ứng viên khớp không cần thiết có ảnh hưởng đến tổng thời gian chạy

• Lệnh chuyên dụng và song song hóa

  • Các đoạn chậm như vòng lặp tìm vị trí quân cờ được gộp thành một lệnh biểu thức chính quy chuyên dụng thay vì ghép từ nhiều lệnh sẵn có
  • Khi sinh nước đi của xe, hệ thống không kiểm tra từng hướng tuần tự mà tạo nhiều trạng thái song song để xử lý một lượt
  • Việc đánh giá vị trí cũng tạo các trạng thái song song cho từng bàn cờ ứng viên để xử lý đồng thời
  • Song song hóa đặc biệt hiệu quả với các tác vụ lặp cùng một phép toán trên nhiều trạng thái, như tính giá trị quân cờ

Các phần triển khai bổ sung có trong mã nguồn

• Mã nguồn còn chứa những thành phần triển khai không được đi sâu trong bài viết
  • Sinh song song nước đi cho các quân trượt như tượng, xe, hậu
  • Quy trình “ô này có đang bị tấn công không” để phục vụ nhập thành
  • Chuyển đổi giữa bàn cờ FEN và biểu diễn bằng biến theo từng ô
  • Phát hiện quyền nhập thành bằng cách theo dõi vị trí vua và xe
  • Phát hiện và theo dõi bắt tốt qua đường
  • Khoảng 2000 dòng test để kiểm chứng độ chính xác của engine qua hàng nghìn ván
• Bài viết kết lại rằng những dự án vô mục đích như thế này đã giúp tác giả học thêm nhiều chủ đề khoa học máy tính ngoài lĩnh vực chuyên môn của mình
• Các dự án liên quan cũng được nhắc tới, gồm printf-tac-toe chơi cờ caro bằng printf của C và 13kB JavaScript Doom clone

[GN⁺]

Các ý kiến trên Hacker News

• Đây là công trình của chính người đã chứng minh printf() là Turing-complete, và đã làm một game bắn súng góc nhìn thứ nhất bằng 13kB JavaScript
  https://github.com/HexHive/printbf
  https://github.com/carlini/js13k2019-yet-another-doom-clone

  • Khi đọc câu “chứng minh printf() là Turing-complete, và làm một game bắn súng góc nhìn thứ nhất …”, thật lòng tôi cứ tưởng câu đó sẽ kết lại theo kiểu game bắn súng kia cũng được triển khai bằng printf
  • Bài viết về quá trình làm Doom có rất nhiều chi tiết nên khá thú vị: https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
    Thời hạn hoàn thành cuộc thi là một tháng, nhưng có vẻ có thể tái sử dụng mã cũ
    Bản thân việc làm hẳn khá vui, và tôi hơi buồn vì giờ do gia đình và công việc, chắc chắn tôi không thể có một tháng thời gian rảnh để dành cho những thứ như thế này
  • Nghe nói “game bắn súng góc nhìn thứ nhất bằng 13kB JavaScript” nên tôi đã kỳ vọng, nhưng khi biết phần render đồ họa dùng WebGL thì hơi thất vọng

• Đến đoạn này, tôi cảm thấy công trình này đã vượt khỏi mức vui điên rồ và trở nên hoàn toàn phi thường. Việc tính toán nhiều vị trí khả dĩ đều diễn ra song song, bằng cách chạy regex trên tập trạng thái/biến đang phình ra, tức là trên các luồng
  “Giờ là phần tôi thích nhất trong ngôn ngữ mà chúng ta đã tạo ra. Nhờ phép màu của regex, và nhờ việc ta thực hiện thay thế toàn cục trên toàn bộ chuỗi, chúng ta có thể chạy nhiều luồng cùng lúc!”
  Kết luận cũng hay. “Bạn mong chờ kết luận gì cho một bài blog như thế này? Thực ra chẳng có kết luận nào cả. Tôi chỉ mong có nhiều người làm những việc hoàn toàn vô dụng như thế này hơn. Nó thật sự rất vui, không ai quan tâm bạn mất bao lâu để hoàn thành, cũng chẳng ai quan tâm nó có chạy hay không; thêm nữa, bạn sẽ học được nhiều hơn mức mình từng muốn về nhiều mảng khoa học máy tính ngoài lĩnh vực của mình.”
  Đúng là một thái độ tuyệt vời

  • Khi gạt bỏ hết những mối bận tâm khác, tôi tự hỏi liệu mình có thể làm được thứ như thế này không
    Điều rút ra ở đây là sức mạnh của việc ngồi xuống và tập trung tinh thần vào một thứ thì không biết có thể đi xa đến đâu; đồng thời tác giả rõ ràng là một người rất tài năng, lành nghề và sáng tạo

• Có vẻ có lỗi ở đâu đó. Ván dưới đây không phải nước đi bất hợp pháp, vậy mà lại kết thúc bằng “Illegal move, you lose”

  1. e2e4, e7e5
  2. d2d4, e5d4
  3. d1d4, a7a5
  4. g1f3, b7b5
  5. b1c3, a5a4
  6. c3b5, a4a3
  7. b5a3, a8a3
  8. b2a3 -->
     Illegal Move
     You Lose.
     Game over.
     FEN của ván trên:
     1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
  • Nếu đi a2a3 ngay nước đầu, hoặc đi a2a3 ở nước thứ hai sau e2e4, cũng bị báo là nước đi bất hợp pháp
    Nhưng cả hai đều là nước hợp lệ, nên đúng là bug
  • Chỉ cần đi a2a4 ở nước đầu cũng xảy ra chuyện tương tự

• Tôi không sợ người chơi cờ bằng 84.688 regex, nhưng tôi sợ người chơi cờ bằng một regex duy nhất

  • Nếu có một heuristic chung để tuyến tính hóa các regex được áp dụng tuần tự, tức là cách gộp hai regex bất kỳ thành một, thì có vẻ có thể áp dụng vào đây
    Cứu tôi với, tôi đang bị nerd-sniping
    Vấn đề tiềm tàng hiện lên ngay trong đầu là backreference
    Regex sẽ trở nên rất dài, nhưng thực chất là đang mã hóa một chess engine…

• Nhìn những thứ như thế này khiến tôi muốn ngả mũ và trang trọng cảm ơn những anh hùng thực sự của nhân loại

• Bug di chuyển trên cột a đã được sửa: https://github.com/carlini/regex-chess/issues/1

• Trường hợp trước đây: cờ viết bằng sed https://news.ycombinator.com/item?id=6261314
  Tất nhiên, phiên bản sed dùng lệnh điều khiển luồng của sed, và có lẽ chỉ tìm trước 1 nước, nên ở điểm đó khá khác với phiên bản này

• Đây không chỉ là một chess engine, mà còn là việc tạo ra máy tính và hợp ngữ chỉ bằng regex

• Bình thường bắt đầu bằng a2a4 thì đâu thua nhanh thế này!

  • Tôi cũng gặp một bug tương tự ở cột a. Chuỗi nước đi là e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

• Cái này cũng đáng để so sánh: https://codegolf.stackexchange.com/q/3503/32575

  • Mọi quy tắc kiểm tra tính chia hết tất yếu đều là ngôn ngữ chính quy, nên cũng không quá đáng ngạc nhiên. Nếu phức tạp hơn thì sẽ không còn là “quy tắc” mà con người có thể thực thi được nữa