This assignment is worth 20 points and has two parts.
Implement A* search in Java. Write a general-purpose implementation that can search any problem that implements this interface:
// S = state type, A = action type
public interface Problem<S, A> {
S initialState();
List<A> actions(S state);
S result(S state, A action);
boolean isGoal(S state);
int cost(S state, A action);
int estimate(S state); // optimistic estimate of cost from state to goal
}
Provide a search() method that returns a Node<S,
A> representing the goal node that was found, or null
if no goal was found. Node<S, A> should
contain at least these fields:
class Node<S, A> {
public S state;
public Node<S, A> parent; // parent node, or null if this is the start node
public A action; // the action we took to get here from the parent
…
}Your code should live in a class that looks like this:
// A* search
class AStar<S, A> {
public static <S, A> Node<S, A> search(Problem<S, A> prob, Stats stats) {
… your implementation here …
}
}
The search should fill in the Stats object with
statistics about the search. Stats should have at least
this field:
public class Stats {
public int expanded; // number of nodes expanded in the search
}You may add any other statistics that you like.
A caller will be able to invoke your search method like this:
Problem<Integer, Integer> p = new MyPuzzle();
Stats stats = new Stats();
Node<Integer, Integer> result = AStar.search(p, stats);
System.out.format("%d nodes were expanded\n", stats.expanded);Here are some Problem instances that you can use for testing:
Be sure that your A* implementation returns optimal solutions to these test problems before you apply it to Sokoban.
You should be able to reuse virtually all of your uniform-cost search implementation from the previous assignment, because A* is essentially a variation of uniform-cost search.
Make your Node class implement
Comparable<Node<S, A>> and give it 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 so you can
retrieve it immediately in compareTo.
Use A* search to solve Sokoban puzzles.
Download the Sokoban code from the Sokoban4J
repository. Write your agent in the class
cz.sokoban4j.playground.MyAgent. 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 Problem<S,
A> interface above and use an A* search to hunt for an
optimal solution. Report the number of nodes that were expanded in
the search by writing to standard output.
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 agent should be able to solve all of the puzzles in the
Sokoban4J/levels/Easy directory while expanding fewer
than 10,000 nodes for each puzzle.
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.
You will need to use a depth-first or breadth-first search to find dead squares. Use box targets as the starting points for your search, and search for squares that are alive.
To test your solver, run the main method in
Evaluate.java , which will run your solver on a series
of 80 Sokoban levels in increasing difficulty order. If you have a
reasonable A* heuristic and dead square detection algorithm, then
with the default 10-second time limit you should be able to solve up
to about the first 30 evaluation levels on a typical desktop or
laptop computer, though the exact number will depend on your
hardware of course.
For debugging your dead square detection, here is a snippet
of code that will print the board and show which squares are dead.
It assumes that dead is a 2-dimensional array of
boolean indicating whether each square is dead:
System.out.println("dead squares: ");
for (int y = 0 ; y < board.height() ; ++y) {
for (int x = 0 ; x < board.width() ; ++x)
System.out.print(CTile.isWall(board.tile(x, y)) ? '#' : (dead[x][y] ? 'X' : '_'));
System.out.println();
}
For example, on level 1 (Easy/level0001.s4jl) the
output might look like this:
===== BOARD ===== ##### #p # # a # # 1# ##### dead squares: ##### #XXX# #X__# #X__# #####
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. :)
All entries received before the soft deadline will automatically be entered into a Sokoban tournament. In the tournament, I will run your solver on a series of Sokoban levels of increasing difficulty. Your solver will have 10 seconds to solve each level in a process with 2 Gb of RAM (specified with the -Xmx Java flag), on a machine with a 2.8 Ghz Intel CPU.
As soon as a program fails to solve 3 levels, its evaluation ends. Your solver's score will be the number of levels that it successfully solved before it reached the third unsolvable level.
Note that solutions in the tournament need not be optimal! I will, however, resolve ties by choosing the solver that found a shorter solution.
I will use the levels in Evaluate.java or a similar
set of levels for the tournament. If you want to replicate the
tournament conditions on your own machine, change the maxFail
constant in main() in that file to 3 so the evalulation
will continue until the 3rd unsolved level.