Assignment 1 - Introduction to Artificial Intelligence
This project is aimed to create a Sokoban game that we can play manually or automatically using searching algorithm. We use two searching algorithms here, the first is 'BFS' for blind search and 'A*' for heuristic search. Our team selects Pygame to create the UI of this game. In this project, we are going to play and solve the Sokoban game in 80 maps including 40 testcases in Micro Cosmos and 40 testcases in Mini Cosmos (source: link). All problems and tasks we can see in assignment1.pdf file (Vietnamese language). Wiki Refs: link

Sokoban is a puzzle video game genre in which the player pushes crates or boxes around in a warehouse, trying to get them to some goal locations.The game is played on a board of squares, where each square is a floor or a wall. Some floor squares contain boxes, and some floor squares are marked as goal locations.

The player is confined to the board and may move horizontally or vertically onto empty squares (never through walls or boxes). The player can move a box by walking up to it and push it to the square in front. Boxes cannot be pulled, and they cannot be pushed to squares with walls or other boxes. The number of boxes equals the number of storage locations. The puzzle is solved when all boxes are placed at storage locations.

Quach Minh Tuan - To Thanh Phong - Vo Anh Nguyen

1.0.0

• Python >= 3.9.7
• Pip >= 21.2.3

Clone our source code

$ git clone https://github.com/nh0znoisung/Sokoban
$ cd Sokoban

Install Dependencies

$ pip install -r requirements.txt

Run program

$ python main.py

For Breadth First Search algorithm testing result

$ python test_BFS.py

For A star algorithm testing result

$ python test_Astar.py

Before running these command above, we need to delete the BFS.csv and A_star file. Because it will firstly loading the number of testcase that we solved in the last visit in order to the case that we don't need to run all testcases from scratch.

The statistic we use for analyzing is stored in BFS_auth.csv and A_star_auth.csv file. This result recorded when run on Windows 10, CPU Intel Core i5 8250U - 8th generation, RAM 16Gb, SSD 240Gb and all are gathering and editing in all_test.xlsx

$ python statistic.py

Firstly, we need to suitable map that we want to solve. You can click the up or down arrow to choose level between 1 and 40 or clicking the change button to toogle between Mini Cosmos and Macro Cosmos. When change occurs, the new map is displayed in the left side. Note: The map and the level is not sorted by the difficulty. Some adjance map may just have some same things in the map and deffrent in the position of boxes or goals or player.

Choose your game play. In this step, we have only 3 options including Manually that we can self-play and control the player with 4 directions (Up, Left, Right, Down); BFS and A* for running algorithm automatically.

In the process of moving in self-playing, we can undo and redo or restart a new game. We can control the player in 4-direction by some instructions below:

• Click Up arrow or W to go up.
• Click Down arrow or S to go down.
• Click Left arrow or A to go left.
• Click Right arrow or D to go right.

The move is available if it satisfies some rules including:

• The forward cell is not the wall.
• If the forward cell is a box, we consider the forward of the forward cell. If that is not a box or a wall, we can move forward and simultaneously push the box to forward cell.

After solving by user or algorithm, the program will automatically save the winning state of the game in Results folder. To be more specific, this folder has 2 important part including history_log.txt file which stores generally all history of all testcases and some text files that represent for history of the single testcase, for example Solution_MICRO COSMOS_test 7.txt. These file are sorted by time in descending order and contain some crucial infomations such as datetime, problem, algorithm, solution, the number of steps, the number of nodes generated, memory, duration,...

By solving the testcase by algorithm, we have Visualize button to simulate the player with the solution that found before.

1. At first, we need to generate these testcases. In this link link, we convert 80 maps into 80 text files manually with some notation. For example, player is @, wall is #, box is x, goal is ?,...

• Video (Vietnamese language): https://www.youtube.com/watch?v=oT5ag8KVyHA
• Slide for presentation (Vietnamese language): slide.pdf

BFS is more effective compare to A* in this problem. To be more specific:

• About the running time, A* algorithm is slower than 3 times compare with BFS. The reason is the algorithm inside when we implement. Firstly, A* needs to calculate the cost whenever it creates a new node. This stage uses Hungarian algorithm for matching the distance between the boxes and the goals and finding the minimum sum of this cost and it wastes O(n^3) while BFS doesn't need to store this value. Moreover, the data structure that we use for storing the list of nodes that is sorted in order of its cost is min-heap (priority-queue). Every operation such as insert delete will cost us O(log(n)) while node in BFS will be stored in a basic list and these operations just cost us O(1).
• About the space, the average node generated in A* algorithm is just bigger little bit compare with that of BFS algorithm. Since BFS will scan nodes in the whole current level until finding the final state or go to the next level and repeat it while A* will choose the node that has the minimum cost and go toward that node and expand more nodes in child level and continue to compare the cost and choose the next node until finding the final state so it's not restricted we must scan all node in a level. Therefore, A* algorithm just combines BFS and DFS and reduces more node generated and space when running.

In general, the solver will run exceed 1 second when the map has the number of boxes and goals more than 4 and the space is large that we need to analyze more space of state.

• This current map is restricted with 80 testcases. We can extend it more map in the collection of game in this link such as pico cosmos, nabo cosmos, DH1 collection,.... We can totally do this by using crawling data map and position of another items with Selenium tool. There are apporximately 1000-2000 maps in this Web.
• We can extend more algorithm such as UCS, DFS, Best first search, Hill Climbing,...

• https://ksokoban.online/

• https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf

• https://verificationglasses.wordpress.com/2021/01/17/a-star-sokoban-planning/
• https://github.com/cynrd/blog/blob/master/sokoban_astar/main.py
• https://github.com/janecakemaster/sokoban