Author: Christophe Theron
Date: 17:03:49 07/05/02
Go up one level in this thread
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
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.