next singular extension test

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.
bob
Posts: 20348
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

next singular extension test

Post by bob » Thu Aug 05, 2010 4:01 am

This is using some code dated 1999, so a bit old. Here's the idea. After the usual stuff in search, before getting into the main loop where I extract the next move, make it, recursively call search, etc... I call a function "SearchSingular()" What it does is search the complete move list, using the normal reduction/extension (except no singular extensions since that would be a never-ending recursive loop) logic, to depth / 2 (for first tests) using an offset null-window of alpha - SINGULAR_MARGIN.

If more than one move fails high on this search, I immediately abandon the search and return(false). If I search 4 moves (currently) without any fail high, I quit and also return(false) (this is a condition that suggests we are at an ALL node where a singular move is not easy to identify).

If I get thru all the moves with just one fail-high on that downward-offset window, that move is flagged as singular, and when it is searched in the normal search, it gets extended by one ply (if no check extension is done).

I am currently not doing this test if I am in check, although I might revise that as testing proceeds. I also do not do it too close to the tips either. I plan the following tests (first two already queued up)...

(1) vary the singular margin between 30 and 100.

(2) vary the depth limit from 4 to 9.

(3) vary the SE search depth (depth of search used to identify that the move is singular). I currently search to whatever remaining depth is divided by 2, but this needs testing as well.

I don't want to get 2/3 running until I get some idea about the best value for the margin, so I am waiting on that to give me some guidance.

I'll post an exact description if this seems to work. I noticed that the date on this file (most of my c files have a "/* last modified xx/yy/zz */" at the front) was 1999. Search depths and speeds were _far_ lower than today, so that this might do something better than what it did in 1999 when I scrapped it. Bruce seemed to like this so maybe he found a better tuning setup than I did. When I explained this previously, I had forgotten some of the details I gave above. But I had to tweak it to fit the current search which has changed a bit from 1999, and discovered a few things that made me think "Hmmm. forgot about that. Some pretty bright guy must have thought of that..." :)

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

Re: next singular extension test

Post by bob » Thu Aug 05, 2010 4:36 am

Before I go to bed, looks like the first run is "break even". No significant Elo gain or loss. So unless I am a genius and got all the parameters right the first time, there might be something to be had from this code... more tomorrow.

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: next singular extension test

Post by zamar » Thu Aug 05, 2010 5:27 am

bob wrote:This is using some code dated 1999, so a bit old. Here's the idea. After the usual stuff in search, before getting into the main loop where I extract the next move, make it, recursively call search, etc... I call a function "SearchSingular()" What it does is search the complete move list, using the normal reduction/extension (except no singular extensions since that would be a never-ending recursive loop) logic, to depth / 2 (for first tests) using an offset null-window of alpha - SINGULAR_MARGIN.
This is not very different from relaxed SE except that here you also do search on expected best move with depth / 2 and alpha - SINGULAR_MARGIN. Personally I'd be very worried about unwanted side effects this kind of search can do to transposition table. Are they a problem?
Joona Kiiski

Mangar
Posts: 65
Joined: Thu Jul 08, 2010 7:16 am

Re: next singular extension test

Post by Mangar » Thu Aug 05, 2010 11:43 am

Hi,

is alpha - margin the same at pv nodes (nodes with a beta - alpha > 1) and non pv nodes?
Maybe at pv nodes alpha + (beta - alpha) / 2 - margin is better? The relevance surely depends on your window. But if for example you find a hudge fail high or fail low you may end in a very large alpha/beta window and alpha - margin is far away from current position value.

Greetings Volker
Mangar Spike Chess

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

Re: next singular extension test

Post by bob » Thu Aug 05, 2010 2:22 pm

zamar wrote:
bob wrote:This is using some code dated 1999, so a bit old. Here's the idea. After the usual stuff in search, before getting into the main loop where I extract the next move, make it, recursively call search, etc... I call a function "SearchSingular()" What it does is search the complete move list, using the normal reduction/extension (except no singular extensions since that would be a never-ending recursive loop) logic, to depth / 2 (for first tests) using an offset null-window of alpha - SINGULAR_MARGIN.
This is not very different from relaxed SE except that here you also do search on expected best move with depth / 2 and alpha - SINGULAR_MARGIN. Personally I'd be very worried about unwanted side effects this kind of search can do to transposition table. Are they a problem?
What kind of side-effects? The searches are perfectly normal alpha/beta searches, the depth is stored correctly, so I am not sure what you mean by "side effects."

The primary difference here is that I don't expect the TT to give me a move to test for SE. I test _everywhere_ and try to quickly determine when it is hopeless to avoid wasting time, while not failing to test a position just because there was no hash hit...

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

Re: next singular extension test

Post by bob » Thu Aug 05, 2010 2:25 pm

Mangar wrote:Hi,

is alpha - margin the same at pv nodes (nodes with a beta - alpha > 1) and non pv nodes?
Maybe at pv nodes alpha + (beta - alpha) / 2 - margin is better? The relevance surely depends on your window. But if for example you find a hudge fail high or fail low you may end in a very large alpha/beta window and alpha - margin is far away from current position value.

Greetings Volker
Yes, I am using alpha everywhere. The issue is, is there just one move that will fail high at the alpha-margin-1, alpha-margin window. I'm not sure why beta would be important. It is certainly possible that this is an issue on fail low/high conditions, but I have not tried to address that (yet).

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: next singular extension test

Post by zamar » Thu Aug 05, 2010 8:38 pm

bob wrote: What kind of side-effects? The searches are perfectly normal alpha/beta searches, the depth is stored correctly, so I am not sure what you mean by "side effects."
By "unwanted side effects" I mean situations where SE search will overwrite TT Entry (with different value + depth) which would otherwise give direct cut-off in usual search.
Joona Kiiski

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

Re: next singular extension test

Post by bob » Thu Aug 05, 2010 8:43 pm

zamar wrote:
bob wrote: What kind of side-effects? The searches are perfectly normal alpha/beta searches, the depth is stored correctly, so I am not sure what you mean by "side effects."
By "unwanted side effects" I mean situations where SE search will overwrite TT Entry (with different value + depth) which would otherwise give direct cut-off in usual search.
I guess this depends on implementation. I don't do the SE search until I have tried everything else. Hash probe, repetition check, even null-move search. However, the TT is an issue in all searches, since it introduces some interesting side effects. I just ignore 'em. Some go to extremes, from not storing mate scores to not storing draw scores. Doesn't solve all the problems so it seems like a waste of time.

Have not yet looked at the results from testing so far, fixing to go see if anything decent popped up...

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: next singular extension test

Post by zamar » Fri Aug 06, 2010 4:06 pm

bob wrote: I guess this depends on implementation. I don't do the SE search until I have tried everything else. Hash probe, repetition check, even null-move search. However, the TT is an issue in all searches, since it introduces some interesting side effects. I just ignore 'em. Some go to extremes, from not storing mate scores to not storing draw scores. Doesn't solve all the problems so it seems like a waste of time.
I'm not talking about TT Entry of current node, but if you for example do SE search with depth = 5, you spoil all child node entries up to that depth. Sounds pretty bad thing for me. The beauty of the relaxed SE extension is that by excluding the likely main move from SE search we preserve the most valuable child node entries.
Joona Kiiski

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

Re: next singular extension test

Post by bob » Fri Aug 06, 2010 7:08 pm

zamar wrote:
bob wrote: I guess this depends on implementation. I don't do the SE search until I have tried everything else. Hash probe, repetition check, even null-move search. However, the TT is an issue in all searches, since it introduces some interesting side effects. I just ignore 'em. Some go to extremes, from not storing mate scores to not storing draw scores. Doesn't solve all the problems so it seems like a waste of time.
I'm not talking about TT Entry of current node, but if you for example do SE search with depth = 5, you spoil all child node entries up to that depth. Sounds pretty bad thing for me. The beauty of the relaxed SE extension is that by excluding the likely main move from SE search we preserve the most valuable child node entries.
Or you don't overwrite them because of depth vs draft???

The one issue I am seeing when doing very detailed analysis, is that the old depth/2 trick I was using is really pretty lousy. What I am doing, in essence, is saying "OK, if I search all moves to a very shallow depth, and one appears to clearly be better, I am going to extend that move when I reach it in the real search." I don't think that makes any sense at all. How often does a move look good to a shallow search, but not to a deep one? Or even worse, how about moves that look good to a deep search but poor to a shallow one. As a result, I am next testing various reductions, from 1 up thru depth/2 to see if any of those are better. In Hsu's original paper, PV-singular tests did not use any reduced depth at all, that was only done when a move failed high in a CUT node, to prove ("prove" in quotes) that the fail-high move is significantly better than the rest. I don't have his paper handy, as I am at home, but I think he either used R=1 or R=2 for those searches. Which while not as accurate as R=0, reduces the cost to something acceptable.

I've been dumping trees with the ttSE and the current SE versions, and do not like what I see. I don't want to randomly extend moves just because they happen to be the result of a TT hit, I don't want to randomly extend moves just because they look good to a very shallow search, I don't want to overlook extending a move just because it doesn't look very good to a shallow search. And so far, my testing is not finding anything that is a real improvement. --so far. Still have a ton of ideas, but I suspect I am going to have to bite the bullet and implement Hsu's approach as well, before giving up... ttSE is by far the easiest, the current code is not that bad. But Hsu's stuff gets quite messy.
Last edited by bob on Fri Aug 06, 2010 7:15 pm, edited 1 time in total.

Post Reply