Period: May 2019
Sokoban is a well-known puzzle video game first introduced in Japan in 1980. In this game, the player controls the warehouse keeper (sokoban) who is placed in a closed warehouse with a number of boxes that need to be put in some predefined goal locations. The keeper can walk around the warehouse and push boxes around in order to get them into goal positions. The goal of the game is to put all boxes into goal positions in the fewest number of moves.
This project involved writing various Lisp functions to implement the components to solve Sokoban for various game dimensions and start states. The game is turned into a search problem consisting of a state representation, a successor function, a goal test, and a cost function. Once defining each of the components of the search problem, the problem can be solved using a generic search engine that implements any search algorithm (e.g. DFS, BFS, A*, etc.). Implementing the solver for this problem gave me experience in defining a search space for a practical problem and coming up with a good heuristic to make the program more efficient. I wrote two heuristic functions: (1) h0 that is a trivial admissible heuristic that returns a constant 0, and (2) h1 which returns the number of boxes which are not on goal positions in the given state.