Null moves + Hash table

[H.G.Muller]

Yes, that is the proper procedure. You have to be able to recognize threats the opponent has after null move, or there would be no point making it. I have the same problem in micro-Max, which has a QS of only recaptures. After a null move there are of course no recaptures, and then the only thing that it would notice is if the null move was illegal (i.e. if the opponent can capture a King after it). Even a P x Q would not be noticed.

So to implement NMP in uMax, I search low-takes-higher and all captures with the piece that last moved before the null move, in stead of recaptures.

[Uri Blass]

Yes, that is the proper procedure. You have to be able to recognize threats the opponent has after null move, or there would be no point making it. I have the same problem in micro-Max, which has a QS of only recaptures. After a null move there are of course no recaptures, and then the only thing that it would notice is if the null move was illegal (i.e. if the opponent can capture a King after it). Even a P x Q would not be noticed.

So to implement NMP in uMax, I search low-takes-higher and all captures with the piece that last moved before the null move, in stead of recaptures.

I wonder if you tried to implement similiar qsearch to tscp in micromax and how many additional chars you need for it.

Note that it is important to have good order of captures in order to have an efficient qsearch and using only the best move of the previous iteration is not enough.

searching low take high and captures of the last piece that moved after null move is not enough to avoid stupid errors because the move may have an indirect threat or may support high takes lower that was not efficient before the move because the lower was defended.

If you have a bad order of captures then I am not surprised that normal qsearch does not help you and you need at least to do the same as tscp and order the captures based on MVV/LVA

http://www.seanet.com/~brucemo/topics/q ... htm#MVVLVA

Uri

[H.G.Muller]

You put the finger exactly on the sore spot: an all-capture QS completely explodes if you don't have good move ordering, and only putting one move in front is not good enough. But better sorting is not really possible within the concept of uMax. It would have to maintain some kind of move stack for that, and this would drive up the complexity enormously.

What I did try, however, was this:

At IterDepth=1 it only considers recaptures (and King captures), as I do in uMax 3.2. This is equivalent to a SEE with unlimited X-rays that does respect pins (on King) and discovered checks. (In principle it is a rather inefficient implementation of SEE, since it does not only try the capture with the lowest piece, so that the search may branch, and it doesn't even consider the capture with the lowest piece first, because it just involves the pieces in board-scan order. But most SEEs are not complicated enough to make this matter much, with only recaptures it can never really explode.)

Then, at IterDepth=2 I do not search all moves, (as uMax 3.2 does), but only captures that have a positive SEE. (i.e. Depth=2 is the QS.) This iteration starts with the move that had the best SEE in iteration 1.

So what you do is first SEE all moves (=search at Depth=1) to determine the best SEE and put it in front, and then SEE all moves again and immediately follow that SEE for a QS of the same move if the SEE was good. This seems a big waste of time, since you do the SEE of every move twice. Without a move stack to store the SEE results from the first iteration this seems unavoidable.

But of course the SEE results of every move are all stored in the hash table. So what happens in practice is that you call Search() for searching the reply of every capture to search it again at Depth=2 (QS). That new node will start probing the hash, to discover that the first (SEE) iteration of its own IID has already been done before. The only thing I have to add is that it then refuses to go on IIDing to iteration 2 if the hash score is a fail high. Because then the capture leading to it had a SEE score that failed low (i.e. it was a bad capture). So almost everything goes automatic, without duplicating any work.

This can be implemented with only a few (~25) characters: I just have to abort IID (by bumping IterDepth to the maximum after the hash store) on a fail high, and calculate the depth h of the reply search a little different (d-1 for d>2, if d<=2 non-captures are not searched, while h=2 for all captures at d==2 and h=1 for recaptures at d==1).

This gives an improvement in strength, but not a dramatic improvement. (Null-move pruning definitely would help more.)

[Sven Schüle]

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 misunderstood how you are using the depth parameter, now I see. Sorry if I have confused you a little bit.

Still I think that searching the null move's subtree with a depth of 0 (i.e., either doing qsearch or, if QS disabled, just returning evaluate()) does not help very much because the intention of null move pruning - verifying that the opponent has a weak position even if he moves twice - seems to be missed. When calling evaluate() only, the opponent even does not make his second move, so where's the proof that he has no threat? When doing QS after null move, checking of threats is restricted to moves considered in QS.

But it's possible that my thoughts are non-standard here. Perhaps I should even take this thread as a request to check my own null move implementation, which currently skips null move searches completely if (depth - 1 - R) is too small. Maybe I'm wrong in doing this?

Sven

[Patrice Duhamel]

I misunderstood how you are using the depth parameter, now I see. Sorry if I have confused you a little bit.
Sven

No problem
skipping null moves when depth < depth_reduction solve my problem,
and now I understand that quiescence is important,
I disabled it because I wanted to be sure the problem didn't come from it.

But I'm not sure to understand what really happens in null moves when depth becomes too small.

[H.G.Muller]

But it's possible that my thoughts are non-standard here. Perhaps I should even take this thread as a request to check my own null move implementation, which currently skips null move searches completely if (depth - 1 - R) is too small. Maybe I'm wrong in doing this?

I think this is indeed wrong. The most important threats are the opponent's captures. If he has good ones you lose material immediately, and QS will see it.

Your thoughts are standard, but unfortunately standard thinking on Null-Move Pruning is rather hand-waving. NMP works because there almost always is a move available that can buy you time. It might be trading a piece, which he has to recapture, or it might be attacking a high or hanging piece, which he has to rescue, before he can get to executing his original threat.

That the number of threats you can recognize is limited in some way in QS, or because of low search depth in general, is of absolutely no importance, as long as they are the same threats you would recognize after two normal plies. If depth=3, after null move you are in QS (R=2), so you won't recognize if his Knight can fork your R+R, costing you the exchange. But if you would do the normal search, amongst all those moves you search you would most likely be able to come up with a move that attacks his Q, or Bx(defended)N, even if they do nothing against the fork threat. And he has to recapture your B or save his Q. Trying the fork on ply 2 would cost him the Q, or you would simply move the B back to where it came from, and the exchange he then takes is not enough compensation.

So his ply 2 is spoken for, and after you play ply 3 you are in QS anyway. And there you will see and ignore exactly the same threats as in the QS after null move, for they are both QS. The null move is merely a probe for what you can expect the search to come up with after your most-delaying move. If you find that that is not very bad (i.e. not bad enough to push you under alpha) a deeper search on the real moves would not find it either. That it can still be arbitrary bad (you might be checkmated in 3...) is irrelevant; since the deeper search won't find it anyway, that search will still be a waste of time.

This whole line of reasoning critically depends on a delaying tactic being available. When this is not the case, NMP immediately leads to tactical mistakes. This you can easily conclude from a few test positions. Typical cases are where you either have no tactical moves at all, or where the main threat is so severe that your tactical attempts for delaying them are simply ignored. (If mate in one threatens, attacking his Queen with a Pawn will make no impression even if the Q is not the piece executing the checkmate...)

That NMP 'works' in general, is simply because these kind of mistakes are much less common in the tree than the cases where the underlying assumptions were fulfilled. (And there is of course always the chance that you have a move available that really counters the threat, tipping the odds even more in your favor. Also keep in mind that when you are above beta, your opponent will play like an idiot, trying everything, which is quickly breaking down his own position offering you zillions of possibilities for nasty threats.) So you save a lot of time with only a moderate bit of extra inaccuracy. By re-applying the time saved to deepen the search, you gain more accuracy than you lost, and so you benefit. This is a statistical thing. If the statistics for delaying moves being available was less favorable, you would over all be hurt by it. This can happen in tactically-poor environments (Pawn endings, Bishops that cannot get to undefended Pawns of the opponents), but theese are easy to recognize, and usually we do switch off NMP in such positions.

[Sven Schüle]

skipping null moves when depth < depth_reduction solve my problem

Hi Patrice,

thanks to this thread I have found an improvement of my null move implementation. Up to now I did the following:
- when depth <= 3 I skipped trying the null move;
- when depth >= 4 I tried the null move with R=2 and searched at least one full ply (depth - R - 1 >= 1).

Now I do this:
- when depth <= 2 I skip trying the null move;
- when depth == 3 I try the null move with R=1 and search one full ply (depth - R - 1 == 1)
- when depth >= 4 [see above]

This seems to give me one more ply with the same number of nodes (in fact it also speeds up a little because it saves full search nodes and thus raises the percentage of the faster QS nodes).

The following additional change did not make any substantial difference, so I discarded it:
- when depth == 2 try the null move with R=1 and perform QS (depth - R - 1 == 0)

I think the "if (depth <= 0) return qsearch()" code (where "depth" is already reduced by R-1) includes both the "successful" and the "neutral" changes I have described, except that in the "successful" case no R=1 but R=2 followed by immediate QS is applied. So maybe many engines already have this kind of improvement which may then only be an improvement of "Surprise".

Sven

[H.G.Muller]

The following additional change did not make any substantial difference, so I discarded it:
- when depth == 2 try the null move with R=1 and perform QS (depth - R - 1 == 0)

It probably will when you save the results in the hash as 4-ply searches, rather than 2-ply searches, for the benifit of later iterations.