Implement a program (in your favourite 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 54 removes 55
(34 54) (57 55)
(32 34) (53 33)
(76 56) (64 66)
(78 76) (24 44 64)
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:
Play the game by varying the depth of search (from 1 to 5) and plot the above 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. There will be extra credit for implementing a graphical version, however, no credit will be given for any incomplete program that attempts to use graphics.