Author: Robert Hyatt
Date: 16:04:24 09/30/00
Go up one level in this thread
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... >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.