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 astar/src 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> {
  int 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 astar/src 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.)

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.

If you are opening Sokoban4J in Intelli/J, then when the "Import Project" window appears, be sure to select "Import project from external model" and click on "Maven". On the following page, check the box "Search for projects recursively", which will allow Intelli/J to find the various Maven subprojects.

Write your agent in Sokoban4J-Playground/src/main/java/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. 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 should live in the DeadSquareDetector class in MyAgent.java. Given a Sokoban board, it should return a 2-dimensional array of booleans with the same dimensions as the board. A value of true means that the corresponding square is dead.

To test your solver, run the main method in Evaluate.java , which will run your solver on a series of Sokoban levels of increasing difficulty order. Your agent should be able to solve the puzzles in the Sokoban4J/levels/sokobano.de/Aymeric_Medium.sok directory in at most 5 seconds per puzzle on a typical machine.

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. 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. :)

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, which you can find in Aymeric_Hard.sok .

Your solver will have 5 seconds of CPU time to solve each level. As soon as a program 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.

Your solver must find an optimal (i.e. shortest possible) solution to each level that it solves.

You can use Evaluate.java to run the same levels on your own machine. If you want to replicate the tournament conditions exactly, change the maxFail constant in main() to 3 so the evaluation will continue until the 3rd unsolved level.

Note: the tournament levels are hard! If you don't implement any extra optimizations, you will probably not be able to solve even the first tournament level in 5 seconds (and will not be eligible for any tournament points).