AI Problem Construct a tree with a branching factor of 3 at each level, and 81 l

Question

AI Problem

Construct a tree with a branching factor of 3 at each level, and 81 leaves. This tree will represent two complete MAX-MIN pairs of moves. The top level of the tree is MAX; the next level (3 nodes) is MIN; the third level (9 nodes) is MAX; the fourth (27) is MIN; and the fifth (81 nodes) are the leaves of the tree, labeled with the following numbers, grouped in sets of 27, and reading from left to right:

837 259 538 257 948 632 495 172 246

147 842 578 246 956 102 453 927 317

956 401 345 123 734 432 827 193 273

As usual, MAX is trying to achieve the highest number; MIN the lowest.

(a) What is the overall value of this tree to MAX?

(b) How many of these leaves 81 leaves actually have to be evaluated by an alpha-beta game search algorithm assuming that possible moves are examined from left to right?(

c) How many leaves have to be evaluated by alpha-beta assuming that movesare examined from right to left?

(d) Suppose the root player is MIN. (That is, the levels of the tree are now MIN, MAX, MIN, and MAX.) Now how many of the 81 leaves have to be evaluated by an alpha-beta searcher if moves are examined from leftto right?

Explanation / Answer

The Algorithm:

Now that we have gained a basic understanding of how Alpha-Beta Pruning works we can examine the actual algorithm in more detail. First I'm going to introduce you to some definitions used by the algorithm. Then we will see some Pseudo Code for the algorithm and finally we will step through a generalized walk through of the algorithm.

Alpha ( œ )

minimal score that player MAX is guaranteed to attain.

Beta ( ß )

An Alternative Definition:

Let Alpha be the value of the best choice so far at any choice along the path for MAX.

Let Beta be the value of the best (i.e. lowest value) so far at any choice point along the path for MIN.

It is important to note that we now have a Max-Value Function and a Min-Value Function as opposed to the minimax function given previously to handle the minimax problem. They both return the minimax value of the node except for nodes that are to be pruned which are simply ignored. Refer below for the actual algorithm.

Back to the Table of Contents

Pseudo Code:

function Max-Value(state, game, œ, ß) returns the mimimax value of state

if CUTOFF-TEST(state) then return EVAL(state)
for each s in SUCCESSORS(state) do

function Min-Value(state, game, œ, ß) returns the mimimax value of state

if CUTOFF-TEST(state) then return EVAL(state)
for each s in SUCCESSORS(state) do

Note: That to actually use this algorithm one needs to combine it with the Minimax Decision Function. See Figure 5.3 in the text

Back to the Table of Contents

Alpha-Beta Search: A Brief Walk through:

Here we are going to go through a generalized run through of the algorithm. It may help your understanding to use a diagram for reference such as Figure 1 shown early in the document.

For each node visited we will assign storage for the path taken to backtrack to that node, a value called Alpha and a value called Beta, as well as the current score for that node.

Set the value of Alpha at the initial node to -Limit and Beta to +Limit. Because initially these are the max values that Alpha or Beta could possibly obtain.

Back to the Table of Contents

Assumptions:

Now with our understanding of how the algorithm works. We are going to examine what the possible gains of this method are over the old minimax algorithm. Before we do that we must note that we are making a number of assumptions about the game. Namely that:

Back to the Table of Contents

Evaluation of Alpha-Beta Efficiency

With the previously listed assumptions taken into account the following gainsimprovements can be calculated.

With Alpha-Beta Pruning the number of nodes on average that need to be examined is O(bd/2) as opposed to the Minimax algorithm which must examine 0(bd) nodes to find the best move. In the worst case Alpha-Beta will have to examine all nodes just as the original Minimax algorithm does. But assuming a best case result this means that the effective branching factor is b(1/2) instead of b.

This translates into a chess game, which normally has a branching factor of 35 having it's branching factor reduced to 6! Simply put this means a chess program running Alpha - Beta could look ahead twice as far in the same amount of time, improving the skill level of our chess program from a novice to an expert level player.

Back to the Table of Contents

An Example using Alpha-Beta Pruning: Tic-Tac-Toe

This is a two player game where each opponent picks a symbol to represent themselves and places them on a 3 by 3 board. The first player to make a complete line wins. This example uses a shockwave animation to show the steps that would be performed if the computer player was using Alpha-Beta search to make it's decisions.

The Players:

Rules:

Back to the Table of Contents

How the Evaluation Function calculates the utility of a move.

Back to the Table of Contents

End State

Animation

You will need to have the shockwave installed in order to view this presentation. There is a version available for Linux, Solaris and Windows machines.

If you don't have the plugin go here Shockwave Web site

If you want to know how to install the plugin go here: Shockwave help

To view the animation from the lectures go here: Tic Tac Toe Animation

The player MAX is the computer player in these examples is 0

The opposition player MIN is the human player in these examples is X

If two collinear board places and a third space in the line is empty, award the player 200 points.

If the player has two nearly complete lines then award the player 300 points.

If the player has a complete line award the player 600 points.

Award the player one addition point for each line that could be completed from his/her current position.

The Evaluation Function calculates the next move by assuming that the opposition will take the best possible move in it's current situation. The utility or worth of a position is calculated by taking the difference between the players score and the opponents score.

For example using the following board above in it's current state the following value of the utility of this game state is 302 for 0 and 201 for X.

So the following the aforementioned rules the utility of this game state is 302 - 201 = 101.

When all possible decisions have been evaluated and the best move has been selected.

Back to the Table of Contents

Disadvantages/Known Problems

So using Alpha-Beta pruning has a number of advantages to it in terms of space/time complexity gains over the original minimax algorithm. So you are probably wondering if this is the best that can be done. In fact it may not be. In addition it does not solve all of the problems associated with the original minimax algorithm. Below is a list of some disadvantages and some suggestions for better ways to achieve the goals of choosing the best move.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.