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 in the picture below is 6 by 6.

In lab next week we will hold a tournament to determine whose program is the ultimate Konane player. 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.

We will represent the board as a two-dimensional list of strings. 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 loses.

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/labs/3/ directory.

1. Open the file konane.py and read through the definitions provided. The board size must be specified in the constructor for the Konane class. There is also a base class called Player and there are three specializations of this class: HumanPlayer, SimplePlayer, and RandomPlayer. Each of these player definitions inherits from both the Player class and the Konane class. Therefore, the board size must also be specified in the constructors for these classes.
2. In the lab directory do: python konane.py to play one game between the RandomPlayer and the HumanPlayer on 4 by 4 board. Including a True at the end of the call to playNGames will show all of the moves and boards during the game.
3. Comment out the human game, and uncomment the call at the bottom of the konane.py to play one game between the RandomPlayer and the SimplePlayer on an 8 by 8 board. Notice that in this case only the outcome is shown.
4. In the file minimax.py, 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: 'B' or 'W'
5. In the file minimax.py, begin implementing the MyPlayer class that inherits from both the Player class and the Konane. Your class must override the abstract methods initialize and getMove from the Player class. It should also implement several other methods, which are described in the file. Notice that the first line of the MyPlayer 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.
• In the MyPlayer class implement a very basic evaluator for Konane. As a starting point you can simply use the number of moves available to each player. Remember that your static evaluator must work equally well for either player (black or white). It should return infinity for a black win and -infinity for a white win. It should return positive values for nodes containing boards that are good for black, and negative values for nodes containing boards that are good for white.
• Test your static evaluator. You can use small 4 by 4 boards. Be sure that it returns reasonable values for both players.
• Implement the alpha-beta minimax search based on this pseudocode that we discussed in class.
6. Once implemented, test the MyPlayer class on 8 by 8 boards. Your minimax player searching to depth 4 should consistently beat both the SimplePlayer and the RandomPlayer. In addition, your minimax player searching to depth 3 should consistently beat your minimax player searching to depth 1. You can also try searching to depth 4 vs searching to depth 2.
7. Once you have thoroughly tested minimax, you can begin the most interesting and creative part of the assignment--designing a good static evaluator for Konane. Playing a number of games yourself may help you get ideas for what features of the game are key elements to winning. The primary difference between Konane players will be in how they evaluate boards. Based on our reading, the static evaluator should:
   • Order the end states correctly.
   • Be time efficient to compute.
   • Be strongly correlated with the actual chances of winning.
8. Explain your static evaluator in the file evalDescription.txt Discuss the various features you considered including as part of the evaluation function. How did you determine which features were the most effective? This should be between one and two pages of single-spaced text.

In order to make the tournament run smoothly, make sure that you have done the following before running handin63:

1. Remove any executable code from your file minimax.py.
2. Rename the class MyPlayer to contain your last name(s).
3. In the initialize method, reset the name to contain your last name(s).

We will hold a tournament to determine the best Konane players. For each move your Konane player will have a search depth limit of 4 and a time limit of 5 seconds. If a move is not returned within the time limit, then a random move will be selected.

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 Friday, September 30 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.

Once you are satisfied with your programs, hand them in by typing handin63 at the unix prompt.