Aritificial Intelligence Project

Iterative Deepening A*, Recursive Best First Search, and Monte-Carlo Tree Search for Sokoban Games

 

Abstract

As the final project, we implemented IDA*, RBFS and MCTS in order to solve Sokoban game which is the well-known single player game. Sokoban game is a big challenge in artificial intelligence study due to its problem complexity. So, we had to apply heuristic functions and deadlock detectors. All algorithms solved problems, but their performances are, of course, different. The result of this experiment shows the possibility to improve algorithms further by considering specific conditions of the environment of the game.

 

The Experiment Results & Discussion

Please see the report.

More Projects on AI algorithms:

1. A Study of Three Vacuum Cleaner Agents: Simple Deterministic Reflex Agent, Random Reflex Agent, and Deterministic Model-based Reflex Agent
2. A Study of Search Algorithms and Heuristics Functions: Iterative Deepening A Star and Recursive Best First Search,Manhattan Distance and Walking Distance
3. A study of solving sudoku: Using combination of various inference rules