Lab 3: Hex Game
Due Feb. 15 by midnight

Hex is a type of connection game, which begins with an empty N by N rhombus-shaped board. Players take turns putting down one piece at a time (either black or white) with the goal of trying to form a connected path between opposing sides of the board. In the empty, 6 by 6 board shown below, the White player is trying to link up pieces between the top and bottom of the board, while the Black player is trying to link up pieces between the left and right sides of the board. 

      white
b  - - - - - -  b
 l  - - - - - -  l
  a  - - - - - -  a
   c  - - - - - -  c
    k  - - - - - -  k
        - - - - - -   
            white
Below is an example ending board where the Black player has successfully formed a winning connection (highlighted in blue). 
      white
b  W - B W B B  b
 l  B W B - W B  l
  a  W B W - B W  a
   c  - B B B B W  c
    k  B W W W W B  k
        W - W B B W   
            white
In this lab you will create an AI Hex player.

Starting point code

You are encouraged to work with a partner on this lab. Please read the following instructions carefully.

  1. First you need to run setup63 to create a git repository for the lab.

    If you want to work alone do: 

    setup63-Lisa labs/03 none
    If you want to work with a partner, then one of you needs to run the following command while the other one waits until it finishes: 
    setup63-Lisa labs/03 partnerUsername
    Once the script finishes, the other partner should run it on their account.

  2. For the next step, only one partner should copy over the starting point code: 
    cd ~/cs63/labs/03
cp -r /home/meeden/public/cs63/labs/03/* .

  3. Whether you are working alone or with a partner, you should now add, commit, and push these files as shown below: 
    git add *
git commit -m "lab3 start"
git push

  4. If you are working with a partner, your partner can now pull the changes in: 
    cd ~/cs63/labs/03
git pull
You are now ready to start the lab.

Introduction

The objectives of this lab are to:

You will need to modify the following python files:

You will also use the following files:

Hex Game

Begin by completing the following steps:

  1. Open the file HexGame.py and review the methods that have been provided. Notice that the board is represented as a list of lists, where the inner lists contain single characters. Blank spaces are '-', black's pieces are 'B' , and white's pieces are 'W'.

  2. When you execute this file you can play a game against a random player. Try playing several games to be sure you understand how the game operates. You are expected to enter moves in a row, col format where the rows and cols start at zero. You can try changing the board size from 6 to 4 for a shorter game or to 8 for a longer game.

  3. Open the file Players.py to see the base class for all Hex game players. There are several simple players defined here to make testing easier.

  4. Be sure you understand how the two methods blackWins and whiteWins in the HexGame class work. The next method you will write will have a similar structure.

  5. Implement the method countConnected. We will use this method in our initial static evaluator for Hex. Given a board and a side (either 'B' or 'W'), it should return a count of the number of pieces for that player that are touching another piece of the same color on the board. For example, on the board below there are 5 connected black pieces (highlighted in blue) and 4 connected white pieces (highlighted in red). 
          white
b  W - W - - B  b
 l  W - - B B -  l
  a  B - W - W W  a
   c  - - B - B B  c
    k  - - - W - -  k
        W - - - B -   
            white

  6. Be sure to test your method before going on. In the playOneGame method you can insert additional print statements each time the board is printed to display the number of connected pieces for both sides.

Bounded Minimax

Next focus on the Minimax.py file, and complete the following steps:

  1. Implement the basicEval method to score boards based on how many connected pieces each player possesses.

  2. Implement the getMove method to start the minimax search and return the best move found.

  3. Implement bounded minimax that does a depth-first traversal of the game tree and backtracks when it hits a leaf or the depth limit. Each call to minimax determines a value for the given node. However, for the root node (at depth 0), we also need to determine the best move to make based on the values of its children nodes. It may be the case that several moves share the same best value. You must randomly select one of these equally-valued options as the best move.

    Here is the pseudocode: 

    boundedMinimax(node) 
  """returns value of the node and sets bestMove"""
  if node's depth is at limit
     return staticEval(node's board)
  get all possible moves from the node's board
  if there are no moves 
     return staticEval(node's board)
  initialize a scores list to be empty
  for each move
     determine the nextBoard
     create nextNode with nextBoard, move, updated depth, other side
     # Recursive call
     set score to boundedMinimax(nextNode)
     add score to scores list
  # maximizing
  if node's side is black 
     if node's depth is 0
        set bestMove to a random move with the maximum score
     return max of scores
  # minimizing
  else 
     if node's depth is 0
        set bestMove to a random move with the minimum score
     return min of scores

  4. Thoroughly test minimax. During testing, use print statements during single games to verify that minimax is correctly making random selections between tied best moves.

  5. Once you are certain that minimax is working properly, comment out the print statements and do more extensive tests using a series of games. With a depth limit of 2, your boundedMinimaxPlayer should win the majority of games against a random player. You can use the playNGames method of the HexGame to accomplish this. For example, in 100 games, the depth 2 minimax player should win approximately 85.

    Also searching deeper should improve results. Thus your boundedMinimaxPlayer searching to depth 2 should outperform one searching to depth 1. Similarly depth 3 should outperform depth 2.

Because any open space on the board is a valid move for either player, there is a very wide branching factor for this game. Thus searching with a higher depth limit (of say 4) will be extremely slow. Adding pruning will significantly speed up the search, allowing us to explore deeper.

Better Static Evaluation Function

Come up with an improved static evaluator for the Hex game and implement it in the betterEval method of the BoundedMinimaxPlayer class. In order to accomplish this, you may need to create additional methods in the HexGame class to help analyze the quality of the boards.

You may want to read more about Hex, especially strategies that people use to win.

Your goal is to create an evaluator that will beat the given evaluator (which uses the countConnected method) when tested in a series of games using minimax players with equal depth limits.

Your static evaluator should:

Write a clear and thorough comment with your betterEval method to describe how it works. If you add methods to the HexGame class, include comments describing these as well.

Alpha-Beta Pruning

Alpha-Beta pruning should always return the same scores as Minimax would, but it can potentially do so much more efficiently by cutting off search down branches that will not change the outcome of the search. However, when there is randomness (as occurs with ties), you may get a different best move selected.

In this algorithm, alpha represents the best value for the maximizer and beta represents the best value for the minimizer. Alpha gets updated in recursive calls that are maximizing and beta gets updated in recursive calls that are minimizing. In the initial call to Alpha-Beta pruning, alpha should be initialized to negative infinity and beta to positive infinity. As long as alpha remains strictly less than beta, the search continues. At any point, when alpha and beta cross, the search cuts off.

Note that in the bounded Minimax pseudocode we maintained a scores list at each recursive level. In the alphaBeta Minimax pseudocode we only maintain the scores list at the root. Here is the pseudocode: 

alphaBetaMinimax(node, alpha, beta) 
  """returns value of the node and sets bestMove"""
  if node's depth is at limit
     return staticEval(node's board)
  get all possible moves from the node's board
  if there are no moves 
     return staticEval(node's board)
  if node's depth is 0: initialize a scores list to be empty
  if node's side is black
     v = -infinity
  else
     v = infinity
  for each move in moves:
     create nextNode as you did before
     score = alphaBetaMinimax(nextNode, alpha, beta)
     if node's depth is 0: add score to scores list
     if node's side is black # maximizing
         v = max(v, score)
	 if v > beta: # pruning 
	    return v
         alpha = max(v, alpha)
     else # minimizing
         v = min(v, score)
	 if v < alpha: # pruning 
	    return v
         beta = min(v, beta)
  if node's depth is 0
     if node's side is black
        set bestMove to a random move with max score 
     else
        set bestMove to a random move with min score
  return v

Similarly to your boundedMinimax player, your alphaBetaMinimax player should beat a random player about 80-85% of the time. Your alphaBetaMinimax player should win approximately 50% of the games versus your boundedMinimax player when both search to the same depth and are using the same evaluator.

Searching deeper should improve a player's performance. For example, better static evaluator should allow an alphaBetaMinimax player of depth 3 or 4 to outperform one of depth 2.

Submitting your code

Before submitting, ensure that you have added your name(s) to the top-level comments. To submit your code, you need to use git to add, commit, and push the files that you modified. 
cd ~/cs63/labs/03
git add HexGame.py Minimax.py
git commit -m "final version"
git push