The objectives of this assignment are:

1. Adversarial Search (Minimax).
2. Developing a static evaluation function (for Connect-4)

Connect-Four is played on a rectangular grid like the one shown above. Each turn involves dropping a marble (coin, disk, whatever) above any column in the grid (that is not already full) - the marble will drop straight down and end up in the column at the lowest point possible (the lowest row that does not already contain a marble in that column). Each player tries to get four of their marbles in a row (horizontally, vertically or diagonally). If you are not familiar with the game, you should check out some of the many web versions of this game, as well as the description on Wikipedia:

• Wikipedia Connect Four Page
• Online (java) perfectgame
• Another online game

NOTE: The standard game is played on a grid with 6 rows and 7 columns - for our tournament the size of the grid will vary (your code must not make any assumptions about the size of the grid!). The strategy for winning (playing a perfect game) on a standard board size is known, but you cannot assume your agent will be playing on a standard size board!

Your assignment is to create a scheme procedure (function) that will determine the best move to be made given the current state of the game and the player whose turn it is. The return value must be a single integer indicating a column number. The number of rows and columns in the current game can be derived from the size of the state representation given your function, you cannot make any assumptions about the size of the game grid.

Your procedure will participate in a tournament to determine the best ConnectFour procedure in the class. The winner will receive a great grade, a sprinkling of fame, and perhaps a cookie. Tournament results will be available on the WWW and will be updated daily. The semifinals and finals will be played out in front of a live audience (that is, during class).

---

IMPORTANT
All Your Procedures must start with your RCS user name
The Procedure that will be called (by the tournament software) is <rcsid>-getmove.

Since your code will be participating in an automated tournament, both your code and your opponents will be running in the same scheme environment. We need to make sure that you don't have a top level procedure that is the same name as a procedure your opponent has written. Here are the rules:

• All your top-level procedures and global variables must be prefixed by your RCS user name. For example, my procedures would have names like hollid3-getmove and hollid3-checkcolumn.

• The only scheme procedure that will be called by the tournament system is the procedure described above. This procedure must be named <rcsid>-getmove and has the following prototype (I use my RCS id as an example):

  (hollid2-getmove board player)

  board is the representation of the current state of the game as described below, and player is 1 for the player who got to go first and 2 for the other player. Your procedure must be capable of determining the best move for either player (since in some games you will be 1 and in others you will be 2).

  Board data structure: The board will be represented by a scheme list of the columns, the first element represents the leftmost column in the game board. Each column is represented by a list of board squares, the first element represents the top position (highest square in the column).

  Each game board square is either a 0, 1 or 2:

  • 0 : square is available (empty)
  • 1 : player 1 has a marble on the square
  • 2 : player 2 has a marble on the square

  For example, the following scheme list represents the state of the this game board (on a grid of 6 rows and 7 columns, and red was the first player):

  '( (0 0 0 2 2 1) (0 0 0 2 1 2) (0 0 0 0 2 1) (0 0 0 0 1 2) (0 0 0 1 2 1) (0 0 0 2 1 1) (1 2 1 1 2 2) )

  0 1 2 3 4 5 6

  Assuming the variable board holds the list value show above, a call to hollid2-getmove would look like this:

  (hollid2-getmove board 1)
  ;; Value: 5
  

  The return value is the move that my program is making and indicates a red marble should be dropped in column 5.

• Your procedure cannot take more than 30 seconds to decide on a move (when run on a Thinkpad T43p).

• Your procedure cannot attempt to redefine any of the tournament code or opponent code. Your procedure cannot make use of any tournament code or opponent code (you need to provide everything your procedure needs in your submission).

• In the tournament, ties will go to the smaller code. Size is determined by reducing all procedure and variable names to a single character and removing all whitespace).

Sample Code (MIT Scheme)
Some sample code is here. This code includes:

• the definition of a procedure named play-connect4 that will pit two getmove procedures against each other.
• A bunch of possibly useful support routines
• A sample getmove procedure that returns a random move.
• A sample getmove procedure that allows a human to play (prompts for moves).
• More documentation on game board representation and some other useful tidbits.

Note: You should not make any assumptions about the tournament environment, if could involve completely different code than is provided in the sample code. If you want to use some of the procedures defined in the sample code, you must include them (and they need to be named with your rcsid).

Your grade depends on the following formula:

• Correct implementation of Minimax: 60%
• Useful static evaluation function: 30%
• Performance in the tournament: 10%

Note that how well your code does depends on two factors:

• How good your static evaluation function is
• The depth of search possible within the time constraints. If you use alpha,beta pruning this will mean you can search deeper!