Author: Robert Hyatt
Date: 20:59:13 10/01/00
Go up one level in this thread
On October 01, 2000 at 11:42:27, Vincent Diepeveen wrote: >On September 30, 2000 at 19:04:24, Robert Hyatt wrote: > >>On September 30, 2000 at 16:45:26, Vincent Diepeveen wrote: >> >>>On September 30, 2000 at 10:25:47, Gian-Carlo Pascutto wrote: >>> >>>> >>>>I've read about singular extensions a lot and have >>>>seen this question multiple times on CCC but there's >>>>still one thing that I have never seen: >>>> >>>>a good, usable description of how to actually IMPLEMENT >>>>them, or even psuedocode >>> >>>this has been never given by Hsu, and that's exactly >>>what sucks. >>> >> >>What do you mean? The paper in the JICCA was perfectly clear on how it >>works. I used that to implement SE in CB... > > >But using that implementation i search many plies less. > >What bruce is doing is already more clever. I disagree. What Bruce is doing is more simple. It is not better. Nor even as good as the classic SE algorithm. It costs me a ply in Cray Blitz, but it finds some startling tactical things. In DB Hsu modified it a bit to extend when there was more than one 'nearly singular' move... which was the one complaint I had about the original implementation... I have never had time to try the latest Hsu idea however... > >> >> >>>However using what Bruce described, >>> >>>first search the moves with a REDUCED depth, then >>>extend singular moves. >>> >>>I doubt overhead is 1 ply. For DIEP it's more like 3 ply >>>or so. Of course if you don't always use them it costs less, >>>but then they work less powerful. >>> >>>>So, if you use singular extensions and have used them, >>>>and your implementation was at least acceptable, >>>>please, pretty please... >>> >>>I could never ever get them to work. >>> >>>I personally remember that the deep blue claimed like winning 9 >>>rating points with them, that was at a depth of like 8 ply they >>>searched back then. Nowadays that would be significantly less. >>> >>>They work for sure to solve many tactical problems a lot sooner, >>>but the practical usage of them is very doubtful. >>> >>>For nullmove programs some other extensions passed them on the >>>left and the right. Very interesting are nimzo's deep search >>>extensions, so extending more if you search deeper, after getting >>>a ply or 10 quickly. >>> >>>The basic advantage of threat extensions is that if you nullmove >>>you see threats very cheaply anyway. >>> >>>If you use singular extensions, then depending upon how bigtime you >>>limit them they cost more or less. >>> >>>Yet basically a move which is a margin S better as *all* the other moves in >>>a position p is called a singular move. >>> >>>that means for example that after 1.e4,h5? 2.Qxh5?? that 2..Rxh5 is a singular >>>move already. >>> >>>So the first thing most people do is exclude captures from the singular >>>extensions. Secondly you can distinguish 3 types of singular extensions >>>roughly. >>> >>> - if your best move is between alfa and beta (so a PV move) then >>> you have a very accurate score for your best move m: score PVscore). >>> So you need a quite >>> cheap research then (cheap because the other singular moves are >>> way harder to detect). You just search with a reduced depth the >>> other moves with a window [PVscore-S,PVscore-S+1] >>> now if that window doesn't fail high then you have a singular >>> move m. >>> >>>Way more interesting to solve tricks is if there is only 1 move that >>>gives a beta cutoff. Yet this is real bigtime overhead. >>> >>>Let's before looking to any implementation first consider this: >>>you want to know whether a move m is singular, knowing it gives a beta >>>cutoff. That means that if you search all other moves with a reduced >>>depth (usually depth-2) that you search ALL moves instead of a SINGLE >>>move. Though these singular moves work great, the overhead of this >>>is just too much for anyone, assuming your branching factor doesn't >>>suck TOO much. >>> >>>If you don't use nullmove and have a brnaching factor of a factor 10 >>>or something, then sure it doesn't matter anything, because searching >>>for a singular move you need n searches of 1/100 of the current search. >>> >>>however if you have n other legal moves and you have a branching factor >>>of 2.5 or something, then searching the remaining moves with reduced >>>depth-2, means each tree is of size 1/2.5 * 1/2.5 = 1/6.25 = 0.18 >>>Now if you have like 40 legal moves on average (as the average >>>number of moves in positions MY program searches is at least 40, >>>and not the reported 35 as is in most books), then 40 * 0.18 = 6.4 that's >>>2 additional plies just for beta singular moves. We still didn't >>>count the extra nodes for the extra subtree you search because of >>>the extension! >>> >>>Just the overhead is in advance 2 ply for beta singular moves if you >>>have a pretty good branching factor. Obviously you must put in your >>>hashtable that you extended this move m, because if later this gets a PV >>>move, then you want to extend it again. >>> >>>Now actually though it's cool to extend only moves that fail high, >>>this is not the same as the above definition. >>> >>>For example if beta is 0.181 and this move is giving a cutoff, but the >>>second best move is 0.179 then we talk about a singular margin of just 0.02 >>>depending upon what move got first. >>> >>>Less overhead but not easier to do are alfa singular moves as you need >>>to search all nodes anyway. However here you have a similar problem as >>>with betasingular moves. If you want to know exactly whether they >>>are a margin S singular, then you need first a true score from the >>>best move. So you need to search the best move with a window [-infinite,alfa] >>>first. That sucks IMHO. >>> >>>So practical the only interesting thing IMHO are the beta singular moves, >>>but that's not the true definition of singular moves, apart from the >>>PV singular moves which you can extend pretty easy, it's very tough >>>to extend other moves as you don't know their exact value, just a cut >>>value somehow. >>> >>>Now there are rude methods to still apply singular moves in a very >>>stripped and limited way. >>> >>>>(Of course, an online reference to the above is also >>>>good enough ;) >>>> >>>>-- >>>>GCP
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.