Author: Robert Hyatt
Date: 14:13:12 02/18/99
Go up one level in this thread
On February 17, 1999 at 13:55:27, Vincent Diepeveen wrote: >On February 16, 1999 at 04:45:43, Frank Schneider wrote: > >>I experimented a little bit with nullmove deepsearch extensions and with >>singular extensions and now I have some questions: >> >>1. In all my tests the searchtree (#nodes to finish n iterations) increased >> by a factor of 1.5 to 4. Although testresults were interesting I believe >> this is too much. What are your experiences? >> >>2. Is it correct to assume that singular extensions work best if there are >> only few other extension heuristics. >> >>3. How would you describe the difference between nullmove deepsearch extensions >> (Donninger) and the nullmove threat detection by Deep Thought? >> >>4. Who uses >> - singular extensions >no >> - nullmove deepsearch extensions >no >> - nullmove threat detection > >yes, if there is a mate threat i sometimes extend. > >>5. What is the best (easiest) way to implement singular extensions? > >Let's see 3 cases of SE implementation in a position where i >have a score for a move m, which is the best move and i >want to see whether it's best. > > a) your score s is <= alfa > b) your score s is > alfa and < beta > c) your score s is >= beta > >Easiest case is b) > >Let's see that first, for searching with a singular difference S: > >s is a true score, so you can search ALL OTHER MOVES with a window > >[alfa,beta] = [s-S,s] > >If all scores are <= s-S then your move is singular in case b. > >Now case a. We get back a score s. We know that to be singular all moves n >which are unequal to m must have a lower score. > >There is however one big problem: score s is a bound. It is not >a true score, so in fact s could be theoretical s-i where i > 0. > >Practical with nullmove and a q-search that doesn't search all moves using >minimax, but prunes at >= beta, which as far as i know all programs do, >s is likely to be not the true score of m. > >So we must first get the TRUE score of m before deciding what its score is. >We then need to research m again. Eeasiest is to research with >[-infinite,s] > >If we get a fail high then we can assume that s is the true score. >If we don't get a fail high then the new score s' is the true score of >move m. > >Now it will be obvious that researching with -infinite is rather silly. > >It is in fact doing a minimax search, as you remove your bound and >research this move with the initialy limits. > >So it is not very wise to do that at the same depth as you initially did. >It is wiser to research using a reduction factor for the remaining depth you >search with. > >Then it's obvious to see that the overhead of singular extensions is >depending upon your branching factor. The better your branching factor, >the bigger the overhead. > >This insight is easy to get: > >Suppose your branching factor is 5. then if you reduce a depth d with >2 ply, then that tree is more or less 1/5*5 = 1/25 part of the tree at >depth d. > >If your branching factor is say 2.5 to 3, then it is way more than 1/9 >extra overhead, just for this move. > >Case c goes like case a, just that you need to search initially with >[s,infinite] instead of [-infinite,s]. > >Let's take an easy example of a position where humans see directly the >problems and programs have more problems: > >r1b1k2r/p2n1ppp/1p2p3/3p2B1/P2P4/1Nn1P3/5PPP/R3KB1R w KQkq - > > r = b = k = - r ... 1 ... > o - = n = o o o ... 2 ... > - o - = o = - = ... 3 ... > = - = o = - B - ... 4 ... > O = - O - = - = ... 5 ... > = N n - O - = - ... 6 ... > - = - = - O O O ... 7 ... > R - = - K B = R ... 8 ... >position deriving from an analysis of Eric de Haan and Vincent Diepeveen >white to move > >Here i saw directly that white could win the piece at c3 after f3, and then >put pressure at c3 with bd3 kd2 and rhc1. > >That's simply an idea. so when i start searching i start with > >f3,Bb7,Bd3,Kd2 and i see that the piece gets captured after Rhc1. Now >that is not a computer analysis. > >For the computer to see the problem is depending upon evaluation. >Let's take the variation without nullmove and without hung pieces >evaluation and without recapture extension: > normal depth >f3 1 >h6 2 >Bh4 3 >g5 4 >Bf2 5 >Bb7 6 >Bd3 7 >Rc8 8 >Kd2 9 >e5 10 * >Rhc1 11 >exd4 12 * >exd4 13 >something 14 >Rxc3 q-search > >Now a human sees that h6-g5 is not smart, and that g5 is forced >after h6, although for a computer this can be exchanged for Rc8 too. > >The singular extensions in THIS line are without a smart evaluation >(so material considerations) marked with a star, so: e5 and exd4. > >Questionable is what happens after >f3 1 >h6 2 >Bh4 3 >g5 4 >Bg3 5 >Bb7 6 >Bd3 7 >Rc8 8 >Kd2 9 >h5 10 >Rhc1 11 >something 12 >Rxc3 q-search > >Now we see that Bg3 is way better than Bf2, and therefore should get >objectively a singular extension. However we only see that it is better >AFTER we already have found it to be winning. > >Now we know how very little ply we need to find this for humans easy case >of getting a hung piece, we are gonna search for another way to delay >this combi. Even if the g5 bishop gets via h4 to g3, then still we can >delay things with f6 and e5 and capturing at d4. > >So the line now becomes: >f3 1 >f6 2 >Bh4 3 >g5 4 >Bg3 5 >Bb7 6 >Bd3 7 >Rc8 8 >Kd2 9 >e5 10 >Rhc1 11 >exd4 12 >exd4 13 >something 14 >Rxc3 q-search > >Now we clearly see that f6 is a clear case of a singular move here, >as it is the only move that delay the loss. > >I think this is a problem that is very important to realize, >but let's go on and take the nullmove program at the short line: > >f3 1 >h6 2 >Bh4 3 >g5 4 >Bg3 5 >Bb7 6 >Bd3 7 >Rc8 8 >Kd2 9 >nullmove 10 >Rhc1 11+R >something 12+R >Rxc3 q-search > >Now that's *without* any extensions yet. > >Now let's take cray blitz. It does detect for threats in nullmove. >And R=1 for the nullmove reduction factor. R=2 for the singular extension >reduction factor. Further it has recapture extensions. >So it sees already after Rhc1 the problems because >of the q-search nullmove. That is 12 ply, even without singular extensions. > >In this line however Bg3 and Bb7 should be singular extended! >So actually it should find it at 10 ply, if everything would be normal. I ran this test and found two things. First, from ply=2 on, CB likes f3 and would _never_ play anything else. from plies 2-8 the score climbed slowly but white is a pawn down so it was less than zero. At ply=9 it got a fail high, but no PV back so the score was -.117 at that point. At ply=10 it failed high again with an evaluation of +1.5. Crafty needs 14 plies, about 3 minutes on my quad, to fail high on this position. > >Bg3 is logically explainable, but Bb7 is not. > >Now let's get to the line for nullmoveprograms when playing f6: >f3 1 >f6 2 >Bh4 3 >g5 4 >Bg3 5 >Bb7 6 >Bd3 7 >Rc8 8 >Kd2 9 >e5 10 >Rhc1 11 >exd4 12 >exd4 12 (recapture extension) >something q-search (qsearch threat detected! >Rxc3 q-search > >I know from Bob that >Cray blitz needs 12 ply to find f3 without being negative. >However cray blitz should see that f6 here is a singular extension >and that Bb7 is a singular extension. Why is f6 a singular extension? >Easy: because all other moves lose. however it cannot see f6 as >it reduces depth and therefore needs a lot more ply to see that the other >variation with h6 loses. So f6 is very logically to explain. >However, Bb7 is tougher to explain. If you don't play Bb7 then the piece >gets directly lost in my opinion. > >So i can't explain this, except that this line is 11 ply to see, and >that the 'shorter line' is the line that eats up 12 ply. > >So for cray blitz the problem is not the f6-g5-e5 line, >but the h6-g5 line. > >This means that effectively Cray blitz has won zero plies in seeing this >problem by using singular extension. The nullmove-threat detection >in the q-search however has won a full ply for it, and the reduction factor >of 1 has reduced problems with another ply. > >Yet, if we look with a more objective point of view to this problem, then we >see that it did not extend all singular extensions, namely it missed >in the h6-g5 line that Bb7 is a singular extension. > >Now we compare this singular extension to DIEP that doesn't use >singular extensions, nor threat detection in q-search nor recapture extension >nor R=1. Diep uses R=3. > >So it's likely to assume that if Singular Extensions failed in cray blitz >to see this from human viewpoint forced combination, that diep needs > >a) 2 ply extra the 2 ply bigger reduction factor >b) another ply extra for the nullmove-threat quiescencesearch > >Now what diep has is a good evaluation. I think i can say very well in >this position, as diep evaluates the piece at c3 quickly to be hung. >so after > >f3 1 >h6 2 >Bh4 3 >g5 4 >Bg3 5 >Bb7 6 >Bd3 7 >Rc8 8 >Kd2 9 >nullmove 10 >Rhc1 11+R > >Now diep sees that the piece is clearly hung and it gives a huge penalty. > >R=3, so 11+3 = 14 ply needed. > >Output from the parallel version (running at 1 processor, so >note that the number of nodes is not exactly correct as the number of >nodes at the first ply are not added to it yet, one should add 1 node >for every ply it searched to the printed number of nodes): > >PII-450 80mb hashtables. > 00:00 0 1 -0.58 Nb3-d2 > 00:00 8 1 -0.44 Bf1-d3 > 00:00 8 1 -0.43 g2-g4 > 00:00 8 1 -0.31 Bf1-b5 >1 36 ( 0, 35) 0.00 > 00:00 48 2 -0.74 Bf1-b5 Bc8-b7 > 00:00 48 2 -0.43 g2-g4 >2 59 ( 0, 35) 0.01 > 00:00 114 3 -0.83 g2-g4 Bc8-b7 > 00:00 328 3 -0.48 Bf1-b5 Bc8-b7 Ra1-c1 Nc3xb5 a4xb5 >3 60 ( 0, 35) 0.10 > 00:00 1134 4 -0.97 Bf1-b5 Nc3xb5 a4xb5 a7-a5 > 00:00 1551 4 -0.63 g2-g4 h7-h5 g4xh5 >4 61 ( 0, 35) 0.31 > 00:00 2862 5 -1.10 g2-g4 h7-h5 f2-f3 h5xg4 f3xg4 > 00:00 5666 5 -0.66 Bf1-b5 Bc8-b7 Ra1-c1 Ra8-c8 g2-g4 > 00:00 6403 5 -0.56 Bg5-f4 Bc8-b7 Bf4-d6 >5 62 ( 0, 35) 0.68 > 00:00 9914 6 -0.81 Bg5-f4 Bc8-b7 Bf1-b5 g7-g6 > 00:01 15596 6 -0.80 Bf1-d3 Bc8-b7 g2-g4 Nc3-e4 Bg5-f4 > 00:01 27029 6 -0.70 Ra1-c1 Nc3-e4 h2-h4 h7-h6 Bg5-f4 Bc8-b7 >6 63 ( 0, 35) 1.89 > 00:02 43433 7 -0.51 Ra1-c1 Nc3-e4 h2-h4 f7-f6 Bg5-f4 e6-e5 Bf4-h2 >7 64 ( 0, 35) 3.40 > 00:06 115191 8 -0.51 Ra1-c1 Nc3xa4 Bf1-b5 Na4-b2 Rc1-c2 Nb2-c4 Bb5xc4 d5 >xc4 Rc2xc4 >8 65 ( 0, 35) 7.45 > 00:11 237937 9 -0.50 Ra1-c1 Nc3-e4 h2-h4 Nd7-f8 Nb3-d2 Ne4xg5 Bf1-b5 Bc8 >-d7 Bb5xd7 Nf8xd7 h4xg5 >9 66 ( 0, 35) 14.70 > 00:25 531381 10 -0.31 Ra1-c1 Nc3-e4 Bg5-f4 g7-g5 Bf4-c7 Ke8-e7 f2-f3 Ne4 >-f6 h2-h3 >10 67 ( 0, 35) 27.95 > 00:38 817776 11 -0.48 Ra1-c1 Nc3-e4 Bg5-f4 g7-g5 Bf4-c7 Ke8-e7 Bf1-b5 Bc >8-b7 f2-f3 Ne4-d6 Ke1-e2 >11 68 ( 0, 35) 50.18 > 01:46 2334305 12 -0.45 Ra1-c1 Nc3xa4 Bf1-b5 Na4-b2 Rc1-c2 Nb2-c4 Bb5-c6 >Ra8-b8 Bg5-f4 e6-e5 Bf4xe5 Nc4xe5 d4xe5 >12 69 ( 0, 35) 126.17 > 03:18 4640332 13 -0.47 Ra1-c1 Nc3-e4 Bg5-f4 g7-g5 Bf4-c7 Ke8-e7 f2-f3 Ne >4-f6 Bf1-d3 Bc8-b7 h2-h4 Rh8-g8 Ke1-f2 g5xh4 Rh1xh4 > 07:08 9515739 13 -0.39 f2-f3 Bc8-b7 Ke1-d2 Ra8-c8 Bf1-b5 Nc3xb5 a4xb5 Rc >8-a8 Rh1-c1 a7-a5 Rc1-c7 h7-h6 Bg5-f4 g7-g5 >13 70 ( 0, 35) 436.78 > 15:09 19918887 14 0.65 f2-f3 f7-f6 Bg5-h4 g7-g5 Bh4-f2 b6-b5 a4xb5 Ra8-b >8 h2-h4 Ke8-e7 h4xg5 f6xg5 Ra1xa7 >14 71 ( 0, 35) 929.00 > 20:30 27165495 15 0.62 f2-f3 h7-h6 Bg5-h4 b6-b5 a4xb5 Nd7-b6 Ke1-d2 Nc3- >a4 Nb3-c5 Na4-b2 Kd2-c3 Nb2-c4 e3-e4 >15 72 ( 0, 35) 1272.46 > >So Diep needs 19.9M nodes to see f3 to be winning. I think branching factor >clearly wins here from singular extensions and all kind of threat extensions. > >Only fiddling with the nullmove reduction factor (from 3 to 2) >would find this problem for me 1 ply earlier, where Singular extension >takes care i never see this problem that quick, as i never will search >deep enough. > >Now singular extensions show a lot of problems > a) you need a singular margin S, which means that you give a true > or false definition to something being singular. For example: > if i pick 0.50 pawns for S, then we will miss something that > is 0.49 pawns better, even if it is a fail high singular extension. > b) SE is not giving you real singular moves. Only easy cases > of singular moves are recognized as you search the tree with a > reduced depth. So singular moves based on a deep search cannot be > used, although that are the most interesting ones, as is clear in > this problem. > c) the overhead of singular extensions becomes very big when your programs > branching factor gets better. > I found in DIEP (after say 9 ply the branching factor becomes > between 2.0 to 3.0 normally spoken) singular extensions increase > my branching factor > considerably. So i could hardly search 10 plies after many > hours, using a CORRECT implementation of singular extensions with > singulair reduction factor=2, and no way to speed that up, where > normally DIEP searches after 3 minutes already 11 or 12 ply. > d) Near the leafs singular extensions cannot be used in a search > as we work with a reduction factor, which we need otherwise we > search close to minimax. I found this in DIEP a very big problem, > as searching WITH singular extensions already eats up a > big bunch of plies, and then another few ply are cut away. So singular > extensions far in the tree form a big problem to see. > c) singular extensions work to find forced combinations, but a forced > combination in the eyes of a human is not necessarily having only 1 > forced move. A singulair position in human eyes can have 2 or more > moves too. > d) Singular extensions work especially well AFTER you already see the truth > of something. This has to do with d). You can only detect threats > based on a reduced depth. So you can only see something > after it is already clear with the normal search that it is way better, > as you researched it to be singular with a reduced depth that is way > smaller than the big search. This is nice to get a big score, but > i personally think this wasting nodes. > >Conclusion most combinations i know from games have very little easy >to recognize singular moves, way less than the 3 plies DIEP already gives >up after a few minutes. As hardware gets faster the number of extra >plies needed by just the Singular extension is getting larger and larger. > >I see singular extensions as a limited and very restricted >form of threat extensions that need a huge overhead to be detected as you >need a lot of extra search. > >On the other hand we see that a simplistic eval term which was already in >gnuchess saves a full ply of search. > >>Thanks in advance, >>Frank
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.