🌟 Sokoban Search Algorithms

• Author: Quan Hoang Ngoc
• Course: Assignment 1
• Semester: HK2, 2024

---

📖 What Is It?

This project explores the implementation of search algorithms—Depth-First Search (DFS), Breadth-First Search (BFS), and Uniform Cost Search (UCS)—to solve the Sokoban game, which is modeled as a search problem. The main aim is to investigate their effectiveness through detailed experimentation and statistical analysis.

---

🎯 Why Do We Do It?

• Educational Purpose: To gain hands-on experience with classic search algorithms and their applications in solving real-world problems, specifically within the context of the Sokoban game.
• Comparative Analysis: To evaluate the strengths and weaknesses of DFS, BFS, and UCS in tackling Sokoban, with the goal of determining the most efficient algorithm.

---

👥 Who Is the User?

This project is ideal for:

• Students: Those studying algorithms and AI who want a practical understanding of search techniques.
• Game Developers: Individuals looking to implement AI solutions in gaming.
• Hobbyists: Anyone interested in the intersection of algorithms and puzzles.

🎥 Show-off

• Watch the video demonstration: Application DFS BFS UCS for Sokoban Game - Modeling Search Problem - [AI course - CS106 - UIT]

---

📁 Repo Structure

• RESOURCES: Contains project guidelines, documents, and reports.
• SOURCE CODE: Includes the implementation code.
• Backup: OneDrive Backup of Project Files

---

🚀 How Did We Do It?

• Implementation: Developed the DFS, BFS, and UCS algorithms in Python, including comprehensive comments and documentation.
• Libraries Used: Integrated pygame and pyautogui for interactive gameplay.
• Experimental Framework: Conducted extensive experimentation and statistical analysis using Kaggle Colab P100 with 29GB RAM for optimal performance evaluation.
• Presentation: Compiled findings into a detailed project report outlining experiment goals and results.

---

⚙️ How to Install This Project

1. Download the source code from the repository.
2. Run Sokoban.py to play the game.
3. Modify the configurations in constants.py for customized gameplay.
4. The project follows the MVC architecture: with the View defined in Sokoban.py and the Controller in Game.py.
5. Alter algorithms in solver.py under the auto_move() function to experiment with different approaches.

🔧 Requirements

• Python >= 3.0
• pygame
• pyautogui

---

🏆 What Did You Learn?

• Enhanced understanding of various search algorithms and their applicability to complex problems.
• Insights into performance trade-offs between different algorithms (DFS, BFS, UCS) when solving puzzles.
• Gained practical programming experience in Python, as well as collaboration skills through project structure and documentation.

---

⭐ Achievement

• Successfully implemented and tested multiple search algorithms for the Sokoban game, with UCS identified as the most efficient.
• Developed a comprehensive experimental framework that highlights the importance of choosing appropriate algorithms based on problem constraints.

---

🌟 Donate

If you find this project useful, please consider giving it a star ⭐ to support further development. Your support inspires continued knowledge sharing and project enhancement. Thank you!

---