Author: Vincent Diepeveen
Date: 10:33:29 09/06/02
Go up one level in this thread
On September 05, 2002 at 14:06:08, Eugene Nalimov wrote: >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. Not really, the best move is usually best, because usually the problem of *a move* cutting off is shown next iteration by major overhead. So at this iteration i a move could cutoff in very little nodes, but if it next iteration fails low it obviously is a whole subtree you researched. >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.