Solving Sokoban with Artificial Intelligence

The Sokoban game https://en.wikipedia.org/wiki/Sokoban is a good testbed for introducing Artificial Intelligence. The domain is more complicated than a normal line following robot, but not so difficult that it will become out of reach for the average programmer. In the following blog post, a tutorial is given how to realize an Artificial Intelligence system which can play Sokoban autonomously.

The first thing to do, is to localize the task of creating an AI within a larger horizon. On the lower end, a manual controlled teleoperated game is available which is played by a normal user. No AI at all is available, but the human operator can solve each level with a bit thinking. On the other end, an autonomous playing AI system is the goal which doesn't need a human in the loop but can decide the next by it's own. Somewhere in between these points, the project is located.

The baseline for Sokoban and most other AI projects is, that the game can be played by a human. So we need a reasonable well programmed Sokoban game (Python is your friend) which is asking for keyboard input from a human user. The game engine calculates the position of the moved boxes and print out a “you won” message, if all the boxes are on the target position. The important thing to know is, that this baseline works which means that the combination of a game plus a human solver can play Sokoban reasonable well.

The next step is to increase the autonomy of the system which means to make the game easier for the human operator and decide some or all actions by an AI in the loop. Like i mentioned before, it's a continuous from a teleoperated controller until an autonomous controller. The steps in between are:

1. Teleoperation (human decides all)

1a teleoperation with a time delay

1b teleoperation with predictive modellilng

1c action recognition as support

1d sketch based control

1e solver based control

2. Fully autonomous system

The steps in between are numbered with 1a to 1e. An AI who is playing Sokoban is located on one of these steps. If we want to shorten the development process the first thing to do is to program an activity recognition system which is observing what the human is doing. And then a sketch based goal planner can be realized which is able to play the game semiautonomous ...

Let us slow down the overall pipeline a bit and focus on the activity parser. If the human press the arrow keys he is doing something in the game. He can approach a box, he can move a box, he can walk into a certain direction and he can partly fulfill the task by moving one out of two boxes to the desired goal. Such activities are normally not visible in the Sokoban game. They should be formalized in a computer program and print out in realtime. This is equal to build a model of Sokoban and allows to track the actions of a human. It is equal to a semantic parser which determines what the player is doing in the game.

The second thing what is usually not visible is the overall plan the human operates. Most player have a rough idea how to solve a level before they execute the first action. This plan has to made visible too. It can be realized with a sketch which is drawn in the game. Such plans are utilized quite often in so called walkthrough tutorials. It's a high level description how to solve a level. If the plan is put as an overlay over the map, the game will become much easier to solve.

If the aim is to create a fully autonomous system the AI contains of an activity parser, a plan description language and the ability to match a the activity with a sketch. On top a solver can be realized which is executing subtasks alone.