For this problem you will experiment with the Konane playing program from lab by comparing the effects of different search strategies and evaluation functions. You will need to use the lab computers in Science 104 for these exercises. As a reminder, to run Konane, click the IDLE icon in the Dock and then type the following commands at the Python prompt:
>>> import ai >>> ai.konane()
Have the computer play 20 games against itself using the random strategy for each player (Red and Blue), with a board size of 6. How many games are won by Red? How many by Blue? Record your results in the first line of the table below. Are these results about what you expected?
Next, compare the random strategy to the minimax strategy with a search depth of 1. In order to compensate for any asymmetry that might arise from going first (i.e. playing Red), you should perform two separate runs of 20 games each, the first one with Red playing randomly and the second with Blue playing randomly. Use the default static evaluation function (#3) for all of your runs. Record your results in the table below. Does the minimax/depth=1 strategy show a consistent advantage over playing randomly, or are they about even?
Next, compare minimax with a search depth of 2 against a search depth of 1, again playing 20 games each and using evaluation function #3. Record your results in the table below. Does a depth 2 minimax search give a consistent advantage over a depth 1 search? If not, can you explain any discrepencies?
Finally, compare search depth 3 to search depth 4, and record your results in the table below. Does one show a consistent advantage over the other? If not, can you explain any discrepencies?
Now let's compare the effects of using different static evaluation functions with minimax. You should use a search depth of 4 and a board size of 6 for this part. First, compare evaluation function #1 to #2. Function #1 evaluates a board based only on the number of moves available to each player, while function #2 looks only at the number of pieces that are threatened on each side. Perform 20 runs with Red using function #1 and Blue using #2, then 20 more runs with the functions reversed. Record your results in the table below. Does either function show a consistent advantage over the other?
Lastly, compare evaluation function #1 (moves only) to #3 (moves plus threats). Does function #3 show a consistent advantage over #1, or are they about the same? Record your results in the table below.
Red strategy Blue strategy # Red Wins # Blue Wins Advantage? ------------------------------------------------------------------------------- random random random minimax/depth=1 minimax/depth=1 random minimax/depth=1 minimax/depth=2 minimax/depth=2 minimax/depth=1 minimax/depth=3 minimax/depth=4 minimax/depth=4 minimax/depth=3 eval function #1 eval function #2 eval function #2 eval function #1 eval function #1 eval function #3 eval function #3 eval function #1 -------------------------------------------------------------------------------
Suppose the board evaluation function for Tic-Tac-Toe gives +10 for a win for X, -10 for a loss for X, and 0 for a draw. Given the board state below with X to move, draw the entire game tree from this state down to the leaf nodes (the terminal states). Write the value of each terminal state next to it, and then use the minimax algorithm to calculate the optimal move for X. For non-terminal states, write the backed up minimax value next to each state.
Connect-3 (a simplified version of Connect-4) is a two-player game in which the players take turns dropping colored discs into a 3 × 4 vertically suspended grid, with Black making the first move, as illustrated below. The object of the game is to be the first to connect three discs of the same color in a straight line vertically, horizontally, or diagonally.
We can use the following static evaluation function to evaluate a board from Black's point of view: the sum of the number of possible ways to complete three in a row for Black minus the sum of the possible ways to complete three in a row for Red. For example, this function gives a value of -2 for the board shown below:
A portion of the game tree is shown below. The root node of the tree shows the board state after 4 moves have been made. It is Black's turn to move next.
Complete the third level of the tree by showing all of the states that could be generated from the right two nodes on the second level.
Using the static evaluation function given above, evaluate all of the board states on the third level and write the corresponding value below each leaf node.
Show the minimax values that would get backed up to the second and first levels of the tree, and use this to determine Black's move from the position at the root.
In the tree you have constructed, show which leaves do not have to be evaluated if alpha-beta pruning is applied, assuming that the leaf nodes are generated in left-to-right order.
Consider the artificial neuron shown below. This neuron has three input units and a threshold value of 0.5. The weight of each connection is also shown. The output activation of the neuron is 1 if the total net input exceeds 0.5, or 0 if it doesn't.
Complete the table below by calculating the net input and the final output of the neuron for each of the given input patterns:
Input pattern Total net input Output -------------------------------------------------------------- 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Without changing the neuron's threshold value, find a new set of connection weights that will cause the neuron to output 1 if at least two of its three inputs are 1. In other words, the output of the neuron for each of the above input patterns using the new weight values should be as follows:
Inputs Output ---------------------- 0 0 0 => 0 0 0 1 => 0 0 1 0 => 0 0 1 1 => 1 1 0 0 => 0 1 0 1 => 1 1 1 0 => 1 1 1 1 => 1