What am I missing with respect to MTDf

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
jorose
Posts: 267
Joined: Thu Jan 22, 2015 2:21 pm
Location: Zurich, Switzerland
Full name: Jonathan Rosenthal

What am I missing with respect to MTDf

Post by jorose » Thu Jun 21, 2018 1:28 pm

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.

The CPW gives the following pseudocode for MTDf:

Code: Select all

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?
-Jonathan

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: What am I missing with respect to MTDf

Post by AlvaroBegue » Thu Jun 21, 2018 1:48 pm

Disclaimer: I have never implemented MTD(f) myself.

I suspect a fail-soft alpha-beta implementation could be very important here.

The details of your hash table also matter: You may want to try storing an upper bound and a lower bound, each with its own depth.

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: What am I missing with respect to MTDf

Post by Pio » Thu Jun 21, 2018 5:33 pm

Hi, you can look at following post viewtopic.php?t=53388for an idea of how to speed up convergence.

If you want to speed it up more you can use probabilistic scores that are not as fine grained.

BR
Pio

Henk
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: What am I missing with respect to MTDf

Post by Henk » Thu Jun 21, 2018 9: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.

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: What am I missing with respect to MTDf

Post by Pio » Thu Jun 21, 2018 10:11 pm

Henk wrote:
Thu Jun 21, 2018 9: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
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: What am I missing with respect to MTDf

Post by Henk » Fri Jun 22, 2018 8:02 am

Pio wrote:
Thu Jun 21, 2018 10:11 pm
Henk wrote:
Thu Jun 21, 2018 9: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.

bob
Posts: 20547
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: What am I missing with respect to MTDf

Post by bob » Mon Jul 02, 2018 7:40 pm

I think you probably have a couple of issues.

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.

Post Reply