Matthew Days, Yangzi Jiang
Faculty Sponsor: Dr. Raghu Ramanujah
Sokoban, a puzzle game invented in Japan, poses a challenging problem for studying the performance of search algorithms due to its enormous number of possible states and often irreversible moves. In this project, we test two search algorithms on the Sokoban domain—specifically, Iterative Deepening A* (IDA*) and Monte Carlo Tree Search (MCTS). Additionally, we investigate ways to optimize the performance of these algorithms using the knowledge that is specific to the domain of Sokoban.