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
3 Mar 30, 2022
6 Sep 03, 2021
13 Dec 06, 2022
19 Sep 30, 2022
4 Feb 14, 2022
20 Dec 31, 2022
201 Dec 21, 2022
87 Dec 25, 2022
8 Jan 04, 2023
26 Nov 23, 2022
2 Dec 21, 2021
2 Dec 28, 2021
16 Oct 26, 2022
589 Dec 30, 2022
28 Jan 04, 2023
4 Aug 06, 2022
219 Dec 27, 2022
165 Dec 07, 2022
176 Dec 30, 2022
3 Aug 04, 2022