Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: "ALL node" definition

Author: Robert Hyatt

Date: 06:03:43 02/24/03

Go up one level in this thread


On February 24, 2003 at 02:45:08, Tony Werten wrote:

>On February 23, 2003 at 21:46:44, Robert Hyatt wrote:
>
>>On February 23, 2003 at 10:30:26, Tony Werten wrote:
>>
>>>On February 21, 2003 at 23:48:52, Robert Hyatt wrote:
>>>
>>>>On February 21, 2003 at 13:26:34, Alvaro Jose Povoa Cardoso wrote:
>>>>
>>>>>Could someone please define what "ALL node" is and axplain how do we process
>>>>>these type of nodes?
>>>>>
>>>>>Best regards,
>>>>>Alvaro Cardoso
>>>>
>>>>If you look at a perfectly ordered alpha/beta tree, after you search the first
>>>>branch at a node to establish alpha, you search the rest of the branches, and
>>>>at each successor you search only one node (the refutation move).  But at the
>>>>next ply below that you have to search _all_ moves.  This alternates down
>>>>through the tree.  At "all" nodes, move ordering is totally irrelevant.  At
>>>>successors to all nodes, you get "cut" nodes where you only need to search one
>>>>move, if you can search a good move first...
>>>
>>>If you're sure the other moves don't give a cutoff, why bother searching them at
>>>all ?
>>>
>>>Tony
>>
>>
>>I am not sure, as I said.  92% of the time the _first_ move causes a cutoff
>>if one occurs.  That only leaves 8% for the rest.  What is the probability
>>that the good captures, the hash move, the killer moves and a few history
>>moves won't cause a cutoff but a move left over will?  Very low.  But _not_
>>zero.
>>
>>However, this is what forward pruning ideas are based on, and several programs
>>are using the idea to good effect, at the risk of overlooking something that
>>is obscure.  I just haven't elected to take that "jump" yet, but it is on my
>>list of things to play with.
>
>You should I think. That 92% seems quite high. I'm happy with the
>branchingfactor of my program, but I come nowhere near 92%. If I would I would
>certainly try to "report fail low" after trying hashmove, captures, killers, 4
>history, all checks and say 2 highest positional moves.

It is an easy statistic to gather, and it is the fh% number in the crafty
output.  Bruce Moreland and I both played with the idea of such forward
pruning, but neither of us thought it was very reliable.  However, we didn't
try restricting it with respect to depth (ie only near the tips, or 1/2 way
out to the tips, or whatever) and we didn't try a depth reduction rather than
just totally giving up on the remaining moves either (IE search to 1 or 2 plies
less deeply).



>
>Or the opposite. Report fail low at a cut node if the previous ones didn't give
>a cutoff. Might be safer because you'll end up researching the node (and if
>beta-alfa!=1 you won't skip)
>
>Tony



This page took 0.04 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

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