Author: Robert Hyatt
Date: 06:14:15 01/23/98
Go up one level in this thread
On January 23, 1998 at 01:19:24, Don Dailey wrote: >Bob, > >This is a good post from you. It does address many of my misgivings >with MTD(f) and your experiences closly mirror mine. > >First of all I didn't mean to imply you were not a performance freak, >I know in fact that you are. Also I want to emphasize that I'm not >critical of you or anyone else who does not use MTD(f). I can see >you clearly understand the problems involved and have made an informed >decision. I can't even say for sure my decision to use it is right. this is an interesting problem of course. I first tried this sort of algorithm in 1980 or 81. Murray Campbell suggested that this was at least something to play with because the searches go so very quickly. I even played in one ACM event using this. But the "predicted move" problem was a problem since we generally had nothing useful. Thinking about this, in Crafty I added the "puzzling" feature which is used by Ponder() when there is no predicted move (such as when a move at the root fails high and time runs out, or the move fails high but then I can't resolve the score and it fails low. I now do a fairly short search (I believe I use something like 1/10th of the normal search target if the game is long enough) and do a search to get the opponent's move for pondering. It works. But it is not as accurate as the normal search move. I just checked 10 games that went over 100 moves each. In that 10 games, this happened 26 times. I then ran the normal search again, and for 18 of those 26 games, the real predicted move was right while the "puzzled" move was wrong. In the other 8 positions, the puzzled move was wrong while the search move was right. Odd result of course. I don't have any good data about "puzzling". I just got tired of watching Cray Blitz "sit" after failing high and then running out of time. Storing old predicted moves is also not good because we found ourselves predicting blunders many times when we had no real predicted move. Puzzling works, but it ain't great... > >We do get a lot of benefit from it so it's hard to throw it away. >Your point about the PV's cancelling the benefit of the speedup it >probably not the case, at least for us. I agree it cancels some >of the benefit but we do in fact predict a lot of moves. It just >really pisses me off that occasionally a really obvious move like >a recapture does not get predicted and we have lost some free time. >But most of the time we get these. A good solution for tournaments >is to do a short search for prediction and this will always produce >a good move. We could do a 9 ply search for instance and stop if >it exceeds 1/2 second or some such hack. It's ugly but workable. this works partially. It is what I have done for a couple of years, just to handle the fail-high/out-of-time problem... > >I am with you in my distaste for this behavior. I HATE these ugly >PV's I cannot trust. I have yet to see what will happen when I >implement proper PV's but I'll let you know. Your note is discouraging! I hope it is possible, but the only solution I see (due to every other ply failing low) is to somehow *hope* that at least one of the final re-searches also fails high, so you load the hash table with best moves from the fail-low re-searches (which gets even-ply best moves stored in the hash table, and the fail-high re-search will store odd-ply best moves. And then you get to hope that somehow the right positions don't get clobbered before you can stomp back thru them picking up *all* the best moves. > >I realized you clearly knew what you were talking about (as if there >was any doubt!) when you brought up the issue of lazy evaluation! >Yes, mtd(f) plays hell with it. I have always relied heavily on >lazy evaluation (I call it score fudging) but over the years have >grown to hate it. With mtd(f) my experiences with it have been >awful. mtd(f) (for those watching) relies heavily on the scores >returned from each probe. With lazy evaluation you tend to return >relaxed scoring information which affects the efficiency of mtd(f)! >Your nodes per second go up, but the number of nodes needed go up >to match it! It really sucks! There is also some bad side behavior >if your "fudge margin" is too small AND it crosses the beta boundary. >For instance you >interpret (sc - fudge) as a lower bound because it is above beta but >fudge is too small and it turns out the real situation is that the >score is in fact and upper bound (below beta!) Your error can >propogate to the root and be more than the difference between your >error and fudge when this happens. What happens is blunders. >My solution to this one was to limit the evaluation so that it never >was greater than FUDGE in either direction. Another hack. I >discovered this one when the error got GREATER as I increased the >fudge margin until it exactly matched my error and was suddenly >fixed. This never happened unless the error "crossed over!" what it did to me was to simply blow up the number of re-searches needed to make alpha/beta "touch". I started off with a fail-high value of "X", and would get back X+N, as a fail-soft estimate of how far to move the window up for the next re-search. But then I would get a X+N+Q score back because the lazy eval now lets the score get a little higher before it decides that it doesn't need to eval any more. This was a real problem for me. Aske quoted some very low re-search numbers. I couldn't approach them with my current eval, and in many cases this turned out to be 2x slower or worse. Once I figured out why this was "broken" I decided that +15% was going to be offset by my eval losses. My eval is now about 50% of the total search time. If it wasn't "lazy" I don't know what it would be, but I rarely have to do a full evaluation, maybe only 10-20% of the time depending on the position... > >But now I'm about to commit hearesy. I know this will generate a >ton of HATE mail but here goes (my arms now protecting my face): >I now believe lazy evaluation is problematic at best, incorrect in >general. Even without mtd(f), as my evaluation has grown more >sophisticated I am noticing lots of problems with lazy evaluation. >I simply have too many big scoring terms now and it's getting harder >and harder to cascade them. I used to calculate material and pawn >structure (looking for square of pawn stuff) and then fudge it. Then >try the next largest big scoring thing etc. But now I have aggressive >king safety, more aggressive pawn evaluation in general, and much more. I have had to get "less lazy" myself. However, I have put all the "big" stuff up front. It turns out that for me, the small positional terms were the biggest cpu burners, so I still do the big stuff like passed pawns, trapped bishops, king safety threats and so forth, then I take a lazy exit if possible before doing the smaller things like piece centralization, file analysis, piece coordination, and so forth. But slowly, things are getting pulled "above" the lazy exit... A real pain. CB had the best lazy eval I have ever seen, as I carefully kept up with the min and max score for each piece. So I knew *exactly* how far a single piece could swing the score, and when that piece gets captures, I could reduce the eval error estimate accordingly. I did that early in Crafty but had to toss it because now one piece's scores can depend on the location of other pieces. Got too messy.. >It's impossible to arrange my code >such that I can test these in cascading order to take advantage >of lazy eval. Too many things depend on other things and I would >have to use too big a margin to fix it (which decreases its benefit.) >I end up doing almost all my evaluation to get to all the big scoring >things. > >Even with fudging I get little benefit (I used to get 30% in the >old days when life was simpler), now get very little, so I'm not >crying too much over the loss of it. YES I threw it out. I feel >this huge burden being lifted now and have found peace! I know >now that my scores are always correct and I don't lose any sleep >over it! I am looking into some ways to do really fast evaluation >and still keep it sophisticated and will share my discoveries (assuming >I come up with any) with the group. I'll probably reinvent someone >elses wheels! note that you *can* do lazy eval and be 100% accurate. I believe Bruce does the same thing that I did... maintaining a global "error" factor that is adjusted as pieces are removed thru captures or added thru promotions. But it gets *very* complicated if you have inter-piece interactions... > >Not to mention the way information is presented. I always liked >watching the move list proceed and with MTD(f) this is gone too >(unless you want to watch it over and over for each probe of each >iteration!) It's only a semantic issue but I prefer the normal >mini-max behavior. > >Anyway, all your points are well taken. MTD(f) is a strange beast >and I'm not really promoting it. If anyone wants to try it out >who hasn't yet, be prepared for a real struggle. I consider it >worth the problems and I believe it makes my program stronger. But >it's not hard for me to believe it could also be the wrong choice >for a different program. If your program relies heavily on score >fudging it will probably decrease your performance. > It took me quite a while to get this working correctly. There were lots of unexpected things. I agree that the "binary" driver looks intuitive but sucks with two straws. :) Hashing was another thing since we never get *EXACT* results any more, only fail-high or fail-low. The only thing I didn't try to do was to keep alpha/beta *above* the true score as long as possible as that is the most efficient tree to search. I'm going to look again one day. But the one thing I hated was no PV. I couldn't figure out how to debug bad moves or whatever because I had no idea *why* a move was played, only that it *was* played... Drove me crazy. > >- Don > >
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.