Author: Robert Hyatt
Date: 09:47:07 07/05/02
Go up one level in this thread
On July 05, 2002 at 00:17:09, Uri Blass wrote: >On July 04, 2002 at 22:26:44, Robert Hyatt wrote: > >>On July 04, 2002 at 11:57:11, Uri Blass wrote: >> >>>On July 04, 2002 at 10:07:37, Robert Hyatt wrote: >>> >>>>On July 04, 2002 at 03:49:40, Uri Blass wrote: >>>> >>>>>On July 03, 2002 at 14:29:17, Robert Hyatt wrote: >>>>> >>>>>>On July 03, 2002 at 13:46:17, Christophe Theron wrote: >>>>>> >>>>>>>On July 02, 2002 at 20:20:37, Robert Hyatt wrote: >>>>>>> >>>>>>>>On July 02, 2002 at 18:54:49, Keith Evans wrote: >>>>>>>> >>>>>>>>> >>>>>>>>>Sorry to be anal retentive, but that's a bit of a stretch. Here's what they say: >>>>>>>>> >>>>>>>>>"The chess chips optionally support the use of an external FPGA (Field >>>>>>>>>Programmable Gate Array) to provide access to an external transposition table, >>>>>>>>>more complicated search control, and additional terms for the evaluation >>>>>>>>>function. In theory this mechanism would have allowed the hardware search to >>>>>>>>>approach the efficiency and complexity of the software search. Null move search >>>>>>>>>was also explicitly supported by this method. Due to time constraints, this >>>>>>>>>capability was never used in Deep Blue." >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>>Read on. On page 67, section 4.1, item 3, "mate threat". >>>>>>>> >>>>>>>>"It is relatively simple using a null move search to detect if there is a >>>>>>>>threat in the current position.... The Deep Blue implementation ... >>>>>>>> >>>>>>>>Which matches what I said. They had support for a normal null-move search >>>>>>>>had they wanted to use it, but they did use null-move to detect threats, >>>>>>>>something that has been done before (and several of us use a form of mate >>>>>>>>threat extension based on this idea presently). >>>>>>>> >>>>>>>>So they used null-move in at least one way, without using it as a forward >>>>>>>>pruning algorithm, which fits with Hsu's "no errors in the search" theme he >>>>>>>>mentioned repeatedly over the years. Extra extensions were one thing to him, >>>>>>>>but outright errors were something else not to be tolerated. Right or wrong. >>>>>>>>I obviously disagree about the errors in a normal null-move search, but I >>>>>>>>can hardly argue with their success... >>>>>>> >>>>>>> >>>>>>> >>>>>>>That's my point as well. >>>>>>> >>>>>>>I don't argue about their success. >>>>>>> >>>>>>>I'm just saying that they succeeded because their chips were very fast. So fast >>>>>>>that they allowed them to use inferior search techniques and still succeed. >>>>>>> >>>>>> >>>>>>Could you not make the _same_ statement about chess 4.0 in 1975? Until that >>>>>>point _everybody_ was doing forward pruning like mad. They discovered that a >>>>>>a shallower full-width search had fewer errors and they stomped everybody into >>>>>>the ground until everyone converted... >>>>> >>>>>It is different. >>>>>It is obvious that selective search from the first plies >>>>>is a mistake when you have speed. >>>>> >>>>>It also seems obvious that pruning rules that are based >>>>>on the remaining depth is a good idea and you can use them >>>>>and see everything if you search deep enough. >>>>> >>>>>Uri >>>> >>>> >>>>Everybody is overlooking an _important_ detail, so lets take this back to >>>>CS101: >>>> >>>>1. Forward pruning is a form of selective search. You cull moves you think >>>>are no good, so that the rest are basically "extended" or searched deeper than >>>>the "lemon" moves. >>>> >>>>2. Search extensions do _exactly_ the same thing. They extend the moves you >>>>think are "good" so that they are searched more deeply, while the ones you >>>>do not extend are not searched that deep. >>>> >>>>In simple terms, the two ideas are _identical_ in every way, as far as the >>>>final result. To say that doing a full-width search with lots of very >>>>sophisticated extensions is not as good as doing a sophisticated selective >>>>search (forward pruning) is not a particularly sensible statement to make. >>>> >>>>_anybody_ that has spent any time on tree-searching will realize that _either_ >>>>will produce _exactly_ the same result assuming the extensions and forward- >>>>pruning are done with the same skill level. >>>> >>>>So picking on this aspect of deep blue is simply a strawman argument. They >>>>clearly do more extensions than the rest of us. Which _may_ offset their >>>>lack of forward pruning. Believing or claiming anything else shows a lack >>>>of understanding of something... >>>> >>>>As far as your selective search comments, It is obvious (to me) that everybody >>>>is not doing selectivity just deeply in the tree. It is being done near the >>>>root as well, based on some very trivial oversights that some programs make from >>>>time to time. Oversights that a 4 ply full-width search would see. >>> >>>Yes >>> >>>I also do selective search in movei by null move pruning >>>and I think that it is a mistake >>>but I have more important mistakes to correct in movei >>>so I do not care about it now. >>> >>>pruning deep in the tree and extensions are not the same >>>because the lines that the deeper blue team did not prune >>>were not only stupid lines but also quiet lines. >>> >>>searching lines that appear to be bad lines >>>and quiet lines to the same depth is a mistake. >>> >>>Uri >> >> >>Selective pruning and selective extensions are _identical_ in result, different >>in implementation. Searching bad and quiet lines to the same depth is fine >>so long as you search critical lines to a deeper depth... > >If you search bad line to smaller depth relative to quiet lines you can get a >speed improvement. > No you can't. Here is why. My "selective search algorithm" will extend by 2 plies those moves that a null-move search won't fail high on. If the null move search _would_ fail high, the move doesn't get that extension. Result? My selective extensions will search a tree of _exactly_ the same size as the null-move search. This is all "basic search algorithm" stuff. Extending set {x} of moves 2 plies, or reducing the depth of set {y} by 2 plies will produce exactly the same result, assuming that {x} and {y} are absolutely disjoint sets. Of course, my selective extension search will report an iteration depth of 12, while your selective forward pruning search will report a depth of 14. But the trees will be _identical_. >searching everything to at least depth 12 seems to me a waste of time even if >you can search 200M nodes per second. Selective pruning programs _still_ do this, however... They can't possibly prune _every_ bad move... Not even close... > >It is better to search bad lines to depthes 8-13(depending how bad is the line >and if the final position is a quiet position) and quiet lines to depth 14. > >Uri See above. This is simply not true... In the context that selective extensions _or_ selective forward pruning can produce this _same_ result. And I do mean _same_.
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.