CompSci 366 Assignment 1

(Acknowledgement: This assignment has been adapted with permission from Assoc. Prof. Matt Evett of the University of Michigan)

due date 11.59 pm Sunday 7th. May 2006
10% of 366 (marked out of 100)

In the computer gaming world, an AI agent that plays a game is often called a "bot" (short for "robot"). There are many game sites where you can match your wits against other human players, or, if you choose, against an AI—a bot. Develop a checkers-playing bot. Your program should be able to play against other bots via an intermediary checkers server, called Referee. Your program must use the minimax algorithm with alpha-beta pruning. You will have to create your own heuristic function for evaluating board positions. If at all possible, write your program in Java, as Referee will provide an RMI-based interface to allow bots to play against each other without human interaction. (See below for how to accomodate Referee. It is possible for non-Java programs to use RMI as well. The easiest way is to write a short Java-based program that interfaces with your foreign-language program via Java's JNI technology.)

 

We will use the standard American/Britsh rules (frequently asked questions). with one modification: if both opponents have pieces on the board after 100 moves, the side with the most pieces will win. If there number of pieces is equal, the game is a draw. Here is a description of the notation used to indicate board positions and moves.

Specifications:

Black should always play first. Your program should be able to play as either black or white. Your program should use the standard board notation as described above; the black pieces shall start on squares 1-12 and the white pieces shall start on squares 21-32. Your program should specify each move using this notation. For example, Black might start with the move "9 13". Captures are indicated implicitly; Black might capture a white piece on square 14 from square 9 using the move "9 18". If multiple pieces are captured, provide the full movement sequence: "9 18 25", for example, capturing pieces at squares 14 and 22.

Your program should also be able to start from any initial board position, including the locations of all black and white pieces remaining, and an indication of whose turn it is to move. If your program displays the board, please display it with the black pieces on top, as shown in the diagram above. This will help avoid confusion.

Specification of the RMI Interface:

This section specifies how to make sure that your checkers agent can be run by the referee program. The two agents will register themselves with rmiregistry on their respective machines. The referee program then invokes the getMove method on each of the agents, as needed, to effect each game.

In more detail: define your agent class in some package other than "referee". This class must implement the referee.Player interface. This means you will have to provide two methods, getMove() and getName. When you create your agent object, it should be registered with rmiregistry as either "referee.first" or "referee.second". You must be able to specify which!

By the way, rmiregistry should be run from the directory that contains the "referee" directory and your package's directory (your .class files, along with Player.class and your agent class's stub and skeleton .class files will be in the latter).

Once there are two agents up and running you can run the Driver. This will use RMI to connect to the two agents and run two games--each player gets to be White once.

Example Session:

Try running my sample session on your PC with everything running locally.

  1. Download Player.java, HumanPlayer.java, Board.class, Driver.java, CheckersFrame.class, and BoardPanel.class into a directory named "referee". (If you are using Java 1.5, download this Board.class, CheckersFrame.class and BoardPanel.class instead.)
  2. Assuming "referee" is in a directory named "Foo" you should cd to "Foo".
  3. Download permit.txt into Foo.
  4. javac referee/*.java
  5. rmic referee.HumanPlayer
  6. rmiregistry
  7. You'll have to open another console window now, as rmiregistry will keep running until you kill it. In that window, cd to Foo again, and continue:
  8. java -Djava.security.policy=permit.txt referee.HumanPlayer 1 "Mohammed Ali"
    (This will start an agent that relies on human input to determine what move it makes.) You should see the message "Player first (named Mohammed Ali) is waiting for the referee"
  9. Open a third console window, cd to Foo again, and repeat a version of the previous step:
    java -Djava.security.policy=permit.txt referee.HumanPlayer 2 "Joe Fraser"
    (This will start an agent that relies on human input to determine what move it makes.) You should see the message "Player second (named Joe Fraser) is waiting for the referee".
  10. Open yet a fourth console window, cd to Foo again, and continue:
  11. java -Djava.security.policy=permit.txt referee.Driver 20

This will start a two-game match between the agents. The optional command-line argument in step 11 ("20") specifies that each game will automatically end after 20 moves. If you omit the argument, each game will last 100 moves. When the match ends, the Driver will report the score.

So what you have to do is provide another class in lieu of HumanPlayer. To test it against yourself as one of the opponents, change step 9 so that it is starting your AI (and make sure that your AI is registering itself as "referee.second" with rmiregistry.) For example, suppose you develop your AI so that all your classes are in the package Greatest, and that your main class (the one implementing the referee.Player interface) is called Crusher. Thus, all your .java and .class files will be in a directory named "Greatest", and that directory will be a peer to the "referee" directory. Assuming that you use the command-line arguments in the same way that my HumanPlayer class does, step 9 will be:

java -Djava.security.policy=permit.txt Greatest.Crusher 2 "Joe Fraser"

To test your bot against itself, change both steps 8 and 9. I.e., (continuing our example), those steps become:

java -Djava.security.policy=permit.txt Greatest.Crusher 1 "Bobba Fett"

java -Djava.security.policy=permit.txt Greatest.Crusher 2 "Luke Skywalker"

By the way, if you'd like to see the full javadoc for my code, look here.

Hint:

This link leads to a pseudocode representation of the main methods you'll need to complete the assignment.

Warning: there are many checkers playing programs available on the internet. You may certainly examine other programs (including their heurstics) to help you with the assignment. The code you submit, however, must be wholly your own creation--you may not copy or borrow code from another program.

Submission

Sumbit your source code and a short report describing your bot in a single zip archive via the  web drop box.

Marking guidelines