Author: Robert Hyatt
Date: 21:33:59 07/05/02
Go up one level in this thread
On July 06, 2002 at 00:11:41, Ricardo Gibert wrote: >On July 05, 2002 at 23:29:52, Robert Hyatt wrote: > >>On July 05, 2002 at 19:56:10, Christophe Theron wrote: >> >>>On July 04, 2002 at 22:23:34, Robert Hyatt wrote: >>> >>>>On July 04, 2002 at 12:10:26, Christophe Theron 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... >>>>> >>>>> >>>>> >>>>>In this case, claiming that you are doing brute force just because you do not >>>>>want errors in your search is also a lack of understanding. >>>>> >>>>>Didn't Hsu say this? Aren't you repeating his words every time you can? >>>> >>>>So? >>>> >>>> >>>>> >>>>>First your point is that they have picked brute force because they had enough >>>>>power and did not want mistakes in the search, and now you are saying that they >>>>>had a selective search and that it is equivalent to what can be achieved with >>>>>strong pruning. >>>> >>>>I said the two results can be _identical_. This is covered in most good >>>>AI books that talk in any detail about minimax search... >>>> >>>> >>>> >>>> >>>>> >>>>>Thinking about it, it seems that you can indeed get the same search enveloppe by >>>>>either pruning or extending. >>>> >>>> >>>>:) As I said... >>>> >>>> >>>>> >>>>>But thinking twice about it, I think that it is not possible with the search >>>>>extension techniques used in Deep Blue to get something equivalent to the simple >>>>>and efficient pruning techniques we know today. >>>> >>>> >>>>Based on what? >>> >>> >>> >>>Based on the description they have made of it. >>> >>> >>> >>> >>>>I _despise_ hearing that kind of statement with _zero_ >>>>testing to support it. Very similar to the "bitmaps can't do this or >>>>that" statements that show up from time to time. And which I find very >>>>amusing as a bitboard practitioner. >>> >>> >>>I think you don't get what I said. >>> >>>I'm just saying that given their framework (which is described in their >>>publication) one cannot get a search enveloppe equivalent to the enveloppe you >>>get with currently known pruning techniques.\ >> >> >> >>Why? Did you see the part where they extend 2 plies at times? That is >>_all_ you need to behave just like null-move, which shortens some paths >>by 2 plies.... >> >> >> >>> >>>I'm not talking here about the superiority of one system on the other. >>> >>>You were talking about the classic idea that one can get the same search >>>enveloppe with either pruning or extensions. >>> >>>Actually there is no discussion here. It is true, in theory. >>> >>>That started to make me think about: "how can I get the same enveloppe by using >>>extensions instead of pruning" (in Chess Tiger for example). >>> >>>And suddenly I find myself thinking about ideas I had never met before. >>> >>>Here I'm not trying to oppose your ideas. Actually I have forked out of the >>>initial discussion about Deep Blue. >>> >> >> >>I think either approach is very interesting. I have done both although I >>haven't done forward pruning in a _long_ time (other than n ull-move of >>course). >> >> >> >> >> >>> >>> >>> >>>>Their search definitely "worked". That seems to be all that counts in the >>>>game of chess. Wins and losses.. >>>> >>>> >>>> >>>> >>>>> >>>>>I smell that there is something important behind this and I will have to think >>>>>more about it. That's an interesting research area. >>>>> >>>>> >>>> >>>>It is also well-known. The two approaches are totally complementary. Same >>>>final result. Totally different ways of getting there. >>> >>> >>> >>>That's what I wanted to say. >>> >>>For example you are at 5 plies before the horizon and decide to stop searching >>>here. >>> >>>What is the equivalent of this when one is using extensions? >> >>You extend all the _other_ moves except here. >> >> >> >>> >>>In other terms, can the definition of extensions be expanded to cover both >>>"classical extensions" schemes AND pruning? >> >>I don't see why not. IE the only difference is going to be the iteration >>depth you report. Which is better? reporting 10 but extending 2 plies, or >>reporting 12 but cutting most stuff off at 10 plies? >> >>IE isn't a "forward prune" basically a "negative extension"?? >> >> >>> >>>I'm always interested in generalizations, as they can help to uncover new ideas. >>> >>>I don't remember having read a paper on this. >>> >>> >>> >>> >>>>>>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. >>>>> >>>>> >>>>> >>>>>It's not as simple as that. >>>>> >>>>>"Near the root" can mean several different things. >>>>> >>>>>You can apply some kind of gross pruning system near the root and make big >>>>>shortsighted mistakes. >>>>> >>>>>You can also apply some detection near the root and collect information to prune >>>>>later. Then you don't make such big mistakes. >>>>> >>>>>The argument that pruning will make obvious blunders sometimes is simply wrong. >>>> >>>>That argument is provable. Several have shown positions that Tiger simply >>>>can not see. The last one posted here you replied "the forward pruning >>>>simply misses that..." >>> >>> >>>Yes I remember. >>> >>>It was Fernando using Chess Tiger for Palm in blitz. >>> >>>The program was reaching ply depth 3 and missed a fork (or something like that) >>>at the second ply. >>> >>>I'm not sure you could catch the PC version as easily, even at bullet time >>>controls. :) >>> >> >>The one I recall wasn't a palm. It was a normal tiger. IE people regularly >>report positions that fritz can simply not solve, period. Because the position >>zaps null-move searchers. The same thing will happen to _any_ program that >>does forward pruning, since there is no way to make it perfect enough to not >>discard a good move that looks horrible by any imaginable rule. >> >>BTW, Tiger/Fritz aren't the only programs that have "killer positions". I >>have more than enough for my program... > >So do humans, but it forward pruning is not only a good idea, it is essential >for good play for humans. Are you _sure_ you forward prune? Or do you just look at "interesting moves" deeper (selective extensions)? I personally believe humans do not forward prune... because I am _sure_ that a human looks at every move on the board at the root position, and says "these two are interesting and deserve a deeper search." And if both turn out to be bad, then we go back and pick a third to look at if needed... So perhaps the idea of "forward pruning" is foreign to us as well... > >> >> >> >>> >>> >>> >>> Christophe
This page took 0.02 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.