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 = AStar.search(p);

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

Cube.java – a search through a 3-dimensional state space
NPuzzle.java – the classic sliding-block puzzle

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 AStarTest.java. 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.

hints

You will need to make only a few changes to your uniform-cost search implementation from the previous assignment, because A* is essentially a variation of uniform-cost search.
Your Node class should have a compareTo method that compares nodes by f-cost, defined as f(n) = g(n) + h(n), where g(n) is the path cost and h(n) is the heuristic estimate.
Do not compute the heuristic estimate on every call to compareTo; that will be expensive since the priority queue compares nodes very often. Instead, store the heuristic estimate as a field in the Node class.
For debugging, print out the number of states that your A* search has explored. (As you experiment with heuristics and optimizations in the following Sokoban problem, it will be helpful to see their effect on this number.)

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/MyAgent.java , 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:

A non-trivial admissible, consistent heuristic to guide the A* search. (The number of unplaced boxes is a trivial heuristic; surely you can do better than this.)
Dead square elimination. Your implementation should create a list of dead squares, which are squares from which a box cannot possibly be pushed to any goal (even if Sokoban could teleport to any location). You should prune the search at any point where a box is pushed to a dead square.

For example, in the following picture every square that is adjacent to a wall is dead:

Your dead square detector must live in a class named DeadSquareDetector, and have this signature:

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

Given a Sokoban board, it should return a 2-dimensional array of booleans with the same dimensions as the board. detect[x][y] should be true iff the corresponding square is dead.

To help you test your dead square detector, here is a file DeadSquareTest.java with a class that you can run. If your detector is working correctly, it should produce this output.

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

hints

The easiest approach is to use BoardCompact as your state class and either EDirection or CAction as your action class. If you want to make your solver more efficient, you could experiment with the other available board state classes (BoardSlim, BoardCompressed or StateMinimal) or even invent your own.
In your implementation of the result method, you will need to clone the given board state since result is supposed to leave the existing state unchanged. You can call perform to apply an action to the cloned state.
Use a depth-first or breadth-first search for dead square detection. Start at the target square(s) and search for squares that are alive.

There are many additional techniques and optimizations you could optionally implement. If you are interested in that, I recommend reading this Sokoban Solver documentation written by a former MFF student. It suggests various useful ideas (only some of which the author implemented in his own program). If those aren't enough for you, the Solver page on the Sokoban Wiki has many more ideas that could keep you busy for a while. :)
Just like in the previous assignment, you will probably want your agent to use classes from the ai_1 project. You can either (a) copy the ai_1 source files you need into the Sokoban project, or (b) modify the Java project file (pom.xml) and Sokoban startup script (sokoban or sokoban.bat) to create a project dependency.

For option (b), insert this dependency into pom.xml:

<project>

  ...

  <dependencies>  
    <dependency>
      <groupId>cz.cuni.mff</groupId>
      <artifactId>ai-1</artifactId>
      <version>0.1</version>
    </dependency>
  </dependencies>
</project>

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 %*

tournament

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:

Finding an optimal (i.e. shortest possible) solution to each level.
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).