hgm wrote:Well, I don't use PVS either. Prof. Hyatt told me once that many of the fail highs on a null window in a PV node are actually false fail highs, and disappear when you do a re-search.
But perhaps I am too pessimistic, and in realiity it might not happen often enough to wreck mtd(f), provided you do not trust the actual scores (bounds) returned by the searches. So if it says score >= bound > beta, you should only take it to mean score >= beta, and not score >= bound. Research with a window (bound, higerBeta) will often fail low in such a case.
This is true. Bruce Moreland and I played with this issue back around 1995-1996 or so. I had the following that could happen at the root:
1) normal search result, times runs out, play the move.
2.) aspiration window fail high, time runs out, play the move.
3.) null-window (not null-move) search fails high at root, time runs out, play the move. This would make an occasional horrible blunder. In pathological positoins _every_ move at the root would fail high on null-window search but not on a normal search. I finally decided that null-window fail highs at the root could not be trusted until the asipration search also failed high or got a real score back... And once I did that, all the oddball moves went away and things lived happily ever after..
My experience with it has been positive. I wonder if there is some implementation bug/issue that you ran across? My biggest problem came with stupid PV's but that was eventually ironed out.
There were some cases where a really high score took too long to converge, but I solved that with some minor modifications.
I'll let you know what I come up with, I will try it with my new program and let you know if I find any problems.
Did you get an improvement in search speed? I did every time and it's too much to ignore - unless there are truly bad pathological cases that cannot be easily handled.
Note that I am not talking about mtd(f) above, but normal PVS. If the null-window search fails high at the root, and I play this move, it often immediately fails low on the next search after my opponent moves, leaving me in a dead lost position. What caught my eye the most was that in some near-endgame or endgame positions, the null-window search would fail high and then fail low on the research, then the next null-window search would fail high and then low, right on down the line... We quit trusting this null-window fail-high without a real re-search confirmation, and the problem went away...
I could probably remove that exception today and find positions that are pathological if you are interested in seeing some...
I was planning to implement PVS in my engine soon, but after seeing your post, I decided to take another look at MTD(f). I think I had decided to use PVS instead of MTD because I understood it better, but I don't really remember; I made that decision quite a while back. Anyway, after looking at MTD again, it actually looks simpler to me than PVS . . . except for one aspect.
I didn't do too much searching, but the information I saw didn't really explain how to determine the current best move and the rest of the PV.
The most obvious method (assuming fail soft) seems to be to just use the same moves you store in (or retrieve from) the hash as PV moves, despite the fact that every node either fails high or fails low. Of course, I would never trust hash moves from failed nodes to be the best for other search algorithms. But with MTD(f) we always have a zero window, and, in the final iteration, either alpha or beta is always the actual value of the nodes along the PV. Does that fact make this method of getting the PV trustworthy? And if not, how is the best move usually found and is it possible, in that case, to get the PV beyond the first move?
It still seems to me that MTD(f) should be very good burrying its head in the sand in cases where there is distant trouble. To achieve a fail high (and create the illusion that the root move being searched is good) it will play a lot of null moves, reducing the depth so much that the trouble remains behind the horizon. This will work until you up the null window so much that even the short sequence of null-move replies can make your own sequence of null moves fail low. Then you are forced to play real moves in stead of null moves, decreasing the amount of reduction, and bringing the really lethal moves of the opponent within the horizon. With a disastrous fail low as a consequence.
What conclusion does MTD(f) draw when at alpha = +0.20 only one root move fails high, while all others fail low, but at alpha = +0.21 that same move fails low with an upper-bound score of -16.30? (And all other moves fail low too.) Does it play the move, assumiing that its score is +0.21?
If MTD(f) typically has null moves in all its branches (so that they are all reduced), I am not surprised that it seems faster than PVS. Was this comparison made by searching a set of test positions to the same nominal depth? Or was it determined at search depth where the tactical ability was the same?
I'm going to implement both PVS and NULL move so that I can compare them directly and I will be able to test them against each other too.
Generating the PV's was indeed a bit of a problem but it's been 10 years since I last did implemented mtd(f). This problem is solvable, but I don't recall the gory details. When I go to implement it, I know the details will come flooding back to my brain. I should have the old code archived somewhere, but I was unable to locate it the last time I looked, although I didn't try too hard.
The initial way I did it was to pick them out of the hash table, but I remember finding a better way later.
Maybe I should implement it sooner rather than later since there might be some interest and it never hurts to buddy up on things like this.
Something better than just picking them out of the hash table is to research each one separately and as a separate step. Let the hash table do the work for you. You already have the best move, so starting with it, apply the move, search for the second one, apply that, search for the third and so on, reducing the depth each time so that you are moving forward into the PV. You may (or may not) need to put the hash table in read only mode, experiment with that. I think these searches would be almost instantaneous since the PV is implicitly stored in the hash tables and this procedure will decode it.
That's not what I did because I think I would remember doing that. But I think this would work and it would be plenty fast.
kaustubh wrote:Don Dailey is MTD(f) the reason for your happy smiling face on your profile photo. Just joking.
Yes! I was much younger when this picture was taken, and I wanted to use my most flattering picture as my avatar!
You're not fooling anyone, buddy. That's obviously a picture of President George Bush.
Are you kidding? I am much better looking that George! Please don't tell anyone since it might bring shame to the family, but George is related to us. It's a dirty little secret we have tried to keep hidden, but there is no use in trying to deny it now, sooner or later the striking resemblance would give us away.
