Trình giải Sokoban bằng AI: Khi thuật toán A* tối ưu hóa từng bước đi

Sokoban, trò chơi xếp kho kinh điển từ những năm 1980, vừa có một bản nâng cấp thú vị dành cho cộng đồng yêu thích thuật toán. Một nhà phát triển đã công bố trình giải câu đố này bằng AI, sử dụng thuật toán A* cải tiến để tìm ra lời giải tối ưu — không chỉ đơn thuần là hoàn thành màn chơi, mà còn với số bước di chuyển ít nhất tuyệt đối.

Dự án này không chỉ là một trò chơi giải trí, mà còn là một minh chứng sinh động cho thấy sức mạnh của các kỹ thuật tối ưu hóa trong khoa học máy tính. Trình giải được viết bằng JavaScript thuần, chạy trực tiếp trong trình duyệt, giúp người chơi có thể trải nghiệm sức mạnh của AI ngay lập tức mà không cần cài đặt gì thêm.

Trò chơi Sokoban và luật chơi

Trong Sokoban, người chơi điều khiển một nhân vật ("người giữ kho") trên một lưới ô vuông, với nhiệm vụ đẩy tất cả các hộp đến vị trí mục tiêu. Điểm đặc biệt của phiên bản này là nhân vật cũng phải kết thúc trên một ô mục tiêu — vì vậy mỗi bàn chơi có số mục tiêu nhiều hơn số hộp là một.

Luật chơi khá đơn giản:

• Người chơi di chuyển lên, xuống, trái, phải mỗi lần một bước
• Không thể đi xuyên qua tường hoặc hộp
• Có thể đẩy một hộp nếu ô phía sau hộp đó là ô trống hoặc ô mục tiêu
• Mỗi bước chỉ được đẩy một hộp, và hộp có thể bị đẩy ra khỏi ô mục tiêu nếu cần

Mục tiêu cuối cùng là đưa mọi hộp và nhân vật đến đúng vị trí mục tiêu với số bước di chuyển tối thiểu.

Thuật toán A* trong giải quyết vấn đề Sokoban

Phần quan trọng nhất của dự án này nằm ở cách thuật toán hoạt động. Sokoban về bản chất là một bài toán tìm kiếm đường đi trên đồ thị trạng thái, và phương pháp ngây thơ (explore từng bước di chuyển) sẽ "nổ tung" khi gặp các bàn có mật độ hộp dày đặc.

Cách tiếp cận của tác giả là sử dụng một phiên bản cải tiến của thuật toán tìm kiếm A*:

1. Macro-push A* với chi phí tối ưu

• Mỗi cạnh trong không gian tìm kiếm là toàn bộ một cú đẩy hộp, không phải từng bước đi của nhân vật
• Chi phí được tính bằng: (quãng đường ngắn nhất của nhân vật đến vị trí đẩy) + 1
• Tổng chi phí này chính xác bằng số bước di chuyển thực tế tối thiểu

2. Nén trạng thái thành bitmask

• Các hộp được đóng gói vào một số nguyên 32-bit dựa trên các ô "sống" (live cells) của bàn chơi
• Vị trí nhân vật được lưu trong một số nguyên riêng
• Toàn bộ trạng thái chỉ chiếm ~8 byte, thay vì ~1 KB như cách lưu trữ thông thường
• Kết quả: hàng triệu trạng thái có thể được lưu trong vài chục MB bộ nhớ

3. Hàng đợi bucket + bảng băm mở

• Hàng đợi ưu tiên được triển khai dạng dial bucket queue, có độ phức tạp tuyến tính theo chi phí
• Tập hợp các trạng thái đã thăm được lưu trong một mảng băm phẳng, không cấp phát bộ nhớ động
• Thiết kế này rất thân thiện với bộ nhớ cache của CPU

4. Cắt tỉa các trạng thái không khả thi

• Sử dụng bảng các ô chết (dead squares) tính toán bằng cách duyệt ngược từ mục tiêu
• Kết hợp với kiểm tra đóng băng (freeze check) để loại bỏ các vị trí chắc chắn không thể giải được
• Một hàm cận dưới (lower bound) dựa trên khoảng cách đẩy có nhận biết tường giúp thuật toán A* đảm bảo tính tối ưu tuyệt đối

Kết quả ấn tượng và giới hạn của trình duyệt

Với cách tiếp cận này, các màn chơi từ 1 đến 14 được giải trực tiếp trong trình duyệt với tốc độ vài mili giây và đạt được số bước tối ưu tuyệt đối — con số được hiển thị trên giao diện chính là kết quả mà thuật toán trả về.

Tuy nhiên, màn chơi thứ 15 lại là một câu chuyện khác. Với 8 hộp và mê cung phức tạp, việc tìm kiếm tối ưu đòi hỏi phải khám phá ~49 triệu trạng thái và cần hơn 1 GB bộ nhớ — quá nhiều để chạy trong một tab trình duyệt thông thường. Giải pháp của tác giả là tính toán trước lời giải tối ưu (184 bước) bằng phiên bản C++ song song của cùng thuật toán, chạy trên 24 lõi CPU trong khoảng 5 giây, sau đó phát lại lời giải được lưu sẵn trong trang web.

Giá trị mã nguồn mở đối với cộng đồng

Điểm đáng chú ý nhất của dự án này là nhà phát triển đã công bố toàn bộ mã nguồn, từ phiên bản JavaScript chạy trong trình duyệt lẫn phiên bản C++ gốc dùng để tính toán nặng. Điều này tạo ra một nguồn tài liệu học tập quý giá cho những ai quan tâm đến:

• Tối ưu hóa thuật toán tìm kiếm trong không gian trạng thái lớn
• Kỹ thuật nén dữ liệu để giảm bộ nhớ
• Thiết kế cấu trúc dữ liệu thân thiện với bộ nhớ cache
• Cắt tỉa không gian tìm kiếm dựa trên phân tích tĩnh

Với cộng đồng lập trình viên tại Việt Nam, đây là một ví dụ tuyệt vời minh họa cách một bài toán lý thuyết (A*) có thể được áp dụng vào thực tế với những cải tiến thông minh, vượt xa cách triển khai cơ bản trong sách giáo khoa.

Kết luận

Dự án trình giải Sokoban này không chỉ là một công cụ giải trí — nó là một bài học thực hành sâu sắc về thuật toán và tối ưu hóa. Nó cho thấy rằng với những kỹ thuật hợp lý (nén trạng thái, hàng đợi hiệu quả, cắt tỉa thông minh), một vấn đề tưởng như "không thể giải nổi" có thể được xử lý trong thời gian thực ngay trên trình duyệt. Đối với những ai đang tìm hiểu về trí tuệ nhân tạo, tìm kiếm heuristic, hay đơn giản là muốn thử thách bản thân với những câu đố hóc búa, dự án này chắc chắn đáng để khám phá và học hỏi.