Is LMR safe within NULL move reduction

[AlvaroBegue]

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.

The problem is that to keep the program understandable you have to stay away from transposition tables, the null-move heuristic and LMR. That's enough to never win a game against program that uses these "more random" techniques.

[hgm]

But at least you would understand why you reproducibly lose!

[hgm]

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.

Not at all. Joker, for instance, does LMR on all non-captures except passer pushes (and checks, of course, which are extended). There is nothing random about that, and when it overlooks something, at a certain depth, you can still count out completely why it was beyond the horizon, just as you can with a fixed-depth search. You just have to couny null moves for 3 and non-captures for 2.

[Don]

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.

I don't think he really meant that, although you are right that null move is probably not safe by any reasonable definition.

The reason I know is that he followed up that statement with fears that some micro would find a relatively simple threat that null move missed. What he said was laced with fear that a micro would embarrass the program.

The strongest example of this is that he was a big advocate of extensions - and he even admitted there were so many that it weakened the program. When I asked why he would do something that weakened the program he said that they must be able to see anything that a micro might see doing a highly selective search. He feared the thing he would not do!

I don't know how the other team members felt, but his philosophy was extremely conservative, it was not about taking it to the micro programs but defending against them and not failing to see any possible thing that some micro might discover either by being highly selective or by Deep Blue missing something due to being selective. I think he figured they could "cover" both scenarios with their immense computer power.

I detected a great deal of naivety about computer chess but to be fair Hsu was very smart and was a hardware person, not a chess programmers as such. At the time nothing could touch Deep Blue so they certainly didn't do badly. I just had this feeling that it could have been quite a bit more than it was. Also, to be even more fair they had to deal with both software and hardware issues - and their primary focus was on chip building and making the hardware work.

[Don]

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.

I don't think he really meant that, although you are right that null move is probably not safe by any reasonable definition.

The reason I know is that he followed up that statement with fears that some micro would find a relatively simple threat that null move missed. What he said was laced with fear that a micro would embarrass the program.

The strongest example of this is that he was a big advocate of extensions - and he even admitted there were so many that it weakened the program. When I asked why he would do something that weakened the program he said that they must be able to see anything that a micro might see doing a highly selective search. He feared the thing he would not do!

I don't know how the other team members felt, but his philosophy was extremely conservative, it was not about taking it to the micro programs but defending against them and not failing to see any possible thing that some micro might discover either by being highly selective or by Deep Blue missing something due to being selective. I think he figured they could "cover" both scenarios with their immense computer power.

I detected a great deal of naivety about computer chess but to be fair Hsu was very smart and was a hardware person, not a chess programmers as such. At the time nothing could touch Deep Blue so they certainly didn't do badly. I just had this feeling that it could have been quite a bit more than it was. Also, to be even more fair they had to deal with both software and hardware issues - and their primary focus was on chip building and making the hardware work.

I would also say that at the time a lot less was known about selectivity. Null move was starting to become well know but engineers are conservative and we were only starting to get away from the "brute force rules" age of computer chess.

[AlvaroBegue]

[...] At the time nothing could touch Deep Blue so they certainly didn't do badly.

Although that statement is plausible, is there any direct evidence of this?

As far as I can tell, they only participated in a computer-chess tournament once (8th WCCC in 1995) and they didn't win. Of course the 1997 version was probably stronger, so those 1995 games are not evidence that what you are saying is wrong.

Deep Blue had been dismantled by the 9th WCCC in 1999.

[Don]

[...] At the time nothing could touch Deep Blue so they certainly didn't do badly.

Although that statement is plausible, is there any direct evidence of this?

There was little doubt. Deep Blue and it's predecessors won almost every tournament they were in. The 8th WCCC was not the only tournament. I met them for the first time in Dallas when their program was called Chiptest.

As far as I can tell, they only participated in a computer-chess tournament once (8th WCCC in 1995) and they didn't win. Of course the 1997 version was probably stronger, so those 1995 games are not evidence that what you are saying is wrong.

Deep Blue had been dismantled by the 9th WCCC in 1999.

After beating Kasparov in the puny 4 games match it was in their best interest to dismantle it. In those days, a computer program was almost like a magic trick, you really didn't want people looking too hard. As you say it was already possible to beat it with a good micro so the handwriting was on the wall as they say. Had they kept it around to witness Moores Law it would have gotten ugly for them pretty shortly.

[Henk]

Sounds interesting. But what do you mean with count null move as 3 etc. Please explain.

[hgm]

I mean a null move counts for 3 plies (if R=2). So if you search ply, a branch like PVmove - PVmove - capture - recapture - lateMove - null will bring you into QS at 9 ply (as the null counts for 3, and the lateMove for 2). Depending on whether you search null move when the remaining depth is 1, you might already search this branch at 6 ply, because that would leave 2 ply after the recapture, and at that depth late moves would not yet be reduced, so you would be left with 1 ply after the lateMove, and try a null that jumps into QS. You would need to search at least 10 ply to see any non-capture that refuted the second null.