Verification search

[lkaufman]

Are you saying that Houdini is 4x faster than Ivanhoe at seeing tactics in general, or is it specifically on tactics involving attacking the king? I know of one or two changes in Houdini that help see king-attack tactics, but I believe they have almost no measurable elo-benefit.

[diep]

Are you saying that Houdini is 4x faster than Ivanhoe at seeing tactics in general, or is it specifically on tactics involving attacking the king? I know of one or two changes in Houdini that help see king-attack tactics, but I believe they have almost no measurable elo-benefit.

It' s a mix of tough positions where a difficult (for computers) best move has to be found, from games mine mostly that i collected over the years.

Ranging from a better move in openingspositions to just mating the opponents king to exchange sacrafices in order to positionally win the game.

All those Fruit/Rybka clones have usually near 100% identical evaluation,
with piece square tables and material evaluation. In fact most have very little passed pawn logics in evaluation. Everything well tuned.

So most of the elo difference then is not evaluation yet search.

Small differences in search you see have hundreds of elopoints impact then.

The most important observation there is that getting more plies that hardly increase the chance of finding a better move hardly is losing it from changes that pick up more. Typically you see such changes in search that pick up more lose you a ply or 2, yet it's elowise a lot stronger.

But well look realistic around, ivanhoe is doing futility last 10 plies or so. How would you expect that to increase playstrength that much?

If i'd do last 10 plies futility in Diep i'm also gonna get 30 plies deep each move, but i bet i lose 300 elopoints

[Don]

Are you saying that Houdini is 4x faster than Ivanhoe at seeing tactics in general, or is it specifically on tactics involving attacking the king? I know of one or two changes in Houdini that help see king-attack tactics, but I believe they have almost no measurable elo-benefit.

It' s a mix of tough positions where a difficult (for computers) best move has to be found, from games mine mostly that i collected over the years.

Ranging from a better move in openingspositions to just mating the opponents king to exchange sacrafices in order to positionally win the game.

All those Fruit/Rybka clones have usually near 100% identical evaluation,
with piece square tables and material evaluation. In fact most have very little passed pawn logics in evaluation. Everything well tuned.

So most of the elo difference then is not evaluation yet search.

Small differences in search you see have hundreds of elopoints impact then.

The most important observation there is that getting more plies that hardly increase the chance of finding a better move hardly is losing it from changes that pick up more. Typically you see such changes in search that pick up more lose you a ply or 2, yet it's elowise a lot stronger.

But well look realistic around, ivanhoe is doing futility last 10 plies or so. How would you expect that to increase playstrength that much?

If i'd do last 10 plies futility in Diep i'm also gonna get 30 plies deep each move, but i bet i lose 300 elopoints

You have to do what works for the ELO. We prune pretty heavily too and we are aggressive with reductions. But if we don't do that we lose ELO. We don't care how many ply of search we get, we only care about how strong it plays.

[Eelco de Groot]

Sometimes I think Houdini does not do Nullmove, so it never stops searching... Recursive nullmove can shave off a lot of depth, no limit if it weren't for the reduction itself running out of enough plies to reduce.. After a reciprocal null move is done suddenly you have legal positions again. Very weird stuff, amazing that it works so well in general! I have no way of measuring it but I think, very uneducated guess, nullmove reduces very roughly about as much as Late Move Pruning and Futility Pruning (not counting LMR) in Rainbow Serpent, measured against non reduced moves. Just a gut feeling, could be very wrong. RS does LMP and Futility everywhere in the last 24 plies still, so compared to that Ivanhoe is like a knight with agoraphobia 10 plies, pffft. There must be a way to strengthen the verification search though. I know Ryan Benitez has discovered a trick to improve nullmove in the source in less than 5 minutes for Fruit for an improvement by twenty elopoints, and on this forum only Chris Conkie was told how to do it. But we never found out what it was. It can't be in new Fruit's verification search though because Ryan abandoned doing that.

Didn't sleep too well because I wanted to do something like that, how hard could it be to find such a thing? But I don't think I am really on to it yet. I did think of a way to 'link' nullmove and the verification search a little bit like in Glaurung was done by Tord with the threatmove that links nullmove search with the full search. But because the nullmove will have failed high in case of verification, you do not have a 'real' threatmove, as the response move to nullmove (I call this the 'repair' move) does not cross alpha. But on the plusside, you have tried almost every illegal move possible after the nullmove, trying to find that cut-off. On the downside again there is no way to know the best move in an All-node and the deeper you search the worse the estimate of the real value is going to be, if you even store such a thing. But still, I think there is something you could do with the stored move, if you do actually do store the move that is still called the bestmove in Stockfish, even if it is very little. I call the result a 'weak threatmove' and because verification search does not do a nullmove in the first ply, you can replace a 'real' threatmove with this 'weakThreatmove' that I thought up in the half hour I gave myself to find Ryan's five minute change. It is likely I messed up the implementation, but this is what I got done after half an hour between sleepcycles:

Previous version:

Code: Select all

    // Step 7. Static null move pruning (is omitted in PV nodes)
    // We're betting that the opponent doesn't have a move that will reduce
    // the score by more than futility_margin(depth) if we do a null move.
    if (   !PvNode
        && !ss->skipNullMove
        &&  depth < RazorDepth
        && !inCheck
        &&  refinedValue - futility_margin&#40;depth, 0&#41; >= beta
        &&  abs&#40;beta&#41; < VALUE_MATE_IN_MAX_PLY
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return refinedValue - futility_margin&#40;depth, 0&#41;;

    // Step 8. Null move search with verification search &#40;is omitted in PV nodes&#41;

changed to:

Code: Select all

    // Step 7. Static null move pruning (is omitted in PV nodes)
    // We're betting that the opponent doesn't have a move that will reduce
    // the score by more than futility_margin(depth) if we do a null move.
    if (   !PvNode
        && !ss->skipNullMove
        &&  depth < RazorDepth
        && !inCheck
        &&  refinedValue - futility_margin&#40;depth, 0&#41; >= beta
        &&  abs&#40;beta&#41; < VALUE_MATE_IN_MAX_PLY
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return refinedValue - futility_margin&#40;depth, 0&#41;;
        else if &#40;ss->skipNullMove
            &&  &#40;ss-1&#41;->currentMove != MOVE_NULL
            &&   ss->threatMove != MOVE_NONE
            &&   depth > ONE_PLY
            &&  !PvNode
            &&   ss->currentMove == MOVE_NULL&#41; //&#91;We are in verificationsearch&#93;
            &#123;
                 weakThreatmove = ss->threatMove;
                 ss->threatMove = MOVE_NONE;
            &#125;


    // Step 8. Null move search with verification search &#40;is omitted in PV nodes&#41;

Previous version:

Code: Select all

            // Do verification search at high depths
            ss->skipNullMove = true;
            verificationValue = search<NonPV>&#40;pos, ss, alpha, beta, depth-R*ONE_PLY&#41;;
            ss->skipNullMove = false;

            if &#40;verificationValue >= beta&#41;
                return nullValue;

changed to:

Code: Select all

            // Do verification search at high depths
            ss->skipNullMove = true;
            ss->threatMove = (ss+1)->currentMove;
            verificationValue = search<NonPV>&#40;pos, ss, alpha, beta, depth-R*ONE_PLY&#41;;
            ss->threatMove = MOVE_NONE;
            ss->skipNullMove = false;

In Step 13:

Code: Select all

&& (!threatMove || !connected_threat(pos, move, threatMove))

changed to:

Code: Select all

&& (!threatMove || !connected_threat(pos, move, threatMove))
&& (!weakThreatmove || !connected_threat(pos, move, weakThreatmove))

Of course I have to declare weakThreatmove and make sure it gets evaluated in Splitnodes too so changes to thread.cpp and thread.h were necessary too, for me that is by far the most complex part to make changes and where most compilation errors are possible. But that is more obvious to the better programmers here, I will leave those changes out from this posting. So only very little changes had to be made in the (modified) Stockfish code, the effect of which are unknown though:

I have no idea if this is actually doing some good as it actually increases the possibility of a nullmove pruning, not more safe nullmove pruning, because the verification search does less futility pruning; there are slightly more moves searched there that can cause the verification search to fail high. It still may be more accurate though but I have no idea at the moment, only ran McMad's latest testposition and only with this new version so far.

Eelco

[diep]

Eelco, maybe get some sleep first!