Do you evaluate internal nodes?

[Tord Romstad]

I am a little surprised that so many evaluate all internal nodes.

That's funny. I'm surprised for the opposite reason: I thought almost everybody evaluated all internal nodes these days.

It is funny that you guys started this thread, because I started experimenting with this on Sunday.
Currently I use eval only for the non-leaf futility pruning.

Last time I tried eval>=beta for null move (long time ago), it didn't work. Naum was searching much faster, but it was causing the 'blind spots' in the search.

On Sunday I had an idea that seems to be solving the blind spot problem in some test positions, but the test match against Fruit showed no improvement. I think that search is still unstable.

Did someone try maybe eval + [some margin] > beta as a condition?
Would be slower, but search might be more stable.

Yes, I have tried this many times, with positive as well as negative margins. So far, I haven't found anything which works better than a zero margin.

After reading your post, I decided to try to drop the static eval > beta condition and run some tests. The conclusion is the same as before: Glaurung's strength drops like a stone if I allow null move everywhere.

Tord

[Naum]

Hi Tord,

When I tried not to do eval>beta when null-move does the q-search (NullMoveDepth==0), I got an improvement in test games and also most of the test positions.
I think you do eval>beta for any depth, but test positions indicate that Naum doesn't like it. Of course, I should try testing this in games.

Regards,
Alex

[Gian-Carlo Pascutto]

After reading your post, I decided to try to drop the static eval > beta condition and run some tests. The conclusion is the same as before: Glaurung's strength drops like a stone if I allow null move everywhere.

Tord

You shouldn't allow two nullmoves in a row (eval >= beta does this), or allow at most 2 in a row.

Otherwhise you just put nullmove upon nullmove and end up pruning 20 ply searches with the qsearch alone.

[L?szl? G?sp]

I might not be that experienced in chess programming but I find Gian-Carlo's statement faulty (I know it's widely accepted in the community). When 2 nullmove is tried in a row, the eval >= beta condition fulfills only once, for the better side.

Best regards,
L?szl?

[Volker Böhm]

The first item on this list is by itself more than enough to compensate for the expense of evaluating internal nodes in my program. Avoiding too many useless null move searches saves a lot of nodes.
Tord

Hi Tord,

I can?t fully agree. You do not need a full eval to reduce nullmoves.
Only the most static part of the eval is really good for this decision: Material, Pawn-Structure and Piece-Square-Tables are a good approach. All of them could be evaluated at practically no cost (incremental or hashed).

Greetings Volker

[Volker Böhm]

Sometimes a simple question is hard to answer. Spike calls part of eval for futility pruning, but not in general. Thus I answered no.

Greetings Volker

I wonder if you tried to evaluate every node and use it for pruning or reductions.

I use it mainly for pruning when for reduction I use mainly history based reduction.

I consider to change to glaurung type reduction of bad moves that seem better.

I believe that history based reduction can be productive but I also believe that practically evaluation based reduction can be better because after improving evaluation based reduction you may need to change the history based reduction to be based on different history if you want it to work and when you have limited time to experiment it may be better to improve evaluation based reduction.

Uri

Hi Uri,

no I didn?t try evauation based reduction, I only tried reduction rules that differ from history reduction (like pushing passed pawns, doubling rooks, ...) but I wasn?t sucessfull finding terms that gives better result than history.

In my opignon a "plain" history reduction like I?ve seen in Fruit 2.1 is not far away from evaluation based reduction:
Most moves are at leaves. Most good moves at leaves are moves where eval is better than eval from other moves from same position. Thus much eval influence in history tables!

In my tests reducing the eval influence thus reducing the weight of moves near the leaf improves history pruning.

Greetings Volker

[H.G.Muller]

Doing two null-moves in a row is always meaningless. It is true that the condition eval>beta prevents this, but even if one does not (always) use that condition to decide on the desirability to try a null move, one should add a test to prevent two null-moves in a row.

By the way, I look upon the null-move as a metaphor for any move that does not cause an acute threat to the opponent, useful in order to find out if he has any threats up his sleeve without unduly complicating the situation by new threats.

This inspired to me the idea of a 'null-capture': if you want the engine to figure out if it is save to capture anything (e.g. the piece last moved, to check if it is hanging) you can of course do it with a regular capture move, but the piece you capture with might add all kinds of threats to the situation that tell you more than you wanted to know (namely if it is a good idea to try to capture it with higher valued pieces as well), and therefore often obscures the answer you are interested in. So a 'null-capture' would be a move that removes the enemy piece without adding any offensive complications to the situation.

To implement this, one could for instance replace the enemy piece by a piece of our ow called a 'striker', a piece that is accounted in your material evaluation as the piece with which you captured, but is not allowed to make any moves (i.e. it is on strike), while at the same time replacing the capturing piece on the square it came from by a 'block' or 'ghost' of the piece (but preventing new tactical moves over this square that would be specific to this mode of capture, but will prevent that we use this piece a second time).

To me it seemed that such a pseudo-move could be useful in QS, where the aim is to reach a quiet situation (i.e. where eval is meaningful) as quickly as possible. The null-capture would help to achieve this by preventing 'overshoot' from a situation where you resolve an old tactical tension at the expense of starting a new one. The score of the null-capture could be used as a reference: the score of any true capture is likely to be better, just as the score of any true quiet move is likely to be better than that of the null move.

Has such an idea ever been tried?

[Richard Pijl]

I might not be that experienced in chess programming but I find Gian-Carlo's statement faulty (I know it's widely accepted in the community). When 2 nullmove is tried in a row, the eval >= beta condition fulfills only once, for the better side.

This is not true for every engine. Some engines are dependent on side to move in their evaluation function for e.g. passed pawn evaluation. It might very well be (especially with nullwindows) that eval>=beta, for either side to move.

Doing two null-moves in a row is always meaningless.

This is not true. It does two things:
- implicit zugzwang verification (when limited to two null-moves in a row)
- implicit internal iterative deepening

Richard.

[H.G.Muller]

- implicit internal iterative deepening

Hmm, with this you mean that doing a null-move before any of the others is another way to first search the same position with a lower depth, and that the results (best move, value) of such a search are passed down towards the node closer to the root through the hash table anyway?

This is indeed a clever and very elegant idea! It could probably shrink my 2000-character chess program Micro-Max (which implements both a hash table and iterative deepening) by quite a lot of characters. In the current version I need the overhead of an extra loop for it. In addition, it might also very elegantly blend into a QS with null moves, for which in the current version of Micro-Max I had no room.

[mridul]

Doing two null-moves in a row is always meaningless. It is true that the condition eval>beta prevents this, but even if one does not (always) use that condition to decide on the desirability to try a null move, one should add a test to prevent two null-moves in a row.

Double nullmove is a known technique to minimise the effects of zugwang to a large extent - initially proposed by Vincent Diepeveen and now used by many.

Mridul

[H.G.Muller]

Ah. I guess I am not familiar with that problem because I seem to use the null-move in a slightly different way as others do. The score of the null-move doesn't participate directly in the determination of the maximum value, but acts as a default value for moves that are pruned. So it can only seem a good solution if there are indeed moves available, i.e. no zug-zwang. (If the fatal move that zugzwang forces me to do is not considered at the level where I tried the first null move, it will certainly not be considered two null-moves later, so I would not detect it anyway. But that is true for anything that lies beyond the horizon.)

[L?szl? G?sp]

I made the mistake that I followed my own logic. So I accept that the eval > beta condition doesn't work for others automatically, but I think they do something wrong. In principle nullmove is a try to prove that the already established variation is the best (on a given depth). With R=1 this is true. R=2 is already an aproximation. When R=2 we can use lazy eval as V?lker suggests since we already made errors. Ok, the error is not that big and relative safe as the practice shows. But in my opinion nullmoves with R = 2 (3,..) is not optimimal. I think the optimal (and technically sound) solution is the recursive nullmove with R=1 and with the "full symmetrical eval" > beta condition. Certainly in zugzwang situation nullmove is not applicable.

[Uri Blass]

Hi Tord,

When I tried not to do eval>beta when null-move does the q-search (NullMoveDepth==0), I got an improvement in test games and also most of the test positions.
I think you do eval>beta for any depth, but test positions indicate that Naum doesn't like it. Of course, I should try testing this in games.

Regards,
Alex

same for me.

eval>beta does not seem to work for me and I do not do null move when the remaining depth is smaller than 2 because I have other pruning algorithm in that case and I found that null move+evaluation after it is too expensive there.

I may try doing null move pruning when the remaining depth is 1 only in part of the cases but I doubt if it is going to help much.


Uri

[H.G.Muller]

I have always eyed null-move pruning with suspicion: it seems a fundamentally wrong approach to (partly) solve a genuine problem. As a consequence it might be a dead end, despite the initial improvement it gives.

Null-move is all about threat detection, and the null move is likely to recognize the same threats at lower search depth as the best real move, due the classical horizon effect: the side to move will use its first ply for a forcing move (initiating an exchange of a valuable piece, or attacking such a piece), eating up two plies of search depth (and perhaps do this repeatedly) to push that threat beyond the horizon. In the null-move branch he cannot do that, since a null-move is guaranteed to be non-forcing).

But it always seemed better to me to solve the problem of delaying tactics fundamentally, rather than circumvent it: the forcing and forced moves used to push things over the horizon should not be allowed to do so (e.g. by a combination of extensions for the forced move, and making sure the forcing moves cannot eat away so much depth from the other side that it still can try the pending threat after the delaying party exhausted its options). Then you could reduce the search depth in every branch by the same amount as you do after null-move, without missing anything, which would cause enormous tree reduction (or - alternately - increase in playstrength) in cases where the null-move does not produce the fail high we hoped for, because there actually happens to be a threat that we can't afford to ignore.

[Gian-Carlo Pascutto]

I might not be that experienced in chess programming but I find Gian-Carlo's statement faulty (I know it's widely accepted in the community). When 2 nullmove is tried in a row, the eval >= beta condition fulfills only once, for the better side.

Best regards,
L?szl?

You need to add the restriction if you remove the eval >= beta check. If you have the eval >= beta check, then it normally isn't needed (exceptions discussed above).

[Sven Schüle]

Null-move is all about threat detection

Hi "H.G.",

isn't it the other way round: null-move pruning tries to prove that there is _no_ threat, even if the opponent moves twice in a row?

Also "delaying tactics" in my opinion is not a main issue of null-move pruning.

It is possible that I did not understand everything you wrote, but nevertheless: I fear you do not cover the key point here.

Of course different opinions exist

Sven

[L?szl? G?sp]

I might not be that experienced in chess programming but I find Gian-Carlo's statement faulty (I know it's widely accepted in the community). When 2 nullmove is tried in a row, the eval >= beta condition fulfills only once, for the better side.

Best regards,
L?szl?

You need to add the restriction if you remove the eval >= beta check. If you have the eval >= beta check, then it normally isn't needed (exceptions discussed above).

If you meant this already, you are right - I agree.

I have always eyed null-move pruning with suspicion: it seems a fundamentally wrong approach to (partly) solve a genuine problem. As a consequence it might be a dead end, despite the initial improvement it gives.

I think you should reconsider your viewpoint on nullmove thoroughly. In chess (game) tree search alpha-beta and nullmove should go hand in hand. Alpha-beta is not optimal alone since it works for any tree with random leaf-node values. Since in reality they are not random, by nullmoving we are able to maximize one side's gain with less effort and thus terminate the search earlier (in successful cases), reducing the search tree tremendously without missing anything.

Best regards,
L?szl?

[H.G.Muller]

Alpha-beta is not optimal alone since it works for any tree with random leaf-node values. Since in reality they are not random, by nullmoving we are able to maximize one side's gain with less effort and thus terminate the search earlier (in successful cases), reducing the search tree tremendously without missing anything.

Well, I certainly agree with the first part of your statement. As for the second part, I interpret 'maximize' as 'set an upper limit on', and this I am not so sure of. By searching with reduced depth after the null-move you might overlook threats that would have been recognized at the full search depth. The branches that you prune because of this, might have recognized the threat.

I am not denying that null-move pruning on the average helps you (a lot), but at the price of introducing some mistakes as well. So I would prefer to replace it by something that would achieve the same useful purpose, but did not introduce those mistakes. Based on what I wrote above, I think that this should be possible. But the proof of the pudding is of course in the eating of it, so I will implement this and we will see...

[Ron Murawski]

I use it for the following purposes:

• Avoiding unnecessary null move searches. If the static eval is below beta, it is unlikely that the null move search will return a score above beta, and I just skip the null move search.

The first item on this list is by itself more than enough to compensate for the expense of evaluating internal nodes in my program. Avoiding too many useless null move searches saves a lot of nodes.

Tord

I just tried this idea. For my chess engine lazy eval scoring worked better
than using a full eval score. I have not tried lazy eval plus a margin yet.

Thanks for the idea. It works well!

Ron

[L?szl? G?sp]

Alpha-beta is not optimal alone since it works for any tree with random leaf-node values. Since in reality they are not random, by nullmoving we are able to maximize one side's gain with less effort and thus terminate the search earlier (in successful cases), reducing the search tree tremendously without missing anything.

Well, I certainly agree with the first part of your statement. As for the second part, I interpret 'maximize' as 'set an upper limit on', and this I am not so sure of. By searching with reduced depth after the null-move you might overlook threats that would have been recognized at the full search depth. The branches that you prune because of this, might have recognized the threat.

I am not denying that null-move pruning on the average helps you (a lot), but at the price of introducing some mistakes as well. So I would prefer to replace it by something that would achieve the same useful purpose, but did not introduce those mistakes. Based on what I wrote above, I think that this should be possible. But the proof of the pudding is of course in the eating of it, so I will implement this and we will see...

Hi H.G.,

I also consider nullmove with R >= 2 technically not exact (I refer to my earlier post). But what objection can you have against the nullmove with R=1. It doesn't seem to be so efficient at first sight but in my opinion it has the potential when used recursively.

Regards,
L?szl?