Need a way to rank game outcomes. The ranking function is called a utility
function. A simple utility function may give 1,0 or +1 for lose,
draw and win.
Consider noughts and crosses with two players called MAX and MIN. If
MAX is X and goes first then the tree is as follows.
Max will always try and maximize the utility function for the terminal
state and min will always try to minimise it.
An exhaustive search of the game tree for a solution is usually not
possible.
Consider the following simple game tree.
The utility function is only applied to terminal nodes. If max makes
move A_{1} then Min should make move A_{11}. Thus the result
of making move A_{1}is a value of 3 for the utility function. Similarly
A_{2} leads to a value of 2 and A_{3} a value of 2. Max
wants to maximise the utility function and so A_{1} is the best
move to make.
Minimax consists of 5 steps.
If the maximum depth of the tree is m and there are b moves at each node then the time complexity of minimax is O(b^{m}) . The algorithm is depth first so memory requirement is O(bm).
Instead of doing this we could use a heuristic evaluation function to estimate which moves leads to better terminal states. Now a cutoff test must be used to limit the search.
Choosing a good evaluation function is very important to the efficiency of this method. The evaluation function must agree with the utility function for terminal states and it must be a good predictor of the terminal values. If the evaluation function is infallible then no search is necessary, just choose the move that gives the best position. The better the evaluation function the less search need to be done.
e.g. the following shows some evaluations of chess positions.
The evaluation function is often a linear combination of features.
In general:
The analysis may stop just before your opponent captures one of your pieces or the analysis stops just before you capture one your opponent's pieces.
This is called the horizon effect: a good (or bad) move may be just over the horizon.
e.g. consider the following chess position. Black is ahead in material
but if white can reach the eighth row with it's pawn then it can win. Black
can stall this for some time by checking the white and so will never see
that this is a bad position.
If you have an idea that is surely bad, do not take time to see how terrible it is.
Consider the following example:
Search proceeds exactly as for minimax evaluating A_{11} A_{12}
A_{13} and A_{1} until, after looking at A_{21},
we find that A_{2} must have a utility less than 2. We now know
that A_{2} is a bad choice because A_{1} has a higher utility
and we need not evaluate any more branches below A_{2} .
The following diagram shows this for a general case.
If we have a better choice m, either at the parent node of n
or at any choice point further up, then n will never be reached
in actual play.
Minimax is depth first, so all that need be remembered is the best
choice found so far for the player (MAX) and the best choice found so far
for the opponent (MIN). These are called alpha and beta respectively.
The following algorithm illustrates this.
Suppose the tree is ordered as follows:
^
____________________________o____________________________
/

\
v ________o________
_______o________
________o________
/
 \
/ 
\ /
 \
^ o
o o
o o
o o
o o
/  \ /  \
/  \ /  \ /  \
/  \ /  \ /  \
/  \
14 15 16 17 18 19 20 21 22 13 14 15
26 27 28 29 30 31 12 13 14 35 36 37 38 39 40
* * * *
* * * *
* * *
Only those nodes marked (*) need be evaluated.
How many static evaluations are needed?.
If b is the branching factor (3 above) and d is the depth (3 above)
s = 2b^{d/2}  1 IF d even
s = b^{(d+1)/2} + b^{(d1)/2}  1 IF d odd
For our tree d=3, b=3 and so s=11.
This is only for the perfectly arranged tree. It gives a lower bound
on the number of evaluations of approximately 2b^{d/2} .The worst
case is b^{d} (minimax)
In practice, for reasonable games, the complexity is O(b^{3d/4}).
Using minimax with alpha beta pruning allows us to look ahead about half
as far again as without.
Now each position has no known outcome only an expected outcome. The
expected value for a chance node above a max node is:
see: http://www.chess.ibm.com/meet/html/d.3.2.html for more details of Deep Blue