Null Move recommendations

Code, algorithms, languages, construction...

Null Move recommendations

Postby kickstone » Fri Jul 29, 2016 5:39 pm

Making good progress on my engine thanks to these discussions. Have implemented iterative deepening, PVS, killer moves, and ordering of root moves based on previous iteration node counts. I am now working on null move pruning before I look at LMR and futility pruning. My first cut at null move looks something like this with R = 2:

generate root moves (no null move here) and call alphaBeta(depth - 1, ...., true) // doNullMove = true

then in alphaBeta before generating moves:

if (doNullMove && !inCheck && depth > R) {
nullValue = alphaBeta(depth - R - 1,..., false) // using zero window around beta
if (nullValue >= beta) { return beta }
}

this has sped up the search considerably but as depth goes higher i'm curious what people do to in terms of changing R (adaptive NMR) or other techniques.

I have noticed that some people do not include the restriction depth > R when deciding when to do null move. They just reduce depth and then at the beginning of alphaBeta just add:

if (depth <= 0) { return quiescence() }

so we fall immediately into quiescence search. (fyi i do allow checks in the first two plies of qSearch so this is still a possibility for me)

So are people restricting null move to depth > R or not?

And in terms of making R a function of remaining depth, I know some people use much higher Rs when depth remaining is high. But what is high depth is different for each engine.
Assuming i strive to achieve a 12 ply search. What are people using for R at various depths. If it does change do you use a formula or just an array indexed by depth.

Depth R
12 root (no null move)
11 ?
10 ?
9 ?
8 ?
7 ?
6 ?
5 ?
4 ?
3 ?
2 ?
1 ?

also does anyone try to estimate wether null move is worth doing by restricting null move to lazyEval >= beta ? where lazyEval is material value + pieceSquare (which i update incrementally - so not expensive for me to get)

thanks in advance
kickstone
 
Posts: 14
Joined: Fri Feb 26, 2016 7:27 am

Re: Null Move recommendations

Postby User923005 » Sat Jul 30, 2016 12:56 am

Here is the Stockfish Null move search step:

Code: Select all
    // Step 8. Null move search with verification search (is omitted in PV nodes)
    if (   !PvNode
            &&  eval >= beta
            && (ss->staticEval >= beta - 35 * (depth / ONE_PLY - 6) || depth >= 13 * ONE_PLY)
            &&  pos.non_pawn_material(pos.side_to_move()))
    {
        ss->currentMove = MOVE_NULL;
        ss->counterMoves = nullptr;

        assert(eval - beta >= 0);

        // Null move dynamic reduction based on depth and value
        Depth R = ((823 + 67 * depth) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY;

        pos.do_null_move(st);
        (ss+1)->skipEarlyPruning = true;
        nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -beta+1, DEPTH_ZERO)
                    : - search<NonPV>(pos, ss+1, -beta, -beta+1, depth-R, !cutNode);
        (ss+1)->skipEarlyPruning = false;
        pos.undo_null_move();

        if (nullValue >= beta)
        {
            // Do not return unproven mate scores
            if (nullValue >= VALUE_MATE_IN_MAX_PLY)
                nullValue = beta;

            if (depth < verification_depth * ONE_PLY && abs(beta) < VALUE_KNOWN_WIN)
                return nullValue;

            // Do verification search at high depths
            ss->skipEarlyPruning = true;
            Value v = depth-R < ONE_PLY ? qsearch<NonPV, false>(pos, ss, beta-1, beta, DEPTH_ZERO)
                      :  search<NonPV>(pos, ss, beta-1, beta, depth-R, false);
            ss->skipEarlyPruning = false;

            if (v >= beta)
                return nullValue;
        }
    }
User923005
 
Posts: 606
Joined: Thu May 19, 2011 1:35 am

Re: Null Move recommendations

Postby H.G.Muller » Sun Jul 31, 2016 1:07 pm

Using R > 2 at any depth has never worked for me. But I can imagine it also depends on how much you reduce late moves (which I only reduce by 1).

I also do null move at d=2, and even at d=1, where there is nothing to reduce. I don't see aproblem with dropping directly into QS.
H.G.Muller
 
Posts: 176
Joined: Sun Jul 14, 2013 10:00 am

Re: Null Move recommendations

Postby theturk1234 » Mon Aug 01, 2016 5:22 am

I just add the condition that the depth has to be at least 4 in order to try null move. You look at so few nodes at the lower depths that it's not worth doing null move in my opinion.
theturk1234
 
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm

Re: Null Move recommendations

Postby kickstone » Wed Aug 03, 2016 1:03 am

Thanks...after some extremely limited testing this seems to work for my engine:

bool PVNode = alpha != beta - 1;

I do a null move if (doNullMove && !PVNode && depth > 2 && lazyEval >= beta - 50)

then if depth > 6 i use R = 3 otherwise R = 2.

again lazyEval is just material + piece square values.

Originally i ignored the lazyEval condition completely which was faster than restricting it to lazyEval >= beta. But adding the 50 centipawn margin didn't really slow the search that much so anytime i can decrease the chance of a bad reduction i guess thats good. After a null move I don't allow any other null moves in its subtree. Speed is much better than i imagined.

Anything i'm missing?
kickstone
 
Posts: 14
Joined: Fri Feb 26, 2016 7:27 am

Re: Null Move recommendations

Postby AlexNe » Thu Aug 17, 2017 11:00 am

theturk1234 wrote:I just add the condition that the depth has to be at least 4 in order to try null move. You look at so few nodes at the lower depths that it's not worth doing null move in my opinion.


You're right, it makes sense to do it that way.
AlexNe
 
Posts: 1
Joined: Fri Aug 11, 2017 12:22 pm


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 3 guests

cron