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 evaluation function for estimating the utility 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).
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.
class MinimaxPlayer(Konane, Player): def __init__(self, size, depthLimit): Konane.__init__(self, size) self.limit = depthLimit def initialize(self, side): """ Initializes the player's color and name. """ self.side = side self.name = "MinimaxDepth" + str(self.limit) + "YourLastNames" def getMove(self, board): """ Returns the chosen move based on doing an alphaBetaMinimax search. """ def staticEval(self, node): """ Returns an estimate of the value of the state associated with the given node. """ def successors(self, node): """ Returns a list of the successor nodes for the given node. """ def alphaBetaMinimax(self, node, alpha, beta): """ Returns the best score for the player associated with the given node. Also sets the instance variable bestMove to the move associated with the best score at the root node. Initialize alpha to -infinity and beta to +infinity. """Notice 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 to the class. Therefore you will not need to pass it as an argument to the minimax method. You should be able to use your MinimaxPlayer in the following way:
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
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 September 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.