Assignment 3: Sokoban

This assignment is worth 20 points and has two parts.

1. A* search (5 pts)

Implement A* search in Java.

First clone (or update your existing copy of) the ai_1 repository. Look in the src/search subdirectory, which has source files for the classes described in this section.

Write a general-purpose implementation of A* that can search any problem that implements the HeuristicProblem interface, which extends the Problem interface from the previous assignment:

// S = state type, A = action type
interface Problem<S, A> {
  S initialState();
  List<A> actions(S state);
  S result(S state, A action);
  boolean isGoal(S state);
  double cost(S state, A action);        

interface HeuristicProblem<S, A> extends Problem<S, A> {
  double estimate(S state);  // optimistic estimate of cost from state to goal

Your code should live in a class that looks like this:

// A* search
class AStar<S, A> {
  public static <S, A> Solution<S, A> search(HeuristicProblem<S, A> prob) {
     your implementation here 

The search() method should return a Solution<S, A> if a solution was found, otherwise null. Solution<S, A> is the same class from the previous assignment:

class Solution<S, A> {
  public List<A> actions;  // series of actions from start state to goal state
  public S goalState;      // goal state that was reached
  public double pathCost;  // total cost from start state to goal


A caller will be able to invoke your search method like this:

  HeuristicProblem<Integer, Integer> p = new MyPuzzle();
  Solution<Integer, Integer> result =;

The src/problems directory includes a couple of HeuristicProblem instances that you can use for testing:

It would be wise to ensure that your A* implementation returns optimal solutions to these test problems before you apply it to Sokoban. Run the tests in You should be able to solve each of the 15-puzzle instances in that file within a few seconds. If it takes significantly longer, your A* implementation is not working as efficiently as it should.


2. Sokoban (15 pts)

In this part of the assignment, you will use A* search to solve Sokoban puzzles.

Begin by downloading the Sokoban code from the Sokoban4J repository.

Write your agent in src/ , which contains a simple depth-first search implementation that you can delete and replace with your own solver.

In your agent code, create an instance of the HeuristicProblem<S, A> interface above and use an A* search to hunt for an optimal solution.

You wil want to use the Sokoban API.

To receive full credit for this assignment, implement the following:

public static boolean[][] detect(BoardCompact board) 

Your agent should be able to solve the puzzles in levels/Aymeric_Medium.sok in at most 4 seconds per puzzle on a typical machine. You must return an optimal (shortest) solution to each puzzle. To test your solver, run

$ ./sokoban MyAgent -levelset Aymeric_Medium -timeout 4000 -optimal





    The startup script 'sokoban' will now look like this:

java -cp 'target/classes:../ai_1/target/classes:libs/*' SokobanMain $*

    Or, on Windows, 'sokoban.bat' will look like this:

java -cp "target/classes;../ai_1/target/classes;libs/*" SokobanMain %*


All entries received before the soft deadline will automatically be entered into our Sokoban tournament. To compute your tournament score, I will run your solver on a series of Sokoban levels of increasing difficulty. In last year's tournament I used the levels in Aymeric_Hard.sok . This year you may use Aymeric_Hard for testing/training; in the actual tournament, I will use either that set or another set of levels of comparable difficulty.

In the tournament, your solver will have 3 seconds of CPU time to solve each level in succession. As soon as a solver fails to solve 3 levels, its evaluation ends. Your solver's score will be the number of the highest level that it successfully solved before it reached the third unsolvable level. I will resolve ties in favor of the solver that that used less CPU time in solving the highest level that was solved.

This year there will be two tournament categories:

  1. Finding an optimal (i.e. shortest possible) solution to each level.

  2. Finding any solution to each level. In this category I expect that agents will be able to solve more difficult levels.

To replicate the tournament conditions on your own machine, run

$ ./sokoban MyAgent -levelset Aymeric_Hard -timeout 3000 -maxfail 3 -optimal

For category 2, where non-optimal solutions are allowed, omit the -optimal argument.

You will need to submit a single solver that I will run in both categories. However, your solver may wish to behave differently depending on whether an optimal solution is requested, i.e. which tournament category it is running in. The field 'boolean optimal' in the ArtificialAgent superclass will be true if an optimal solution is requested.

Note: the tournament levels in Aymeric_Hard are not so easy! If you don't implement any extra optimizations, you will probably not be able to solve even the first of these levels in 3 seconds (and will likely not be eligible for any tournament points).