Author: Vincent Diepeveen

Date: 10:55:27 02/17/99

Go up one level in this thread

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. 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

- Re: Singular Extensions, Nullmove deepsearch
**Frank Schneider***23:22:05 02/18/99*- Re: Singular Extensions, Nullmove deepsearch
**Vincent Diepeveen***12:05:48 02/19/99*

- Re: Singular Extensions, Nullmove deepsearch
- Re: Singular Extensions, Nullmove deepsearch
**Robert Hyatt***14:13:12 02/18/99*- Re: Singular Extensions, Nullmove deepsearch
**Vincent Diepeveen***17:38:06 02/18/99*- Re: Singular Extensions, Nullmove deepsearch
**Robert Hyatt***18:56:32 02/18/99*

- Re: Singular Extensions, Nullmove deepsearch

- Re: Singular Extensions, Nullmove deepsearch

This page took 0.07 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.