Introduction to AI (COMP-424)
Winter 2010

Project

Goal

The main goal of the project for this course is to give you a chance to play around with some of the AI algorithms discussed in class, in the context of a fun, large problem. The game selected for this year's competition (proposed by one of the students in the class) is called Philosophers' football.

The game

The rules are simple, but the gameplay is complex enough to favor players with good tactics and long-term strategy.
You can find the rules at http://en.wikipedia.org/w/index.php?title=Phutball&oldid=333212052.

If you want to get an idea whence the name derives, watch this: http://www.youtube.com/watch?v=ur5fGSBsfq8
(The board game is an American-football version thereof.)

Some items to emphasize:

  1. The board has rows {0, ..., 20} and columns {0, ..., 14} (or {A, ..., O} in the GUI). When indexing board positions, the order is (row, column).
  2. Player 1 has to reach rows 19 or 20, Player 2 has to reach rows 0 or 1.
  3. Rows 0 and 20 are beyond the goal lines. You can't place philosophers there. Also, you can't pass the ball beyond the goal line you're defending.
  4. You can never pass the ball beyond columns 0 or 14, not even past the goal line you're trying to reach.
  5. It is always legal to make the 'empty move', i.e. to leave the ball where it is. In particular, if you've just passed the ball but don't want to move it again (although you could), play the empty move in order to make it the opponent's turn.
  6. If your AI player makes an illegal move or takes more than 5 seconds, you lose.
  7. The game ends in a draw after 300 moves.

The GUI

The client/server software

Download the Java server and client software here.

During the tournament, the game will be played with each player running on a different computer (to avoid contention for CPU). The players will communicate with the server via TCP socket connections. Of course, the server and clients can all be run on the same machine too.

The Philosophers' football server and an example client are provided. Please see the README.txt file for a description of the included files.

To run a server and two random players on the local machine:

  1. Download and extract the code. In the directory containing the code, compile with
       javac boardgame/*.java phootball/*.java
  2. Launch a server to listen on port 8123: 
       java boardgame.Server -p 8123
    The server GUI appears.
  3. In a different console, launch the first player to connect with:
       java boardgame.Client phootball.PhootballRandomPlayer localhost 8123
  4. In yet another console, launch the second player:
       java boardgame.Client phootball.PhootballRandomPlayer localhost 8123
The game starts as soon as both clients are connected.

See the README.txt file for more information on running the client and server. The server software also allows for locally running clients to be launched from the GUI, for humans to play against software players or other humans, and for game log files to be viewed.

Implementing a player

A framework is provided to help you implement your player. It handles communication with the server and maintains a copy of the current game board.

You are also provided with the source code for a simple random player (the class phootball.PhootballRandomPlayer), which you may use as a starting point.

To implement a player, create a boardgame.Player subclass. You need only define two methods:

  1. a default constructor
  2. the chooseMove() method
Then your new Player subclass can be passed as an argument to the client software.

A simple player will look like this: 

////////////////////////////////////////////////////////////////////////
package mypackage;

import boardgame.Board;
import boardgame.Move;
import boardgame.Player;

public class MyPlayer extends Player {
   
    /** A default constructor is needed so that the client 
    software can create a MyPlayer object. */
    public MyPlayer() {
        // The string passed to the Player constructor will be 
        // used to identify the player to the server. In your 
        // final version, this should be your SOCS username. 
        super("myusername"); 
    }
    
    /** Choose a move to play */
    public Move chooseMove(Board theboard) {
        // Cast the argument to the object class we want to work with
        PhootballBoard board = (PhootballBoard) theboard;
                
        // Am I Player1 or Player2?
        int myId = this.getColor();
        
        // Pick a move to play somehow...
        // ...
        // ...
        // ...
        
        // Create a move object to send to the server.
	// See the PhootballBoard.java file for a description of the parameters.
        PhootballMove m = new PhootballMove(myId, moveType, destinationRow, destinationColumn);
        return m;
    }
} 
////////////////////////////////////////////////////////////////////////

To run this player instead of the random player, pass it as the argument to the client software:
    java boardgame.Client mypackage.MyPlayer localhost 8123

Documentation:
The boardgame.Player class also provides other methods to be overridden. See the source code for boardgame.Player, phootball.PhootballBoard and phootball.PhootballMove for further documentation.

You are not required to use the provided PhootballBoard and PhootballMove classes in your code. It may be preferable to represent the board in a way better adapted to the particular algorithms you will use, since these classes were written with the server in mind.

In fact, you are not required to use any of the client software provided as long as your player correctly communicates with the server and runs on the SOCS lab machines. Java remains the recommended language, but use whatever you are most comfortable with. (If you're mainly worried about performance, do some research before making a decision.) You are reminded that your code must run on Linux; if you have any special requirements, ask.

Advice

Some hints on writing a winning player:

  1. Play the game against the random player, your player and/or other people to get a feel for the strategy required.
  2. Start small and build up your player incrementally. Here is a natural progression of steps:
    • Figure out an evaluation function for board positions.
    • Encode a minimax-like algorithm with fixed depth (or iterative deepening).
    • Insert alpha-beta pruning.
    • Add whatever other heuristics you think may help.
    • Devise ways to tune the heuristics, manually or, better yet, using learning.
  3. Test your code after each significant change. Make sure you always have a working program.
  4. Experiment to see what effect your changes have. Leave yourself time for tweaking your player and trying out different approaches.
  5. Ask questions if you
    • have trouble understanding the provided code,
    • need help getting started,
    • get stuck,
    • are wondering if your ideas will work,
    • or have any philosophical question, be it about football or not.

Requirements and evaluation

 You should hand in two components:
  1. An implementation of your player program.
  2. A written report documenting your approach.
Both of these components are mandatory in order to receive a passing grade on the project.

Due date:
The due date for your code and report is April 9, 2010 (the last day of classes). The competition will be held starting on Monday April 12, 2010, and will go on for roughly 10 days. Results will be posted on the website as they become available.

Academic integrity:
This is an individual project. The exchange of ideas regarding the game is encouraged, but sharing of code and reports is forbidden and will be treated as cheating. Please see the syllabus and www.mcgill.ca/integrity for more information.

Your implementation can be carried out in the programming language of your choice. The recommended language is Java and supporting code for that language is supplied to simplify your task. You should focus on providing 'intelligence' for your player. The minimum requirement is for your code to be able to defeat the random player that is provided as an example.

It is mandatory that you have a working and documented program. Programs that are not working will not receive credit. Programs that are not documented will not receive full credit.

We will hold a competition between all the programs submitted by students in the class. The competition will play every player against every other player, once as Player1 and once as Player2, in order to ensure fairness. The top 5 players in this competition will receive bonus points. Even if you are not a top player, you will receive bonus points if your approach is interesting and attempts to combine different AI techniques.

The report must be typed and grammatically sound. The suggested length is 5-8 pages (~300 words per page), but the most important part is to produce a report that is clear and concise. The report must include the following required components:

  1. An explanation of how your program works, and a motivation for your approach.
  2. A brief description of the theoretical basis of the approach (about a half-page, in most cases); references to the text of other documents, such as the textbook, are appropriate but not absolutely necessary. If you use algorithms from other sources, briefly describe the algorithm and give a citation to your source.
  3. A summary of the advantages and disadvantages of your approach, expected failure modes, or weaknesses of your program.
  4. If you tried other approaches during the course of the project, summarize them briefly and discuss how they compared to your final approach.
  5. A brief description (max. half page) of how you would go about improving your player (e.g. by introducing other AI techniques, changing internal representation etc.).

Submission instructions

 The project report and code should be sent by e-mail to cs424@cs.mcgill.ca.

All the players will be tested against the random player before the tournament and we will try to contact you if we have trouble running your player. The tournament will be run using SUN Java 1.5 with the -server flag on Linux.

If you have any special requirements (e.g. persistent data), please notify Bob by e-mail () in addition to mentioning it in your README file.