Author: Vincent Diepeveen
Date: 08:42:27 10/01/00
Go up one level in this thread
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. > > >>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.