Author: Robert Hyatt
Date: 20:31:52 07/05/02
Go up one level in this thread
On July 05, 2002 at 13:55:00, Uri Blass wrote: >On July 05, 2002 at 12:47:07, Robert Hyatt wrote: > >>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. > >I agree that every pruning can be described as extensions but this was not what >I meant when I explained that you can get a speed improvement. > >The point is that it is possible to get usually the same results faster relative >to deeper blue (in few cases you are going to be slower) but the total result is >improvement. > >Deep blue had extensions but I believe that they did not have rules to extend >quiet lines of logical moves. > >Uri I'm not going to try to match their numbers. We don't even know how many nodes they actually search since they didn't count them...
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.