Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Question for Hyatt about Alpha/Beta

Author: Bob Durrett

Date: 10:43:26 02/05/04

Go up one level in this thread


On February 05, 2004 at 12:41:02, Robert Hyatt wrote:

>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.

I see you are trying to simplify the alpha/beta algorithm for my sake and I
truly appreciate that.  However, in spite of that effort, you are still a mile
over my head.  Anyway, I would never have been dumb enough to stick my hand in
the first hole!  : )

What I'm getting from all this is that you seem to be saying that the quality
and nature of the position evaluation simply are irrelevant when it comes to
shaping the tree [by pruning, etc.].  It sounds like the same branches will be
evaluated NO MATTER WHAT happens in the position evaluation.  That's what I'm
reading, anyway.  It also sounds like the main objective is to minimize the
amount of computer time consumed by the position evaluation code.  Why have any
at all?

What am I missing?

Bob D.

>
>
>>
>>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 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.