Using SEE to prune in main search

[jdart]

I have done some experimentation with LMR > 1 ply lately. Arasan 12.2 does this under some conditions. See is not currently one of them.

Note that several programs do very aggressive LMR - IvanHoe is one example. Its reduction is:

new_depth = depth - 2 + EXTEND - (4 + BSR (4 + cnt));

where "2" is the regular reduction for the next ply, so if I read this right it will do an extra reduction of 6 (3 plies) at least (this is done for depth >= 7, or 3.5 plies).

[lkaufman]

Isn't this aggressive reduction done only at cut nodes, where it doesn't make so much difference what you do due to re-searches?

[jdart]

Isn't this aggressive reduction done only at cut nodes, where it doesn't make so much difference what you do due to re-searches?

Yes, it is at cut nodes. But that still means if you do not trigger research, you are accepting a quite reduced depth score as valid.

[bob]

Isn't this aggressive reduction done only at cut nodes, where it doesn't make so much difference what you do due to re-searches?

Yes, it is at cut nodes. But that still means if you do not trigger research, you are accepting a quite reduced depth score as valid.

I agree. The decisions that are based on a "guess" of whether a node is ALL, PV or CUT are basically flawed. If you disable things everywhere but in the ALL/CUT nodes, you simply make it harder to change your mind. Not a good idea. I see absolutely nothing that says that once you find a score for the first move searched, that you should search the remaining moves with different extensions and reductions. What possible justification can there be? None.

[bob]

[quote I reduce the first move searched by 1 ply, but only if it is not a hash move, a good capture nor a killer. "

I don't know of any other program that will reduce the very first move other than at cut nodes. Did you also test reducing starting at the second move, and if so how much better was it to reduce the first move? Do you do this even at PV nodes, and if so do you ever get PVs shorter than nominal depth? If not why not?

I tested everything. Remember, to actually reduce the first move, there must be no hash move, no good captures, and no killers. That is very unlikely. In fact it is _extremely_ rare by measurement. I discovered this 1 ply on first move, 2 on the rest quite by accident but after carefully testing, it worked well for me. Of course, we are talking about maybe 3-4-5 Elo at most, but almost every change we make is 2-3-4-5 Elo (when they work) so we take 'em and add 'em up.

[lkaufman]

[quote Yes, it is at cut nodes. But that still means if you do not trigger research, you are accepting a quite reduced depth score as valid.

I think this just means you might miss the opportunity to take a cutoff. So it's just a question of which way is faster, extra reductions at cut nodes shouldn't hurt search quality, I believe.

[outAtime]

From what I can tell so far from my own tries is that going straight from depth -1 on the first move to depth -4 or -5 on all (non pv) remaining moves in the main search (some conditions excluded) fails to improve the engine badly, even if the moves are researched. I haven't added any pruning to the search, so maybe I could reduce in a more aggressive fashion if some "bad" moves were already out of the equation. This is why I became interested in the SEE pruning idea and I like the code example pointed out in this thread, but it isn't at all trivial atm, so it is down on the list. I have become interested in "expected bad moves which should not be reduced". Maybe it is a counterproductive idea, but if there are expected good moves which should not be reduced, why not? So far these moves seem to appear towards the end of the move list. I compare this to Monty Hall---only instead of 3 doors, maybe there are 100, we pick 1 door that for whatever reason we expect to have a "best move" behind it and search it with depth -1, then Monty Hall (reductions) opens another 80 for us. We still can't be sure about the door we picked because we don't know whats behind the remaining 19 doors, but maybe statistically we should search the remaining 19 doors with depth -1 as well---almost as though we could trade our first pick for the remaining 19, having a good idea about the other 80, and keep the first one if we don't like it. I've tried pruning these remaining moves, and the search seems to "lose information" somehow.

[bob]

[quote Yes, it is at cut nodes. But that still means if you do not trigger research, you are accepting a quite reduced depth score as valid.

I think this just means you might miss the opportunity to take a cutoff. So it's just a question of which way is faster, extra reductions at cut nodes shouldn't hurt search quality, I believe.

That means you are less likely to discover a better move...

We have tried lots of such tricks over the years. For example, find the best move at depth=N, then search remaining moves with value+10, value+11, rather than value, value+1, which makes it harder to "change your mind" for tiny score changes. Everybody has noticed that you can expend a tremendous amount of error to improve the score by .01 or .02, and actually end up playing a worse move.

However, that "fix" is provably weaker when you test thoroughly.

If you are convinced your best move is really best, reducing the effort everywhere else is a good idea. But if you are wrong, boom...