Singular Margin based on depth?
Moderators: hgm, Rebel, chrisw
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Singular Margin based on depth?
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Singular Margin based on depth?
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 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.
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Singular Margin based on depth?
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!bob wrote: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 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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Singular Margin based on depth?
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 wrote: It is not at all obvious to us why a deeper search should require a larger margin
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Singular Margin based on depth?
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?
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Singular Margin based on depth?
So you think that bigger the margin against the remaining moves and bigger is the probability to extend the correct move ?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 why in your opinion singular extension works better if the margin is not very big ?
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Singular Margin based on depth?
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.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?
Miguel
-
- Posts: 481
- Joined: Thu Apr 16, 2009 12:00 pm
- Location: Slovakia, EU
Re: Singular Margin based on depth?
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.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.
But with other improvements in Critter's search this became (almost) a non-issue and now I use a fixed margin.
-
- Posts: 481
- Joined: Thu Apr 16, 2009 12:00 pm
- Location: Slovakia, EU
Re: Singular Margin based on depth?
1.) If you don't have a best move there is nothing singular to extend anyway.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???
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.
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Singular Margin based on depth?
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.mcostalba wrote:So you think that bigger the margin against the remaining moves and bigger is the probability to extend the correct move ?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 why in your opinion singular extension works better if the margin is not very big ?
But I think this is all obvious, and does not help find the answer to the posted question.