Author: Peter McKenzie
Date: 15:46:29 05/15/00
Go up one level in this thread
On May 15, 2000 at 17:56:48, Andrew Williams wrote:
>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.
No getting around that I'm afraid.
>
>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.
It is equivalent in the sense that if you search to the same depth, you get the
same score returned by the search. But doing it your way searches a bigger
tree.
The whole point of futility pruning is to avoid making *futile* moves in the
search tree. Your method doesn't achieve this.
>
>EXCEPT that I think I've been doing this one ply too high in the tree. From
true
>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.
right, but then the whole thing would then become somewhat pointless! You would
just be repeating your stand-pat test but effectively with some lazy evaluation.
>
>If any of this doesn't make sense, please feel free to point it out. I'm
>confusing myself now.
I understand what you're saying.
>
>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.