Author: Uri Blass
Date: 21:17:09 07/04/02
Go up one level in this thread
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. searching everything to at least depth 12 seems to me a waste of time even if you can search 200M nodes per second. 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
This page took 0.01 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.