Use Piazza or email me, if you have any questions or problems with the assignment. Start early, so you still have time to ask in case of problems!

Implement an agent that is able to play the game of Breakthrough. This game is a simplified version of chess.

The game is played on an grid if width W (<latex>$2 \leq W \leq 10$</latex>) and height H (<latex>$4 \leq H \leq 10$</latex>). The initial state is setup such that both players have two rows of pawns of their respective color. White's paws are on rows 1 and 2 while black's pawns are on rows H-1 and H. The two players “white” and “black” take turns in moving one of their pawns. White moves first. Pawns move like in chess, that is, they can move one spot straight forward (up for white or down for black) onto an empty square or they can capture an opponents piece by moving one spot diagonally forward. As opposed to chess, pawns on the second row can not move two spaces at once. The goal of the game is to advance any one pawn to the opposite side of the board (i.e., to promote a pawn). The game ends, if one of the players has reached his goal or if the player who's turn it is does not have any legal move. This can happen if he does not have any pieces left, or if all his pawns are in positions where they cannot move. The game ends in a draw if none of the players wins. The scores are 100 points for winning, 50 points for a draw and 0 points for losing.

The legal moves for the agent are called “(MOVE x1 y1 x2 y2)” meaning that the pawn at x1,y1 is moved to x2,y2. x1,x2 are integers between 1 and W. y1,y2 are integers between 1 and H.

1. Develop a model of the environment. What constitutes a state of the environment? What is a successor state resulting of executing an action in a certain state? Which action is legal under which conditions? (Note that the board size is flexible and your agent should be able to handle games with different board sizes within the given restrictions for width and height).
2. Implement a state evaluation function for the game. You can start with the following simple evaluation function for white (and use the negation for black): 50 - <distance of most advanced white pawn to row H> + <distance of most advanced black pawn to row 1>
3. Implement iterative deepening alpha-beta search and use this state evaluation function to evaluate the leaf nodes of the tree.
4. Keep track of and output the number of state expansions, current depth limit of your iterative deepening loop and runtime of the search for each iteration of iterative deepening and in total.
5. Improve the state evaluation function or implement a better one.
6. Test if it is really better by pitching two agents (one with each evaluation function) against each other or by pitching each evaluation function against a random agent. If you run the experiments with the random agent, you need to repeat the experiment a decent number of times to get significant results. Don't forget to switch sides because white has an advantage in the game.
7. Do all experiments with time constraints (play clock) of 1s, 5s and 10s.
8. Make your code fast! The more state expansions you get per second, the better the player. Ideally, you should be able to solve the

• java project for the agent development

The files in the archive are similar to those in the first programming assignment. The archive contains code for implementing an agent in the src directory. The agent is actually a server process which listens on some port and waits for the real robot or a simulator to send a message. It will then reply with the next action the agent wants to execute.

For implementing your agent:

• Add a new class that implements the “Agent” interface. Look at RandomAgent.java to see how this is done.
• You have to implement the methods “init” and “nextAction”. “init” will be called once at the start and should be used to initialize the agent. You will get the information, which role your agent is playing (white or red) and how much time the agent has for computing each move. “nextAction” gets the previous move as input and has to return the next action the agent is supposed to execute within the given time limit. “nextAction” is called for every step of the game. If it is not your players turn return “NOOP”.
• Make sure your agent is able to play both roles (white and black)!
• You can make sure to be on time by regularly checking whether there is time left during the search process and stopping the search just before you run out of time, e.g., by throwing an exception that you catch where you call the search function the first time.
• To specify the port your agent is running on change the build.xml file as follows and use the command line ant -Darg0=PORT run with PORT being the port number:

build.xml

      ...
      <target name="run" depends="dist">
              <java jar="${dist}/${projectname}.jar" fork="true">
                      <arg value="${arg0}"/> <!-- add this line here! -->
                      <jvmarg value="-Xmx500m" />
              </java>        
              <antcall target="clean" />
      </target>
      ...

Please hand in a zip file containing:

• the source code and an executable jar file for your agent
• a short description of your heuristic
• the results of the experiments and which conclusions you draw from them

To create the zip file you just edit the “student” property in the build.xml and call the “zip” target using ant (execute “ant zip” in the directory containing the build.xml). Make sure to have all files that are to be in the zip file in the directory containing the build.xml or below.

The deadline is TBA. We will have a tournament between your agents afterwards. Extra points for the top players!