Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!helios!jadam
From: jadam@cs.tamu.edu (James P Adam)
Newsgroups: comp.ai
Subject: Re: Chess question
Summary: Minimax && alpha-beta pruning
Keywords: Chess minimax alpha beta pruning decision tree
Message-ID: <13478@helios.TAMU.EDU>
Date: 19 Mar 91 21:01:10 GMT
References: <1991Mar18.045610.2977@ux1.cso.uiuc.edu> <18585@milton.u.washington.edu> <1991Mar18.184332.12001@ux1.cso.uiuc.edu>
Sender: usenet@helios.TAMU.EDU
Organization: Computer Science Department, Texas A&M University
Lines: 33


>In any game it's always possible to end up in any given "legal" board
>position.  In order to make sure this position doesn't lead to some other
>outcome, all possibilities must be checked.  ( I think the original question
>asked if white should always be able to win. )  
>How does the computer know what positions are going to lead to forced
>mate if it hasnt already checked all the posibilities?

   There is a method known as Minimax, which is used to build a
tree of possible moves, given a "starting state."  A move is made,
and the resulting situation is weighted based on its advantages for
"our" side.  If we are looking at a move that "we" will make, we always
try to go for the move that results in the highest value (max) next
state.  If we are looking at a move that "they" will make, we always
pick the best move for them (i.e., assume they know what they are doing),
thus producing the "min").
    Looking ahead a certain number of moves (a.k.a. "plies"), we can 
choose the best move for us to make now based on the best value state
that we have located later in the tree.
     Still, even looking ahead 2-3 plies in chess--if done exhaustively--
would be a monumental task.  (Figure a couple of hours of processing
time, minimum, on a pretty quick piece of gear.)  So it is necessary
to have some means of culling out moves.  How?  That's the trick, but
it really means building your weighting system well.  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.) 
     Pruning the tree of possible decisions IS necessary, however, and
it is done even in the "world-champion" computers that have specialized
hardware used only for playing chess.
     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.
   Jim