Null moves + Hash table

[Patrice Duhamel]

I try to add null moves pruning in my engine,
but after this change, I get wrong result,
I found that if I remove the transposition table it works better.

is there something special about the use of the transposition table with null moves ?
or the problem comes from the transposition table ?

I made tests with WAC.epd : (5 seconds/move)

all tests without quiescence search, without aspiration window,
but use mvv/vla + killer moves + history heuristic.

- no transposition table, no null moves : 155 / 300
- transposition table, no null moves : 164 / 300
- no transposition table, null moves : 181 / 300
- transposition table, null moves : 141 / 300


Patrice.

[Steve Maughan]

Patrice,

You have a bug

Do you adjust the hash table key for the side to move? This is important - there should be a white_to_move key that is xor'ed when playing a null move (and any other move for that matter). I suspect that this may be the problem.

Steve

[Patrice Duhamel]

Yes I update the hash key in my makenullmove and unmakenullmove functions, I'm not using the white_to_move key, but another key used only for null moves.

[Sven Schüle]

Hi Patrice,

(Edit: sorry, I saw Steve's and your answers too late.)

is it possible that you have a hash key bug when making or unmaking the null move?

Recently I found a small bug in Surprise, I had missed to apply the necessary hash key update in case the previous position had a nonzero ep target square. Unfortunately the effect of fixing this bug was very limited.

Of course the side to move change must be reflected in the hash key, too. I do no other hash key updates than these two when null moving.

For me it was very helpful to have a function that generates the hash key from scratch and then, in a debug-compiled version, to compare with the incremental hash key. Some guys have already pointed this out in the past. I found also a second hash key bug this way.

Sven

[Sven Schüle]

Yes I update the hash key in my makenullmove and unmakenullmove functions, I'm not using the white_to_move key, but another key used only for null moves.

Perhaps try to XOR with the white_to_move key instead of an own key, and see what happens?

Sven

[Patrice Duhamel]

Perhaps try to XOR with the white_to_move key instead of an own key, and see what happens?

I try with the white_to_move key, but this doesn't solve the problem.

[H.G.Muller]

How can you expect any sensible moves without Quiescence Search? Or does your evaluation correct for hanging pieces?

Normally, without QS, you are playing a different game. So what you count as 'not solved' might actually be the best move in that other game, and the null move and TT might help you to find more true solutions which you then count as wrong...

[Patrice Duhamel]

I was wrong when I say using the white_to_move key change nothing,
I compared the hashkey with a build hash key at each node, and found errors,
now using the white_to_move key, I see no problem with hashkey,
but this not solve the problem...

How can you expect any sensible moves without Quiescence Search? Or does your evaluation correct for hanging pieces?

My evaluation function is poor, and in all tests, I disabled the quiescence search, to test only hash table and null moves,
(to be sure the problems doesn't come from quiescence)

when using hash table and null moves, I should have better result
than without hash table and without null moves ?

example : 8/4pb1N/3BkN2/1p3p2/1Qp5/K6B/8/8 - - 0 1

in this position, using hash and not null moves, or only null moves, I found the mate in 2,
but I don't find it when using hash and null moves.

[H.G.Muller]

when using hash table and null moves, I should have better result
than without hash table and without null moves ?

These are all checkmate in N problems?

For finding checkmates it is well known that null-move pruning makes it worse, even time-wise. (Of course null-move pruning always makes it worse depth-wise, but the idea is that the increased speed allows you do reach much larger depth in the same time.)

Depending on how you implemented your checkmate handling, the hash might also make that worse by not going for the quickest mate, but for the first one it finds. And because of hits on deeper TT entries it might see a deeper mate first.

For non-checkmate problems, where the game continue beyond the horizon, I see no reason why null-move pruning or hash table should make the program better. These are tricks that are supposed to allow the search to reach a larger depth in a shorter time. But if a larger depth in general will not result in a better move, as it will without a QS, you would not expect a better move from this.

[Patrice Duhamel]

These are all checkmate in N problems?

No, they are not all checkmate problem.

In my example, I try to give more time to think, and see he found the mate in 2, but at depth 12
without null moves and hash, he found the mate at depth 4.

is there something to do to help finding the mates at a smaller depth ?
a better evaluation function ?

[H.G.Muller]

Well, if without hash table and null-move pruning it does not find mate in 2 for any search depth of 5 ply and higher, there obviously is something wrong in the checkmate logic of your search. On ply 5 his King will be captured, and if it doesn't notice that...

Or do you mean that it is actually mate in 4, and that the mate in 2 only exists in the imagination of the engine?

[Patrice Duhamel]

No, it's the opposite,
in my example (it's a mate in 2),
without hash table and null-move pruning, it found the mate at depth 4.
but if I use hash table and null-move pruning, it find the mate only at depth 12.
(and with only hash table, it found the mate at depth 4)

[H.G.Muller]

OK, to summarize: you have a mate in 2, which means that the third ply gives the mate, and on the fourth ply your program discovers that it is in doesn't have any legal moves and is in check. So it seems logical that you need 4 ply.

Now with null-move pruning, if it finds some 4-ply branch that ends pretty good before finding the mate, the move leading to the mate will be will be met with a null-move reply, reducing the depth by 3(?). So you have used up 5 ply, and the 6th ply is the move that checkmates. Normally, that would make you discover that you are checkmated on the 7th ply.

Now do you allow null-move when in check? Then the program would try the null move first as 7th ply, reducing another 3 ply, so that is 10 ply. Without a QS you would not start trying a reply to the null move before the search depth is 11 ply, and only then you would disscover that you can capture the King. That is still less than 12 ply, though.

So it seems there is indeed something wrong.

The best way to find what it is, is usually print an overview of all moves that it searched (plus the score it found for them) in all nodes on the branch that you think is in error. In this case that branch is not very deep, only the 3 ply leading to the checkmate. Printing all moves in these nodes will quickly show you what is wrong.

[Patrice Duhamel]

Thanks for your help.

My depth reduction value is 2, and I don't allow null-moves when in check. The only thing missing with null moves is I do nothing about zugzwang positions.

I will print all moves and try to see what happens.

[H.G.Muller]

Yes, with those parameters it should definitely find the mate at 6 ply.

Just keep track of the move path in make by something like

Path[ply] = Move;

and then put a print statement under a condition like

if(ply==1 || Path[1]==m1 && (ply==2 || Path[2]==m2 && (ply==3 || Path[3]==m3 && ... ))))

where m1, m2, m3, ... are the moves of the branch you want to examine.

[Patrice Duhamel]

I found the problem,
with null moves, I call the search function with a new depth = (depth - DEPTH_REDUCTION - 1)
depth can become < 0,
I have a test to return evaluate() when depth <= 0,
but I'm saving the value as EXACT in the hash table.

depth is unsigned in my hash table, and it was wrong when depth < 0

to solve the problem, I don't save the value in the hash if depth < 0,

but I don't know if I must save the value in the hash or not in this case ?

[H.G.Muller]

You should at least do a Quiescence Search in reply to the null move. But of course yu suppressed QS here, so I guess returning eval is the current mode of QS.

I expect null-move pruning not to work at all in this case: the entire idea of NMP is to test for threats, and a 1 ply search of the null move does not do that without QS. It becomes then equivalent to a 0-ply search of the null move: you might as well have used the eval before null move, for it is the same. That would make you prune any node with remaining depth R+1 if eval>beta, and makes NMP degenrerate into a disastously unsound version of deep futility pruning / razoring. Normally you prune there only if eval > beta + MARGIN, where the MARGIN is already as big as a Queen at two ply. You now use MARGIN = 0 at three ply...

Without QS, search the null move at least to two ply before attaching any value to its score. If the result is above beta you can then safely prune a 5-ply search.

If storing results from such shallow searches pays, depends on the speed of the engine. There are engines that do not store QS nodes.

[Sven Schüle]

I found the problem,
with null moves, I call the search function with a new depth = (depth - DEPTH_REDUCTION - 1)
depth can become < 0,
I have a test to return evaluate() when depth <= 0,
but I'm saving the value as EXACT in the hash table.

depth is unsigned in my hash table, and it was wrong when depth < 0

to solve the problem, I don't save the value in the hash if depth < 0,

but I don't know if I must save the value in the hash or not in this case ?

Hi Patrice,

"new depth" <= 0 in your case means that you don't do a null move search because you are already too close to the horizon. I think the "new depth" value can only be useful when > 0 so you do a null move search, otherwise the scope of "new depth" ends immediately.

Now I don't know why you call evaluate() here, I think you should instead proceed with the normal search using "depth" (not "new depth" of course), having accepted that there is no way to do null move pruning at the current node, but also considering that you have not reached the horizon yet.

This would also make your following question about storing something in the hash table obsolete.

Sven

[H.G.Muller]

I don't agree: null move can also be useful when the reduced depth gets negative. Even with R=2 a 3-ply search would have a null-move-reply search of 0 (i.e. QS level). A 2-ply search could thus be cut by a 1-ply null-move search, a significant saving. With R=3 you even save one ply extra.

In Joker I even do a null-move search in nodes with depth=1. Although there is nothing to reduce there, using the null move there when eval >= beta still results in savings: It can be tried without move generation (and I do bulk move generation in Joker). Furthermore, it is guaranteed not to be a bad move: if I would try to cut by a randomly picked move, I might pick a move with a negative SEE, or with a soft-pinned or overloaded piece. The null move cannot have such bad effects.

And, last but not least, if the 1-ply null move does cut the node, the position goes in the hash table with score beta and draft 1+R = 3 or 4, so that later hits upon that position (e.g. in the next 3 or 4 deepening iterations) will be hash-pruned.

[Patrice Duhamel]

Now I don't know why you call evaluate() here, I think you should instead proceed with the normal search using "depth" (not "new depth" of course), having accepted that there is no way to do null move pruning at the current node, but also considering that you have not reached the horizon yet.
Sven

My code for null-moves looks like the standard null-moves found here :
http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.html

when depth is < 0 they return evaluate(),
(or the value returned by quiescence search)

I have to add the condition (depth > DEPTH_REDUCTION) before calling search for null move ?

You should at least do a Quiescence Search in reply to the null move. But of course yu suppressed QS here, so I guess returning eval is the current mode of QS.

I will enable quiescence search.
I call quiescence at depth=0, and compare the value returned with alpha and beta, to know if I have to save in the hash table as EXACT, LOW, or HIGH.