It gets us into a very simple kind of algorithm, which is the minimax algorithm, which is kind

of epitomized here. When max has, when it's max's turn, then in this game he has nine

choices and wants to take the best one, no matter what min does, in this case min has

eight choices because one field is already taken and min tries to maximize for herself,

which hurts max. So max wants to find the best choice given that min tries to minimize

his chances. The important thing to realize is the utility you get at the end. You know

that you've won or lost only very much at the end, in principle. So the thing that happens

here is we're propagating the utilities back through the minimax tree and that directly

gets us to the algorithm. So we looked at this example in detail. We will look at it

more. So given utilities at the base here, we can see that max can expect a minimal utility

of three because min cannot force the utility lower than three if max has the choice. Min

always takes the minimum of the utility, whereas max takes the maximum, which gives us three

in this case. That's the basic algorithm. Very easy to write down in a mutually recursive

algorithm and it's also very easy to implement. There is a couple of problems. The problem

is even though the algorithm works exactly as we are expecting, updating these max and

min values, in this case is we're doing essentially a breadth-first search. As we know, this grows

very rapidly, which basically means we have to keep the fringe in mind and the fringe

may grow too big before we get the utilities. That is the main problem. That's also something

we're going to optimize around later today. Minimax is wonderful. It's completely infeasible

because it's breadth-first search. There's no way, if you think about it, you can't really

do iterative deepening search here because you want to maximize over all of those if

you want to be systematic.