I felt like implementing something for the first time in a while in Winter. The debugging page on CPW mentions implementing MTDf even if you intend to use PVS, so I did. Unfortunately the performance is absolutely terrible in Winter (several hundred elo weaker than my PVS implementation) and I am having trouble seeing how it could be anything but terrible, despite what many far more knowledgeable and capable engine authors have said about it. In other words I feel I am misunderstanding something horribly.
function MTDF(root : node_type; f : integer; d : integer) : integer;
g := f;
upperbound := +INFINITY;
lowerbound := -INFINITY;
repeat
if g == lowerbound then beta := g + 1 else beta := g;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;
until lowerbound >= upperbound;
return g;
If you are very close to the target eval this seems fine, but what if you missed a tactic, so you are not winning a pawn as previously expected. Then your initial guess will be around 100 centipawns too high. Unless I missed something that means it will now require 100 researches in order to correct the score in that case assuming centipawn granularity and even worse numbers assuming greater granularity? This seems absurdly expensive. What am I missing?
I implemented mtdf two or maybe three times. But it was always worse or at least not better than principal variation search.
Maybe because of Skippers fine grained evaluation function (ahum, hi hi hi). Maybe if new_eval computes 30 * ( old_eval() div 30 centi pawns) it gets equal results in speed.
Henk wrote: ↑Thu Jun 21, 2018 11:19 pm
I implemented mtdf two or maybe three times. But it was always worse or at least not better than principal variation search.
Maybe because of Skippers fine grained evaluation function (ahum, hi hi hi). Maybe if new_eval computes 30 * ( old_eval() div 30 centi pawns) it gets equal results in speed.
Hi Henk!
Maybe I am missing something but why would you want to divide and then multiply. That will just make your evaluation worse and will not speed up anything. To make it close in your example you would have to shift the null window by 30 as well in every step. Why not just divide by 30?
Whatever search technique you are using it seems smarter to use probabilistic scores both when it comes to widening windows as well as different pruning descions. Otherwise you would have to scale the evaluation prior to those decisions or have unlogical code.
Henk wrote: ↑Thu Jun 21, 2018 11:19 pm
I implemented mtdf two or maybe three times. But it was always worse or at least not better than principal variation search.
Maybe because of Skippers fine grained evaluation function (ahum, hi hi hi). Maybe if new_eval computes 30 * ( old_eval() div 30 centi pawns) it gets equal results in speed.
Hi Henk!
Maybe I am missing something but why would you want to divide and then multiply. That will just make your evaluation worse and will not speed up anything. To make it close in your example you would have to shift the null window by 30 as well in every step. Why not just divide by 30?
Whatever search technique you are using it seems smarter to use probabilistic scores both when it comes to widening windows as well as different pruning descions. Otherwise you would have to scale the evaluation prior to those decisions or have unlogical code.
Dividing eval by a number is only an attempt to get less evaluation states. The less states the faster MTDf searches. Quality of play may worsen though because of bad/coarse evaluation. I have no experience with using probabilistic scores and widening windows or I can't remember.
By the way I'm still busy with neural network approach. Or maybe you can train a neural network to predict lower and upper bound of next search window. Any decision making is possible with neural networks but usually training is too slow to be practical.
One is an evaluation that has a lot of terms and a wide scoring range, which makes it very difficult for MTD(f) to stabilize within a couple of tries, so that it becomes more expensive. The second is that the way you implement the convergence is also pretty important. I did an MTD(f) version years ago after Don D. kept bugging me to try it. However I could NEVER get it to work better than normal PVS. It was particularly nasty for me since I use alpha and beta to make all sorts of decisions, and you are constantly shifting the window around trying to find the best move. The more similar moves you have, the harder it becomes and if you are not real careful, you waste more time researching than you save by always doing a null-window search. The "easy" positions are easy since if you only have one move that fails high, you don't need to re-search unless you demand the true score. But most positions are not so easy and you don't reach that magic point until several shifts have occurred.
Plain old PVS had similar growing pains. I remember Ken vaguely mentioning an early version since his Belle hardware didn't give any PV moves or anything, and Murray Campbell mentioned the idea while we were talking. We sat down, I modified Cray Blitz to use PVS and could not find anything I didn't like compared to normal alpha/beta with an aspiration window that I was using. But multiple quirks did show up over time that required some thought, so it may well be that MTD(f) required more than the 3-4 months I invested. I might still have that old MTD(f) code around somewhere, not sure.