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.
If you want to work alone do:
setup63-Lisa labs/03 noneIf 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 partnerUsernameOnce the script finishes, the other partner should run it on their account.
cd ~/cs63/labs/03 cp -r /home/meeden/public/cs63/labs/03/* .
git add * git commit -m "lab3 start" git push
cd ~/cs63/labs/03 git pull
The objectives of this lab are to:
You will need to modify the following python files:
You will also use the following files:
Begin by completing the following steps:
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
Next focus on the Minimax.py file, and complete the following steps:
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
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:
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