Reduced depth search after Fail high at the root

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Viz
Posts: 98
Joined: Tue Apr 09, 2024 6:24 am
Full name: Michael Chaly

Re: Reduced depth search after Fail high at the root

Post by Viz »

Well, if it was the case lazySMP wouldn't work.
But it does work.
Ofc search from scratch to certain depth will result in the same result, but research wouldn't and can be vastly different because of all data you have acquired previously - transposition table moves and history heuristics shaping up stuff in a massive way.
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Reduced depth search after Fail high at the root

Post by hgm »

Viz wrote: Thu May 16, 2024 5:35 pm Well, if it was the case lazySMP wouldn't work.
But it does work.
Ofc search from scratch to certain depth will result in the same result, but research wouldn't and can be vastly different because of all data you have acquired previously - transposition table moves and history heuristics shaping up stuff in a massive way.
Lazy SMP works fine if all threads attempt to search the same tree, as one would expect. But since there was no disclaimer here that lowering the depth for a research should never be done in a single-threaded search, that seems off topic here.

And as you now confirm, in the engine that you describe the depth parameter has no relation to what is searched, as it can be "massively different" for the same depth. Of course most engines don't work that way at all, and for those lowering the depth would be a pointless exercise.
AndrewGrant
Posts: 1809
Joined: Tue Apr 19, 2016 6:08 am
Location: U.S.A
Full name: Andrew Grant

Re: Reduced depth search after Fail high at the root

Post by AndrewGrant »

You missed my entire comment, HGM.

> Depth stopped being meaningful (between entities) the first time anyone did unsound pruning. Which I imagine is 40+ years ago.
Friendly reminder that stealing is a crime, is wrong, and makes you a thief.
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
JacquesRW
Posts: 69
Joined: Sat Jul 30, 2022 12:12 pm
Full name: Jamie Whiting

Re: Reduced depth search after Fail high at the root

Post by JacquesRW »

hgm wrote: Thu May 16, 2024 6:25 pm Of course most engines don't work that way at all, and for those lowering the depth would be a pointless exercise.
Do they not? Basically any engine over like 2200 CCRL will have something like LMR and already depth is starting to lose its original meaning, because a re-search with different move ordering will cause a massive difference to the tree shape. With transposition tables and history heuristics, as Viz mentioned, this seems enough to cause a re-search to be drastically different already. I can't comment on whether the depth reduction would be useful at that level or not though.
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Reduced depth search after Fail high at the root

Post by hgm »

AndrewGrant wrote: Thu May 16, 2024 6:46 pm You missed my entire comment, HGM.

> Depth stopped being meaningful (between entities) the first time anyone did unsound pruning. Which I imagine is 40+ years ago.
I thought my previous comment already referred that to the dustbin. Unsound pruning in no way makes depth a meaningless parameter. It can of course alter the meaning, but that is something completely different.
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Reduced depth search after Fail high at the root

Post by hgm »

JacquesRW wrote: Thu May 16, 2024 6:55 pm
hgm wrote: Thu May 16, 2024 6:25 pm Of course most engines don't work that way at all, and for those lowering the depth would be a pointless exercise.
Do they not? Basically any engine over like 2200 CCRL will have something like LMR and already depth is starting to lose its original meaning, because a re-search with different move ordering will cause a massive difference to the tree shape. With transposition tables and history heuristics, as Viz mentioned, this seems enough to cause a re-search to be drastically different already. I can't comment on whether the depth reduction would be useful at that level or not though.
LMR needs not be based on move ordering; it can just as well be based on move type (e.g. good capture / non-capture / bad capture). Even if one uses ordering by history for deciding the magnitude of the reduction (and you can get easily above 2400 CCRL without doing that) it is questionble how much the ordering will be different on re-search, as history is a heuristic that tend to confirm itself: moves with good history tend to produce more cutoffs, not so much because they are better than others, but because they will be tried before the others.
Uri Blass
Posts: 10420
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Reduced depth search after Fail high at the root

Post by Uri Blass »

hgm wrote: Thu May 16, 2024 7:31 pm
JacquesRW wrote: Thu May 16, 2024 6:55 pm
hgm wrote: Thu May 16, 2024 6:25 pm Of course most engines don't work that way at all, and for those lowering the depth would be a pointless exercise.
Do they not? Basically any engine over like 2200 CCRL will have something like LMR and already depth is starting to lose its original meaning, because a re-search with different move ordering will cause a massive difference to the tree shape. With transposition tables and history heuristics, as Viz mentioned, this seems enough to cause a re-search to be drastically different already. I can't comment on whether the depth reduction would be useful at that level or not though.
LMR needs not be based on move ordering; it can just as well be based on move type (e.g. good capture / non-capture / bad capture). Even if one uses ordering by history for deciding the magnitude of the reduction (and you can get easily above 2400 CCRL without doing that) it is questionble how much the ordering will be different on re-search, as history is a heuristic that tend to confirm itself: moves with good history tend to produce more cutoffs, not so much because they are better than others, but because they will be tried before the others.
I understand that you basically want depth of the line to be based only on the moves of the line(for example you are not against a rule that a bad capture will always be reduced even if you found that it is the best move in previous iteration).

This also means that you cannot use null move pruning in the way engines use it today because null move pruning is based on the question if there is a threat and a threat is relative to the score you got in the search and this score may be changed.

If I understand correctly the only way that you accept null move pruning is
if the threat is measured relative to the evaluation of the position and you ignore the evaluation that you already got earlier in the search to decide if to do null move pruning.

I believe this is not what engines usually do
and basically if 1.d4 failed high and you got +10 score earlier because it wins the opponent queen,
they decide that 1.e4 has no threat even if 1.e4 wins a knight and clearly improve the evaluation relative to doing nothing.
AndrewGrant
Posts: 1809
Joined: Tue Apr 19, 2016 6:08 am
Location: U.S.A
Full name: Andrew Grant

Re: Reduced depth search after Fail high at the root

Post by AndrewGrant »

hgm wrote: Thu May 16, 2024 7:18 pm
AndrewGrant wrote: Thu May 16, 2024 6:46 pm You missed my entire comment, HGM.

> Depth stopped being meaningful (between entities) the first time anyone did unsound pruning. Which I imagine is 40+ years ago.
I thought my previous comment already referred that to the dustbin. Unsound pruning in no way makes depth a meaningless parameter. It can of course alter the meaning, but that is something completely different.
I'll once again repost my comment and add additional emphasis lol

> Depth stopped being meaningful (between entities) the first time anyone did unsound pruning. Which I imagine is 40+ years ago.

A classical example is engines that love to extend, vs engines that love to reduce. They'll get drastically different depths on average, and yet that number does not really indicate their strength relative to one another.
Friendly reminder that stealing is a crime, is wrong, and makes you a thief.
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Reduced depth search after Fail high at the root

Post by hgm »

Ah, with 'entities' you meant different engines. Sorry I missed that. Then yes, of course, different engines attach different meaning to their depth parameter. This is not really relevant to the issue, though. The original question was about redoing the search at lower depth after fail high with the same engine. Not repeating the search with a different engine...
Viz
Posts: 98
Joined: Tue Apr 09, 2024 6:24 am
Full name: Michael Chaly

Re: Reduced depth search after Fail high at the root

Post by Viz »

hgm wrote: Thu May 16, 2024 7:31 pm
JacquesRW wrote: Thu May 16, 2024 6:55 pm
hgm wrote: Thu May 16, 2024 6:25 pm Of course most engines don't work that way at all, and for those lowering the depth would be a pointless exercise.
Do they not? Basically any engine over like 2200 CCRL will have something like LMR and already depth is starting to lose its original meaning, because a re-search with different move ordering will cause a massive difference to the tree shape. With transposition tables and history heuristics, as Viz mentioned, this seems enough to cause a re-search to be drastically different already. I can't comment on whether the depth reduction would be useful at that level or not though.
LMR needs not be based on move ordering;
LMR is extremely heavily based on move ordering, not only it reduces more for latter moves, but it also takes into account history sum to reduce less/more in basically any strong engine - and this is worth quite a chunk of elo, in fact, continuation histories are worth more in LMR reductions than they are worth in move ordering itself in Stockfish, for example.