Is LMR safe within NULL move reduction

[Steve Maughan]

Hi Henk,

You seem too hung-up on not finding the best move. Chess is not a solved game - no chess program always find the best move. So chess programming comes down to finding rules-of-thumb (i.e. heuristics), which normally indicate a good move. All of these heuristics are wrong sometimes, the skill of chess programming is minimizing the times they are wrong and adding heuristics which will guide the search in the right direction.

There is virtually zero "luck" in computer chess. If Monarch (my old engine) played 1000 games again Houdini it would win zero games.

Steve

[syzygy]

unlike null move pruning that may cause the program never to find the best move in cases of zugzwang LMR is safe in the meaning that you can be sure that finding the best move is only a question of time.

Yes, in a world where an engine can search as long as it wants you are right. In this world engines play with a time control. Therefore the time needed to find out that a reduction of a move was wrong might not be there. This makes it unsafe.

Of course plain alpha/beta is much less safe than (well-implemented) LMR + null move, because when playing with a time control the engine will miss many more tactics and subtle ways to improve its position than LMR + null move. (I am sure you agree.)

The problem is that any engine in existence is unsafe.

[hgm]

Indeed, it is unsafe to move unless you have a mate or tablebase score that is within the horizon. Better never use engines!

[Don]

No it is not safe, because whole LMR is not safe.

I take the view that our definition of "safe" is wrong. In other words, failing to use LMR and null move pruning is NOT safe. You will get crushed by a program that uses them because they won't miss all the things your program will miss.

In other words we need different language for expressing these concepts.

I had a long conversation with Hsu many years ago about deep blue and something really stood out that he said. He said that they would not use null move pruning because it "wasn't safe." He was making a distinction between playing strength and being embarrassed by "missing" some move. That makes no sense because playing strength (as measured by ELO) has the odds built in to it. The higher it is, the less likely you will lose a game or be embarrassed.

I know that they eventually did embrace null move pruning - perhaps due to my conversation, perhaps not.

When you ask if it's safe, I think you are concerned with pruning away some move at a particular iteration - and the answer is that null move pruning and LMR will make your program miss things at the same depth that a brute force full width search won't. However, a reasonably good implementation of both will give you a lot of ELO, and if you like to win then the safest bet is to use both of these techniques.

You are probably concerned (as I am too) that piling up reduction on top of reductions has to take it's toll at some point. Even though it can and does happen that you lose several ply, you gain several ply of search depth with a quality implementation of null move pruning combined with LMR. Keep in mind that most program forbid reductions for checks, captures and suspected high ranking moves. Captures and checks form the heart of chess, and following them goes a lot way towards mitigating serious errors. When a move is reduced it's still searched, and when a "best" move is pruned by mistake it's not always game critical.

You might end up missing a good move and this might cost you the game.

If you restrict yourself to safe optimization methods you have to stick to plain alpha beta and a very limited (= safe) form of futility pruning.

Then you can be sure that within the search horizon of your program you want miss a good move.

Thomas...

That's it in a nutshell. You cannot be too paranoid about "missing" a move or else you will "miss" moves for reason of limited search horizon.

[syzygy]

Indeed, it is unsafe to move unless you have a mate or tablebase score that is within the horizon. Better never use engines!

Let's all find another hobby!!

[syzygy]

I had a long conversation with Hsu many years ago about deep blue and something really stood out that he said. He said that they would not use null move pruning because it "wasn't safe." He was making a distinction between playing strength and being embarrassed by "missing" some move. That makes no sense because playing strength (as measured by ELO) has the odds built in to it. The higher it is, the less likely you will lose a game or be embarrassed.

I know that they eventually did embrace null move pruning - perhaps due to my conversation, perhaps not.

I always thought DB never used null move? From what I understand from this paper, Deep Blue did perform null move searches, but to extend rather than to prune.

[tpetzke]

Hi Don,

you don't have to convince me. I'm using Null Move (incl. static null move pruning) and a very (maybe too) aggressive LMR scheme in my engine.

When you develop a chess engine there is no way around those. But if you start a chess engine it might be wise to delay those techniques until your alpha-beta framework, move ordering schema, transposition table, mate distance pruning (the safe stuff) etc... is fully functional and debugged. And that is a lot of work.

A safe engine is not a strong engine but it might be a good first step towards one.

Thomas...

[Don]

I had a long conversation with Hsu many years ago about deep blue and something really stood out that he said. He said that they would not use null move pruning because it "wasn't safe." He was making a distinction between playing strength and being embarrassed by "missing" some move. That makes no sense because playing strength (as measured by ELO) has the odds built in to it. The higher it is, the less likely you will lose a game or be embarrassed.

I know that they eventually did embrace null move pruning - perhaps due to my conversation, perhaps not.

I always thought DB never used null move? From what I understand from this paper, Deep Blue did perform null move searches, but to extend rather than to prune.

I could be wrong, but my understanding is that the software component of their search used a limited form of null move pruning and was much like a conventional program of the time. I think the software does a few ply of searching then gets results from hardware which is sort of like a super evaluation function. This of an evaluation function black box - which actually does a search. So maybe deep blue doing a 1 ply search would play like a program doing several ply of searching.

I think the hardware search is pretty basic full width but I really don't know the details of how it's all put together and I might even be wrong about the above.

[Henk]

It seems that it is all of about reasoning with chances. If the program does this you have a good chance of finding good moves in that or these chess position but you can never be sure.

The nice thing about a more brute force method is that errors or bad moves are easy to explain. The answer is 'It's because the program only searches N plies deep'.

If you use LMR or similar reductions and you lose games you keep asking why did the program reduced that variant and lost the game. The answer is because it was ranked lower in the move order or something like that. Vague and less clear. More randomness involved.

[AlvaroBegue]

I think I know what Hsu meant when he said that null-move pruning is not safe. A program that uses minimax with iterative deepening will eventually find the best move in every single position (although "eventually" here might mean after the thermal death of the universe). We'll say that a search technique is safe if it preserves this feature. Examples are quiescence search, alpha-beta pruning, move-ordering heuristics, extensions, reductions... Then there are techniques that will make your program pick the wrong move in some positions, regardless of how much time you give it. Examples of these are selective search (some idea from the 80s to only try the N most promising moves at each node), transposition tables (at least most versions of them, because of graph history interaction) and the null-move heuristic (because of zugzwang).

In that sense LMR is safe, within null move reduction or otherwise.