MTD(f) experiences

[Don]

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

I have never been able to get PVS or any flavor of aspiration searching to be as effective (as fast) as mtd(f) and wonder if I am missing something. I have implemented very good PVS searches in the past and have no trouble with it, but when I then implement mtd(f) I always get a general speedup and it's more than trivial.

And it's much simpler than PVS (although PVS is pretty simple too.) There is only 1 parameter instead of 2, the hash table can be simplified and I just don't understand why it's not popular.

I am wondering if it simply an issue of popularity and style. With mtd(f) you don't have the "classical" chess program behavior of looping though a move list in a single pass and perhaps this puts some people off? But not using mtd(f) for that reason seems like a big sacrifice to make, just for the sake of imitating all the other programs.

What popular or strong programs use mtd(f) now?

[hgm]

I thought that search instability kills the whole idea. All searches fail one way or the other, and thus can be full of null moves, reducing the depth to almost nothing. The fact that a search fails high on a null window (alpha, alpha+1) doe not mean that the score is above alpha in a large-enough fraction of the cases to be a meaningful finding.

[Don]

I thought that search instability kills the whole idea. All searches fail one way or the other, and thus can be full of null moves, reducing the depth to almost nothing. The fact that a search fails high on a null window (alpha, alpha+1) doe not mean that the score is above alpha in a large-enough fraction of the cases to be a meaningful finding.

Is that the general consensus?

If that's true, then PVS would be bad and it would be even worse with aspiration, but that is apparently what is popular.

All my programs that have done mtd(f) used null move pruning and I never saw any problems. But it seems that if nobody, or very few are using it, there must be a problem with it and I'm trying to figure out what it is.

I may have to explore this based on what you are claiming here.

[hgm]

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.

[bob]

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

I have never been able to get PVS or any flavor of aspiration searching to be as effective (as fast) as mtd(f) and wonder if I am missing something. I have implemented very good PVS searches in the past and have no trouble with it, but when I then implement mtd(f) I always get a general speedup and it's more than trivial.

And it's much simpler than PVS (although PVS is pretty simple too.) There is only 1 parameter instead of 2, the hash table can be simplified and I just don't understand why it's not popular.

I am wondering if it simply an issue of popularity and style. With mtd(f) you don't have the "classical" chess program behavior of looping though a move list in a single pass and perhaps this puts some people off? But not using mtd(f) for that reason seems like a big sacrifice to make, just for the sake of imitating all the other programs.

What popular or strong programs use mtd(f) now?

I played with it a few years back and reported on the results. With my evaluation, which changes significantly from iteration to iteration, I found mtd(f) was overall significantly slower because of the extra re-searches needed to zero in on the true score for a particular iteration. I even did the hash table modification as well to store two bounds so that when I cross over the true score, as I zero in, searches on both sides of the true score will get useful hash information...

But nothing made it work better than my normal PVS search...

[Gerd Isenberg]

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

I have never been able to get PVS or any flavor of aspiration searching to be as effective (as fast) as mtd(f) and wonder if I am missing something. I have implemented very good PVS searches in the past and have no trouble with it, but when I then implement mtd(f) I always get a general speedup and it's more than trivial.

And it's much simpler than PVS (although PVS is pretty simple too.) There is only 1 parameter instead of 2, the hash table can be simplified and I just don't understand why it's not popular.

I am wondering if it simply an issue of popularity and style. With mtd(f) you don't have the "classical" chess program behavior of looping though a move list in a single pass and perhaps this puts some people off? But not using mtd(f) for that reason seems like a big sacrifice to make, just for the sake of imitating all the other programs.

What popular or strong programs use mtd(f) now?

On several occasions Vincent Diepeveen had big discussions with Rudolf Huber, who's engines SOS and ParSOS rely on mtd(f). Vincent claims bad worst case behavior in root fail low situations of mtd(f) and advocates for PVS even without aspiration windows. Maybe that made other programmers lazy to try it.

[bob]

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..

[Don]

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.

[Pradu]

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

I have not done extensive testing with MTD; however, can you post your program's analysis (with MTD) on this position:
[D]8/8/8/8/2k5/1p6/8/1K6 b - - 0 1
It needs to find the draw through search only so you might want to turn off just your recognizers or egtbs/egbbs. Here's are the final PVs from SOS v51 (an MTD engine IIRC).

Code: Select all

 99	+2.31	4.9M	0:03.84	Kb4 Kb2 Kc4 Kb1
 98	+2.31	4.8M	0:03.77	Kb4 Kb2 Kc4 Kb1
 97	+2.31	4.7M	0:03.70	Kb4 Kb2 Kc4 Kb1
 96	+2.31	4.6M	0:03.64	Kb4 Kb2 Kc4 Kb1

My MTD version of Buzz (may have been broken implementation--I didn't check rigorously) from a long time back gave a similar result (I don't have this version anymore).

[Don]

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

I have not done extensive testing on MTD; however, can you post your program's analysis (with MTD(f)) on this position:
[D]8/8/8/8/2k5/1p6/8/1K6 b - - 0 1
It needs to find the draw through search only so you might want to turn off just your recognizers or egtbs/egbbs. Here's are the final PVs from SOS (an MTD engine IIRC).

Code: Select all

 99	+2.31	4.9M	0:03.84	Kb4 Kb2 Kc4 Kb1
 98	+2.31	4.8M	0:03.77	Kb4 Kb2 Kc4 Kb1
 97	+2.31	4.7M	0:03.70	Kb4 Kb2 Kc4 Kb1
 96	+2.31	4.6M	0:03.64	Kb4 Kb2 Kc4 Kb1

My MTD(f) version of Buzz (may have been broken implementation--I didn't check rigorously) from a long time back gave a similar result (I don't have this version anymore).

Whatever that is, it isn't an mtd(f) issue. There is nothing about mtd(f) that is incorrect.

If you are not used to mtd(f) it can be tricky and buggy. It's conceptually cleaner and simpler than PVS, but if you "grew up" on PVS it could have a surprise or two.

I usually start by adjusting my program to only have even scores and then I use odd scores to represent the zero width window (instead of two scores.) No score will ever be returned that is equal to this value and it just seems slightly easier to think about this way.

I don't have a program to try this on yet (unless I dig out some very old programs I have written many years ago, and I'm not even sure I know where they are.)

The one I am working on now I just started a few days ago. I just finally implemented and debugged hash table today which is a prerequisite for mdt(f). I feel like I just now have a real program in the sense that it is complete (knows all the legal moves, has null move selectivity and hash tables, passes perft tests, recognized draws by rep and stalemates, has a primitive evaluation of sorts - mostly mobility, UCI works and you can play real games with it.)

I ran your problem anyway, though, but not with mtd(f), and it sees the draw at depth 10. I have not hooked up my kpk database yet of course or it would see it on any depth.

I will try that position when I have mtd(f) working, but it's not very high up in my todo list yet.