Null Move Pruning giving the opposite result

[Sven]

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

Code: Select all

                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];
                //...
                // 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];

To me it looks like you do not restore the hash key correctly whenever old_enpassant != 0. The enPassant property of the board "changes" from old_enpassant to 0 so you need to XOR with the corresponding BoardHash.EnpassantHashKeys[...] values of both old_enpassant and 0 when making and unmaking the null move. Doing this only if old_enpassant != 0 may or may not be faster (but I would prefer to avoid the additional "if"). There are certainly tricks to do this as fast as possible but I guess this would not affect overall performance at all.

Since your test position has potential to create a lot of positions with the ep target square set within the first four plies (after a4 by White or c5 by Black), this might result in severe damage to your hash key and could explain any undesired behaviour.

To debug possible hash key problems, it may be a good idea to add an assertion after each UnmakeMove() that the hash key is now the same as before the corresponding MakeMove().

Also I noticed that you do not increment "ply" when making a null move (maybe you do this by intent but I do not understand why).

[pedrojdm2021]

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

Code: Select all

                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];
                //...
                // 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];

To me it looks like you do not restore the hash key correctly whenever old_enpassant != 0. The enPassant property of the board "changes" from old_enpassant to 0 so you need to XOR with the corresponding BoardHash.EnpassantHashKeys[...] values of both old_enpassant and 0 when making and unmaking the null move. Doing this only if old_enpassant != 0 may or may not be faster (but I would prefer to avoid the additional "if"). There are certainly tricks to do this as fast as possible but I guess this would not affect overall performance at all.

Since your test position has potential to create a lot of positions with the ep target square set within the first four plies (after a4 by White or c5 by Black), this might result in severe damage to your hash key and could explain any undesired behaviour.

To debug possible hash key problems, it may be a good idea to add an assertion after each UnmakeMove() that the hash key is now the same as before the corresponding MakeMove().

Also I noticed that you do not increment "ply" when making a null move (maybe you do this by intent but I do not understand why).

Hello, thank you for your time I was finally able to fix it.

the main problem i think it was that i was not collecting the "principal variation" correctly. so i made a PV table and stored it in there and also implemented the "Late move reduction" and now it seems to be working the engine just fine, have to do more tests on it but for now i am very happy with the results, programming sometimes can be very weird haha

[Sven]

Glad to read that you found something ...

I have to admit, though, that I don't really believe that you have actually fixed the null move problem you reported ... My experience simply tells me that it is very unlikely that changing PV collection code or LMR code helps to fix a bug in null move pruning.

So yes, I have to agree: "programming sometimes can be very weird" - at least when doing random changes ...

So seriously, does your engine now search significantly less nodes with null move pruning enabled, compared to having it disabled (and not changing anything else)?

[pedrojdm2021]

Glad to read that you found something ...

I have to admit, though, that I don't really believe that you have actually fixed the null move problem you reported ... My experience simply tells me that it is very unlikely that changing PV collection code or LMR code helps to fix a bug in null move pruning.

So yes, I have to agree: "programming sometimes can be very weird" - at least when doing random changes ...

So seriously, does your engine now search significantly less nodes with null move pruning enabled, compared to having it disabled (and not changing anything else)?

This is what actually the problem was:

The problem is that before i was not collecting a "real" PV at all before i did these changes

i only did something like this inside the negamax search:

Code: Select all

if (score > alpha)
{
 mybestmove = this_move;
}

i learned the bad way that even that i don't the the whole PV path since my engine is not an real uci engine, i only need the best move, that is not the way of getting the actual best move.

yesterday i added the Late Move reduction and i found that the engine was working quite nice but it ended up giving me movements for the opposite player when i was on my turn. So i did some debugging and found that the issue was that: a bad way of "collecting" the: pv/best_move

I fixed that, and tested a whole game AI vs AI, it seems to be working nice.
The tests:
"tricky" position on depth 6:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Removed the null move pruning + this "Late move reduction" feature: 63.484 nodes
Added the null move pruning + "Late move reduction" feature: 57.314 nodes

So it was my conclusion on this: always collect pv even if you don't need the whole "path"

Also i found that the Null move pruning requires LMR to work, or at least for me it was it lol.
This is an interesting article that helped me a lot:
https://web.archive.org/web/20150212051 ... m/lmr.html

[abulmo2]

I fixed that, and tested a whole game AI vs AI, it seems to be working nice.
The tests:
"tricky" position on depth 6:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Removed the null move pruning + this "Late move reduction" feature: 63.484 nodes
Added the null move pruning + "Late move reduction" feature: 57.314 nodes

So it was my conclusion on this: always collect pv even if you don't need the whole "path"

Your test is flawed on several points:
- It uses a single position. You cannot conclude anything on a single position. Nullmove pruning is supposed to diminish the number of visited nodes in average, not on every position.
- It uses a shallow depth. You need a deeper search to see nullmove really shining.
- You mix several features: nullmove pruning and late move reduction. Then you wrongly conclude they help each other. Test things one at a time otherwise you will not know if something is working.
- The node reduction does not necessary means that a feature X is worth something. It is possible that a feature reducing the node count also diminish the search speed or affect the quality of the search leading to a weaker engine despite the observed node reduction. The only right test is to play thousands of games with your engine with feature X against your engine without the feature X (directly or undirectly by playing against a gauntlet of other opponent engines). That way you can conclude your feature is worth something.

Here is an example with my simple program Dumb to illustrate my point of view:

Your test on a single position at depth 6:
with nullmove 65,074 nodes; without nullmove 53,316 nodes, so nullmove increased the node count by 22%. Can you conclude my nullmove implementation is crap ?

Test on 200 positions at
depth 6: with nullmove 1,390,647 nodes; without nullmoves 1494519 nodes, so nullmove decreased the node count by 7%
depth 12: with nullmove 50,297,950 nodes; without nullmoves 67,650,106 nodes, so nullmove decreased the node count by 25%
depth 18: with nullmove 1,006,284,779 nodes; without nullmoves 2,114,043,826 nodes, so nullmove decreased the node count by 52%
Now nullmove seems to works better, doesn't it ?

Test by playing games (between the two programs and other versions);

Code: Select all

 # PLAYER                  : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb                  :    0.0   ----   2458.5    4000   61.5%
   4 dumb-no_nullmove      :  -85.2    9.6   1871.5    4000   46.8%

so my nullmove implementation is worth approximately 85 Elo in this program.

[pedrojdm2021]

I fixed that, and tested a whole game AI vs AI, it seems to be working nice.
The tests:
"tricky" position on depth 6:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Removed the null move pruning + this "Late move reduction" feature: 63.484 nodes
Added the null move pruning + "Late move reduction" feature: 57.314 nodes

So it was my conclusion on this: always collect pv even if you don't need the whole "path"

Your test is flawed on several points:
- It uses a single position. You cannot conclude anything on a single position. Nullmove pruning is supposed to diminish the number of visited nodes in average, not on every position.
- It uses a shallow depth. You need a deeper search to see nullmove really shining.
- You mix several features: nullmove pruning and late move reduction. Then you wrongly conclude they help each other. Test things one at a time otherwise you will not know if something is working.
- The node reduction does not necessary means that a feature X is worth something. It is possible that a feature reducing the node count also diminish the search speed or affect the quality of the search leading to a weaker engine despite the observed node reduction. The only right test is to play thousands of games with your engine with feature X against your engine without the feature X (directly or undirectly by playing against a gauntlet of other opponent engines). That way you can conclude your feature is worth something.

Here is an example with my simple program Dumb to illustrate my point of view:

Your test on a single position at depth 6:
with nullmove 65,074 nodes; without nullmove 53,316 nodes, so nullmove increased the node count by 22%. Can you conclude my nullmove implementation is crap ?

Test on 200 positions at
depth 6: with nullmove 1,390,647 nodes; without nullmoves 1494519 nodes, so nullmove decreased the node count by 7%
depth 12: with nullmove 50,297,950 nodes; without nullmoves 67,650,106 nodes, so nullmove decreased the node count by 25%
depth 18: with nullmove 1,006,284,779 nodes; without nullmoves 2,114,043,826 nodes, so nullmove decreased the node count by 52%
Now nullmove seems to works better, doesn't it ?

Test by playing games (between the two programs and other versions);

Code: Select all

 # PLAYER                  : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb                  :    0.0   ----   2458.5    4000   61.5%
   4 dumb-no_nullmove      :  -85.2    9.6   1871.5    4000   46.8%

so my nullmove implementation is worth approximately 85 Elo in this program.

You are right, i am going to do some deeper tests on that, thank you for your information

[Desperado]

I fixed that, and tested a whole game AI vs AI, it seems to be working nice.
The tests:
"tricky" position on depth 6:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Removed the null move pruning + this "Late move reduction" feature: 63.484 nodes
Added the null move pruning + "Late move reduction" feature: 57.314 nodes

So it was my conclusion on this: always collect pv even if you don't need the whole "path"

Your test is flawed on several points:
- It uses a single position. You cannot conclude anything on a single position. Nullmove pruning is supposed to diminish the number of visited nodes in average, not on every position.
- It uses a shallow depth. You need a deeper search to see nullmove really shining.
- You mix several features: nullmove pruning and late move reduction. Then you wrongly conclude they help each other. Test things one at a time otherwise you will not know if something is working.
- The node reduction does not necessary means that a feature X is worth something. It is possible that a feature reducing the node count also diminish the search speed or affect the quality of the search leading to a weaker engine despite the observed node reduction. The only right test is to play thousands of games with your engine with feature X against your engine without the feature X (directly or undirectly by playing against a gauntlet of other opponent engines). That way you can conclude your feature is worth something.

Here is an example with my simple program Dumb to illustrate my point of view:

Your test on a single position at depth 6:
with nullmove 65,074 nodes; without nullmove 53,316 nodes, so nullmove increased the node count by 22%. Can you conclude my nullmove implementation is crap ?

Test on 200 positions at
depth 6: with nullmove 1,390,647 nodes; without nullmoves 1494519 nodes, so nullmove decreased the node count by 7%
depth 12: with nullmove 50,297,950 nodes; without nullmoves 67,650,106 nodes, so nullmove decreased the node count by 25%
depth 18: with nullmove 1,006,284,779 nodes; without nullmoves 2,114,043,826 nodes, so nullmove decreased the node count by 52%
Now nullmove seems to works better, doesn't it ?

Test by playing games (between the two programs and other versions);

Code: Select all

 # PLAYER                  : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb                  :    0.0   ----   2458.5    4000   61.5%
   4 dumb-no_nullmove      :  -85.2    9.6   1871.5    4000   46.8%

so my nullmove implementation is worth approximately 85 Elo in this program.

You are right, i am going to do some deeper tests on that, thank you for your information

Well, instead of enabling more features you should disable all stuff that is not necessary to fix the problem.
That is imo the best way to encapsulate the problem.

Another thing that wasn't mentioned before is (at least i did not read it), that the Nullmove is not just change the side to move.
That is the theory, but making a nullmove in your engine means also updating the hashkey for example, or the ep-passent status changes and some more stuff needs t be considered. In general there is a simplified make_move() routine like make_null() that updates everything. Your code at the beginning of the thread only changes the side to move.

It will definetely result in a bug, because all stuff using the hash (that wasn't updated) will result in undefined/unwanted behaviour (repetition detection,transposition lookup). Especially because the side to move flag is (should be) part of the hashkey.

[pedrojdm2021]

I fixed that, and tested a whole game AI vs AI, it seems to be working nice.
The tests:
"tricky" position on depth 6:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Removed the null move pruning + this "Late move reduction" feature: 63.484 nodes
Added the null move pruning + "Late move reduction" feature: 57.314 nodes

So it was my conclusion on this: always collect pv even if you don't need the whole "path"

Your test is flawed on several points:
- It uses a single position. You cannot conclude anything on a single position. Nullmove pruning is supposed to diminish the number of visited nodes in average, not on every position.
- It uses a shallow depth. You need a deeper search to see nullmove really shining.
- You mix several features: nullmove pruning and late move reduction. Then you wrongly conclude they help each other. Test things one at a time otherwise you will not know if something is working.
- The node reduction does not necessary means that a feature X is worth something. It is possible that a feature reducing the node count also diminish the search speed or affect the quality of the search leading to a weaker engine despite the observed node reduction. The only right test is to play thousands of games with your engine with feature X against your engine without the feature X (directly or undirectly by playing against a gauntlet of other opponent engines). That way you can conclude your feature is worth something.

Here is an example with my simple program Dumb to illustrate my point of view:

Your test on a single position at depth 6:
with nullmove 65,074 nodes; without nullmove 53,316 nodes, so nullmove increased the node count by 22%. Can you conclude my nullmove implementation is crap ?

Test on 200 positions at
depth 6: with nullmove 1,390,647 nodes; without nullmoves 1494519 nodes, so nullmove decreased the node count by 7%
depth 12: with nullmove 50,297,950 nodes; without nullmoves 67,650,106 nodes, so nullmove decreased the node count by 25%
depth 18: with nullmove 1,006,284,779 nodes; without nullmoves 2,114,043,826 nodes, so nullmove decreased the node count by 52%
Now nullmove seems to works better, doesn't it ?

Test by playing games (between the two programs and other versions);

Code: Select all

 # PLAYER                  : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb                  :    0.0   ----   2458.5    4000   61.5%
   4 dumb-no_nullmove      :  -85.2    9.6   1871.5    4000   46.8%

so my nullmove implementation is worth approximately 85 Elo in this program.

You are right, i am going to do some deeper tests on that, thank you for your information

Well, instead of enabling more features you should disable all stuff that is not necessary to fix the problem.
That is imo the best way to encapsulate the problem.

Another thing that wasn't mentioned before is (at least i did not read it), that the Nullmove is not just change the side to move.
That is the theory, but making a nullmove in your engine means also updating the hashkey for example, or the ep-passent status changes and some more stuff needs t be considered. In general there is a simplified make_move() routine like make_null() that updates everything. Your code at the beginning of the thread only changes the side to move.

It will definetely result in a bug, because all stuff using the hash (that wasn't updated) will result in undefined/unwanted behaviour (repetition detection,transposition lookup). Especially because the side to move flag is (should be) part of the hashkey.

Thank you for your help, i really appreciate it! yes, i am going to do a rewrite of the AI module taking in mind all stuff, and testing each feature carefully

[pedrojdm2021]

I fixed that, and tested a whole game AI vs AI, it seems to be working nice.
The tests:
"tricky" position on depth 6:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Removed the null move pruning + this "Late move reduction" feature: 63.484 nodes
Added the null move pruning + "Late move reduction" feature: 57.314 nodes

So it was my conclusion on this: always collect pv even if you don't need the whole "path"

Your test is flawed on several points:
- It uses a single position. You cannot conclude anything on a single position. Nullmove pruning is supposed to diminish the number of visited nodes in average, not on every position.
- It uses a shallow depth. You need a deeper search to see nullmove really shining.
- You mix several features: nullmove pruning and late move reduction. Then you wrongly conclude they help each other. Test things one at a time otherwise you will not know if something is working.
- The node reduction does not necessary means that a feature X is worth something. It is possible that a feature reducing the node count also diminish the search speed or affect the quality of the search leading to a weaker engine despite the observed node reduction. The only right test is to play thousands of games with your engine with feature X against your engine without the feature X (directly or undirectly by playing against a gauntlet of other opponent engines). That way you can conclude your feature is worth something.

Here is an example with my simple program Dumb to illustrate my point of view:

Your test on a single position at depth 6:
with nullmove 65,074 nodes; without nullmove 53,316 nodes, so nullmove increased the node count by 22%. Can you conclude my nullmove implementation is crap ?

Test on 200 positions at
depth 6: with nullmove 1,390,647 nodes; without nullmoves 1494519 nodes, so nullmove decreased the node count by 7%
depth 12: with nullmove 50,297,950 nodes; without nullmoves 67,650,106 nodes, so nullmove decreased the node count by 25%
depth 18: with nullmove 1,006,284,779 nodes; without nullmoves 2,114,043,826 nodes, so nullmove decreased the node count by 52%
Now nullmove seems to works better, doesn't it ?

Test by playing games (between the two programs and other versions);

Code: Select all

 # PLAYER                  : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb                  :    0.0   ----   2458.5    4000   61.5%
   4 dumb-no_nullmove      :  -85.2    9.6   1871.5    4000   46.8%

so my nullmove implementation is worth approximately 85 Elo in this program.

You are right, i am going to do some deeper tests on that, thank you for your information

Well, instead of enabling more features you should disable all stuff that is not necessary to fix the problem.
That is imo the best way to encapsulate the problem.

Another thing that wasn't mentioned before is (at least i did not read it), that the Nullmove is not just change the side to move.
That is the theory, but making a nullmove in your engine means also updating the hashkey for example, or the ep-passent status changes and some more stuff needs t be considered. In general there is a simplified make_move() routine like make_null() that updates everything. Your code at the beginning of the thread only changes the side to move.

It will definetely result in a bug, because all stuff using the hash (that wasn't updated) will result in undefined/unwanted behaviour (repetition detection,transposition lookup). Especially because the side to move flag is (should be) part of the hashkey.

I finished the test and now it worked as expected. The problem that i did was that on MakeNullMove and UnmakeNull move i was not incrementing/reducing the ply, i think it was the issue also i did a rewrite that i told to you before and now just works great, with only null move pruning + PVS + Transposition tables, i have not added the LMR again to the algorithm.