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 - - - - - - whiteBelow 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 whiteIn this lab you will create an AI Hex player.

- 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. - 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/* .

- 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

__If you are working with a partner__, your partner can now pull the changes in:cd ~/cs63/labs/03 git pull

The objectives of this lab are to:

- Use the bounded minimax algorithm to play Hex.
- Improve the efficiency of minimax by adding alpha-beta pruning.
- Create an informative static evaluation function for Hex.
- Test your minimax player against other opponents.

You will need to modify the following python files:

`HexGame.py``Minimax.py`

You will also use the following files:

`Queues.py`, which we've seen several times before`Players.py`, which contains several simple Hex players

Begin by completing the following steps:

- 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'`. - 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. - 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. - 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. - 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

- 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.

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

- Implement the
`basicEval`method to score boards based on how many connected pieces each player possesses. - Implement the
`getMove`method to start the minimax search and return the best move found. - 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

- Thoroughly test minimax. During testing, use print statements during single games to verify that minimax is correctly making random selections between tied best moves.
- 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.

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:

- Not consider the past or future, but just evaluate the current board
- Be efficient to calculate
- Score terminal states correctly with maximal positive values for Black and maximal negative values for White
- Generate scores that are correlated with the chances of winning

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 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.

cd ~/cs63/labs/03 git add HexGame.py Minimax.py git commit -m "final version" git push