Author: Robert Hyatt
Date: 09:26:22 10/01/98
Go up one level in this thread
On October 01, 1998 at 09:03:43, Ernst A. Heinz wrote: >On October 01, 1998 at 08:46:23, Robert Hyatt wrote: >> >>If you generate one move at a time, how are you searching the best captures >>first? MVV/LVA? using SEE can reduce the size of that tree significantly >based on tests a couple of us ran 3 years ago... > >Was that data published anywhere? Or do you have it still handy by chance? > >My own tests with "DarkThought" do not show any significant differences >between MVV/LVA and SEE. > >Could it be that your observed gains were due to aggressive SEE pruning in >the quiescence search instead of yielding gains by better move ordering in >higher parts of the search tree? > >=Ernst= It was in rec.games.chess.computer (more likely rec.games.chess) about three-four years ago. Hsu and I were having this discussion. John Stanback and I both ran tests. Here's the "summary"... just using SEE ordering over MVV/LVA reduced the tree size by 10-15% (counting nodes only). Note that this forced a full quiescence search of all captures, using both MVV/LVA and SEE to order and compare. But, after that test, I re-enabled my normal q-search code which tosses out captures that SEE says lose material, and that cut the tree by another 50%, which we couldn't do when testing MVV/LVA because it would be grossly unsafe. So the bottom line was using SEE + the q-search trick cut the tree to 40% of what it was using the traditional MVV/LVA approach. This was, for a while, something that could be turned on/off in crafty and many ran the test. The data was always similar to what I found. I believe that John converted to SEE after this discussion and reported similar results as well... My "SEE" code is only a couple of percent of the total search time: % cumulative self self total time seconds seconds calls ms/call ms/call name 16.49 47.87 47.87 17150992 0.00 0.00 Evaluate 7.46 69.52 21.65 15753832 0.00 0.00 MakeMove 6.11 87.25 17.73 5589902 0.00 0.00 GenerateCaptures 5.78 104.02 16.77 3071 5.46 72.60 Search 5.25 119.26 15.24 AttacksRookFunc 5.13 134.15 14.89 FirstOne 4.90 148.37 14.22 15753802 0.00 0.00 UnMakeMove 4.61 161.74 13.37 AttacksBishopFunc 4.48 174.76 13.02 5502491 0.00 0.00 EvaluatePawns 4.17 186.86 12.10 17150992 0.00 0.00 EvaluateKingSafety 4.08 198.71 11.85 9118140 0.00 0.00 Swap 3.65 209.32 10.61 11957708 0.00 0.00 NextMove 3.53 219.57 10.25 11128825 0.00 0.01 Quiesce 3.41 229.47 9.90 8933056 0.00 0.00 EvaluateDevelopment 2.88 237.84 8.37 25848292 0.00 0.00 Attacked 2.29 244.48 6.64 PopCnt 2.14 250.68 6.20 LastOne 1.71 255.63 4.95 10568769 0.00 0.00 AttacksTo In the above case, "Swap()" is the static exchange evaluator, and over about 10 moves in a game, the above shows 4% for Swap. Which means that the tree shrinks by 10-15% if you don't toss out losing captures in the q-search, for a 4% cost in cpu time, which means about a 10% improvement in search speed, the value we agreed on in the r.g.c discussion a while back. Factoring in the 50% loser capture savings however, and this becomes a *huge* win... I've used SEE since about 1974 or so... Coko used it in 1970 for example... MVV/LVA is a nice hardware approach when there is no way to do a SEE circuit in reasonable circuit space and time, of course...
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.