Weight: 5%
Due: Monday, March 2nd, by 23:59
Group Size: 1-2
Programming Language: The skeleton is in Java, but you can do this in any language
Provided skeleton: prog2.zip

Having the computer play a game with a human player has always been an attractive way to showcase artificial intelligence, though one could argue that the intelligence used for choosing a good move in a particular game is too restrictive to be generally useful. However, writing a game playing agent introduces important concepts that are useful throughout any type of AI work, including real-time constraints (humans won't wait forever while you think) and the ability to evaluate a state or situation to inform a decision.

This is an assignment where you get an opportunity to write a game playing agent. The game is the classic “Connect 4” game, where the objective is to be the first to bring 4 tiles of the same color (your color) into a vertical, horizontal or diagonal configuration. The red player in the following screen shot has just won the game (diagonal from top left).

You will start with a skeleton program in Java. This program won't run until you have filled in some of the basic game playing methods, but you'll find special TODO markers in the code to guide you through the process. In essence, you need to focus on the State class to begin with, in order to provide some of the crucial game playing information about each state (e.g. the successor function, what moves are available and which player's turn it is) and a mechanism to change the state through a move. Notice that a move is simply indicating the column you want to drop a piece into, so at any given time you have 7 possible moves (unless a column is full). A Search class is also provided to find the best move, but currently it picks a move by random, so this is a class you'll then need to refine and at least have it perform a proper search for a move that should lead to a future good state. This is where you have total freedom of approach!

The State class contains an evaluation function. This is used by the search algorithm when the maximum depth has been reached. Then the leaves are evaluated with this function. The current implementation that you are given is sufficient to play the game once you have the other parts of the State and the Search classes. It evaluates terminal states correctly, but all intermediate states have a neutral evaluation (meaning it is considered favourable for neither player). It is your job to fill in the code for evaluating intermediate states more intelligently.

To test your game playing agent, you'll of course play against it yourself, but when you have all turned in our assignments, we'll have a tournament between your agents! All that is required to participate in the tournament is that your program input/output commands and information in the same standard format (defined below) as the skeleton using stdin/stdout, and that it runs in a Linux/MacOSX environment (i.e. don't use anything Windows specific).

Submit a single zip or rar file into MySchool with all of the code required to run your game playing agent. Include a readme.txt if needed for explaining how to run it (especially important if you're not using the Java skeleton). Remember to document your code! Especially the parts where you do something clever

Also be prepared to have your agent run up against other people agents in a tournament! Make sure you're using the stdin/stdout mechanism for communicating with your program.

The skeleton you are provided with does not compile as is. You need to fill in at least the TODOs in the file State.java, except those that are marked otherwise. When this is done the files should all compile. If you have ant installed you can issue the command ant compile in the root directory. The class files will be put in the bin directory. You run the application by changing to that directory and issuing the command java Connect4.

Note that all interaction with the program is through the command line. The window that displays the board is only for showing the current state, you cannot click it or otherwise interact with it.

The command line interface is simple. A prompt is indicated by > and all command names are one character long. You can see the list of available commands by issuing the command h.

If you want to write your agent in a different language, you are free to do so as long as you clear the specific language with the teachers. If you do this, your program must use stdin and stdout to communicate with the user, as this interface is also used to communicate with the tournament server. Make sure your program at least accepts (and handles correctly) the commands i, m, r, d, g, p and q (in other words, all commands are essential but the h command).

The output of the program only matters in three cases.

1. When the user is expected to enter something, the prompt line must start with “>” and no other line of the output can start with this character. This is to enable the server to detect when your program is ready for commands.
2. When the g command is given by the user or server, your program can output any number of lines - but one of them must be of the form bestmove x, where x is the name of a column to drop a piece in. There should be no other text on this line.
3. When the p command is given, your program should only respond with one line. This line should contain exactly 1 + 6*7 = 42 characters.
   • The first character should be either B (for black) or R (for red) indicating which player has the next move
   • The following characters should represent the squares on the board, each one being . (for blank), R (for red) or B (for black). The following 7 characters should show the bottom line of the board, from left to right, and the next 7 characters should show the second line from the bottom etc. The example below shows the line printed for the state in the picture above.

> p
BBBBRBB.RBBB...RBBR...RRR....BRR....RR.....

If you don't use the Java skeleton as a base, make sure you also flush the standard output every time you display the prompt.