Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Question for Hyatt about Alpha/Beta

Author: Uri Blass

Date: 11:41:16 02/05/04

Go up one level in this thread


On February 05, 2004 at 13:43:26, Bob Durrett wrote:

>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 is simply wrong impression.

It is clear that evaluation influence the tree that the program searches.

if I evaluate only material and search the opening position to depth 2
I may get a line like 1.a4 a5 in the tree when I may never search that line if I
use a better evaluation(even only piece square table) because 1.e4 may be the
best move at ply 1  and 1.a4 may be refuted by 1...e5 when 1...e5 may be
searched first based on killer moves.

evaluation can also influence pruning because of different threats and different
moves that you prune by null move pruning.

Uri



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.