IASBS Artificial Intelligence I (981)
Assignment 1
Fall 2019
Mohammadmahdi Alijani (964413)
Alireza Nadirkhanlou (964407)
This project solves Sokoban puzzles using basic A.I. search algorithms (both uninformed and informed). The project is still in development, and as of now, you can only use uninformed algorithms to solve your puzzles.
The core layer of this solver is written in C++.
- Uninformed
- Breadth-first search (BFS)
- Depth-first search (DFS)
- Iterative deepening depth-first search (IDS or IDDFS)
In order to avoid producing too many repititious states, we store the N most recent checked states in a state_history buffer. Bigger N values helps the algorithm to reach an answer with checking fewer states, but will also slow it down because for every produced state, it has to compare it to N previously checked states.
Searching this buffer could be quite a bottleneck for the algorithm, so for each algorithm, we implemented a duplicate with Multi-threaded searching using the OpenMP library, which noticably speeds up the whole process. You need to enable OpenMP support for your porject to be able to use these algorithms.
Your input must be in the following format:
# Wall . Floor S Player @ Box X Goal
Note that the four sides of the game map must be surrounded with walls (reduced code complexity) Example:
############ ######..X### #S....@@..## #####..X#### ############
(We are aware this format is not the standard format of this puzzle, but our assignment had this format as a standard, and after presenting the project, we will switch to the standard format!)
After sorting out your input, you can easily choose the path to your input, and after loading it, choose the algorithm you want to solve the puzzle with. In the console window, you can see how many states were checked (COUNT) in order to find the answer.
Here you can also set your State History buffer size!
After solving the puzzle, you will see Mr. Sokoban (!) start to move the boxes into the goal spots. In the console window, you will see a string of steps consisting of L's, R's, D's and U's denoting the path to solve the puzzle!
Coming soon...