Author: Robert Hyatt
Date: 21:29:43 07/05/02
Go up one level in this thread
On July 06, 2002 at 00:07:48, Ricardo Gibert wrote: >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. I wouldn't disagree with the "luck" part. I was fortunate enough to have luck on my side more than once in various WCCC and ACM tournaments. However, I would not want to call their search "sub-optimal" when it is so much better than mine, based on the results they produced against me (and others). IE when I get to 3000 horsepower, getting that next 1000 is not nearly so important since I am so far ahead of everybody else (computer programs) already... Which would you rather have: an "optimally set up v6 on gas at maybe 300 horsepower" or "a sub-optimally set up 600CI hemo producing 3000 horsepower." Of course, your engine is more "optimal" than mine. :) But it comes in second place _every_ time. Did the work you spent making yours optimal really result in something more significant than the work I spent in making a sub- optimal engine that leaves everyone in the dust? IE the DB guys spent a _lot_ of time building that 3,000 horsepower engine. And everybody is knocking them because they weren't able to get that last 1,500 horsepower out of it. That I don't quite get...
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.