Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!hsdndev!cmcl2!lanl!cochiti.lanl.gov!jlg
From: jlg@cochiti.lanl.gov (Jim Giles)
Newsgroups: comp.ai
Subject: Re: Chess question
Keywords: Chess minimax alpha beta pruning decision tree
Message-ID: <18415@lanl.gov>
Date: 19 Mar 91 23:19:45 GMT
References: <1991Mar18.045610.2977@ux1.cso.uiuc.edu> <18585@milton.u.washington.edu> <1991Mar18.184332.12001@ux1.cso.uiuc.edu> <13478@helios.TAMU.EDU>
Sender: news@lanl.gov
Reply-To: jlg@cochiti.lanl.gov (Jim Giles)
Organization: Los Alamos National Laboratory
Lines: 111

In article <13478@helios.TAMU.EDU>, jadam@cs.tamu.edu (James P Adam) writes:

|> [...]                                                 It needs to know
|> the difference (in chess) between a lost-piece-gambit that results in
|> superior positional power && simply a lost piece.  (Etc., etc., etc.) 
|> [...]
|>      This method of pruning, by the way, is referred to as "alpha-beta"
|> pruning.  It's an algorithmic approach that certainly has plenty of
|> specific applications in chess programming.

This description is not true.  Alpha-beta uses the same evaluation 
function as the ordinary minimax search.  Furthermore, it gets
the _same_ result as the corresponding minimax search would.  To
see how, consider a game where each player always has three options
and you're going to search three plies deep:

  p1:
    p11:
       p111:
       p112:
       p113:
    p12:
       p121:
       p122:
       p123:
    p13:
       p131:
       p132:
       p133:
 ...

Here the numbers after the colons are the value assigned to the
position by the evaluation function.  Note, I haven't filled in 
these values - that's the job of the search!  At each step, player
one would pick the best (max) of the pn or pnnn positions and
player two would pick the worst (min - all numbers from player
one's point of view).

The search goes as follows: traverse the tree depth first and evaluate
the leaf p111.  Say that this value is zero.  Continue depth first
evaluating p112 and p113: with values (say) of -10 and +10 respectively.
Now back up the max of these to p11 - player one clearly prefers +10
and the third ply is his turn.  So p11 is +10.  Now, continue the
search down the p12 arm.  Say the value of p121 is +20!  This means 
that p12 will be at least +20 since no matter what p122 and p123 are,
unless they are eve larger than +20, player one will always select
p121.  _BUT_ since ply two is the second player's turn, and he wants
the minimum score, you _already_know_ that player two will _not_
pick p12.  So, you don't have to evaluate p122 and p123 at all.

This is the gist of alpha-beta pruning.  The final table(with * for
branches not evaluated) may look like this:

  p1: +10
    p11: +10
       p111: 0
       p112: -10
       p113: +10
    p12: +20 (or more)      alpha is +10
       p121: +20
       p122: *
       p123: *
    p13: +12 (or more)      alpha is still +10
       p131: +3
       p132: +12
       p133: *
  p2: -2 (or less)          beta is +10
    p21: -2
       p211: -5
       p212: -20
       p213: -2
    p22: *
       p221: *
       p222: *
       p223: *
    p23: *
       p231: *
       p232: *
       p233: *
  p3: -10 (or less)         beta is still +10
    p31: -10 
       p311: -10
       p312: -12
       p313: -15
    p32: *
       p321: *
       p322: *
       p323: *
    p33: *
       p331: *
       p332: *
       p333: *

Note that at p2 and p3, pruning was applied higher up than the bottom
level.  The term alpha-beta refers to the fact that you keep track
of the highest score that's plausible to be backed up to the next level
(the alpha) as well as the lowest plausible score (the beta).  Any
even ply node which has a descendent higher than the current alpha
is not worth pursuing further.  Any odd ply node with a descendent 
less than the current beta is also not worth further study.  I have
noted the alphas and betas on the right in the table.

I apologise for the length of this post, but I wanted to post 
the whole table so that people could verify for themselves that
the backed up values are valid no matter what the * positions
evaluate to.  Obviously, in this game, player one will pick move
p1, then player two will pick p11 and player one will then pick 
p113.  This is no accident - alpha-beta produces more cutoffs if
the most viable moves at each level are examined first.

J. Giles