Author: Eric Oldre
Date: 06:44:12 08/11/04
Go up one level in this thread
On August 10, 2004 at 22:05:22, Stuart Cracraft wrote:
>On August 10, 2004 at 18:48:25, Robert Hyatt wrote:
>
>>On August 10, 2004 at 17:15:06, Uri Blass wrote:
>>
>>>On August 10, 2004 at 16:02:37, Robert Hyatt wrote:
>>>
>>>>On August 10, 2004 at 15:32:57, Uri Blass wrote:
>>>>
>>>>>On August 10, 2004 at 12:52:28, Robert Hyatt wrote:
>>>>>
>>>>>>On August 10, 2004 at 10:59:29, Tord Romstad wrote:
>>>>>>
>>>>>>>On August 10, 2004 at 10:35:29, Anthony Cozzie wrote:
>>>>>>>
>>>>>>>>Plus, if you have only PST eval you should be getting 3-4M nps, so SEE probably
>>>>>>>>slows you down a _lot_.
>>>>>>>
>>>>>>>Yet another proof of how bad my programming skills are. With PST eval and
>>>>>>>nothing
>>>>>>>else, I get about 800,000 nps (on a PIV 2.4 GHz). Adding SEE slowed me down to
>>>>>>>around 750,000 nps.
>>>>>>>
>>>>>>>Tord
>>>>>>
>>>>>>
>>>>>>SEE slowed me down by 10%. Move ordering improved to speed me up 10%.
>>>>> Washed
>>>>>>out to no advantage, _until_ I added the stuff about tossing out captures that
>>>>>>can't bring the score back to within the alpha/beta window.
>>>>>
>>>>>I doubt if you can give one number for speed improvement thanks to better order
>>>>>of moves.
>>>>>
>>>>>I think that the improvement can be bigger at longer time control.
>>>>
>>>>I don't believe the "percentage" will change, as I used long time controls for
>>>>all my testing... I don't pay much attention to blitz except to spot gross
>>>>problems...
>>>
>>>For every long time control there is longer time control and if you did the test
>>>some years ago the hardware got better.
>>>
>>>I do not see reason not to believe that the percentage will change because
>>>better order of moves should give bigger improvement in longer time control.
>>>
>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>>
>>>>>
>>>>>
>>>>> That made me about
>>>>>>2x faster overall, which is a _big_ gain.
>>>>>
>>>>>
>>>>>2xfaster overall only thanks to pruning?
>>>>>
>>>>>It seems to me too much advantage for SEE.
>>>>
>>>>I only report what I get.
>>>>
>>>>Hsu asked the question, I (and Stanback and others) ran the tests to see.
>>>>
>>>>>
>>>>>Note that even without SEE you can prune in the qsearch captures that cannot
>>>>>bring the score to alpha/beta window and if you are queen down relative to
>>>>>alpha then it is clear that capture of a rook will not bring the score back to
>>>>>alpha even without SEE so if the first version did not use that pruning you have
>>>>>not fair comparison.
>>>>
>>>>
>>>>That's a gross case. What about the case where the window is X, the current
>>>>material is X-2.00, and now you need to know whether the capture will bring you
>>>>back into the window. A good SEE score is _way_ better than MVV/LVA, as MVV/LVA
>>>>would say that QxR is ok, where SEE would say -4 since the rook is defended.
>>>>
>>>>The test was simply "normal q-search" with pure losing captures thrown out with
>>>>SEE vs normal q-search ordered by MVV/LVA."
>>>>
>>>>The current approach is a bit better than even that experiment of course.
>>>
>>>If I understand correctly
>>>You claim that only pruning captures in the qsearch based on SEE did you twice
>>>faster(better order of moves only compensate for being slower and not more than
>>>it.
>>>
>>>I find it hard to believe when I remember that I checked that even with tscp
>>>simple approach that does not have SEE only near 20% of the nodes are qsearch
>>>nodes so even if you save all the qsearch you still do not get being twice
>>>faster and pruning bad captures based on SEE does not save all the qsearch
>>>nodes.
>>>
>>>Uri
>>
>>What I said was this: Hsu and I had a "discussion" about SEE vs MVV/LVA in
>>rec.games.chess.computer. I claimed that SEE was better, he claimed MVV/LVA was
>>just as good.
>>
>>I first modified Crafty's q-search and normal search so that it used MVV/LVA to
>>order captures (there was a version or two of this released so that others could
>>run the tests as well). This version could _not_ prune captures as MVV/LVA
>>doesn't give enough information to decide whether a capture loses or wins... IE
>>if the largest piece hanging is a rook, and the smallest attacker is a queen,
>>MVV/LVA tries QXR first, whether the rook is defended or not.
>>
>>I then modified the normal crafty to use SEE but without excluding losing
>>captures, since MVV/LVA q-search had to try all captures for safety.
>>
>>I compared the two and found that SEE produced 10% smaller trees (this was on a
>>fast machine for significant searches) but was 10% slower, meaning there was no
>>advantage for either.
>>
>>Then I turned my original quisecence search pruning back on, something that
>>works for SEE but not MVV/LVA and the tree size dropped by 50% over a test set
>>of positions. This was based solely on the idea of (a) no SEE losing captures
>>(no reference to alpha/beta or the infamous "delta pruning" I now use); (b)
>>after 4 plies of q-search, no "exchanges" (even trades) either. That was what
>>early Crafty did, copied from a simple CB q-search that I used after the normal
>>CB q-search gave up on checks and threats and went to a simple capture-only
>>search near the end of the variations.
>>
>>My current "delta pruning" approach is even more effective in eliminating
>>q-search nodes. It would be easy to turn it off to compare tree sizes of
>>course.
>
>Okay I am in the dark about the infamous delta pruning. So I will go do
>the requisite CCC search for the 2nd to keywords in that 3-word phrase
>and perhaps the Delta of Oracle, woops, the Delphi of Oracle will give
>me Delta knowledge.
>
>Stuart
I believe what Robert was talked about was this....
a) pruning losing captures.
if(see_value>0){do_search=true;}
vs b) pruning with "delta"
if(see_value+static_eval>alpha){do_search=true;}
at least that was my understanding of what he meant by "delta" pruning.
Eric
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.