Author: Anthony Cozzie
Date: 08:15:28 01/15/04
Go up one level in this thread
>OK, but I don't think you played with MTD(f) long enough to make it work >really well. You cannot simply replace PVS with MTD(f) and expect that >your engine will play as well as or better than before; it takes a long >time to learn all the tricks. Many techniques which work well with PVS >are less effective with MTD(f), and the same holds true in the opposite >direction. This, of course, makes it very difficult to make an objective >comparison of the two algorithms. 1. I did the full upper/lower bound hash rather than limit/type. 2. I tried probing in qsearch 3. I experimented quite a bit with heuristics for varying the window, as opposed to plaat's next_try = current try-1. I probably spent about a week on it. I think in the _average_ case MTD(f) can even be better than PVS() [my implementation was about equal] with some tuning. It can find tactical shots much faster, because it goes through the entire move list sooner than PVS(). It is the _worst_ case where MTD(f) falls apart; in my personal opinion the worst cast is more important. What I found was that a fail high in MTD(f) is very fast, while a fail low is very slow. In a fail high, only 1 child node is searched, while in a fail low _all_ nodes must be searched. So it was quite common for me to see stuff like this: searching [19,20] -> 20 [n=4000] searching [21,20] -> 20 [n=200,000] I am not exaggerating 4,000 vs 200,000. It is easily a difference of 30 and sometimes 50. The thing I ended up doing was a combination of binary search, fixed low, and simple up. So Zappa's search looked like this: searching [4,5] -> 4 [n =2,000,000] [first search always by far the longest] searching [-10,-9] -> -9 [n = 20,000] [zero window fail highs are crazy fast] searching [-9, -8] -> -8 [n = 20,000] searching [-8, -7] -> -7 [n = 20,000] searching [-7, -6] -> -6 [n = 20,000] searching [-6, -5] -> -6 [n = 1,000,000] [fail low -> way more nodes] Now you have a troublesome tradeoff to make. You want to have a reasonable number of searches, but you also don't want to fail low. Suppose your position is tight, and your score suddenly goes from -.2 -> -1.5 (you discover a mating sequence where you must throw a pawn). Now your MTD(f) search looks like this: searching [-20, -19] -> -20 [n = 2,000,000] searching [-40, -39] -> -40 [n = 1,000,000] searching [-60, -59] -> -60 [n = 1,000,000] searching [-80, -79] -> -80 [n = 1,000,000] searching [-100, -99] -> -100 [n = 1,000,000] searching [-120, -119] -> -119 [n = 20,000] searching [-119, -118] -> -119 [n = 1,000,000] So while the best case performance in my example was 3.1 MLN nodes, the performance in the fail low case was 7 MLN nodes. I know I am pulling these numbers out of the air, but this is what I saw in test positions and game - it might be even worse than what I am describing. Now, writing all this has given me an idea. You start out trying an MTD(f) window at prev_score - 8. If it fails high, than you continue your MTD(f) ways. If it fails low, you switch over to PVS(). This is fresh off the neurons so it may not work/be stupid/make you feel less handsome/etc. 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.