Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Question for Hyatt about Alpha/Beta

Author: Robert Hyatt

Date: 09:41:02 02/05/04

Go up one level in this thread


On February 05, 2004 at 12:22:44, Bob Durrett wrote:

>
>Bob Hyatt:
>
>I was going through the older CCC bulletins to make sure I didn't miss anything
>important and noticed the thread begun by Russell,
>http://www.talkchess.com/forums/1/message.html?345569.  After checking Russell's
>reference, I saw something you wrote cited below.  This made me really curious
>about how the alpha/beta algorithm might be impacted by improvements in the
>position evaluation code.  It seems to me, intuitively, that accurate assessment
>of positional [and other non-material] factors in a position, along with the
>correct assessment of material factors, would give
>values which would change the interpretations of failing alpha or beta tests.
>It seems that this would significantly alter the way searching would proceed.
>
>If this is unclear, I can try to be more detailed if you wish.  [I never claimed
>to be a Pulitzer Prize winning author.]
>
>Bob D.

The point is this:  First we start with a pure minimax framework.  And that
search is going to search a tree of a given size, when given a specific depth
limit.  It is going to find the path to the "optimal" endpoint as defined by the
min/max strategies, using the evaluation function you write.  It doesn't matter
how good or bad the evaluation function is, either, because pure minimax simply
finds the path to the optimal position as defined by the eval.  If you use
material only, or the most sophisticated positional evaluator in the world, you
search the same number of nodes and find the optimal path.

Alpha/beta does the _same_ thing, but by ordering things carefully, and proving
that some branches are irrelevant by the alpha/beta test, we reach the _same_
optimal position, but after searching far fewer nodes.  But the "same" score is
a critical point.

All this means is that your eval can be as gross as you want, but it should not
affect the size of the tree, so long as your move ordering fits your evaluation
function.   IE if your eval maximizes material, but your move ordering is
ordering for give-away chess, then it isn't going to work well because you won't
be searching the minimal alpha/beta tree with that backward ordering.

But if you do them right, the evaluation won't change the size of the tree in
general, although obviously any scoring change can change the size of the tree
if the move ordering code doesn't factor that in at all.  Chess is dominated by
material, and our move ordering takes this into consideration when ordering
moves.  If your eval produces huge positional scores that frequently add up to
way more than a pawn's value, then the move ordering is not working with the
evaluation very well, and the resulting tree will not be optimally sized.

In the below excerpt, hopefully now you see what it means.

Think about a different example:

There are three holes in a wall.  I give you the following assignment:

  "go to each hole, stick your hand in for one minute, and then when
   you have finished, report back and tell me which hole was the least
   unpleasant experience."

You stick your hand in the first hole, and for 60 seconds all you get is a
stream of warm water running over your hand.  You stick your hand in the second
hole, and are met with almost frozen saltwater at around zero degrees Celsius.
Do you stick around in that hole to see if something even worse happens, or is
the freezing water enough to convince you that is is _already_ worse than the
first hole (warm water) you tried?  And, of course, if you wait around any
longer, something even _worse_ might happen.

That is the alpha/beta algorithm.  I only prove that B is worse than A.  I don't
need to know exactly how much worse, that is irrelevant to the task of simply
choosing the best move, overall.


>
>http://groups.google.com/groups?q=%22The+meaning+of+Alpha+and+Beta%22&hl=en&lr=&ie=UTF-8&selm=a6d9ho%24899%241%40juniper.cis.uab.edu&rnum=1
>
>Referenced by:
>
>http://www.talkchess.com/forums/1/message.html?345569
>
>> An alpha cutoff is what happens when you search the second move,
>>> and you prove that if you play that move, your opponent has a move
>>> he can play that will produce a score less than your "lower bound"
>>> you established for the first move.  There is no need to search
>>> further.
>>>
>>> For example, after that +1 on the first move, you try the second
>>> move and after trying the first move the opponent has in reply to
>>> that move, you discover you _lose_ a pawn.  The score is -1.0...
>>> There is no need to search other opponent moves to produce a
>>> score even lower than -1.00, because you already know this move
>>> is at _least_ -1.00 and possibly worse, while the first move is
>>> +1.00.  You stop searching this move and move on to your third
>>> choice...



This page took 0.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.