Author: Eugene Nalimov
Date: 11:06:08 09/05/02
Go up one level in this thread
Actually, often you don't want to search the objectively best move first. You want to search the move that will cause a beta cutoff and will result in a smallest subtree being searched. For example, if you are currently ahead in a material (compared to beta) than you probably don't want to start a deep sequence of mutual checks. All you need is some quiet move that will preserve your advantage. [I first read about that in a 1974 paper published by KAISSA team, but the idea is simple enough and certaintly was formulated earlier]. Thanks, Eugene On September 05, 2002 at 13:57:34, Robert Hyatt wrote: >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 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.