Author: Ricardo Gibert
Date: 21:07:48 07/05/02
Go up one level in this thread
On July 05, 2002 at 23:36:31, Robert Hyatt wrote: >On July 05, 2002 at 20:03:49, Christophe Theron wrote: > >>On July 05, 2002 at 13:38:53, Uri Blass wrote: >> >>>On July 05, 2002 at 12:50:34, Robert Hyatt wrote: >>> >>>>On July 05, 2002 at 11:29:08, Uri Blass wrote: >>>> >>>>>On July 05, 2002 at 11:00:14, Tony Werten 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. >>>>>>> >>>>>>>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. >>>>>> >>>>>>Wich would be the same as searching to 14 ply and prune to 8 or >>>>>>searching to 8 ply and extending to 14. >>>>>> >>>>>>OR searching to 11, prune to 8 and extend to 14 ( guess what, there are even >>>>>>more possibilities depending on how strong you prune or extend ) >>>>>> >>>>>>Tony >>>>> >>>>>You missed my point. >>>>> >>>>>My point is that the programmers of deeper blue did not search bad lines to >>>>>smaller depth relative to quiet lines and even if you can search 200M nodes per >>>>>second it is a mistake to do it. >>>> >>>> >>>>But they _did_ do this. They did all sorts of extensions, from singular, >>>>to threat moves, to you-name-it. That extends non-quiet moves, while >>>>leaving the quiet moves alone. I don't think it so easy to quantify a move >>>>as "bad". Just look at WAC141 and tell me how that queen move looks good to >>>>_any_ surface analysis. Yet it wins. Pruning that could lose the game if >>>>you are black. Or miss winning it if you are white... I don't buy the >>>>concepts of "bad", "quiet" and "tactical". I prefer "extendable" or "non- >>>>extendable" instead... >>>> >>>> >>>> >>>>> >>>>>Not pruning based on evaluation is a big mistake because in a lot of the lines >>>>>that the computer searches one side is losing material for no compensation. >>>> >>>>Again, WAC141 is the perfect counter-example to this... >>> >>> >>>A change can be a good change even if I solve part of the positions slower. >>>If I solve more position at every time control then it means that the change is >>>probably a good change. >>> >>>It is also possible to learn from positions that I do not solve about better >>>rules when not to prune. >>> >>>Uri >> >> >> >>You mean that Deep Blue's search was very far from optimal? >> >>Geez... Don't tell Bob. :-) >> >> >> >> Christophe > > >I think the discussion about "optimal" is pointless. Here is why: > >You and I are going to drag-race 3 race match. Rules are, you get to use >a v6 engine block of your choice. Anything goes, but you have to run on >pump gas, which means no supercharger to speak of. > >I, on the other hand, am going to run a bored/stroked Hemi from Chrysler. >With carburetors I can make over 1500 horsepower on pump gas. But I am >going with dual huffers and run it on nitro. I am going to stop tuning >at the 3000 horsepower mark, even though experience has shown that way >more power is available. My motor isn't optimal. Does it matter? You >have no chance whether it is optimal or limping along at 3000 horsepower. >You are going to be down by almost 10:1 in power... > >That was sort of what Deep Blue did. Except it wasn't 10:1, it was >way over 100:1. So "optimal" is not an important concept when you have that >kind of static advantage... This is an argument that applies to comparisons with other chess programs, but not with the human players such as Kasparov. In the actual, match against Kasparov their "success" was hardly "overwhelming" and owed a good measure to good luck.
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.