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
28 Nov 06, 2022
1 Dec 24, 2021
16 Jul 20, 2022
59 Oct 13, 2022
11 Nov 08, 2022
0 Jul 18, 2021
11 Mar 14, 2022
3 Sep 30, 2021
3 Aug 04, 2022
56 Dec 08, 2022
50 Dec 03, 2022
2.2k Dec 31, 2022
17 Dec 23, 2022
1.6k Dec 30, 2022
54 Dec 30, 2022
43 Dec 29, 2022
7 Mar 22, 2022
4 Nov 10, 2022
5 Mar 21, 2022
114 Dec 28, 2022