For this lab 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 evalutaion function for estimating the utility of a given Konane board. As mentioned in the reading, "it should be clear that the performance of a game-playing program is dependent on the quality of its evaluation function" (Russell and Norvig, page 171).
You may work with a partner on this lab. If you work as a team, turn in only one copy of the lab and be sure that both of your names appear at the top of every file.
game = Konane(8) game.playNGames(10, SimplePlayer(8), RandomPlayer(8), 0)Notice that the last argument determines whether the moves and the board will be displayed. When this argument is 0, only the final outcome will be shown.
game = Konane(6) game.playOneGame(HumanPlayer(), RandomPlayer(6), 1)
class MinimaxPlayer(Konane, Player): def __init__(self, size, depthLimit): Konane.__init__(self, size) self.limit = depthLimit def initialize(self, side): #complete this def getMove(self, board): #complete thisNotice that the first line of the MinimaxPlayer constructor calls the constructor of the Konane base class. Also notice that the depth limit for the search is passed in as an argument. You should be able to use your MinimaxPlayer in the following way:
game = Konane(8) game.playNGames(2, MinimaxPlayer(8, 2), MinimaxPlayer(8, 1), 0)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
You should not make any changes to the Konane class. However, because the MinimaxPlayer class inherits from the Konane class, you are welcome to override any of the methods provided in the Konane class.
During lab on February 6th, we will hold the tournament to determine whose program is the ultimate Konane player. If your program is not operational for some reason, you must compete against the other programs.