You are strongly encouraged to work with a partner on this assignment. Be sure to add both names to the top of every file. Only one of the partners needs to turn in the code.
For this assignment you will implement the minimax adversarial search algorithm with alpha-beta pruning on the game of Konane, also known as Hawaiian Checkers. The game is played on an N by N board of black and white pieces. N may be as small as 4 or as large as 8. The board shown below is 8 by 8, and uses 'B' for black pieces and 'W' for white pieces.
0 1 2 3 4 5 6 7 0 B W B W B W B W 1 W B W B W B W B 2 B W B W B W B W 3 W B W B W B W B 4 B W B W B W B W 5 W B W B W B W B 6 B W B W B W B W 7 W B W B W B W B
In order to play Konane, the black player goes first and removes one black piece from the corner or the center of the board. For an 8 by 8 board, this equates to positions (0,0), (3,3), (4,4), or (7,7). Next the white player removes a white piece adjacent to the space created by the first move. Then the players alternate moves, each jumping one of their own pieces over one horizontally or vertically adjacent opponent's piece, landing in an empty space on the other side, and removing the jumped piece. If desired, this may be continued in a multiple jump, 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.
I will provide you with a Python implementation of the Konane game. You will implement minimax and then focus on finding a good evaluation function for estimating the value of a given Konane board. It has been noted that "the performance of a game-playing program is dependent on the quality of its evaluation function" (Russell and Norvig, page 171).
Do an update63 to get the files you'll need in your cs63/homework/04/ directory.
game = Konane(8) game.playNGames(2, MinimaxPlayer(8, 2), MinimaxPlayer(8, 1), False)Executing the above commands should demonstrate that the minimax player which searches to depth 2 will outperform a minimax player which only searches to depth 1.
Game 0 MinimaxDepth2 wins Game 1 MinimaxDepth2 wins MinimaxDepth2 2 MinimaxDepth1 0
We will hold two tournaments. One tournament will have both a depth limit of 4 and a time limit of 5 seconds. The other tournament will have only a time limit of 5 seconds.
Each Konane player should conduct a minimax search and return a move within 5 seconds. If a move is not returned within the time limit, then a random move will be selected. In addition, each Konane player may not use more than half a gigabyte of memory. This can be monitored using the top command.
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. 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.
During class on Tuesday, October 23 we will hold the tournament to determine whose program is the ultimate Konane player. If for some reason your program is not operational, you must compete against the computer champion.