Author: martin fierz
Date: 08:19:52 03/29/04
Go up one level in this thread
On March 29, 2004 at 11:14:17, Anthony Cozzie wrote: >On March 29, 2004 at 11:05:17, martin fierz wrote: > >>On March 29, 2004 at 10:27:19, Anthony Cozzie wrote: >> >>>On March 29, 2004 at 10:01:55, martin fierz wrote: >>> >>>>On March 29, 2004 at 09:46:48, Uri Blass wrote: >>>> >>>>>On March 29, 2004 at 08:54:09, martin fierz wrote: >>>>> >>>>>>On March 29, 2004 at 07:04:13, Uri Blass wrote: >>>>>> >>>>>>>On March 29, 2004 at 06:25:28, martin fierz wrote: >>>>>>> >>>>>>>>On March 28, 2004 at 18:55:53, Artem Pyatakov wrote: >>>>>>>> >>>>>>>>hi artem, >>>>>>>> >>>>>>>>[snip] >>>>>>>> >>>>>>>>>>>On the other hand, I think a lot of researchers have been overly ambitious and >>>>>>>>>>>have tried to replace Alpha-Beta & tricks with a neural network or some totally >>>>>>>>>>>different approach. I think that with the current state of AI tools, these >>>>>>>>>>>efforts are bound to fail. >>>>>>>>>> >>>>>>>>>>A lot of researchers? Other than myself, I don't know of any other workers who >>>>>>>>>>are attempting a complete and competitive chess playing program that doesn't >>>>>>>>>>tread the oft traveled A/B bag-of-tricks road. >>>>>>>>> >>>>>>>>>That's good a point (will probably include in paper) - not many are working on a >>>>>>>>>complete chess program, since most just address a particular section, like the >>>>>>>>>evaluation function. But one old effort - MORPH - comes to mind, and I think I >>>>>>>>>noticed a couple of other failed Neural Net efforts (don't have references >>>>>>>>>handy, but I can look). >>>>>>>> >>>>>>>>steven is doing a completely radical departure from A/B. but many others are >>>>>>>>applying more gradual changes to the A/B-model, with reasonable success >>>>>>>>(smarthink, kaissa, gothmog come to mind, and probably most commercial engines >>>>>>>>too). at least these engines make considerably larger attempts to shape their >>>>>>>>game tree than a "classic" A/B searcher like crafty does. >>>>>>>> >>>>>>>>[snip] >>>>>>>> >>>>>>>>>As I mentioned before, I decided to concentrate my research on move ordering for >>>>>>>>>a couple of reasons: >>>>>>>>>1) Move ordering promises big payoffs if done right. >>>>>>>> >>>>>>>>how much deeper can you search if you reach 95% move ordering success (defined >>>>>>>>as cutoff @ 1st / all cutoffs) instead of ~90% that most get today? how much if >>>>>>>>you reach 100%? >>>>>>> >>>>>>>I cannot answer the 95% question but I can answer the 100%. >>>>>>> >>>>>>>If you reach 100% then always choosing the first move is enough because if the >>>>>>>first move does not generate a cutoff no move is going to generate a cutoff so >>>>>>>you can finish to search to the end of the game very quickly because you search >>>>>>>only one move in every ply. >>>>>>> >>>>>>>Uri >>>>>> >>>>>>you do not answer the question here - and what you answer is wrong too :-) >>>>>>always choosing the best move first to search means you search sqrt(N) moves per >>>>>>ply on average, not 1 move per ply. >>>>> >>>>>No >>>>> >>>>>In that case you do not need to search the other moves because you know that >>>>>they are worse. >>>>> >>>>>If you always start from the best move than the pruning strategy of not >>>>>searching moves except the first move is simply correct and I see no reason not >>>>>to use it. >>>>> >>>>>Uri >>>> >>>>come on uri, this is ridiculous. of course you can use that shortcut IF you know >>>>that your move ordering is 100% perfect. in that case you need no search at all >>>>either. obviously this is an academic question and has nothing to do with >>>>reality, and is not what i'm asking... the question remains: in the extremely >>>>unlikely case that you have 100% perfect move ordering (by accident), what do >>>>you gain compared to 90% perfect (in the usual sense of move ordering %age)? >>>> >>>>cheers >>>> martin >>> >>>It would be possible to determine this experimentally - just keep track of each >>>position and the best move at each ply on the hard disk. It wouldn't be >>>practical for use but it would be pretty interesting. >>> >>>anthony >> >>if i had to do this i would produce a mock A/B program which first randomly >>decides whether the node is a fail-high node (~50% of all cases i guess), and >>then again randomly decides whether it fails high on the first move (~90% of all >>cases), and finally decides to fail high somewhere in between move 2...N if not >>on the first move (perhaps with equal probability, or with decreasing >>probability from move 2...N). by playing around with the probabilites of these >>random decisions, you can easily determine the numbers i'm looking for, and see >>how they depend on the quality of your move ordering. >> >>i disagree though that this is not practical: for example, if you find that >>going from 90% to 91% move ordering (= fail high at first/total fail highs) you >>need to search 50% less nodes on a typical search depth your engine reaches, >>then you definitely know you should work on your move ordering. if you find that >>you need to search 0.1% less nodes, you know that working on MO is a waste of >>time from now on. the true value will probably lie somewhere in between, but in >>any case, it gives you an idea of what you might gain with more expensive MO >>schemes. >> >>i can imagine some kind of formula just by doing some assumptions, which may be >>completely wrong...: >> >>the totally wrong-ordered case goes as >>nodes(depth) ~ (N*N)^D/2 >> >>the totally ordered case goes as >>nodes(depth) ~(1*N)^D/2 >> >>this formula stems from the fact that you search exactly 1 move at player A's >>moves, and all N at player B's moves AFAIK, so for going 2 ply deeper i need 1*N >>nodes. so let me assume random move ordering for player A, meaning i get the >>best move right on average at move N/2, which gives me >> >>nodes(depth) ~ (N*N/2)^D/2. >> >>perhaps that should read (N*sqrt(N))^D/2, because it might be the geometric >>instead of the arithmetic mean?! >> >>in any case, you can now assume that you find the best move 1st in the fraction >>F (~0.9), and in the remaining case at random, this leads to >> >>nodes(depth) ~ (N*(1*F+(N/2*(1-F)))^D/2. >> >>plugging in some numbers like N=20 (reduce from 40, trying to account for >>nullmove?!), D=10, F=0.90 and 0.91 i get >> >>nodes(10, F=0.90) = 79 million >>nodes(10, F=0.91) = 62 million >> >>so for 1% better move ordering i get 22% less nodes?! seems rather excessive. >>let me try again using sqrt(N) instead of N/2 - that still gets a 12% reduction. >> >>hmm, either my formulas are crap or i really have to work on my move >>ordering ;-) >> >>cheers >> martin > > >OK, we did not communicate here. aha, i see - this time i understood! let's see, even better than "muse-@-XY" would be "zappa-@XY", because i generally believe that such experiments should be made with the best possible engine ;-) anyway, thanks for the suggestion, it sounds very sensible. a bit of work, but definitely doable. cheers martin > >What I am proposing is this: > >Create some code that stores for each transposition table key the best move at >each ply. Requires maybe 1/2 GB of memory for a reasonable depth search (my >back-of-the-envelope unoptimized computation). > >E.G.: > >Key 0x8432762183 >Q-Nxd5 >1-Nf3 >2-Nf3 >3-Qc3 >... > >Run search, record node counts. Keep track of every time the move ordering was >wrong (both at PV and CUT nodes). > >Flush transposition table. Run search iteratively until move ordering is >perfect. You can use the new table to simply always choose the best move first. >This might require a few runs since the tree might search different nodes as the >move ordering gets better. > >At that point you will have a search of muse with perfect move ordering. Record >the number of nodes visited versus a regular search. Of course, this is not >practical for a tounament game (for obvious reasons). > >Some interesting sub-experiments: move ordering differences by ply - 3% at 5 ply >vs 100 % at 8 ply (?) Also, move ordering at PV nodes vs fail-high nodes. > >anthony
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.