Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Caution K v KBN and lazy eval or futility

Author: Andrew Williams

Date: 14:56:48 05/15/00

Go up one level in this thread


On May 15, 2000 at 16:39:13, Peter McKenzie wrote:

>On May 15, 2000 at 12:03:30, Andrew Williams wrote:
>
>>On May 14, 2000 at 22:47:34, Jon Dart wrote:
>>
>>>On May 14, 2000 at 16:53:46, Brian Richardson wrote:
>>>
>>>>This was discussed in ICCA Vol 21 # 2 (Extended Futility and Dark Thought).  I
>>>>also have tried various regular futility, extended futility and razoring (as
>>>>outlined in the ICCA article), but they did not seem to help, at least given
>>>>Tinker's mix of searching algorithims.
>>>>
>>>>Anyone else getting "good" results with them?
>>>
>>>Arasan has used razoring for the past couple of versions. It is helpful
>>>but the improvement over no razoring is not dramatic.
>>>
>>
>>I've tried razoring, but my program didn't seem to like it.
>>
>>>I looked at Heinz's book but I didn't find his pseudocode (Figure 3.1)
>>>immediately useful, because it assumes that search() starts with making
>>>a move, while most people's search() routine will start with move
>>>generation and will then search the generated moves.
>>>
>>
>>I found it confusing when I read it in the JICCA. In fact when I first
>>implemented it I had a comment to remind myself that what I had was in
>>fact functionally equivalent to Ernst's code, even though it looked
>>different. Here is what I have at the moment:
>>
>>/*
>>This is near the top of my alphabeta(...) routine, just after I check to see
>>if any extensions are necessary. DEPTH is the target depth after extensions
>>have been added. UB is the external upper bound in my mtd(f) implementation.
>>In this context, it is the equivalent of beta in PVS programs. I'm experimenting
>>with this at the moment, and I'm using simple_material_score() instead of
>>evaluate(), because evaluate() is very expensive in my program. Using evaluate()
>>should be safer
>>*/
>>if(ply >= DEPTH) {
>>	abNodes--;
>>	return quiesce(ply, DEPTH, alpha, beta);
>>} else if(!inChk && (ply == (DEPTH-1)) && pcesLeft[WHITE] &&  pcesLeft[BLACK]) {
>>	int sMS;
>>
>>	sMS = simple_material_score();
>>
>>	if(sMS >= (UB + 450)) {
>>		return UB;
>>	}
>>}
>
>This isn't futility pruning
>
>>
>>/*
>>I was chatting with Pete McKenzie the other day about extended futility and
>>saying that it was causing my program to do stupid things. I realised after
>>that I had made a mistake in implementing it, so I'll have to try it again.
>>This is what it should look like (I think).
>>*/
>>  else if( (extensionsAtPly[ply] < ONEPLY) &&
>>            (ply == (DEPTH-2)) &&
>>            pcesLeft[WHITE] && pcesLeft[BLACK] )
>>   {
>>	int sMS;
>>
>>	sMS = simple_material_score();
>>
>>	if(sMS >= (UB + 950)) {
>>		return UB;
>>	}
>>}
>>
>>Obviously, 450 and 950 are arbitrary numbers which could really be
>>anything. If any of this doesn't look right to anyone, I'd be more
>>than interested in hearing about it.
>
>This isn't extended futility pruning
>
>The various types of futility pruning are done when the score is significantly
>lower than alpha, the pruning you are doing is done when the score is
>significantly above beta.
>

That's how I understood it. But I didn't want to put it in my main while()
loop because it was getting untidy with other stuff.

So, my thinking was: Suppose that at the previous ply the score is significantly
below alpha. The other side now makes a move. If it's not a capture, the score
now will be significantly above beta and I can cutoff. I think that what I am
doing is equivalent to what you are describing.

EXCEPT that I think I've been doing this one ply too high in the tree. From
your description below, it looks like I should be doing this as an alternative
to entering the qsearch because I'm doing the test at the next level down in
the search.

If any of this doesn't make sense, please feel free to point it out. I'm
confusing myself now.

Andrew



>The idea of basic futility pruning is that when the score is significantly below
>alpha at frontier nodes (the nodes immediately prior to entering the q-search),
>you only need to examine checks, captures and pawn pushes to 7th and 8th.  All
>other moves are sure to fail low, so we don't bother searching them.  Eg. unless
>you have a very whacky eval function, its *impossible* to fail high by moving
>Kg1-h1 when static score is 2 pawns below alpha (at a frontier node).
>
>Advanced futility pruning is basically the same thing at pre-frontier nodes,
>with the following differences
>- bigger futility margin (typically 5 or 6 pawns)
>- it isn't theoretically sound because it is still possible (although unlikely)
>that a quiet move can cause a fail high even when static score is very low.
>
>>
>>Andrew



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.