CS63 Fall 2005
Lab 3: Minimax Konane
Due: Friday, September 23 by 11am

CONTENTS

INTRODUCTION

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.

GETTING STARTED

  1. Save konane.py to your own directory. Read through the class definitions.

  2. Try executing this file. The main program at the bottom of the file will prompt you to try several test cases. Add to or modify these test cases to get a feel for the game.

  3. Try playing a 6 by 6 game as a HumanPlayer against the RandomPlayer. Or try challenging another person to a game.

LAB INSTRUCTIONS

  1. Implement a MinimaxNode class to hold the necessary information for a search node in a minimax game tree. It should include the following data:
    • state: the current board configuration
    • operator: the move that resulted in the current board configuration
    • depth: the depth of the node in the search tree
    • player: the maximizer or the minimizer

  2. The Player class is the base class for creating a Konane player. Implement a MinimaxPlayer class that inherits from both the Player class and the Konane class as shown below. Your class must override the abstract methods initialize and getMove from the Player class. It should also implement several other methods, which are sketched out below. 
    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.

  3. Implement the alpha-beta minimax search based on this pseudocode.

TOURNAMENT PLAY

Each Konane player should conduct a minimax search to depth 4. The key difference between players will be in how they evaluate boards. Given two Konane players with fixed static evaluators, the game outcome will be deterministic. Therefore, 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 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.

WHAT TO HAND IN

Use cs63handin to turn in these two files. If you worked as a team be sure to include both partner's names at the top of each file.