Lab 4: Game playing

Lab 4: Game Playing
Due March 5th by midnight

Starting point code

This lab my be done alone or with a partner of your choice. Go through the following steps to setup your directory for this lab.

First you need to run setup63 to create a git repository for the lab. If you want to work alone do:
```
setup63 labs/04 none
```
If you want to work with a partner, then one of you needs to run the following while the other one waits until it finishes.
```
setup63 labs/04 partnerUsername
```
Once the script finishes, the other partner should run it on their account.
For the next step only one partner should copy over the starting point code.
```
cd ~/cs63/labs/04
cp -r ~meeden/public/cs63/labs/04/* .
```
Whether you are working alone or with a partner, you should now add all of the files to your git repo, commit, and push them as shown below.
```
git add konane.py minimax.py
git commit -m "lab4 start"
git push
```
If you are working with a partner, your partner can now pull the changes in.
```
cd ~/cs63/labs/04
git pull
```

Introduction

For this lab you will implement the minimax adversarial search algorithm 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 have provided 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 should be clear that the performance of a game-playing program depends strongly on the quality of its evaluation function" (Russell and Norvig, page 171).

Understanding Konane

Begin by playing a game of Konane. When you execute the program konane.py it will run one 6x6 game where you are playing Black versus an automated player that chooses moves randomly playing White. The program will give you a list of all valid moves that you can take on each turn. Simply choose the index of the move, or -1 to concede the game. It is important that you understand the rules of the game before you start trying to implement minimax.

Open the file konane.py. You should not modify this file. However, you should be sure you understand the structure of the classes defined here. There is a Konane class that implements the game. There is a base Player class, and 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. You will be writing another specialization of this class, a MinimaxPlayer, in the file minimax.py.

There are several methods of the Konane class that will be useful to you as you work on minimax.

generateMoves: Given a board and a player, returns a list of all valid moves.
nextBoard: Given a board, a player, and a move, will return the next board.
opponent: Given a player (either 'B' or 'W'), will return the opposing player.
boardToStr: Converts a board, which is represented as a list of lists, into an easier to view string.
playOneGame: Given two players, runs one game between them.

Implementing Minimax

Open the file minimax.py to begin implementing your solution. Remember to use git to add, commit, and push after you complete each section of the code.

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
- move: the move that resulted in the current board configuration
- depth: the depth of the node in the search tree (the depth of the root should be 0)
- player: for the Konane game this will be 'B' or 'W'

Implement an appropriate static evaluator for Konane in the method eval. The key 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
We know that the game is lost once a player runs out of moves to make. Therefore, comparing the number of moves each player has from a given board should be a pretty good measure. As a first pass, create an evaluator that does the following:
```
determine number of black moves
if there are no black moves return worst score
determine number of white moves
if there are no white moves return best score
return black moves - white moves
```
This will return positive scores when black has more moves than white, and will return negative scores when white has more moves than black.
Implement the getMove method. This should create the root node of the search tree, and call boundedMinimax to determine the best move and return it.

Implement the boundedMinimax method. It should should follow the pseudocode below:

boundedMinimax(node) returns an action
   set values to an empty list
   moves = generateMoves(state)
   if no moves return None
   for each move in moves
      nextState = successor(state, action)
      nextNode = node to store the nextState
      add minValue(nextNode) to values list
   return move associated with the maximum of values

There are still two additional helper methods that need to be written: minValue and maxValue. However, it is important to do incremental testing. Let's set up both minValue and maxValue to return random values:
```
return (random() * 6) - 3
```
We can use these random values to help us test the current method. Add some print statements to boundedMinimax using the self.verbose flag so that you can ensure your implementation is correct. For example, at the start of the method:
```
if self.verbose:
   print "BEGIN boundedMinimax"
```
And then at any point where the function returns:
```
if self.verbose:
   print "END boundedMinimax"
```
Also print out the list of values accumulated, the list of possible moves, and the best move found. Ensure that the move being selected is the one that has been assigned the maximum value.

Once you are convinced that boundedMinimax is working correctly, implement minValue using the following pseudocode:

minValue(node) returns value of state in node
    if node at depth limit return eval(node)
    moves = generateMoves(state)
    if no moves return eval(node)
    v = best possible score
    for each move in moves
       nextState = successor(state, move)
       v = min(v, maxValue(node(nextState)))
    return v

Add debugging code to the minValue method, so that you can observe it running. Continue to use the self.verbose flag to make it easy to turn this debugging code on and off as desired. When the function returns, include information about why it returned (e.g. at the depth limit, no valid moves, etc.).
Once you are convinced that minValue is implemented correctly, you can now implement maxValue. The pseudocode for maxValue is the opposite of minValue. Initialize v to the worst possible score and in the loop use max and call minValue.
Add debugging code to the maxValue method, continuing to use the self.verbose flag.
Once all of the methods are completed, you should be able to use your MinimaxPlayer in the following way:
```
      game = Konane(6)
      game.playOneGame(MinimaxPlayer(6, 2, True), SimplePlayer(6))
    
```
Executing the above commands should demonstrate that the minimax player that searches to depth 2 will outperform the simple player that always selects the first move from the list of valid moves.

Testing a deeper search

So far we have only searched to depth 2. Let's try setting the cutoff at depth 4. When self.verbose is set to True this will generate a lot of output. In order to make the debugging output more readable, we can use a node's depth to indent the print statements appropriately like this:

if self.verbose:
   print " " * node.depth + "message ..."

Update the debugging messages within both minValue and maxValue to include this feature. Then try the following test:

      game = Konane(6)
      game.playOneGame(MinimaxPlayer(6, 4, True), RandomPlayer(6))

Your program should now generate debugging output like the following (which was taken from a point near the end of the game):

BEGIN boundedMinimax
 BEGIN minValue
  BEGIN maxValue
   BEGIN minValue
   END minValue no moves returning 1000
  END maxValue, returning 1000
 END minValue, returning 1000
 BEGIN minValue
 END minValue no moves returning 1000
 BEGIN minValue
  BEGIN maxValue
   BEGIN minValue
    BEGIN maxValue
    END maxValue at depth limit returning 2
   END minValue, returning 2
   BEGIN minValue
    BEGIN maxValue
    END maxValue at depth limit returning -1000
   END minValue, returning -1000
   BEGIN minValue
    BEGIN maxValue
    END maxValue at depth limit returning 0
   END minValue, returning 0
  END maxValue, returning 2
 END minValue, returning 2
VALUES [1000, 1000, 2]
MOVES [[3, 5, 3, 3], [5, 1, 3, 1], [5, 3, 3, 3]]
BESTMOVE [3, 5, 3, 3]
END boundedMinimax

Inventing a better static evaluator

Once your minimax implementation is working correctly, you should focus on trying to come up with a better static evaluator. For example, if you play multiple games against the random player, on occasion a minimax player using the number of moves static evaluator will lose. Try to come up with a better static evaluator that can show improved performance against a the random player.

For example, you may want to consider safe moves vs unsafe moves. A safe move is when one player's piece has a jump but the other player piece does not. This happens when the jumping player's piece is on the perimeter of the board and the other player's piece is not.

Be sure to give a clear and detailed explanation of your static evaluator in the comments of the eval method. Discuss the various features you considered including as part of the evaluation function.

Submitting your code

To submit your code, you need to use git to add, commit, and push the files you modified. You should only have changed minimax.py.

cd ~/cs63/labs/04
git add minimax.py
git commit -m "the latest version"
git push