CS372 Introduction to Artificial Intelligence

Exercise 5 : Game Playing

Konane (Hawaiian Checkers)

Due: Tuesday, November 23, 2004

Konane Boards (Hana Cultural Center, Hawaii)

Implement a program (in your favorite programming language) to play the game of Konane (Hawaiian Checkers). The game is typically played on an 8X8 board of light and dark pieces as shown (using X for dark and O for light).

                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

First, the dark player removes a dark piece either at position 18, 81, 45, or 54. Next the light player removes a light 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 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. For example, after the following moves:

        dark                      light
        removes <5, 4>            removes <5, 5>
        moves <3, 4> to <5, 4>    moves <5, 7> to <5, 5>5
        moves <3, 2> to <3, 4>    moves <5, 3> to <3, 3>
        moves <7, 6> to <5, 6>    moves <6, 4> to <6, 6>
        moves <7, 8> to <7, 6>    moves <2, 4> to <4, 4> to <6, 4>

the board looks 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 . .
        6       X O X O . O X O
        5       O X . . O X . X
        4       X O . . X O X O
        3       O . O . O X O X
        2       X O X . X O X O
        1       O X O X O X O X

Your program should use the MINIMAX algorithm with ALPHA-BETA pruning. For each game, your program should also provide the following information:

  1. The number of times a static evaluation was done.
  2. The average branching factor.
  3. The number of cut offs that took place.

For the sake of consistency, use the same coordinate system as shown for specifying moves.

Play the game by varying the depth of search (from 1 to 6) or ply of 1 to 3, and plot the above results. First implement just the plain MINIMAX algorithm, record the data and plot it. Next, do the same with ALPHA-BETA pruning and record the results.

If you feel inclined to do so, you may use a graphical front end, rather than the text version shown above. However, make sure that all your efforts are initially focused on completing the program as described. If time permits, you may work on the graphics part. You should be able to run your program on computers in the Park 230 Lab.

What to hand in:

A report describing your implementation of the game playing algorithm(s) noting clearly any variations from the standard algorithm. Explain your static evaluation funtion. Compare the data obtained from MINIMAX against ALPHA-BETA and discuss what efficiencies were gained by incorporating pruning. For any additional improvements in your algorithms, try and provide empirical results. Attach a complete listing of your program code at the end of the report.

NOTES:

This is a non trivial project. You are urged to start early (i.e. right away!). Remember, at each stage of completion of the program you have to record empirical data. Plan on completing your program several days earlier than the due date to enable the gathering of this data.

This exercise will be considered equivalent to 3 weekly exercises for credit.

Konane Tournament

On Tuesday, November 23, there will be a friendly Konane Tournament to determine who the ultimate Konane player is. If your program is not operational for some reason, you must compete against the other programs/people.

Back to CS 372 home page