Disappointing Null Move search

[lauriet]

Hi all.

I have some stats from my testing null move in an early middle game position
(yes the times are slow....modest hardware)

Plain vanilla alpha/beta: 7 ply search

Nodes: 22,809,156
Qnodes: 10,791,275
nps: 181,025
time: 126
eval: 43cp
move: e3e4

Add Null move: 7 ply search

Nodes: 26,732,709
Qnodes: 12,132,869
nps: 195,129
null move cuts: 2006
time: 137
eval: 43cp
move: e3e4

Null move is supposed to be good for about an extra 1 or 2 ply but this is not showing this kind of result.

Here is my null move code: On entry its whites turn to move.

{-- now try a null move }
IF NullAllowed AND
(Depth > 2) AND
NOT SearchingPV AND
NOT EndGame AND
NOT InCheck(WhitePieces) THEN
BEGIN
{-- swap sides }
WhitesMove := False;
CompsMove := ComputersMove;

Score := BlacksScore(Beta - 1, Beta, Depth - 3, $8, False);

{-- swap back }
WhitesMove := True;
ComputersMove := CompsMove;

IF Score >= Beta THEN {-- a cut off }
BEGIN
Inc(NullCuts);
WhitesScore := Beta;
Exit; {-- return beta }
END;
END;

(I dont use negamax so this is the maxing procedure (white))
This code follows the (if depth = 0 then evaluate) code, and is prior to generating and searching whites moves.

Can anyone see a problem ?
Or explain this ?

Thanks

[elpapa]

The score returned from the search is from black's point of view, right? In that case don't you need to swap the sign before comparing it to beta? Like this:

Score := -BlacksScore(Beta - 1, Beta, Depth - 3, $8, False);

Or maybe I'm just confused because I'm used to negamax.

[lauriet]

Yes, with the two seperate procedures, blacksscore returns a negative value.
Evaluations are from the side to move's perspective.....whites score is positive for good scores while blackscore are negative for good moves.

[Sven]

Yes, with the two seperate procedures, blacksscore returns a negative value.
Evaluations are from the side to move's perspective.....whites score is positive for good scores while blackscore are negative for good moves.

That sounds wrong for minimax. "side-to-move" scoring perspective is a negamax concept. With minimax all scores are from white's perspective but all search functions where black is to move are minimizing the score. If your static eval returns a score from side-to-move perspective then the BlacksScore() function needs to negate it immediately before using it for anything.

So it seems you are mixing the two concepts. It would be better to stick with just one concept, and it is obvious which one is to be preferred ...

Please show your search code for both colors (WhitesScore() and BlacksScore()), otherwise it is hard to tell what exactly is going wrong.

[lauriet]

I will try to clarify....
The eval function returns a score. If say white is ahead in material/position the score is positive. If black is ahead in material/position the score is negative. So when white or black searches they just get a score. White, for instance will try to maximize its score and black will try to minimize its score.
I believe this is correct as the program plays reasonable moves that make sense.......its just that the null move code is not really doing much. Either I have not implemented it properly or the overhead of it is not worth it at the low plies Im searching.......The articles I have read say how much of a break through it was, so I must be doing something incorrectly.
I believe I can also exit the procedure if the score is less than alpha also ???

Laurie

[op12no2]

I think it's usual to only try the null move search if the static eval is >= beta already, because giving the other side another go can only make things worse so it's pointless trying null move otherwise (I think). Maybe worth a try?

[Sven]

I will try to clarify....
The eval function returns a score. If say white is ahead in material/position the score is positive. If black is ahead in material/position the score is negative. So when white or black searches they just get a score. White, for instance will try to maximize its score and black will try to minimize its score.
I believe this is correct as the program plays reasonable moves that make sense.......its just that the null move code is not really doing much.

The tiny piece of code that you showed does not look incorrect to me. But it is only the part for white to move. So if there is a bug then it might be in the "black to move" part (which would be a typical problem of programs using two functions for the same thing, with side to move being the only difference). Also you might have some trouble with your "WhitesMove", "CompsMove", or "ComputersMove" variable, so you should check these carefully again. I am not fully convincend that it's necessary to have three variables for the concept of which side is to move ... Most programs have just one variable, and it is toggled inside every makeMove/unmakeMove operation (so the code for toggling it does not even appear in the search code).

Regarding your static eval function I suggest that you double check again whether it returns a score from white perspective or from side-to-move perspective, since you have now made two contradicting statements about it.

Either I have not implemented it properly or the overhead of it is not worth it at the low plies Im searching.......The articles I have read say how much of a break through it was, so I must be doing something incorrectly.

A 7-ply search should already benefit from null-move reduction if you implement it correctly. Have you checked your null-move conditions (NullAllowed, NOT SearchingPV, NOT EndGame)?

I believe I can also exit the procedure if the score is less than alpha also ???

Yes, in the black-to-move part of minimax the "beta cutoff" is done if score < alpha. That's why I wrote you should also show us the code for the other side.

[Sven]

I think it's usual to only try the null move search if the static eval is >= beta already, because giving the other side another go can only make things worse so it's pointless trying null move otherwise (I think). Maybe worth a try?

That would be a possible improvement but it should only be tried after ensuring that the basic implementation works!

[lauriet]

FUNCTION WhitesScore(Alpha, Beta : Int16;
Depth : Byte;
CapSq : SquareType;
NullAllowed : Boolean) : Int16;
{-- Whites on move. Tries to find maximum score. This is the Max, in MiniMax
White (Max player) is the one that updates alpha. Alpha holds the
score of the best move found for white at this node }

IF (Depth <> MaxDepth) AND {-- not a root }
NullAllowed AND {-- parameter of call }
(Depth > 2) AND
NOT SearchingPV AND
NOT EndGame AND
NOT InCheck(WhitePieces) THEN
BEGIN
{-- swap sides }
WhitesMove := False;
CompsMove := ComputersMove; {-- save }

Score := BlacksScore(Beta - 1, Beta, Depth - 3, $8, False);

{-- swap back }
WhitesMove := True;
ComputersMove := CompsMove; {-- restore }

IF Score >= Beta THEN {-- beta cut }
BEGIN
Inc(NullCuts);
WhitesScore := Beta;
Exit;
END;

IF Score < Alpha THEN {-- didnt reach Alpha }
BEGIN
Inc(NullCuts)
WhitesScore := Alpha;
Exit;
END;

END;




FUNCTION BlacksScore(Alpha, Beta : Int16;
Depth : Byte;
CapSq : SquareType;
NullAllowed : Boolean) : Int16;
{-- Blacks on move. Tries to find minimum score. This is the Min, in MiniMax.
Black (Min player) is the one that updates beta. Beta holds the
score of the best move found for black at this node }

IF (Depth <> MaxDepth) AND {-- not at root }
NullAllowed AND
(Depth > 2) AND
NOT SearchingPV AND
NOT EndGame AND
NOT InCheck(BlackPieces) THEN
BEGIN
{-- Swap sides }
WhitesMove := True;
CompsMove := ComputersMove;

Score := WhitesScore(Alpha, Alpha + 1, Depth - 3, $8, False);

{-- Swap back }
WhitesMove := False;
ComputersMove := CompsMove;

IF Score <= Alpha THEN {-- alpha cut }
BEGIN
Inc(NullCuts);
BlacksScore := Alpha;
Exit;
END;

IF Score > Beta THEN {-- didnt reach beta }
BEGIN
Inc(NullCuts);
BlacksScore := Beta;
Exit;
END;

END;

[Sven]

FUNCTION WhitesScore(Alpha, Beta : Int16;
Depth : Byte;
CapSq : SquareType;
NullAllowed : Boolean) : Int16;

...

IF Score >= Beta THEN {-- beta cut }
BEGIN
Inc(NullCuts);
WhitesScore := Beta;
Exit;
END;

IF Score < Alpha THEN {-- didnt reach Alpha }
BEGIN
Inc(NullCuts)
WhitesScore := Alpha;
Exit;
END;

END;


FUNCTION BlacksScore(Alpha, Beta : Int16;
Depth : Byte;
CapSq : SquareType;
NullAllowed : Boolean) : Int16;

...

IF Score <= Alpha THEN {-- alpha cut }
BEGIN
Inc(NullCuts);
BlacksScore := Alpha;
Exit;
END;

IF Score > Beta THEN {-- didnt reach beta }
BEGIN
Inc(NullCuts);
BlacksScore := Beta;
Exit;
END;

END;

I think we misunderstood each other. You wrote:

I believe I can also exit the procedure if the score is less than alpha also ???

and I replied:

Yes, in the black-to-move part of minimax the "beta cutoff" is done if score < alpha. That's why I wrote you should also show us the code for the other side.

but my "Yes" was not meant the way you have interpreted it. I thought you were talking about the cutoff condition in the BlacksScore() function where it is obviously "score <= alpha" (of course not "<" as I wrote above). But you may only do the cutoff once: in WhitesScore() if score >= beta and in BlacksScore() if score <= alpha. The additional second condition is wrong in both functions. The idea of null-move reduction is that you check whether your own position is already strong enough that you can let your opponent play twice in a row, and still get a winning score (resp. a score that refutes his previous move). Under the assumption that not moving is "legal" in the current position (by not leaving your king in check) and you are not in zugzwang, this will still result in a correct search in *most* cases but will reduce the overall tree size considerably if you search the null move to a reduced depth. So it is all about getting a beta cutoff (for the maximizing side) or an alpha cutoff (for the minimizing side, when using minimax), but not both at once. In general (i.e., not restricted to null-move reduction) it is a bad idea to prune all remaining moves if you find one move that scores worse than alpha. This might result in overlooking simple tactics since you tend to find faulty "refutations" of strong moves.

Back to your original problem: apart from my remark above your null-move code looks ok to me (it could be improved, e.g. you could reduce by 3 plies instead of 2, or you could allow two null moves in a row, but it should work in general). So let me recall my questions from my previous post:
1) Have you checked the null-move conditions like
- NullAllowed,
- SearchingPV,
- EndGame?
When do you set NullAllowed to true? Maybe try to ignore SearchingPV and EndGame in your null-move condition to see whether it has any effect.
2) Have you checked that the logic related to your 3 variables WhitesMove, CompsMove, and ComputersMove works correctly in the null-move case? (Btw: What does "CompsMove" and "ComputersMove" mean? These variables were not present in the code that you sent me two months ago for review.)

An additional question arises:
3) What does the "$8" mean in your recursive calls?