Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Checks in the Qsearch

Author: Robert Hyatt

Date: 09:47:07 07/05/02

Go up one level in this thread


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.

This is all "basic search algorithm" stuff.  Extending set {x} of moves 2
plies, or reducing the depth of set {y} by 2 plies will produce exactly the
same result, assuming that {x} and {y} are absolutely disjoint sets.  Of
course, my selective extension search will report an iteration depth of
12, while your selective forward pruning search will report a depth of 14.
But the trees will be _identical_.



>searching everything to at least depth 12 seems to me a waste of time even if
>you can search 200M nodes per second.


Selective pruning programs _still_ do this, however...  They can't possibly
prune _every_ bad move...  Not even close...




>
>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.
>
>Uri


See above.  This is simply not true...  In the context that selective extensions
_or_ selective forward pruning can produce this _same_ result.  And I do mean
_same_.



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.