OpenChess

Posted: **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

Posted: **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;
        }
    }

Posted: **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.

Posted: **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.

Posted: **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?

Posted: **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.

OpenChess

Null Move recommendations

Null Move recommendations

Re: Null Move recommendations

Re: Null Move recommendations

Re: Null Move recommendations

Re: Null Move recommendations

Re: Null Move recommendations