Null Move Pruning giving the opposite result

[pedrojdm2021]

Hello, i am new on this world of chess programming, i am enjoying it so far but, i have been trying to implement the null move pruning into my chess engine, but it seems to increment very much the searched nodes count instead of actually reducing it

My null move check (i am doing my engine in C#):

Code: Select all

int legal_moves = 0;
            if (inCheck) _depth++;

            if(_depth >= 3 && !inCheck && ply > 0 && _alpha == _beta -1)
            {
                // switch side
                board.current_state.sideToMove ^= 1;
                
                score = -Negamax(_depth - 1 - 2, -_beta , 1 -_beta  , false);
                // restore side & state
                board.current_state.sideToMove ^= 1;
               
                System.Console.WriteLine("After null make && undo score " + score + " beta " + _beta);

                if (score >= _beta)
                {
                    System.Console.WriteLine("cutoff");
                    return _beta;
                }
             }

when i run the following position with search depth of 4 i get this log:
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

Code: Select all

After null make && undo score 24 beta 25
After null make && undo score 24 beta 25
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
bestmove e2a6 bestscore -15
nodes searched: 87522 in 561ms

without null move pruning, i get this:

Code: Select all

bestmove e2a6 bestscore -15
nodes searched: 36869 in 312ms 

I don't know what i am doing wrong, everything seems ok in terms of code, but i think my search is searching unnesary "null" moves, or i don't know.
anyone has any idea on what could be happening?

what i have so far:
- tranposition tables
- Negamax + alpha-beta + Principal Variation search
- three fold repetition
- Basic material evaluation with piece tables + Mopup Evaluation

[Fabio Gobbato]

Try to avoid 2 null moves in a row. If in the previous ply of the search you have launched a null move search at the current ply you should avoid another null move search.

[MartinBryant]

1: I think some engines have allowed two null moves in a row in the past (maybe some still do?) but as Fabio suggests it might be easier to rule that out by e.g. adding another parameter 'allowNull' to your Negamax function.

2: You don't appear to be updating your TT hash when you switch sides (unless it's embedded in your sideToMove property?) which surely you have to do?

3: It looks like you are only reducing by 2 ply. Bob (Robert Hyatt author of Crafty) did some very extensive tests many years ago that IIRC showed a reduction of 3 to be better than 2 or 4.

Also, I like C# as a language but if you really want speed you should consider C or C++

[niel5946]

Just to elaborate on Fabio’s answer: Keep a “do_null” boolean flag as parameter to the alphabeta method. When you do a null-move, set this to false. Otherwise, you can set it true (for example when looping through all the moves).
The reason for this is that if you do a null-move, you effectively give the opponent a free move, but if you do it again immediately in the next ply, it counts as just giving the move back to you. The effect of this is two fold: 1) The null move itself gets cancelled out, and 2) The returned scores are unreliable.

Additionally, you should make sure to remove the en-passant square (if there is any) before making the null move. Then you can insert it again when you undo the null move.

[hgm]

There should not be any significant effect of doing arbitrary large numbers of null moves in a row, so don't expect disallowing that to solve any problem.

Whether you need a hash-key update on null move depends on whether you account the side-to-move part of the key incrementally or each time you use the key. (Which is an equally valid method, as the stm changes on every move, and each node uses it only once, so there is no benefit whatsoever from handling it incrementally.) If you handle this wrong, it could be responsible for the observed anomaly.

Reducing 3 ply for null move instead of 2 has always been an enormous Elo loss in all my engines. Even when done only above some depth limit ('adaptive null move').

[Henk]

By the way if you do two null moves in a row you get same position again. So you may count it as a two or three fold repetition draw.
Looks like you have to treat a null move like a capture or pawn move to avoid this or not? That is clear the position history.

[hgm]

Correct. You should not count null-move-spanning repeats as draws. That is extra important when you allow 'double null move', but even with sinlge null move you can get a line like move - null - reverse move, and it would be a shame if you now cannot refute that reverse move with another null because it would produce an undesired draw.

[pedrojdm2021]

1: I think some engines have allowed two null moves in a row in the past (maybe some still do?) but as Fabio suggests it might be easier to rule that out by e.g. adding another parameter 'allowNull' to your Negamax function.

2: You don't appear to be updating your TT hash when you switch sides (unless it's embedded in your sideToMove property?) which surely you have to do?

3: It looks like you are only reducing by 2 ply. Bob (Robert Hyatt author of Crafty) did some very extensive tests many years ago that IIRC showed a reduction of 3 to be better than 2 or 4.

Also, I like C# as a language but if you really want speed you should consider C or C++

Yes i tried that, nothing happends aparently, tried setting-up a extra condition to avoid three fold in null move as suggested, tried with reduction of 3 instead of 2, i don't know what could be wrong, and it is not the move generator, i have tested it carefully, it returns the correct perft results by comparing it with stockfish

any ideas? this is my whole negamax function, thank you

Code: Select all

private static int Negamax(int _depth, int _alpha, int _beta, bool _do_null = true)
        {
            // get board's unique hash id
            ulong hash = board.current_state.hash;

            if (ply > 0 && IsRepetition(hash) && _do_null)
            {
                #if !MASTER
                System.Console.WriteLine($"RP ->  {ply}  ply");
                #endif
                // return draw score
                return 0;
            }

            // transposition table lookup entry
            TTEntry entry = TTable.Lookup(hash);

            // Transposition table flag check
            if (entry.hash == hash && entry.depth == _depth)
            {
                if (entry.flag == TTFlag.EXACT) return entry.eval;
                else if(entry.flag == TTFlag.ALPHA && entry.eval <= _alpha) return _alpha;
                else if (entry.flag == TTFlag.BETA && entry.eval >= _beta ) return _beta;
            }

            // Transposition table entry flag
            TTFlag flag = TTFlag.ALPHA;

            if (_depth <= 0)
            {
                // Quiescense search
                return Quiescense(_alpha, _beta);
                //return Evaluate();
            }

            // increment node count
            searched_nodes++;

            // are our king in check?
            bool inCheck = board.InCheck(board.current_state.sideToMove);

            int legal_moves = 0;


            if (inCheck) _depth++;


            // Null move pruning
            if (_do_null && _depth >= 3 && !inCheck && ply > 0)
            {
                // switch side
                //System.Console.WriteLine("Original hash  " + board.current_state.hash);

                byte old_enpassant = board.current_state.enPassant; 
                board.current_state.sideToMove ^= 1;
                board.current_state.hash ^= BoardHash.sideHash;
                board.current_state.enPassant = 0;
                board.current_state.hash ^= BoardHash.EnpassantHashKeys[0];

                //System.Console.WriteLine("Swich side hash  " + board.current_state.hash);

                int val = -Negamax(_depth - 1 - 2, -_beta , 1 -_beta, false);
                
                // restore side & state
                board.current_state.sideToMove ^= 1;
                board.current_state.enPassant = old_enpassant;
                board.current_state.hash ^= BoardHash.sideHash;
                board.current_state.hash ^= BoardHash.EnpassantHashKeys[old_enpassant];

                //System.Console.WriteLine("Restore side hash  " + board.current_state.hash);

                System.Console.WriteLine("null make score: " + val + " beta " + _beta);

                if (val >= _beta)
                {
                    System.Console.WriteLine("cutoff");
                    return _beta;
                }
            }
            
            // principal variation search control            
            bool search_pv = true;
            // generate move list
            List<int> moves = board.GenerateMoves();
            int currentMove = 0;
            int score = 0;
            
            for (int moveIndex = 0; moveIndex < moves.Count; moveIndex++)
            {
                OrderMoves(moveIndex, ref moves);
                // increment ply
                ply++;
                // increment repetition
                repetition_index++;
                repetition_table[repetition_index] = hash;
                // get current move
                currentMove = moves[moveIndex];
                if (board.MakeMove(currentMove))
                {
                    // Principal variation search
                    if (search_pv)
                    {
                        score = -Negamax(_depth -1 , -_beta, -_alpha);
                    }else 
                    {
                        score = -Negamax(_depth -1, -_alpha -1, -_alpha);
                        if (score > _alpha && score < _beta)
                            score = -Negamax(_depth -1 , -_beta, -_alpha);
                    }

                    repetition_index--;
                    ply--;
                    board.UnMakeMove(currentMove);

                    legal_moves++;
                    if (score >= _beta) 
                    {
                        // fail hard beta cut-off
                        TTable.Store(new TTEntry(TTFlag.BETA , hash, _depth, _beta));
                        return _beta;
                    }

                    // found a better move
                    if (score > _alpha)
                    {
                        search_pv = false;
                        flag = TTFlag.EXACT;
                        _alpha = score;
                        best_move = currentMove;
                    }
                }
                else
                {
                    repetition_index--;
                    ply--;
                }
            }
            // we don't have any legal moves to make
            if (legal_moves == 0)
            {
                if(inCheck)
                {
                    // return mating score (closest distance to mate)
                    return -89000 + ply;
                }else 
                {
                    // return stalemate (draw) score
                    return 0;
                }
            }

            TTable.Store(new TTEntry(flag, hash, _depth, _alpha));
            // Move Fails low
            return _alpha;
        }

[pedrojdm2021]

There should not be any significant effect of doing arbitrary large numbers of null moves in a row, so don't expect disallowing that to solve any problem.

Whether you need a hash-key update on null move depends on whether you account the side-to-move part of the key incrementally or each time you use the key. (Which is an equally valid method, as the stm changes on every move, and each node uses it only once, so there is no benefit whatsoever from handling it incrementally.) If you handle this wrong, it could be responsible for the observed anomaly.

Reducing 3 ply for null move instead of 2 has always been an enormous Elo loss in all my engines. Even when done only above some depth limit ('adaptive null move').

i only use the hash keys for transposition tables, i don't know if that could be a TT table problem? i am going to test that

[Edsel Apostol]

Hello, i am new on this world of chess programming, i am enjoying it so far but, i have been trying to implement the null move pruning into my chess engine, but it seems to increment very much the searched nodes count instead of actually reducing it

My null move check (i am doing my engine in C#):

Code: Select all

int legal_moves = 0;
            if (inCheck) _depth++;

            if(_depth >= 3 && !inCheck && ply > 0 && _alpha == _beta -1)
            {
                // switch side
                board.current_state.sideToMove ^= 1;
                
                score = -Negamax(_depth - 1 - 2, -_beta , 1 -_beta  , false);
                // restore side & state
                board.current_state.sideToMove ^= 1;
               
                System.Console.WriteLine("After null make && undo score " + score + " beta " + _beta);

                if (score >= _beta)
                {
                    System.Console.WriteLine("cutoff");
                    return _beta;
                }
             }

when i run the following position with search depth of 4 i get this log:
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

Code: Select all

After null make && undo score 24 beta 25
After null make && undo score 24 beta 25
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -15 beta -15
cutoff
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
After null make && undo score -16 beta -15
bestmove e2a6 bestscore -15
nodes searched: 87522 in 561ms

without null move pruning, i get this:

Code: Select all

bestmove e2a6 bestscore -15
nodes searched: 36869 in 312ms 

I don't know what i am doing wrong, everything seems ok in terms of code, but i think my search is searching unnesary "null" moves, or i don't know.
anyone has any idea on what could be happening?

what i have so far:
- tranposition tables
- Negamax + alpha-beta + Principal Variation search
- three fold repetition
- Basic material evaluation with piece tables + Mopup Evaluation

Fail soft seems stronger in my opinion. Maybe try that.

I also noticed that you are doing null move on most situations. You should limit that. Try this:

Depth is 2 or greater
Not in PV
Not in root
At least 1 non king and pawn piece for the side to move
The current position's eval is greater than beta (this saves a lot of time, not doing null move that will probably just fail)
The hash table query that didn't have enough depth has also a value and a flag, use that as well. So try something like:


if (!inCheck && depth >= 2 && beta==alpha+1 && ply > 0 && eval(pos) > beta && (entry.hash != hash || entry.flag == TTFlag.BETA || entry.eval >= _beta) && at_least1_nonpawn_nonking_pc) { // do null move here