CS63 Spring 2004
Lab 2: Minimax Konane
Due: Friday, February 6 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 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.

LAB INSTRUCTIONS

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

  2. Try executing this file by doing: python konane.py
    This will play one game between a SimplePlayer and a RandomPlayer on a 4 by 4 board.

  3. Rather than playing one game at a time, you can play a series of games using the playNGames method. Try playing 10 games between the SimplePlayer and the RandomPlayer on a 8 by 8 board by changing the last two lines in the file to: 
    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.

  4. Try playing a 6 by 6 game against the RandomPlayer by changing the last two lines in the file to: 
    game = Konane(6)
game.playOneGame(HumanPlayer(), RandomPlayer(6), 1)

  5. Notice that 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. 
    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 this
    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. 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.

  6. Once you are ready to turn in your solution, change the name of your MinimaxPlayer class so that it begins with a unique team name. Be sure to set the self.name class variable to this new team name as well.

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 and a -1 for a loss. 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 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.

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.