AI Lab #5

CS63 Fall 2002
Lab 5: Konane
Due: Friday, November 1 by noon

Lab instructions
The arbiter program
Tournament play
What to hand in

LAB INSTRUCTIONS

Implement a program to play the game of Konane, also known as Hawaiian Checkers. You may work in teams of two or three on this lab. We will play the game on an 8 by 8 board of light and dark pieces as shown below (using X for dark and O for light).

     0 1 2 3 4 5 6 7 
  0  X O X O X O X O
  1  O X O X O X O X
  2  X O X O X O X O
  3  O X O X O X O X
  4  X O X O X O X O 
  5  O X O X O X O X
  6  X O X O X O X O        
  7  O X O X O X O X

First, the dark player removes a dark piece either at position (0, 0), (7, 7), (3, 3), or (4, 4). Next the light player removes a piece adjacent to the space created by the first move. Then the players alternate moves, each jumping one of his/her own pieces over one horizontally or vertically adjacent opponent's piece, landing in a space on the other side, and removing the jumped piece. If desired, this may be continued in a multiple move, as long as the same piece is moved in a straight line. The game ends when one player can no longer move and that player is considered the loser.

Try playing against Aaron Carlisle's Konane game from the 2000 AI class to get a better sense of how the game is played.

Implementation details

You may write your Konane player in Scheme, C, or Java.
As a first step, develop the board representation and the expander function that will find all legal moves from a given board configuration. Start with a program that simply picks a random move from the list of possible successors and plays against a human opponent.
Next add the functionality needed to allow your program to play against itself as well as against a human opponent.
Finally, your program should use the Minimax algorithm with alpha-beta pruning to decide its moves. To use Minimax you'll need to develop a static evalutation function. Your evaluator will largely determine the success of your program, so it is worth spending time testing various methods.
Your game does not need a fancy GUI. You may add this feature, but only once the key pieces of the program are working. It is more important to have a solid playing strategy than a flashy interface.
For each game, your program should gather the following data:
1. The number of times a static evaluation was done.
2. The average branching factor.
3. The number of cut offs that took place during the search.
Play the game by varying the depth of search (from 1 to 4) and plot the above results.

THE ARBITER PROGRAM

Thanks to much hard work by Erik Osheim, with help from Tia Newhall, Sean Finney and Daniel Sproul, we now have an arbiter program to help us run the tournament. To get a copy of the arbiter do the following:

cd to the directory where you want the arbiter directory made
cvs -d /home/osheim/CVS checkout arbiter
cd arbiter
make

If you'd like to test the arbiter, I have provided two different konane players called dumb and smarter. The dumb version does not do any search; it simply returns the first move from the list of successors. The smarter version does a minimax search to depth four using a relatively simple static evaluator. The smarter version should win regardless of whether it goes first or second. You can copy them from:

/home/meeden/Public/cs63/lab5-konane

The arbiter expects to receive two executable programs as arguments. The first one provided will go first and will play X, the second one will play O. Your executable must not take any arguments. To run the arbiter do the following:

./arbiter dumb smarter

You will be able to see the game in progress and a log file will be created showing the entire game.

Arbiter Input Requirements

Konane players should take input from the standard input. The input will represent the opponent's move as four integers as described below.

Standard move: col1 row1 col2 row2
This indicates a jump from the initial position (col1, row1) to the final position (col2, row2).
The move: -1 -1 -1 -1
This indicates that the game is just starting and that no move has been made. Your program has been designated to go first and needs to make a valid opening move.
The move: col1 row1 col1 row1
When the two positions are the same, this indicates that the other player went first, and chose to remove the piece at position (col1, row1). Your program has been designated to go second and needs to make a valid response.
The move: -100 -100 -100 -100
This indicates that the other player was not able to make a move. Your program has won and should terminate.
The move: -50 -50 -50 -50
This indicates that an invalid move as occurred. Your program should terminate.

Arbiter Ouput Requirements

Konane players should output to the standard output. The output will represent the player's move as four integers as described below. Your program should not produce any other ouput. Additional output will disrupt the arbiter's communication protocal. All other output should be turned off or sent to a file.

Standard move: (col1 row1) (col2 row2)\0
This indicates a jump from the initial position (col1, row1) to the final position (col2, row2). Notice that the output is terminated by the null character.
The move: (-100 -100) (-100 -100)\0
This indicates that you have no more moves and have lost the game. Your program should terminate.

Note: After printing your move, you should flush the buffer. For example in C, after the printf line, you should call fflush(stdout);.

TOURNAMENT PLAY

Each konane player should conduct a minimax search to depth 4. The key difference between players will be in how they evaluate boards. Given two konane players with fixed static evaluators, the game outcome will be deterministic. Therefore, each konane player will play every other konane player in the tournament twice, one time going first and the other time going second. Each player will receive a +1 for a win and a -1 for a loss. The winner of the tournament will be determined by the cumulative score over all of these games. It will be possible to have multiple winners.

HAND IN

During lab on October 25, we will hold a tournament to determine whose program is the ultimate Konane player. If your program is not operational for some reason, you must compete against the other programs.
Create a tar file of the file containing the tables of results with your discussion and all the program files you created. Use cs63handin to turn in this tar file.

CS63 Fall 2002 Lab 5: Konane Due: Friday, November 1 by noon

CONTENTS