MTD(f) experiences

[Zach Wegner]

Hello H.G.,

I personally have not used MTD(f). But from what I understand it is very dangerous to make search decisions like null move pruning based upon the bound passed in the search. It is much safer to take the real upper and lower bound from the root and use those. Of course, these start out at the infinities (no point in using aspiration windows with MTD(f)), so no massively reduced null move lines where you wouldn't have the same in PVS.

[Don]

Hello H.G.,

I personally have not used MTD(f). But from what I understand it is very dangerous to make search decisions like null move pruning based upon the bound passed in the search. It is much safer to take the real upper and lower bound from the root and use those. Of course, these start out at the infinities (no point in using aspiration windows with MTD(f)), so no massively reduced null move lines where you wouldn't have the same in PVS.

I have never had an issue with this and my other mtd(f) programs always had null move pruning.

Why don't you consider that an issue with PVS with aspiration window? I don't understand why everyone wants to get as close to mtd(f) as they can with such tricks, but without actually using mtd(f). mtd(f) just takes all of this to it's logical conclusion.

I think I am just going to implement mtd(f) in the next few days and I will run this against the ECM problem suite using PVS and using MTD(f) and we will see what happens. But I put it to you that if mtd(f) is somehow incorrect, then so is any kind of aspiration searching.

By the way, if anyone is interested, mtd(f) actually does have a sense of an upper and lower bound, it's just not passed to the recursive search function. It could be made available to the search if anything thinks it's useful or interesting. And now that I'm thinking about it, it seems like I may have made use of this when fixing up the Principal Variation problem.

[Zach Wegner]

I have never had an issue with this and my other mtd(f) programs always had null move pruning.

Why don't you consider that an issue with PVS with aspiration window? I don't understand why everyone wants to get as close to mtd(f) as they can with such tricks, but without actually using mtd(f). mtd(f) just takes all of this to it's logical conclusion.

I think I am just going to implement mtd(f) in the next few days and I will run this against the ECM problem suite using PVS and using MTD(f) and we will see what happens. But I put it to you that if mtd(f) is somehow incorrect, then so is any kind of aspiration searching.

By the way, if anyone is interested, mtd(f) actually does have a sense of an upper and lower bound, it's just not passed to the recursive search function. It could be made available to the search if anything thinks it's useful or interesting. And now that I'm thinking about it, it seems like I may have made use of this when fixing up the Principal Variation problem.

I DO consider it an issue with aspiration windows. I don't use aspiration windows.

But anyway, all I was saying is that when you use null move with MTD(f), you shouldn't use the bound passed to the search, but rather the real bounds, the same bounds you are talking about in your last paragraph.

[Don]

I have never had an issue with this and my other mtd(f) programs always had null move pruning.

Why don't you consider that an issue with PVS with aspiration window? I don't understand why everyone wants to get as close to mtd(f) as they can with such tricks, but without actually using mtd(f). mtd(f) just takes all of this to it's logical conclusion.

I think I am just going to implement mtd(f) in the next few days and I will run this against the ECM problem suite using PVS and using MTD(f) and we will see what happens. But I put it to you that if mtd(f) is somehow incorrect, then so is any kind of aspiration searching.

By the way, if anyone is interested, mtd(f) actually does have a sense of an upper and lower bound, it's just not passed to the recursive search function. It could be made available to the search if anything thinks it's useful or interesting. And now that I'm thinking about it, it seems like I may have made use of this when fixing up the Principal Variation problem.

I DO consider it an issue with aspiration windows. I don't use aspiration windows.

But anyway, all I was saying is that when you use null move with MTD(f), you shouldn't use the bound passed to the search, but rather the real bounds, the same bounds you are talking about in your last paragraph.

Well mtd(f) is nothing but aspiration! I don't even like to use the term "window" when talking about mtd(f) because there is no window. I use the term "gamma" here because there is no alpha and beta.

Unless I'm missing something, I think you are being paranoid about the window behavior. If you do a zero width null move pruning search you will either see there is an attack, or you won't. But when you do it for next side, you will get the opposite result. If my position is good relative to the gamma point then my opponent is going to find it bad.

This was implemented in Cilkchess and it NEVER was an issue, I suspect you must have had some bad experience with it for some reason that probably wasn't what you think.

[Zach Wegner]

I have never used MTD(f), so I haven't had any problems with it. I know that it's just a series of aspiration windows, but you still have a real upper bound and a real lower bound at the root. Each test search you do will be somewhere in between there. All I am saying is:

Code: Select all

mtdf(int gamma)
{
    if (should_nullmove())
    {
        do_null_search(-gamma);
    }
    ...
}

...is not reliable, while:

Code: Select all

mtdf(int gamma)
{
    if (should_nullmove())
    {
        int bound = (ply & 1) ? -root_alpha : root_beta;
        do_null_search(-bound);
    }
    ...
}

...is.

[hgm]

Why don't you consider that an issue with PVS with aspiration window?

There is a big difference: with aspiration window (which I don't use either) you don't play moves with scores outside this window. If you get a fail low or high, you enlarge the window and re-search. And keep doing that until you get a score inside the window for the move you are going to play.

MTD(f) as I know it does not do that: it only uses null windows.

[Tord Romstad]

I am surprised that there do not appear to many programs that use mtd(f) and I wonder why.

I've used both MTD(f) and PVS: My first program used MTD(f), my two later programs used PVS. My opinion is that it is difficult to directly compare their efficiency, because you can't use exactly the same pruning techniques with both of them. It is likely that MTD(f) works a little bit better in a plain vanilla search with no other pruning than recursive null move, but hardly anyone use such a plain search in any case.

As one of the differences, consider futility pruning, which is used by most PVS programs. When the static eval is too far below alpha, prune all moves which have little chance of bringing the score up to alpha. In MTD(f), you can't do this, simply because there is no alpha or beta, but just a gamma, which is really nothing more than a guess of the value of the root. It is possible to use gamma for futility pruning, but it causes horrible search inconsistencies. What I did instead was to replace alpha and beta by the current bounds at the root in the futility pruning and for all other pruning and reduction tricks where I would have used alpha and beta in a PVS search. The problem with this is that at the beginning of a new iteration, there are no bounds at the root. I solved this problem by using an "aspiration window" around the root score from the previous iteration, and using this window until I had bounds from the new iteration at the root (thanks to Andrew Williams for this idea!). This worked reasonably well, but was slightly less efficient than using alpha and beta in PVS. The difference was almost exactly big enough to compensate for the initial advantage of using MTD(f) in a plain search.

My current opinion is that no algorithm is clearly better than the other -- they are just different. I think most people will be disappointed when they try to switch from one algorithm to the other, simply because they have collected a lot of tricks which works well with their old and familiar algorithm, but which are less efficient, cause inconsistencies or need non-trivial modifications when moving to the other algorithm.

The main reasons I currently use PVS is that I want my search to be efficient even with a tiny hash table, and that my parallel search seems less efficient with MTD (I have no idea why). I am glad I have tried both, though. It gives me a better understanding of search in general, and makes me a better chess programmer.

Tord

[hcyrano]

I implemented MTD(f) and aspiration PVS in my first othello program (applet java)

you can see result on this page :

http://hcyrano.free.fr/concepts/mtdf-pvs.html

of course with same heuristics.

i think is same

[Dann Corbit]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Without seeing an effective implementation, it gets left by the wayside.

[Tord Romstad]

I think that the problem is we have lots of examples of strong programs that use pvs with source code available and zero that use MTD(f).

Perhaps there is a need for an MTD version of Glaurung?

Sigh. So many things to do, so little time. Sometimes I envy all those programmers who are content with just writing a chess engine.

Tord