Checkers Bot

 

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 run a competition, pairing off each program against all the others submitted. The author (or authors) of the program that wins the most matches will receive a full grade bonus to their course grade. The second place programs(s) will receive a half grade bonus. The third place program(s) will receive a half grade bonus to their final exam grade. The fourth place program(s) will receive a half grade bonus to their midterm exam grade.

We will use the standard American/Britsh rules. 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.

Your program should not take longer than 5 seconds on average to respond to the referee's request (invocation of getMove()). This time limit will indirectly create a limit in how many ply your bot can look ahead (i.e., how deep your bot will develop the game tree.)

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". Your package should have a unique name, perhaps something like "yournameCheckerBot", or some such. 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 "first" or "second". You must be able to specify which! You'll see that the HumanPlayer class I provide you uses a command line argument to do this, but there are other ways.

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 referee.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 and unzip referee.zip. This should create a directory named "referee" that contains: Player.java, HumanPlayer.java, Board.class, Driver.java, CheckersFrame.class, and BoardPanel.class.
  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. rmiregistry
  6. 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:
  7. 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"
  8. 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".
  9. Open yet a fourth console window, cd to Foo again, and continue:
  10. 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 8 will be:

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

To test your bot against itself, change both steps 7 and 8. 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.

You may want to create your agent by using referee.HumanPlayer as boilerplate. I.e., copy HumanPlayer.java into your package's directory and change the name of the class to something more to your liking. That way you'll get the necessary RMI code.

To start, I recommend first only having your bot play without jumps (this will quickly lead to deadlocks where no pawns can move). In this situation your successor function (which I call ReachableBoards in my pseudocode) will only return those states that are reachable from a given state by a single forward move of a pawn. Once that version of the bot plays, add the ability to make single jumps (captures). Once that plays, you can add the ability to create "kings" (which can move backward or forward). Once that plays, you can add the ability to do double and triple jumps, etc. By taking this iterative approach you should have a working bot by the time of the tournament. Keep in mind, though, that if your bot is presented a board in which it can capture a piece, it must do so, else it will forfeit that game. A game that doesn't handle jumps correctly can still get a good grade but probably won't win the tournament!

If you fiddle with the name you use to register your player with rmiregistry during debugging, and you start getting weird "marshalling" exceptions, you might try killing rmiregistry and restarting it.

N.B. It is critical that your program be able to run with the provided Player.java and Driver.java files. If you modify them for debugging purposes, make sure that you also test them against the original versions before coming to the tournament!

Note that some IDEs automatically delete all .class files whenever they rebuild the current project. As you don't have the source code for Board, CheckersFrame or BoardPanel, you should make sure that those .class files cannot be deleted. One way to do this is to use this .jar file, which contains Board.class, Player.class, CheckersFrame.class and BoardPanel.class (all in the "referee" package). You'll have to set up your IDE to make proper use of the .jar file.

Although it is perfectly possible to fully debug your player with only a single machine, if you have access to another machine on your home network, it would be great to test your system with an instance of your player on two different machines. You'll need to have rmiregistry running on each participating machine. You can run the Driver on either of them (or, indeed, on a 3rd machine!)

If you examine the main() method in the Driver class, you will see that you can easily modify it to test your players without using RMI. Here's the respective code:

 // DEBUGGING: COMMENT OUT EXACTLY ONE OF THE NEXT TWO LINES
 driver.setUpForRMI(); // Set up to use RMI players
 //driver.setUpForDirect();// Set up to use non-RMI based players.

You'll also want to look at the definition of setUpForDirect(). You'll want to modify it so that at least one of the players is an instance of your bot. If you want the bot to play against itself, you'll set both players to be instances of your bot class.

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.