This assignment is worth 20 points and has two parts.

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.

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

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

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 r

`esult`

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

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