CPSC 430A: Artificial Intelligence

Spring 2005

Assigned: Friday, Feb. 18, 2005

Due: Monday, Feb. 28, 2005, 11:30am

The game of Konane (Hawaiian checkers) is played by two players on an nxn board where n is an even number. As an example, an 8x8 board game starts off with the pieces for the two players arranged as:

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

(We will refer to the player playing the X pieces as X and the player playing the O pieces as O.) First X removes a piece either at position (1,1), (8,8), (4,5) or (5,4). Next O removes a piece adjacent to the space created by X's first move. For example, suppose X removes the piece at (4,5), and then O removes the piece at (4,6), the board would look like:

        1  2  3  4  5  6  7  8
    
    8   X  O  X  O  X  O  X  O
    7   O  X  O  X  O  X  O  X
    6   X  O  X  O  X  O  X  O
    5   O  X  O  X  O  X  O  X
    4   X  O  X  O  .  .  X  O
    3   O  X  O  X  O  X  O  X
    2   X  O  X  O  X  O  X  O
    1   O  X  O  X  O  X  O  X

Then X and O alternate moves, each jumping one of his/her own pieces over one horizontally or vertically adjacent 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 first player who cannot make a legal move loses.

Write a program in lisp to play Konane. The size of the board is one of the inputs to your program.

Your program must make its move by using the alpha-beta pruning algorithm with a d-ply search, i.e., the search tree should be expanded so that the program makes d moves and the opponent makes d moves. Your program should get d as a parameter to the main function. Your program must implement the complete alpha-beta pruning search strategy, i.e., alpha and beta values must be used/updated at each possible node in the search tree, rather than updating one global alpha value and one global beta value.

The choice of whether the computer plays first or the opponent plays first is also an input to your main function.

For example, your program, a lisp function called playKonane, could be called as:

(playKonane 8 4 0)

to mean that the board has size 8x8, that the computer should use a 4-ply alpha-beta pruning search, and that the computer plays first. (A 1 as the last parameter will indicate that the opponent plays first.)

Submission

Create a directory called Konane. This directory should contain all the lisp files you use for your program, a script of a sample game played by your program, and a a short write-up (in a plain text file) explaining your evaluation function, and how you could make it better. Then, in the parent directory of Konane, type the command (when on cs.roanoke.edu or any second floor lab computer in Linux)

submit 430 Konane

You should submit your programs no later than 11:30am on Monday, February 28, 2005.