+ Phát triển tư duy logic va chiến lược: Giải quyết bài toán tìm kiếm trong Sokoban giúp người chơi phát triển khả năng suy luận logic và xây dựng chiến lược hiệu quả * Cải thiện kỹ năn
CƠ SỞ LÝ THUYÊTT c©vvvvvcrrttttttrtsrrred 4
Giới thiệu về trò chơi Sokoban - + - 5 5 23121 S121 22 E31 1 xe 4
Trò chơi Sokoban, có nguồn gốc từ tiếng Nhật với nghĩa là “người kho hàng”, là một trò chơi giải đố logic nổi tiếng toàn cầu Được phát triển bởi Hiroyuki Imabayashi và ra mắt lần đầu vào năm 1982, Sokoban đã trở thành một hiện tượng văn hóa và là nguồn cảm hứng cho nhiều trò chơi giải đố khác.
Hình 2.1: Ví dụ về trò chơi Sokoban
Trong trò chơi Sokoban, người chơi điều khiển một nhân vật trong kho hàng, với nhiệm vụ đẩy các thùng hàng đến vị trí chỉ định Điểm đặc biệt là người chơi chỉ có thể đẩy một thùng tại một thời điểm và không thể kéo chúng Cơ chế này yêu cầu người chơi phải lên kế hoạch cẩn thận để hoàn thành nhiệm vụ.
Sokoban là một trò chơi yêu cầu người chơi tính toán cẩn thận từng động thái để tránh kẹt hàng trong góc và tạo ra tình huống không thể giải quyết Độ khó của trò chơi tăng dần qua mỗi cấp độ, với các bản đồ ngày càng phức tạp, đòi hỏi tư duy logic và kỹ năng giải quyết vấn đề Ngoài việc mang lại sự giải trí, Sokoban còn là công cụ giáo dục hữu ích, giúp cải thiện khả năng tư duy không gian và lập kế hoạch chiến lược của người chơi.
Sokoban đã có ảnh hưởng lớn đến thế giới game giải đố, với nhiều phiên bản khác nhau từ ứng dụng di động đến các trò chơi trực tuyến Nguyên tắc của Sokoban cũng được áp dụng trong trí tuệ nhân tạo, nơi các thuật toán tự động giải các cấp độ, góp phần vào nghiên cứu về tìm kiếm không gian trạng thái và lập kế hoạch.
Giới thiệu về thuật toán BES trong tìm kiếm - ©2525 55552 x+5552 5
2.2.1 Thuật toán BES Breadth-first search là một trong những thuật toán của tìm kiếm mù(ìm kiếm không có thông tin) Tìm kiếm không có thông tin, còn gọi là tìm kiếm mù (blind, uninformed search) là phương pháp duyệt không gian trạng thái chỉ sử dụng các thông tin theo phát biểu của bài toán tìm kiếm tổng quát trong quá trình tìm kiếm, ngoài ra không sử dụng thêm thông tin nào khác Tìm kiếm không có thông tin bao gồm một số thuật toán khác nhau Điểm khác nhau căn bản của các thuật toán là ở thứ tự mở rộng các nút biên
BES là một phương pháp tìm kiếm theo chiều rộng, trong đó nguyên tắc là lựa chọn các nút biên nông nhất gần với nút gốc để mở rộng Thuật toán này bắt đầu từ các nút có độ sâu nông nhất (nút 0) và tiếp tục mở rộng đến các nút có độ sâu tăng dần, theo thứ tự từ nông đến sâu.
CHƯƠNG 2 CƠ SỞ LÝ THUYÊẾT Độ sâu: 0
Hình 2.2: Ví dụ về thuật toán BES
Thuật toán tìm kiếm theo chiều rộng (BFS) hoạt động dựa trên nguyên tắc hàng đợi FIFO (first in first out), cho phép mở rộng các nút được thêm vào sớm hơn trong danh sách nút biên O Khi mở rộng một nút, cần sử dụng con trỏ ngược để ghi lại nút cha, giúp tìm lại đường đi về trạng thái xuất phát khi tìm được trạng thái đích Mỗi nút trong thuật toán được biểu diễn bằng một cấu trúc dữ liệu có chứa con trỏ ngược trỏ tới nút cha Thuật toán được thực hiện với các tham số: Q (tập trạng thái), S (trạng thái bắt đầu), G (trạng thái đích), và P (hành động) Đầu vào của thuật toán là bài toán tìm kiếm, trong khi đầu ra là trạng thái đích.
Khdi tao: O
