Weight: 5%
Due: Thursday, March 3rd, by 23:59
Group Size: 1-3
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 the opportunity to write a game playing agent. The game is the classic “Connect 4” game, where the goal is to connect four of one's own discs of the same color next to each other vertically, horizontally, or diagonally before one's opponent can do so. The red player in the screenshot on the right 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 has the turn) 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 randomly, so this is a class you'll 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 favorable 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 once all the assignments will be turned in, we'll have a tournament between your agents!
• In order to participate, your program's input/output commands and information must conform to the same standard formats (defined below) used by the skeleton. In addition, it should be runnable on a Unix environment (i.e. don't use anything Windows specific). The Java skeleton provided is already conforming to the input/output guidelines, but if you want to use another language, please, refer to the the section The command line interface.
  NOTE: for the tournament we'll use a server capable of running matches and communicate with clients using the standard command line interface described below. Your code will be executed on a Unix client and a wrapper will be used to manage the network communication with the server. So, you don't need to worry about network communication, just follow the input/output guidelines!!!

Submit a single zip or rar file into MySchool with all the required code in order to run your game playing agent. Include a readme.txt explaining how to run it (NOTE: this is important if you're not using the Java skeleton). Remember to document your code! In particular, parts where you implemented something clever

Be also prepared to have your agent competing against other agents in the tournament! Make sure you're using the standard stdin/stdout mechanism for input/output of your program.

The provided skeleton does not compile as it is. You need to fill in, at least, TODOs in the file State.java, except those that are marked otherwise. Once you are done with this, all files should 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 can run the application by changing to that directory and giving the command “java Connect4”.

NOTE: all interactions with the program are through the command line. The window displaying the board is only for showing the current state, you can't interact with it (i.e. select moves).

The command line interface is very 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 implement your agent using a different language, you are completely free to do that, as long as you inform us (Hannes or Angelo) about the specific language you plan to use. If you do this, your program must use stdin and stdout as input/output mechanism, as this interface is also used to communicate with the tournament's 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 the 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). They start showing 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.