8
$\begingroup$

Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning):

enter image description here

When marking the the tree with $[\min,\max]$ values bottom-up, we first traverse node $3$ and assign $B.\max = 3$. Then we traverse $12$ and $8$ in this order, it will make sure $B.max = 3$.

But why is $B.\min = 3$? What is the use of that value?

$\endgroup$
  • $\begingroup$ Where is the picture from? Is it an artificial example? $\endgroup$ – uli Apr 6 '12 at 7:21
  • $\begingroup$ Yes,it just an special case example, I also edit the picture to add the text of min and max. If it appear any errors,just feel free to say. Thank you~ $\endgroup$ – sam Apr 6 '12 at 8:16
  • 1
    $\begingroup$ From the (horrible) Wikipedia article, the tree you give does not seem to be a min-max tree. In particular, $B.\max$ should be $12$; $B.\min$, on the other hand, looks completely right. So what it the question here, really? Are you confused by the example, or do you want applications of min-max trees? In any case, please include a precise (!) definition of min-max trees and/or a reference to one. $\endgroup$ – Raphael Apr 6 '12 at 10:34
  • 1
    $\begingroup$ Please include a reference for the picture; I have reason to believe you did not create it. The linked slides may also answer some questions of yours; they seem to use different trees than you do. $\endgroup$ – Raphael Apr 6 '12 at 10:38
  • 1
    $\begingroup$ The picture seems deceptive.. $\endgroup$ – Strin Apr 6 '12 at 14:43
7
$\begingroup$

This figure (which is in fact correct) is used in the explanation of the alpha-beta pruning algorithm on a minimax tree. Alpha-beta pruning is a method used to prune parts of the minimax tree in an adversarial search problem. In the context of a tic-tac-toe game, minimax trees are meant to allow the computer to search through the space of all possible game boards (configurations of x's and o's) assuming the player moves are optimal. This allows the computer to come up with a move that provides the best outcome (this is why the connect-four game on your computer is so incredibly difficult to beat!). For a more complete description, I highly suggest "AI a Modern Approach" by Stuart and Norvig (pg. 162-170 ish in the 2nd ed.).

Now that we've cleared up some confusion on to the algorithm. Alpha-beta pruning tries to avoid expanding subtrees based on how the minimax algorithm works. We know that the max node at the top level will take the largest value of all its children. So, node $B$ finds the value $3$, and so far, this is the maximum value its willing to pass up to its parent so it puts this value in the MAX slot. Then it finds $12$. Remember that $B$ is a MIN node, so it wants to minimize the value it passes up to its parent, thus it keeps the value $3$ in the MAX slot. Again for $8$. When $B$ has searched all of its children, it knows the maximum lower bound ($\alpha$) solution and the minimum upper bound ($\beta$) solution of its subtree and maintains those values in MIN ($\alpha$) and MAX ($\beta$) (as [3, 3]).

Note: min and max labeled in the figure are NOT the minimum and maximum values of the subtree! They are (quite confusingly labeled) the alpha-beta bounds of the solutions of the subtree (remember this is an adversarial search problem).

Next we move to node $C$. Here we come across a $2$ in the first position. Node $C$, wanting to select the lowest value from its subtree now KNOWS that its parent will not pick its value since node $B$ found a larger value already. Therefore, we can prune the rest of the subtree and continue on to $D$.

Finally, to answer the specific question: Why is $B$.min = 3? A value for $\alpha$ (the maximum lower bound of solutions at this node) and $\beta$ (the minimum upper bound of solutions at this node) is maintained at each node in order to perform the pruning. These values bound the possible cases in which the value from a node (or its subtree) may be part of the solution.

In this example, it does not appear to play a role, however, try to look at more complicated examples (i.e. trees with a height > 3) like this one and see if you can make sense of it.

I cannot do justice to minimax or alpha-beta pruning here (mostly because I haven't used them in years), so if you would really like to understand this please check out a book on AI like the one by Stuart and Norvig (the wikipedia page surprisingly has no visualization either).

$\endgroup$
  • $\begingroup$ Yeah, as you said, I think you're totally agree the picture's correctness,right? Thank you for sharing so detailed process of AlphaBeta prunning, and my question is what's the use of minimum value? Is minimum values always be the same with maximum values? In this case is first 3 of [3,3]. $\endgroup$ – sam Apr 6 '12 at 15:52
  • $\begingroup$ @sam, yes, the picture is definitely correct. I've edited my response to (partially) answer your specific question. Hope this helps. $\endgroup$ – Nick Apr 6 '12 at 16:05
  • $\begingroup$ "When B has searched all of its children, it knows the minimium and maximum values of its subtree and maintains those values in MIN and MAX (as [3, 3])" -- but that is obviously not what happens (it should be $[3,12]$, then). Your explanation later makes more sense. $\endgroup$ – Raphael Apr 6 '12 at 17:14
  • $\begingroup$ @Raphael, I should have been more clear. These aren't the min and max values of the subtree, they are the maximum lower bound and minimum upper bound that the node may propagate to its parent. $\endgroup$ – Nick Apr 6 '12 at 17:18
  • $\begingroup$ @Nick: This is how I understood minimax as well. As the OP confused minimax and min-max initially, you should maybe make that very clear in your answer, and include non-trivial example (other than linked). $\endgroup$ – Raphael Apr 6 '12 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.