Author: Robert Hyatt
Date: 12:08:18 09/05/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. That is true, although in the "general sense of alpha/beta" it doesn't really matter because all the math is dealing with uniform game trees, so that one move is no harder to search than another. But in the case of selective extensions, this might be food for thought. IE it might be better to search a non-check before a check, if there is something to suggest that it is also a good move... > >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. Right, although again this is based on real trees that are non-uniform, which knuth/moore doesn't really address... > >[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.