Minimax Algorithm Explanation

Question

I'm looking at this pseudocode for the Minimax algorithm:

Function Minimax-Decision(state) returns an action
  ;inputs: state (current game state)
  ;'E' means element of, 'a' is the action
  return a E Actions(state) maximizing Min-Value(Result(a, state))

Function Max-Value(state) returns a utility value
  if Terminal-Test(state) then return Utility(state)
  v <-- -infinity
  for a, s in Successors(state) do v <-- Max(v, Min-Value(s))
  return v

Function Min-Value(state) returns a utility value
  if Terminal-Test(state) then return Utility(state)
  v <-- infinity
  for a, s in Successors(state) do v <-- Min(v, Max-Values(s))
  return v

I think I know how the Minimax algorithm works. You fill "score" values from the bottom up starting from the utility scores. At Max's nodes are the largest of its children, Min's will be the smallest. Max predicts that Min will always try to put Max in the worst position possible for next turn, and using that knowledge, Max tries to make the best move possible.

So for: with order Max,Min,Max from the top

1) Max wants to make the best move for himself (max utility) so C1=5,C2=11,C3=8,etc

2) Max predicts that Min will want to put Max in the worst position possible (restrict Max to smallest utility) so B1=5,B2=2,B3=3

3) Max wants to make best possible move, so A=B1=5

Whats confusing me about the pseudocode is the double recursion, and the purpose of v. Can anyone break this one down for me?

Thanks for reading everyone!

Answer 1

I think you can understand this code by walking through an informal proof by induction that it works for trees of depth d.

For depth 1 you just have a single node and both Min-Value and Max-Value return the utility of this node.

For depth d > 1 consider Min-Value first. v starts off as infinity, so at the first call to Min(v, Max-Value(s)) v gets set to the utility of a child node, as computed by Max, because it is Max's turn after Min, and we know it is correct by induction because it is of depth d-1. (This call amounts to an assignment because v <= infinity), Later calls to Min(v, Max-Value(s)) in this routine end up computing the Min of Max-Value(s) over all children of the node passed in. So Min-Value ends up computing the minimum utility over all children of the node passed in, which is the value of that node to Min when it is Min's turn to move.

The argument for Max-Value is much the same as for Min-Value, so the induction tells you that, for trees of any depth, both Min-Value and Max-Value return to you the value of the node passed to them, when it is Max or Min's turn to move and make the choices associated with that node.

You could also show by induction that what this code does is equivalent to what you have described.

So the double recursion arises because it allows Max and Min to take alternate turns as you walk up the tree from the leaves, and v is a temporary which is used to work out the min or max value of all the child nodes of a tree.