An Idea Of speeding up MTD-f

[Pio]

Hi!

I have looked at the MTDF algorithm and wondered if it would not be feasible to modify it to be a little bit more efficient. I am probably wrong since if it is possible to do what I am proposing, I think it would already have been done (or maybe it has been).

The original MTDF-algorithm looks like this in pseudo-pascal-code (see http://people.csail.mit.edu/plaat/mtdf.html)

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;



What I had in mind was to introduce a new variable delta in the mtdf function that you multiply with two for every second pass you either guessed too high both times or guessed too low both times. In the same way delta would be divided by two whenever the guess changed from either too high -> too low or from too low -> too high.

Assume for example that we have initial guess of 0 but actually the true value was 100. Then the idea is that beta will go from 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 96 -> 112 -> 104 -> 100 thus we will only need to pass AlphaBetaWithMemory Ordo(lg(|guessValue - trueValue|)) number of times instead of the original Ordo(|guessValue - trueValue|) number of times.

I think the code might look something like this (but probably I am totally wrong)


function MTDF(root : node_type; f : integer; d : integer) : integer;
delta := 2;
wasPreviousBoundUpper := false;
wasPreviousBoundLower := false;
g := f;
upperbound := +INFINITY;
lowerbound := -INFINITY;
repeat
if g == lowerbound then
if wasPreviousBoundLower then
delta := delta * 2;
else
delta := delta / 2;
beta := g + delta - 1;
wasPreviousBoundUpper := false;
wasPreviousBoundLower := true;
else
if wasPreviousBoundUpper then
delta := delta * 2;
else
delta := delta / 2;
beta := g - delta + 1;
wasPreviousBoundUpper := true;
wasPreviousBoundLower := false;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;
until lowerbound >= upperbound;
return g;


The idea is that the algorithm will be more stable, less prune to bad convergence for fine grained evaluation functions and have less worst case convergence rate.

Good luck with your engines!!!

[Henk]

Yes, idea is not new. Tord already talked about it years ago.

I also experimented with it. It just resembles a binary search.

[Ajedrecista]

Hello Pio:

I am not a programmer and I think I do not fully understand how MTD(f) works (at least I understood your numeric example of 0 and 100), but a doubt comes to me: why delta = 2? Can it have other values? There is probably a value that can work better in average (i.e. many positions) and therefore can be tuned, although the gain could be worthless in comparison with the final gain in speed.

Sorry if my questions sounds stupid. Thanks in advance.

Regards from Spain.

Ajedrecista.

[Pio]

Hola Jesús!

Maybe I wrote it in a wrong way. I wanted delta to become one in the first pass and I think it will be.

I have read more or less all your posts and always like what I read. I guess you are a physicist since your math skills are very good and since you use Fortran.

Actually I had no idea if my code would work since I have never implemented it.

I think your idea is very smart. I think you probably could extrapolate a better guess when going/searching to the next depth. I also guess that when you are ahead a little bit maybe 0.7 pawns it will be wise to guess that you will increase the gain even further and when you are maybe only 0.2 pawns ahead that it will even out. I think the gain is not so big with the refinement I suggested but would be a big win when doing MTDF in its original state especially if you could use statistics about even/odd-effects.

Hasta luego!

[bob]

Hi!

I have looked at the MTDF algorithm and wondered if it would not be feasible to modify it to be a little bit more efficient. I am probably wrong since if it is possible to do what I am proposing, I think it would already have been done (or maybe it has been).

The original MTDF-algorithm looks like this in pseudo-pascal-code (see http://people.csail.mit.edu/plaat/mtdf.html)

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;



What I had in mind was to introduce a new variable delta in the mtdf function that you multiply with two for every second pass you either guessed too high both times or guessed too low both times. In the same way delta would be divided by two whenever the guess changed from either too high -> too low or from too low -> too high.

Assume for example that we have initial guess of 0 but actually the true value was 100. Then the idea is that beta will go from 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 96 -> 112 -> 104 -> 100 thus we will only need to pass AlphaBetaWithMemory Ordo(lg(|guessValue - trueValue|)) number of times instead of the original Ordo(|guessValue - trueValue|) number of times.

I think the code might look something like this (but probably I am totally wrong)


function MTDF(root : node_type; f : integer; d : integer) : integer;
delta := 2;
wasPreviousBoundUpper := false;
wasPreviousBoundLower := false;
g := f;
upperbound := +INFINITY;
lowerbound := -INFINITY;
repeat
if g == lowerbound then
if wasPreviousBoundLower then
delta := delta * 2;
else
delta := delta / 2;
beta := g + delta - 1;
wasPreviousBoundUpper := false;
wasPreviousBoundLower := true;
else
if wasPreviousBoundUpper then
delta := delta * 2;
else
delta := delta / 2;
beta := g - delta + 1;
wasPreviousBoundUpper := true;
wasPreviousBoundLower := false;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;
until lowerbound >= upperbound;
return g;


The idea is that the algorithm will be more stable, less prune to bad convergence for fine grained evaluation functions and have less worst case convergence rate.

Good luck with your engines!!!

Nothing new there. There were SEVERAL attempts to produce faster convergence on the mtdf() searches. But in reality, once you go past the second re-search, you are now passing the number of nodes required to resolve a normal PVS-like search.

I still have an old mtd(f) version of Crafty or two (I did it twice, once back around 12x./13.x when Don Dailey was after everyone to give it a shot, and then somewhere back around 20.0 when the topic came up again. My own personal conclusion was that it will not work well with reductions and forward pruning and an evaluation that produces a fairly wide range of scores. The wider the band of scores you can get for a given position, the harder it is to reach convergence without going to a significant number of re-searches which quickly loses any advantage the null-window searches provide. I went so far as to do a material-only search, and mtd(f) actually looked pretty solid there, although you might guess the program didn't play very well. But you could generally converge with 2 searches, one on X, X+1, the next on X-1, X where you found you now have the real score, X. And if you use fail-soft, on those positions where you can win material, the fail-soft value gives you a GOOD lead on the next search window, so that you can almost worst-case 3 searches to zero in if you fail high or low due to material loss/gain. But when you add in positional scores, look out. And when move ordering changes each time you re-search, you search a different tree since later moves are reduced more, and that further skews the scores and adds to the re-searches.

Good luck on getting it to work. BTW at least one common approach was to keep doubling the offset on the re-searches, assuming no fail-soft to give you a hint on how far to move the window. If you have fail-soft, you don't need that +1, +2, +4 stuff, the score you get back should be the next starting point since it can lie outside the alpha/beta window with fail-soft, giving you a decent hint of how far you have to move the window. But by the 3rd search or so, you are into a losing proposition.

[Pio]

Hi Bob!

Actually I have no intention to implement the algorithm myself. I just thought maybe it would work and would help people who already used MTDF.

I will use a probabilistic search algorithm I have invented, that will be a lot worse but will have the benefit of fixing a sort of lmr stuff by itself and also will give you information about uncertainties for the positions. I think it is more fun to do something new that is bad than copy something good.

One thing that I really think could work in Crafty or other existing engines is my idea about simplification extension that I wrote in another thread.

/Pio

[bob]

Hi Bob!

Actually I have no intention to implement the algorithm myself. I just thought maybe it would work and would help people who already used MTDF.

I will use a probabilistic search algorithm I have invented, that will be a lot worse but will have the benefit of fixing a sort of lmr stuff by itself and also will give you information about uncertainties for the positions. I think it is more fun to do something new that is bad than copy something good.

One thing that I really think could work in Crafty or other existing engines is my idea about simplification extension that I wrote in another thread.

/Pio

Just for completeness, have you read the "conspiracy numbers search" paper???

[bob]

Hi Bob!

Actually I have no intention to implement the algorithm myself. I just thought maybe it would work and would help people who already used MTDF.

I will use a probabilistic search algorithm I have invented, that will be a lot worse but will have the benefit of fixing a sort of lmr stuff by itself and also will give you information about uncertainties for the positions. I think it is more fun to do something new that is bad than copy something good.

One thing that I really think could work in Crafty or other existing engines is my idea about simplification extension that I wrote in another thread.

/Pio

can you give me a link to your idea, or at least the name of the thread???

[Ajedrecista]

Hello again:

Hola Jesús!

Maybe I wrote it in a wrong way. I wanted delta to become one in the first pass and I think it will be.

I have read more or less all your posts and always like what I read. I guess you are a physicist since your math skills are very good and since you use Fortran.

Actually I had no idea if my code would work since I have never implemented it.

I think your idea is very smart. I think you probably could extrapolate a better guess when going/searching to the next depth. I also guess that when you are ahead a little bit maybe 0.7 pawns it will be wise to guess that you will increase the gain even further and when you are maybe only 0.2 pawns ahead that it will even out. I think the gain is not so big with the refinement I suggested but would be a big win when doing MTDF in its original state especially if you could use statistics about even/odd-effects.

Hasta luego!

Glad to see that you like my posts. I do what I can. I am an engineer student and not a physicist; I use Fortran 90/95 since it is the only (?!) programming language teached where I study and I know only the basics.

I find your posts very theorical and probably somewhat difficult to implement sometimes... but I am not a programmer, so my opinion is biased. Keep your path and you will come with a good idea.

Regards from Spain.

Ajedrecista.

[Pio]

Hi Bob!

The thread is http://www.talkchess.com/forum/viewtopi ... ht=#452797

The most relevant post for crafty is this post I guess.

Hi all of you!

I am comming back with a faster but a less accurate simplification extension idea. Of course my idea might not work but I think and hope it can make a difference since the additional computational cost is a constant and the gain in search tree exponential. I guess therfore if you want to see any gains of my idea you would have to test the idea on different time controls and then extrapolate the result to longer time controls to see if it might be a gain.

If you think it is to expensive counting the number of opponents moves you could do an approximation by counting the opponents average mobility based on the opponents pieces instead.

For example you could count the average mobility for the pieces maybe as averagePawnMobility = 1, averageKnightMobility = 6, averageBishopMobility = 7, averageRookMobility = 9, averageQueenMobility = averageBishopMobility + averageRookMobility = 16 and averageKingMobility = 4 and finally take the logarithm of the sum of the opponents averageMobilities multiplied with some constant multiplied with the depth you usually would consider your move as. You could precalculate the logarithms and put them in an array and the averageMobility could easily be incrementally updated when moving or undoing a move.

The benifit of this type of reduction/extension it is that you will look deeper into lines where you simplify the game by removing pieces and thus more easily could see if a move is good or not.

If you want to improve the idea even more you could use two types of averageMobilityValues depending on the game stage and then interpolating between opening (give bonus to knights) and endgame (give bonus to bishops, rooks, queens and king) and then round the value to use the precalculated logarithms.

Good luck with your engines!!!