Author: Vincent Diepeveen
Date: 03:27:06 06/25/01
Go up one level in this thread
On June 24, 2001 at 10:43:06, Rafael Andrist wrote: Paper of Hsu is indeed very clear describing what he did: IEEE99 In those years it still was said that Deep Blue searched 12 ply but fullwidth which would kick butt of the same if searched with nullmove, as well as that some amazing singular extensions which were too expensive to use, that those would improve the level. Only the problem was that around that year (1999) also micro's started searching 12+ ply (some of them, mine still doesn't do that too many times), so then the lies about deep blue became bigger. Now most not only search deeper, but also extend at more depths, so now the thing had to look better, so then it was said that 11(6) means 17 ply. However there is a small theoretical problem here. The last 6 plies the average number of legal moves in a position (not the check positions counted as those get extended anyway which only increases overhead) is 40 or more in middlegame. That means that with a perfect evaluation and perfect move ordering Deep Blue would need: 40 * 40 * 40 nodes to search 6 ply. Add to that factor 2 for qsearch (as each 50% of all nodes you need to try evaluation and opponent might want to answer at that too, so 2 nodes for every 50% positions added is at least factor 2) and extensions. So a theoretical minimum starts with 2 * 40 * 40 * 40 = 128000 nodes for the last 6 ply. Now 200M nodes / 128k = 1562.5 of those searches a second *theoretical*. You can't search 10 to 12 ply fullwidth with 1562.5 nodes a second, even with hashtable because using Bobs own statement that b.f. is lineair (i do not believe this when loading factor of hashtable is not too big and you use a lot of probes) that means that you need for the first 11 ply: 40 (first ply) 4.5 (branching factor all other plies) 40 * 4.5^10 = 136,202,515 Now that's *without* extensions and WITH perfect move ordering and an evaluation which doesn't modify next ply. in 180 seconds you don't even get *close* to that theoretical minimum of 17 ply search, not to mention 18 ply. Even a factor 100 isn't going to save ass here. So the whole discussion is completely nonsense that deep blue ever searched 16 to 18 ply fullwidth. It's invented *after* the PC programs progressed bigtime. Of course things are different if you design a program right *now* in hardware. First of all the hardware tools have been improved, secondly you can use both nullmove and if you're a good designer also hashtables inside a cpu (even though this is going to slow down the cpu itself by a factor of 20 at least). >On June 24, 2001 at 09:54:11, Robert Hyatt wrote: > >>On June 24, 2001 at 04:09:29, Rafael Andrist wrote: >> >>>On June 23, 2001 at 22:24:58, Robert Hyatt wrote: >>> >>>>On June 23, 2001 at 20:02:53, Vincent Diepeveen wrote: >>>> >>>>> >>>>>I do not know much details on schach, but if you give it an entire >>>>>night, then it still will show the same bad branching factor as >>>>>we were used to in 1997. >>>> >>>> >>>>What in the name of heaven are you talking about? "bad branching factor >>>>we were used to in 1997?" In 1996 I was using R=2 null-move, as was Bruce >>>>and others. _we_ were not used to any huge branching factor. My branching >>>>factor today is almost _exactly_ what it was in 1996... >>>> >>>> >>>>My branching factor also remains fairly constant regardless of the depth. >>>>It makes no sense to me that it would get smaller and smaller as you go >>>>deeper. Because eventually it would have to go below 1 and the search >>>>would actually get _faster_ as you go deeper. And that is fully nonsense. >>>> >>> >>>But the BF get's clearly smaller if the search goes deeper. At least with a >>>full-window-search. It's also clear that this process isn't linear. So your >>>second argument that it would ge below zero is nonsense itself. We live in a >>>completly non-linear world! >>> >>>Rafael B. Andrist >> >> >>I don't have any data for searches beyond 15 plies in the middlegame, but for >>the 350 or so searches I have, I don't see the BF as better from 14->15 than it >>is for 12->13... I don't see why it would be so either. unless you assume >>infinite everything like hash table size, etc. > >In my experiments, I didn't go so deep. But the it seems to me, that the BF is >an exponential function of the search depth (different for each side). At this >depths the BF changes only 0.1 or less. It's clear that in some situations the >BF can go up too, e.g. if you queen a pawn in a pawnendgame. > >Can you give me a typical position where you mesured the values? Then it would >be possible to compare. > >Rafael B. Andrist
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.