Sokoban, hay “warehouse keeper”, là trò đố 1980 yêu cầu đẩy mọi hộp lên các vị trí mục tiêu. Dự án Sokoban AI Solver mang lại một phiên bản JavaScript thuần, chuyển đổi từ trình giải C++ gốc sang chạy trực tiếp trong trình duyệt.
Thuật toán chính là A* tối ưu, được triển khai song song để duyệt không gian trạng thái. Với các bảng 1‑14, solver trả về giải pháp tối ưu trong vài mili giây, đồng thời hiển thị số bước tối ưu (ví dụ: 12, 18, 27 bước). Các kết quả này khớp hoàn toàn với các giải pháp được chứng minh bằng C++.
Board 15, một mê cung 8 hộp, yêu cầu khám phá khoảng 49 triệu trạng thái và hơn 1 GB RAM, do đó không thể giải trực tiếp trong tab trình duyệt. Giải pháp tối ưu (184 bước) đã được tính offline trên 24 lõi CPU trong khoảng 5 giây, sau đó được nhúng dưới dạng kết quả cứng trong trang web.
Việc cung cấp một công cụ giải optimal mở nguồn này giúp các nhà nghiên cứu AI, lập trình viên game và người đam mê thuật toán tại Việt Nam có thể khám phá, thử nghiệm và cải tiến các phương pháp tìm kiếm, đồng thời học hỏi cách tối ưu hoá bộ nhớ và hiệu năng trong môi trường JavaScript.
Nguồn: Hacker News — Biên dịch & tổng hợp: danhbaai.com