Author: Robert Hyatt
Date: 10:57:34 09/05/02
Go up one level in this thread
On September 05, 2002 at 13:45:30, Dieter Buerssner wrote: >On September 05, 2002 at 10:47:32, Robert Hyatt wrote: > >>I don't think our serial searches are very bad. IE I get the best move >>first 92% of the time. I'm not sure how much farther I can go with that >>as there will _always_ be flaws that only a deep search exposes, when you >>sort moves in some arbitrary way. > >I guess you meant the fraction of beta cutoffs in the first move you try, by the >92%. Yes. That is the number I measure in Crafty and display. > Then, this number may also be misleading. Is it really the best move, or >just any move, that cutoffs? Many more moves may actually cutoff, but usually we >don't know this (unless writing some experimental unefficient minimax code for >collecting the statistics). Other moves may cutoff much faster (with a smaller >tree following). OK... good point. I will revise that to "Crafty searches a move 'good enough to cause a cutoff' first 92% of the time. I don't think it matters, based on Knuth/Moore's paper. The important thing is to search a move good enough to cause a cutoff first. If you do, then there is no need to search the "best" move first if several are good enough. Their math supported this pretty well, as did mine in the Journal of Parallel Computing back in the late 80's... > In the extreme, an alternative move may cutoff immediately from >the HTs. Enhanced transposition cutoff checks for this, but in general, I think >there are no well known algorithms to find the fastest cutoff move. ETC has a chance, of course. Although for me it was a "break-even" deal. The tree shrank a bit, but the speed was lower due to the extra hash-signature update and extra hash probe. I chose to stick to the KISS approach and dumped it. > >I did some experiments for collecting some statistics a while back. IIRC with >random move ordering, I often got close to 50% cutoffs in the first tried move, >in the nodes that got a beta cutoff. Still, the search efficiency became (not >surprising at all) extremely bad. It's exponential, so 50% is horrible. Due to that large exponent you have to apply. 92% is not great and certainly leaves a lot of room between the real and minimal tree sizes. > >Regards, >Dieter
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.