Project 3 -- Loser Takes All
Due: Thursday, March 11, 2004 (no lates)
- To practice in multi-agent environments
- To implement an agent that can potentially use a wide range of
related to search including adversarial search, heuristics,
functions, and many more
- To lose...
In the last project for this course, you'll apply much of
what you have learned about the concept of search to a
agent. The game is Reverse Checkers, where the goal is to lose a
game of checkers. Your job is to build an agent that will accomplish
in as intelligent a manner as possible.
It's Checkers...in reverse!
The rules of Reverse Checkers are as follows:
- Each player starts with 12 checkers placed on a standard 8 X 8
as shown below.
- A player wins reverse checkers by being the first player to have
moves. Normally, this means a player wins by having all of his/her
captured, but a player also wins if his/her remaining pieces have no
- As shown below, checkers move diagonally forward 1 space, or jump
diagonally forward over an adjacent enemy piece to an empty space
beyond. The piece which is jumped over is captured and removed from
A series of jumps with the same piece can be done in a single turn.
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"
becomes a King. Kings move and jump the same as regular checkers, but
and capture backwards as well as forwards.
- If a player has jumps available, s/he must jump. If a piece
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
necessarily the longest one. For example, if a checker can jump 2
by going diagonally to the left, but can only jump 1 piece by going
to the right, the player can choose the single jump to the right.
You may build your agent using
any search algorithms you wish, including those gleaned from other
sources such as the Web
or from other textbooks. (If you do get inspiration from other sources,
make sure to cite them
as references. Of course, you are not allowed to take actual code from
other sources. All code
must be your own.)
You are required to work in teams of two for this project. One of the
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
Minimax? A genetic algorithm? All three? What add-ons should you
employ to speed things up so you can get more plys? An anytime
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:
Your own style of play will affect the behavior of your agent. Don't be
afraid to experiment.
- Perhaps getting Kinged is a bad thing, since a King has more ways of
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
them out will lead to more multiple-piece jumps.
A few ground rules
Though playing style will vary from agent to agent, every team should
implement the following.
- Your team should design your agent to play a 1-player game against a
Either the agent or the human should be allowed to go first.
- Your agent should print every move it makes according to standard
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
A jump is represented by naming the intermediate squares too, such as
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
agent should output the number of moves that the game took. Remember, a
move is 2 plys.
On the last day of class (when the project is due), we will be meeting
in Olin 110
where your agents will compete against each other in a
checkers tournament. A game will be conducted between agents with the
of manual input, where the output of Team 1's agent will be fed in
the human player of Team 2. (That's why you have the UNDO feature -- in
case you make a typing mistake.) Winners of the first round will go on
play each other. Rounds will continue until only one agent is left
The creators of the
winning agent will both receive five extra points on the final exam,
enough to raise
your final grade for the course a full step.
This project is worth double a normal programming project due to
its complexity. No lates will be accepted for this last
Please hand in both an electronic copy of your project on BlackBoard and a paper copy. In
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
searching algorithms into your agent. An agent with one simple type of
coupled with one or two obvious heuristics will not receive as many
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
of the grades, since more sophisticated agents will tend to do better
There's lots to do for this project (which is why I'm giving you three
weeks). Divide up
coding tasks between your partner and yourself. Test all code
Try to think up good ideas on
your own as well as together. Do some research to get more inspiration.
agent over and over. (You'll be sick of checkers by the time the
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 statementProgramming assignments, like homework
assignments, are individual projects. I encourage you to
others about the general nature of the project and ideas about how to
However, the technical work, the writing, and the inspiration behind
be substantially your own. If any person besides you and your teammate
contributes in any way to
the project, you must credit their work on your writeup. Similarly, if
include information that you have gleaned from other published sources,
cite them as references. Looking at, and/or copying, other people's
written work is inappropriate, and will be considered cheating.