Singular Margin based on depth?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lkaufman
Posts: 3120
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Singular Margin based on depth?

Post by lkaufman » Sat Feb 11, 2012 4:37 pm

One of the ideas in the Ippolit based programs (and in Critter) is that when doing the test for Singularity (for Singular Extension), the margin is proportional to depth. Aside from whether this tests well or not, can anyone explain the rationale for this idea? It is not at all obvious to us why a deeper search should require a larger margin. One might even argue that move ordering gets better with depth, so a smaller margin might be needed at higher depths.

bob
Posts: 20348
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Singular Margin based on depth?

Post by bob » Sat Feb 11, 2012 4:49 pm

lkaufman wrote:One of the ideas in the Ippolit based programs (and in Critter) is that when doing the test for Singularity (for Singular Extension), the margin is proportional to depth. Aside from whether this tests well or not, can anyone explain the rationale for this idea? It is not at all obvious to us why a deeper search should require a larger margin. One might even argue that move ordering gets better with depth, so a smaller margin might be needed at higher depths.
Unknown. Certainly nothing Hsu/Campbell wrote about a "real SE implementation" suggests this. However, the ip* "singular extension" is really a "hack" that doesn't leave me with a "good feeling." You only extend if you get a hash hit with a best move, etc??? Hsu used a "sticky transposition table" so that once a move was flagged as "singular" it would at least be extended for the next iteration, regardless of whether the singular test returned true or not... Perhaps this is a way to limit the overhead of extending "best moves" that are nowhere near "singular" in nature?

lkaufman
Posts: 3120
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Singular Margin based on depth?

Post by lkaufman » Sat Feb 11, 2012 4:59 pm

bob wrote:
lkaufman wrote:One of the ideas in the Ippolit based programs (and in Critter) is that when doing the test for Singularity (for Singular Extension), the margin is proportional to depth. Aside from whether this tests well or not, can anyone explain the rationale for this idea? It is not at all obvious to us why a deeper search should require a larger margin. One might even argue that move ordering gets better with depth, so a smaller margin might be needed at higher depths.
Unknown. Certainly nothing Hsu/Campbell wrote about a "real SE implementation" suggests this. However, the ip* "singular extension" is really a "hack" that doesn't leave me with a "good feeling." You only extend if you get a hash hit with a best move, etc??? Hsu used a "sticky transposition table" so that once a move was flagged as "singular" it would at least be extended for the next iteration, regardless of whether the singular test returned true or not... Perhaps this is a way to limit the overhead of extending "best moves" that are nowhere near "singular" in nature?
The singular extension for hash move only appears to have been a major factor in the rating jump of Rybka 3, though I don't know if the idea was original or is on record as having been used previously in another program. Whether it is a "hack" or not, it works. But back to the question at hand, I guess you are saying that if a certain move is best by some constant margin move after move, it would get extended repeatedly if the excess over the second move is just over the singular margin. So I see the logic of the idea now, although it is addressing a rather unrealistic scenario (constant gap between move 1 and move 2). Anyway, this is probably the reason for the algorithm; thanks for a very intelligent reply!

mcostalba
Posts: 2679
Joined: Sat Jun 14, 2008 7:17 pm

Re: Singular Margin based on depth?

Post by mcostalba » Sat Feb 11, 2012 5:57 pm

lkaufman wrote: It is not at all obvious to us why a deeper search should require a larger margin
Is it clear to you why is required a margin in first instance ? Before to study the idea's refinements it is important to grasp the fundamentals.

lkaufman
Posts: 3120
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Singular Margin based on depth?

Post by lkaufman » Sat Feb 11, 2012 6:24 pm

I thought that the idea behind requiring a margin is obvious, namely that if a move is best by just a couple centipawns at a reduced depth, the probability that it is best at the current depth is not that much over 50%, and so you could very likely be extending the wrong move. Am I missing something here? What is your take on the question in the subject line question?

mcostalba
Posts: 2679
Joined: Sat Jun 14, 2008 7:17 pm

Re: Singular Margin based on depth?

Post by mcostalba » Sat Feb 11, 2012 7:20 pm

lkaufman wrote:I thought that the idea behind requiring a margin is obvious, namely that if a move is best by just a couple centipawns at a reduced depth, the probability that it is best at the current depth is not that much over 50%, and so you could very likely be extending the wrong move. Am I missing something here? What is your take on the question in the subject line question?
So you think that bigger the margin against the remaining moves and bigger is the probability to extend the correct move ?

So why in your opinion singular extension works better if the margin is not very big ?

User avatar
michiguel
Posts: 6269
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Singular Margin based on depth?

Post by michiguel » Sat Feb 11, 2012 7:33 pm

lkaufman wrote:I thought that the idea behind requiring a margin is obvious, namely that if a move is best by just a couple centipawns at a reduced depth, the probability that it is best at the current depth is not that much over 50%, and so you could very likely be extending the wrong move. Am I missing something here? What is your take on the question in the subject line question?
Everything you do in an engine is a gamble. Depending on the outcome and the risk, there is a reasonable bet. At higher depths, in general, if you make a mistake, it is a very serious one. So, you may want to be more conservative, hence, it is not rare that you may like to have higher margins. You really want to make sure that the probability to be wrong decreases.

Miguel

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Singular Margin based on depth?

Post by rvida » Sat Feb 11, 2012 8:00 pm

lkaufman wrote:One of the ideas in the Ippolit based programs (and in Critter) is that when doing the test for Singularity (for Singular Extension), the margin is proportional to depth. Aside from whether this tests well or not, can anyone explain the rationale for this idea? It is not at all obvious to us why a deeper search should require a larger margin. One might even argue that move ordering gets better with depth, so a smaller margin might be needed at higher depths.
Original purpose was to limit the overhead of the exclusion search. Larger margin causes it to fail-high faster on non-singular moves. At lower depths the overhead is smaller and a smaller margin is affordable.

But with other improvements in Critter's search this became (almost) a non-issue and now I use a fixed margin.

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Singular Margin based on depth?

Post by rvida » Sat Feb 11, 2012 8:06 pm

bob wrote:However, the ip* "singular extension" is really a "hack" that doesn't leave me with a "good feeling." You only extend if you get a hash hit with a best move, etc???
1.) If you don't have a best move there is nothing singular to extend anyway.
2.) You don't need a hash hit to get a best move, do you? If a best move exists, IID will find it for you.

lkaufman
Posts: 3120
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Singular Margin based on depth?

Post by lkaufman » Sat Feb 11, 2012 8:40 pm

mcostalba wrote:
lkaufman wrote:I thought that the idea behind requiring a margin is obvious, namely that if a move is best by just a couple centipawns at a reduced depth, the probability that it is best at the current depth is not that much over 50%, and so you could very likely be extending the wrong move. Am I missing something here? What is your take on the question in the subject line question?
So you think that bigger the margin against the remaining moves and bigger is the probability to extend the correct move ?

So why in your opinion singular extension works better if the margin is not very big ?
The bigger the margin, the higher the probability is that if a move gets extended, it will be the correct move. But if the margin is too high, it is likely that no move will be extended. We want a margin that is unlikely to extend a wrong move but still reasonably likely to extend the right one. Only testing can determine the right value.

But I think this is all obvious, and does not help find the answer to the posted question.

Post Reply