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

CONTENTS


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


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:

  1. cd to the directory where you want the arbiter directory made
  2. cvs -d /home/osheim/CVS checkout arbiter
  3. cd arbiter
  4. 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.

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. 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