Reducing the horizon effect

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Mike Sherwin
Posts: 43
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Reducing the horizon effect

Post by Mike Sherwin » Thu Sep 10, 2020 9:57 am

There might be a way to reduce the horizon effect by detecting a stable horizon and extending the search if it is not stable. The idea is to call Qsearch say two ply early and compare the score to that returned by a two ply further search. If the scores are close then the horizon is stable because two additional moves changed nothing. On the other hand if the scores are not close then the horizon is not stable and the search should be extended.

Mike Sherwin
Posts: 43
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: Reducing the horizon effect

Post by Mike Sherwin » Thu Sep 10, 2020 10:31 am

This idea can be brought further down toward the root. If a "stable horizon" can be detected lower in the tree then a level of confidence can be established that may allow for reductions in search depth.

Ras
Posts: 1423
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Reducing the horizon effect

Post by Ras » Thu Sep 10, 2020 1:30 pm

I think we had some discussion along that line, and HGM gave that approach the nickname "headlight algorithm": If you're in your car at night, and don't see a road turn, reduce your headlights. If you still don't see a road turn, turn them down further. Then a road turn comes up, but your headlights are switched off at this point.
Rasmus Althoff
https://www.ct800.net

Mike Sherwin
Posts: 43
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: Reducing the horizon effect

Post by Mike Sherwin » Thu Sep 10, 2020 5:12 pm

I admit that analogy does not enlighten me. Okay I found it. Some slight similarity in idea. Though, not really the same. But, it is hard to discern with the headlights dimmed.

Pio
Posts: 190
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Reducing the horizon effect

Post by Pio » Thu Sep 10, 2020 5:31 pm

Mike Sherwin wrote:
Thu Sep 10, 2020 9:57 am
There might be a way to reduce the horizon effect by detecting a stable horizon and extending the search if it is not stable. The idea is to call Qsearch say two ply early and compare the score to that returned by a two ply further search. If the scores are close then the horizon is stable because two additional moves changed nothing. On the other hand if the scores are not close then the horizon is not stable and the search should be extended.
Hi Mike, I really enjoy your posts 😀. Maybe it is because we have lots of similar ideas. I think your idea of trying to estimate the stability of the position close to the leafs is really great. I have three ideas of how it could be made

1) if the positions’ evaluation deteriorate from grandfather to father to son it shows that the position might get worse and you should extend.

2) The same might be done if the evaluations fluctuate a lot (it could actually be a really stupid way of doing quiescence search) and is a type of generalisation of Qsearch

3) If the move stored in the hash table (transposition table) is the same going one depth greater a counter is increased for the position saved in the TT, if it changes the counter is decreased. When probing for an entry in the TT you read the counters. If the counters are high it means the path is more stable and you can reduce.

Good luck Mike. I follow your threads with great interest and think most of your ideas are great!!!

Mike Sherwin
Posts: 43
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: Reducing the horizon effect

Post by Mike Sherwin » Thu Sep 10, 2020 5:47 pm

Pio wrote:
Thu Sep 10, 2020 5:31 pm
Mike Sherwin wrote:
Thu Sep 10, 2020 9:57 am
There might be a way to reduce the horizon effect by detecting a stable horizon and extending the search if it is not stable. The idea is to call Qsearch say two ply early and compare the score to that returned by a two ply further search. If the scores are close then the horizon is stable because two additional moves changed nothing. On the other hand if the scores are not close then the horizon is not stable and the search should be extended.
Hi Mike, I really enjoy your posts 😀. Maybe it is because we have lots of similar ideas. I think your idea of trying to estimate the stability of the position close to the leafs is really great. I have three ideas of how it could be made

1) if the positions’ evaluation deteriorate from grandfather to father to son it shows that the position might get worse and you should extend.

2) The same might be done if the evaluations fluctuate a lot (it could actually be a really stupid way of doing quiescence search) and is a type of generalisation of Qsearch

3) If the move stored in the hash table (transposition table) is the same going one depth greater a counter is increased for the position saved in the TT, if it changes the counter is decreased. When probing for an entry in the TT you read the counters. If the counters are high it means the path is more stable and you can reduce.

Good luck Mike. I follow your threads with great interest and think most of your ideas are great!!!
ty :)

abulmo2
Posts: 273
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: Reducing the horizon effect

Post by abulmo2 » Fri Sep 11, 2020 6:43 am

Mike Sherwin wrote:
Thu Sep 10, 2020 10:31 am
This idea can be brought further down toward the root. If a "stable horizon" can be detected lower in the tree then a level of confidence can be established that may allow for reductions in search depth.
Don't strong programs à la stockfish do something similar? They check if the static evaluation is improving between current ply and grand parent ply (ply - 2) and change the ways they reduce or the margins to prune bad lines.
Richard Delorme

Mike Sherwin
Posts: 43
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: Reducing the horizon effect

Post by Mike Sherwin » Fri Sep 11, 2020 12:10 pm

abulmo2 wrote:
Fri Sep 11, 2020 6:43 am
Mike Sherwin wrote:
Thu Sep 10, 2020 10:31 am
This idea can be brought further down toward the root. If a "stable horizon" can be detected lower in the tree then a level of confidence can be established that may allow for reductions in search depth.
Don't strong programs à la stockfish do something similar? They check if the static evaluation is improving between current ply and grand parent ply (ply - 2) and change the ways they reduce or the margins to prune bad lines.
I honestly do not know much about SF or any other strong programs, sry.

Post Reply