Due: Monday, November 1, 2023
Konane Boards (Hana Cultural Center, Maui - Hawai'i)
Some background on Konane
Due: Monday, November 1, 2023
Konane Boards (Hana Cultural Center, Maui - Hawai'i)
Some background on Konane
This is an Extra Credit Assignment. After the due date, we will have a class touranment where your game player is pitched agains others in a bracket. WInner will get bragging rights.
Note: For this assignment you can use any programming language of your chosing.
Implement a program 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
1 X O X O X O X O
2 O X O X O X O X
3 X O X O X O X O
4 O X O X O X O X
5 X O X O X O X O
6 O X O X O X O X
7 X O X O X O X O
8 O X O X O X O X
First, the dark player removes a dark piece either at position <8, 8>, <1, 1>, <5, 5>, <4, 4>(row-col). Next the light player removes a light piece adjacent to the space created by the first move. In your implementation, you should standardize the opening to the removal of peices at <4, 4> and <4, 5> for the starting configuration. Then the players alternate moves, each jumping one of their 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. While turns are allowed in the board game, we will restrict our moves to straight line moves. For example, after the following moves:
dark light
removes <4, 4> removes <4, 5>
moves <6, 4> to <4, 4> moves <4, 7> to <4, 5>
moves <6, 2> to <6, 4> moves <4, 3> to <6, 3>
moves <2, 6> to <4, 6> moves <3, 4> to <3, 6>
moves <2, 8> to <2, 6> moves <7, 4> to <5, 4> to <3, 4>
the board looks like
1 2 3 4 5 6 7 8
1 X O X O X O X O
2 O X O X O X . .
3 X O X O . O X O
4 O X . . O X . X
5 X O . . X O X O
6 O . O . O X O X
7 X O X . X O X O
8 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:
For the sake of consistency, use the same coordinate system as shown above for specifying moves. Deviation from the above coordinate system will result in grade penalty and also you will default the game in the class tournament (i.e. YOU will play the game instead of your program).
Implement your program in progressive steps: first implement a program that makes random moves on its turn. Save this version. Next, create a version that uses the MINIMAX algorithm to decide the computer's moves. Save this version. Next, implement ALPHA-BETA pruning. Save this version. Next, add any other personal embellishements/strategies to try and improve the program's play.
Play the game by varying the depth of search (from 1 to 6) or ply of 1 to 3 (a ply is two levels: MAX+MIN).
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.
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. 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!).
Konane Tournament
After the assignment is submitted 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.