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
64 Dec 17, 2022
2.8k Jan 08, 2023
44 Nov 20, 2022
4 Feb 18, 2022
676 Jan 03, 2023
27 Sep 19, 2022
130 Dec 29, 2022
132 Dec 18, 2022
19 Nov 10, 2022
2.1k Jan 06, 2023
0 Jan 20, 2022
27 Dec 30, 2022
47 Jun 18, 2022
1k Dec 29, 2022
165 Dec 29, 2022
12 Oct 22, 2022
73 Jul 21, 2022
225 Dec 25, 2022
34 Aug 27, 2022
83 Oct 10, 2022