Động cơ cờ vua minimax sử dụng biểu thức chính quy

Động cơ cờ vua mini-max 2 lớp

• Cờ vua và biểu thức chính quy: Tác giả đã tạo một chương trình chơi cờ chỉ sử dụng biểu thức chính quy. Chương trình này nhận bàn cờ làm đầu vào và được cấu thành từ 84,688 biểu thức chính quy để tạo các nước đi hợp lệ.

• Thiết kế CPU biểu thức chính quy: Sử dụng biểu thức chính quy để thiết kế thực thi không điều kiện và tập lệnh kiểu SIMD (single instruction, multiple data). Nhờ đó có thể viết chương trình chơi cờ.

• Cấu trúc dữ liệu: Trạng thái hiện tại của máy tính được biểu diễn bởi một chuỗi duy nhất chứa "stack" chương trình và tất cả biến. Mỗi lệnh thao tác với biến của stack hoặc thực hiện đọc/ghi trên một biến cụ thể.

• Các toán tử stack cơ bản:

  • Lệnh push: Thêm giá trị lên đỉnh stack.
  • Lệnh pop: Xóa bỏ phần tử trên cùng của stack.

• Lệnh biến <-> stack:

  • Truy vấn biến: Nạp nội dung của biến lên đỉnh stack.
  • Gán biến: Gán một giá trị cho biến; nếu biến đã tồn tại thì cập nhật, nếu chưa tồn tại thì tạo mới.

• Câu lệnh điều kiện: Dùng câu lệnh điều kiện để kiểm soát luồng chương trình. Tùy theo điều kiện, kích hoạt hoặc vô hiệu hóa một phần cụ thể của chương trình.

• Không thể dùng vòng lặp: Với biểu thức chính quy thuần túy thì không thể triển khai vòng lặp, nên mọi phép tính lặp lại phải được mở rộng trước.

• Thực thi đa luồng: Có thể chạy nhiều luồng cùng lúc bằng khả năng thay thế toàn cục của biểu thức chính quy.

• Viết động cơ cờ vua: Động cơ cờ vua được viết tương tự như các ngôn ngữ lập trình khác, hoạt động nhanh nhờ xử lý song song.

• Đánh nước theo lượt:

  • Đọc nước đi của người chơi: Đọc nước đi đầu vào và xác thực tính hợp lệ.
  • Tạo phản hồi của máy: Sinh tất cả nước đi có thể và chọn nước đi tối ưu.

• Tìm kiếm minimax: Chọn nước đi tối ưu thông qua tìm kiếm minimax độ sâu 2. Quá trình này được thực hiện hiệu quả nhờ xử lý song song.

Dự án này là một ví dụ về việc xây dựng động cơ cờ vua bằng cách sử dụng biểu thức chính quy một cách độc đáo, thể hiện sức mạnh của biểu thức chính quy và thiết kế máy tính sáng tạo.

[GN⁺]

Bình luận Hacker News

• Nhà phát triển này là người đã chứng minh rằng printf() có tính Turing hoàn chỉnh và viết một trò chơi bắn súng góc nhìn thứ nhất bằng JavaScript dung lượng 13kB

  • GitHub: Tính Turing hoàn chỉnh của printf()
  • GitHub: Trò chơi JavaScript 13kB

• Dự án này cho thấy một điểm nổi bật khi việc tính toán nhiều nước đi/các vị trí có thể thực hiện song song

  • Có thể chạy nhiều luồng cùng lúc chỉ bằng biểu thức chính quy

• Không có gì đáng nói nhiều về phần kết luận của bài blog, nhưng tôi hi vọng nhiều người hơn thử các dự án vô nghĩa kiểu này

  • Thú vị, không có áp lực về thời gian hoàn thành hay mức độ thành công, và có thể học được rất nhiều về nhiều lĩnh vực khác nhau của khoa học máy tính

• Có lỗi "di chuyển bất hợp pháp, thua cuộc" trong game cờ vua

  • Trong một ván thử nghiệm, game kết thúc dù nước đi không hề trái luật

• Người chơi cờ sử dụng đúng một biểu thức chính quy còn đáng sợ hơn người chơi cờ dùng đến 84.688 biểu thức chính quy

• Nhìn vào những dự án như vậy tôi muốn bày tỏ sự kính trọng

• Lỗi liên quan đến nước đi a-file đã được sửa

  • GitHub: Sửa lỗi

• Dự án này không chỉ là một động cơ cờ vua mà còn là một máy tính và ngôn ngữ assembly được xây dựng hoàn toàn bằng biểu thức chính quy

• Trước đây đã có một dự án cờ vua được viết bằng sed

  • Phiên bản sed sử dụng lệnh kiểm soát luồng và chỉ duyệt 1 ply

• Khi bắt đầu bằng a2a4 thì nó sẽ không chịu thua nhanh như vậy

• Việc thử một thứ gì đó mà không có mục tiêu "sản xuất" rõ ràng có thể giúp khám phá phương pháp mới và tạo ra đổi mới

  • Động cơ mất quân ở những nước đầu
  • Nhập chữ hoa sẽ bị đánh dấu là nước đi bất hợp pháp

• Đang trong nỗ lực thử đổi mới và trở nên hữu ích