CSc 244

Objectives

• To practice in multi-agent environments
• To implement an agent that can potentially use a wide range of concepts as related to search including adversarial search, heuristics, evaluation functions, and many more
• To lose...

Your Mission

It's Checkers...in reverse!

• Each player starts with 12 checkers placed on a standard 8 X 8 chessboard as shown below.

  

• A player wins reverse checkers by being the first player to have no legal moves. Normally, this means a player wins by having all of his/her pieces captured, but a player also wins if his/her remaining pieces have no legal moves.

• As shown below, checkers move diagonally forward 1 space, or jump diagonally forward over an adjacent enemy piece to an empty space immediately beyond. The piece which is jumped over is captured and removed from the board. A series of jumps with the same piece can be done in a single turn. You cannot jump your own pieces. You cannot jump over the same piece twice.

• When a checker reaches the far side of the board, it is "crowned" and becomes a King. Kings move and jump the same as regular checkers, but may move and capture backwards as well as forwards.

• If a player has jumps available, s/he must jump. If a piece can continue jumping, it must. (i.e. a jumping piece must jump maximally.) However, if a player has a choice of jumps, s/he can choose any of them, not necessarily the longest one. For example, if a checker can jump 2 pieces by going diagonally to the left, but can only jump 1 piece by going diagonally to the right, the player can choose the single jump to the right.

The Details

You are required to work in teams of two for this project. One of the interesting parts of this project is the collaboration between you and your partner. You'll have to make choices and have discussions about what's important: do you implement A*? Minimax? A genetic algorithm? All three? What add-ons should you employ to speed things up so you can get more plys? An anytime algorithm? A quiescent search? What heuristics are important? What weights will be used? How should they be tweaked? Every teams' agent will be different depending on the choices you make.

One good starting point is for you and your partner to play several games against each other so you can start to get a feel of what a favorable board position (state) looks like. This is one way to start forming heuristics. Here's some thoughts to help you get started:

• Perhaps getting Kinged is a bad thing, since a King has more ways of jumping (and thus more ways of helping your opponent) than a regular checker.
• Perhaps getting Kinged is a good thing, since a King has a better ability of running away from a situation where the opponent is trying to force a jump.
• Perhaps keeping your checkers clustered near your starting position is a good thing, since it keeps your opponent from getting Kings and having more options.
• Perhaps keeping your checkers clustered is a bad thing, since spreading them out will lead to more multiple-piece jumps.

A few ground rules

• Your team should design your agent to play a 1-player game against a human opponent. Either the agent or the human should be allowed to go first.

• Your agent should print every move it makes according to standard checkers notation, which is done by labeling the 32 squares that a checker can legally move to, as shown below.

  

  A move is represented by naming the starting and ending squares, such as 11-15. A jump is represented by naming the intermediate squares too, such as 23-14-5. This is how your agent should output its next move and how the human player will input moves. You can represent this as a single string, or have the human input the numbers individually, or whatever. It's up to you. Just don't spend time on a fancy interface. The important part is the AI. The agent, however, should be able to start on either side of the board.

• You should have an UNDO feature that allows the human to take back his/her last move. This is just a safety precaution that may be needed during the tournament (see below).

• After the human player has input a move, your agent has a 1-minute time limit to output its next move.

• When a game is over (and your agent should know when a game is over), your agent should output the number of moves that the game took. Remember, a move is 2 plys.

The Tournament

Grading

Please hand in both an electronic copy of your project on BlackBoard and a paper copy. In addition, you should hand in a brief writeup containing

• what search algorithm(s) you used
• what heuristic/evaluation/objective functions you used
• a description of how you represented states in your agent

I will be grading your project on how well you were able to incorporate good searching algorithms into your agent. An agent with one simple type of search coupled with one or two obvious heuristics will not receive as many points as a more sophisticated agent. Note that your ranking in the tournament will have no direct affect on your grade, though I wouldn't be surprised if the rankings followed the general curve of the grades, since more sophisticated agents will tend to do better (though not always...)

Last Words

Thanks to http://www.jimloy.com/checkers/rules2.htm for the pictures above and to http://www.gamerz.net/pbmserv/checkers.html#rules for some of the phrasing of the rules of Checkers.

Administrative statement