Author: Peter McKenzie
Date: 13:39:13 05/15/00
Go up one level in this thread
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.
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.