Sokoban Bot
Introduction to AI assignment 1 HCM University of Technology, term 211
Abstract
This is basically a solver for Sokoban game using Breadth-first Search and A* algorithm to search state space for a solution. Example level sets are taken from ksokoban.online, "Mini Cosmos" and "Micro Cosmos" (40 levels each)
Algorithm
(see more in the Sokoban.py code, where I explain the algorithm in details)
-
Breadth-first Search: We keep generating new state that is a combination of main character's and crates' co-ordinations push it to the queue. Pop it every loop and proceed to generate more state till solution.
-
A*: Just like above but with a heuristic, the new state is tagged with a cost function to switch to a better branch when possible.
-
In both function, I use a heuristic for more feasible searching, which is the dead lock detection. So actually, the BFS is not a genuine Blind Search, but we will consider it to be a close one. (For real, blind search took so long that I nearly lose my mind waiting)
Instruction
- import Sokoban class from Sokoban.py and call one of the run functions:
Example:
from Sokkoban import Sokoban
sokoban = Sokoban()
sokoban.run_all() #run everything, mini, micro, 80 level, both methods
sokoban.run_all_micro() #run all micro cosmos level (40) with both methods
sokoban.run_all_mini() #run all mini cosmos level (40) with both methods
sokoban.run_all_bfs() #run all level (80) with BFS
sokoban.run_all_astar() #run all level (80) with A*
sokoban.run_one('astar','micro',1) #run Micro cosmos 1 with A*
sokoban.run_one('bfs','mini',3) #run Mini cosmos 3 with BFS
- Or run the game.exe: (see more instruction on the slide)
- Or run the game.py:
python game.py
2 Dec 16, 2022
2 Feb 11, 2022
4 Apr 15, 2022
7 Jun 6, 2022
1 Feb 8, 2022
![[ECCVW2020] Robust Long-Term Object Tracking via Improved Discriminative Model Prediction (RLT-DiMP)](https://github.com/bismex/RLT-DIMP/raw/master/figure/thumbnail_title.PNG)
35 Oct 26, 2022
76 Dec 13, 2022
4 Oct 17, 2021
62 Dec 17, 2022
1 Nov 25, 2021
5 Nov 23, 2022
4 Sep 4, 2021
3 Oct 3, 2022
3 Jan 29, 2022
6 Dec 29, 2021
4 Apr 5, 2022
35 Dec 6, 2022
1 Nov 9, 2021