Checkers Assignment Networked Checkers Bot Competition Meta Information: Summary Networked Checkers Bot Competition -- build a minimax-based AI that plays checkers against other bots via a provided RMI-based intermediary. Topics Minimax, alpha-beta pruning, game trees, ply-limited search, recursion, heuristics, a brief introduction to remote method invocation. Audience Appropriate for an introductory AI course, though a variant (described below) of the project has been used in a third semester programming course (CS3). The assignment is especially popular with students who are interested in gaming, but even non-gamers have a great time. Difficulty This is an intermediate to advanced assignment requiring about 2 weeks. Strengths Students love this assignment. Though somewhat involved, it is not that difficult to get a relatively weak bot up and running. Students are thrilled the first time they see their bot playing against itself, and even more excited when they test it against their classmates' bots. They then have time to improve their bots behavior before the tournament. This is most students' first exposure to remote method invocation, but they need only understand the rudiments to complete the assignment successfully. Weaknesses Some students struggle with moving their bot from playing against itself on a single machine to playing in our networked labs. This is almost always because they have modified some of the provided code in spite of admonishments against this in the specifications. Dependencies Requires an understanding of minimax, alpha-beta pruning, recursion, trees, and the ability to build from provided code. Variants The assignment can be either individual or team-based. Teams of 2 or 3 are usually best, but individuals sometimes win the tournament. The rules of the game can be simplified by not requiring jumps when they are available. Many students find it difficult to get their bots to conform to this rule. The difficulty of the assignment can be decreased by providing an implementation of alpha-beta rather than pseudo-code. It can be further decreased by providing a partial implmentation of the Board class. Assignment: 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. In this assignment you will develop a bot that plays a game of checkers (also called draughts in some parts of the world) against other bots across a network. At the end of the assignment we will run a tournament between all the bots. The bots scoring highest at the tournament will win extra credit for their creators, as well as the accolades and envy of all! Your bot must use the minimax algorithm with alpha-beta pruning. Because your program is required to select its move in less than 5 seconds, your bot will only be able to look forward a limited number of ply. Consequently you will have to create your own heuristic function for evaluating non-terminal board positions. The relative quality of these heuristics is what will separate the better bots from the rest of the pack. The network communication between the bots will be handled by remote method invocation (RMI). Don't worry if you don't know about RMI--I provide almost all the code that you'll need for the communication between the bots. This will allow you to concentrate on writing the code that will make your bot a great checkers player! That said, here are a few details about how all this works: This assignment provides you with a Java class, Referee, that serves as an intermediary between bots. After a set-up process in which the IP addresses of the two bots are specified, the Referee will repeatedly invoke the getMove() method on each bot. This method is provided, as its parameter, the current position of all the pieces in a game of checkers. Your bot specifies its move as the return value of getMove(). It will be easiest if you program in Java, as this assignment provides you with a test bot the contains all necessary RMI code. You need only base your program on this test bot. However, if you are so inclined, it is possible for non-Java programs to use RMI through use of Java's JNI technology. Speak with me if you are interested in trying this approach. If you've not played checkers/draughts before, you can see a quick video tutorial here and a written tutorial here. The Tournament: On the assignment's due date we will run a competition, pairing off each program against all the others submitted. Here's a video of two bots playing against each other. [This will be provided in the final version of the assignment.] Specifications: 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 the number of pieces is equal, the game is a draw. Here is a description of the notation used to indicate board positions and moves. 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 to respond to the referee's request for a move (via invocation of your bot's getMove() method). 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.) You'll have to experiment with your ply limit to determine how big it can be while still providing a response within the time limit. When developing your bot, I suggest a small ply limit. After you've got most of the kinks worked out, increase the ply limit. 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 bot 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) I'll describe what stubs and skeletons are in class, but, briefly, they are what allow remote method invocations to work. 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. This has the referee control a game between two human-driven bots on the same machine. It's a good way to test that RMI runs properly on your own workstation. 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. Assuming "referee" is in a directory named "Foo" you should cd to "Foo". Download permit.txt into Foo. (This file defines security protocol for RMI.) javac referee/*.java (Compile the code.) rmiregistry (Starts the RMI server.) At this point you'll have to open another console window, as rmiregistry will keep running until you kill it. In the new window, cd to Foo again, and continue: 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" 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". Open yet a fourth console window, cd to Foo again, and continue: java -Djava.security.policy=permit.txt referee.Driver 20 This will start a two-game match between the agents. You should see a window asking for the IP address of the first bot, and then another asking for the second. In this example you can simply use localhost as the IP address in both windows: The optional command-line argument ("20") in step 10 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. Provided everything goes well (i.e., you do not see any error messages regarding RMI or sockets) the Referee class will provide a graphical respresentation of the state of the game as the bots play. In this case the bots are two instances of HumanPlayer, meaning you'll have to enter the moves each bot takes. The format of the input to the bot is start end, where start and end are space separated integers in the range of 1-32. The integers correspond to squares on the checkers board as described above, and which are provided in the graphical display (as can be seen in the image below). The input values, start and end indicate the current location of a piece and the position it should be moved to. Be careful to enter legal values as entering an illegal move results in an immediate loss. [If you provide a second argument to referee.Driver when starting that class, illegal moves are allowed and the playerr is prompted for another move.] Here's an image of a game after two moves: Once you've completed this demo, it's time to create your own bot--you need to provide another class in lieu of HumanPlayer. In the beginning I recommend that you test your bot against yourself as one of the opponents. To do that change step 8 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 something like: 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. Hints: This link leads to a pseudocode representation of the main methods you'll need to complete the assignment. I recommend beginning the process of creating 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 all the necessary RMI code. As a general development strategy I recommend an iterative approach: First, program your bot to play without jumps (be advised that this will quickly lead to deadlocks where no pawns can move--but you'll fix this later). 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, even if you haven't gotten to the last stage. 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! By the way, to properly handle moves that involve multiple jumps you should look for a recursive solution. This can be a bit tricky, but a bit of thought should lead you in the right direction. If you examine the main() method in the referee.Driver class, you will see that you can easily modify it to test your bot against itself 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. Things to watch out for: If you start getting weird "marshalling" exceptions, try killing the bots as well as rmiregistry and restarting them all. 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 bot 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!) 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.
