Draw recognizers, futility... mess

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Posts: 813
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza

Draw recognizers, futility... mess

Post by PK » Tue Oct 14, 2008 5:38 am

Last evening I tried to test the most primitive of all draw recignizers, which says "with bare kings and no check return 0 without searching further". So I set up the following KPK endgame:

4k3/8/8/8/8/8/4P3/4K3 w - - 0 1

Without a recognizer program knows it will have a queen at depth 24 and reaches depth 30 in 57.000.000 nodes. Then I switched the thing on - node count dropped to 40 millions, but the queen was seen only at depth 27. So I tried another test, without futility pruning - depth 25, but faster than the original version.

Obviously both techniques do not go well together. Futility pruning relies on bounds, and returning 0 changes them.

Come to think about it, I'm not sure if futility pruning should be used in the endgames. After all, null move is switched off too, once material drops below certain limit. And with triggering conditions based solely on bounds, material and being in check, it might prune a winning pawn push (or, as in my test position, a losing pawn push).

Can anybody confirm or negate the point about switching futility off in the endgame?

Harald Johnsen

Re: Draw recognizers, futility... mess

Post by Harald Johnsen » Tue Oct 14, 2008 8:03 am

I think it's just a matter of taste. Obviously with futility pruning you won't see some moves because the margin will not be big enought to include the delta positional value of a pushed pawn. Otoh you could win enought depth (with fp) to compensate and then search two plies deeper.

I don't reduce (lmr) or prune (fp) some pawn moves in 'end games'.

Code: Select all

static INLINE void extension_pawn(const CON *pcon, PSTE pste, const HASHPawn *phashp, const CM *pcm, int &extension, bool &can_reduce, int a, bool isPV) {
    if( moveisPawnMove(pcm) ) {
        // Pawn push to 7th rank
        if( moveto7thRank(pcm) ) {
            can_reduce = false;
            if( isPV )
                extension = 1;
        // no reduction of pawn moves in end game
        &#125; else if ((&#40;pste->valPcUs + pste->valPcThem&#41; <= 1*valQUEEN&#41;) &#123;
            can_reduce = false;
        &#125; else &#123;
            // don't reduce push of passed pawns
            int from = From&#40;pcm->m&#41;;
            bitboard from_64 = IdxToU64&#40;from&#41;;
            if&#40; from_64 & phashp->side&#91;pste->side&#93;.passed )
                can_reduce = false;
    &#125; else if&#40; moveisPromotion&#40;pcm&#41; )
        can_reduce = false;
Note that this code has note been verified (ie, I don't know if it adds anything to the strengh of the engine).


User avatar
Posts: 23523
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller

Re: Draw recognizers, futility... mess

Post by hgm » Tue Oct 14, 2008 8:45 am

This is not a futility problem, isn't it? To see the promotion at d=24 you have to look far over the horizon. With optimal defense the promotion is only at d=27. So it is a hash matter.

Depending on your move ordering, the deep hash entries close to promotion, which you need to get hits on to look over the horizon might only be filled by paths with sub-optimal defence that go through draw positions. E.g. first push the pawn unhindred, while the black King moves between e8 and d8, and then walk the white King to e6 to take opposition.

Post Reply