MTD(f) experiences

[Zach Wegner]

I probably won't. I could probably make a simple MTD version without much time and effort, but it would be much weaker than the normal version, and people would too easily conclude that MTD isn't good. Writing an MTD version of comparable strength to the PVS version would be a big task, and my time is probably better spent doing other things.

Definitely.

Go is unlikely, at least in the near future. It's a great game, but I can't stand watching the ugly games played by the current generation of go programs (and my own program would of course be far worse, especially in the beginning). Shogi is more attractive from this point of view, but it's a pity that there isn't much of a shogi programming community outside Japan.

If it was a few years ago, I'd agree with you about Go, as the algorithms were horrible and relied on tons of patterns, etc. But the recent MC craze is much more elegant to me. It's like emergence, knowledge resulting from the application of simple rules. I can't really judge whether their play is ugly or not, because I am terrible at Go.

In the nearest future, I'll have to concentrate on completing my chess evaluation function with space and development, adding bitbases, improve my GUI, and finish the iPhone port of Glaurung. Maybe I'll give shogi a try after that.

I'd say, forget bitbases. The other stuff is good though. If you want to try shogi though (or Go), I'll join you. I just need to (don't laugh) learn the pieces.

What's your Summer of Code project about?

It's rewriting the installer for NetBSD. I have some information on this site: http://netbsd-soc.sourceforge.net/proje ... tall-tool/

The project basically boils down into making a configuration file format that describes an installation (what kernel, what sets, what language, partition information, etc.). I'm building up a parser library around that, and then separating the current installer into a front end and back end that use the library. So you can hand edit the file, or create it on another system, and then just stick it on a computer and wait for it to install.

Too embarrassing, and it wouldn't be useful to the community. It is too ugly and messy to be understandable, and not sufficiently strong to prove that MTD(f) is competitive.

Haha, understood. It was worth a shot though.

[bob]

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.

mtd(f) is essentially an aspiration search where the aspiration window is always null. In that regard it is exactly the same except that it guarantees you at least 2 searches where normal aspiration might only need one.

[hgm]

If you can trust only scores that are inside the window, I would say that makes them essentially different , rather than essentially the same.

Never getting a score you can trust, in stead of always, seems of some relevance...

[hcyrano]

mtd(f) is essentially an aspiration search where the aspiration window is always null. In that regard it is exactly the same except that it guarantees you at least 2 searches where normal aspiration might only need one.

right, same analyse

[Bo Persson]

I always liked the search variant called {IIRC} C-Star, which uses mtd(f) like probing, but in a binary search rather than a linear search. There is something very appealing to me about that method.

I thought that's what MTD(f) did? At least, when I was thinking about MTD(f), I would've done it that way.

Here was another thing I thought of doing, in case anyone else hadn't thought of it:
When doing the probes, use MTD(f) to get a score for only the first move, instead of searching all moves when the others will likely fail. Then the rest of the root node becomes like PVS.

MTD(f) does a linear search. I would guess that a good hash implementation would be essential, because the initial guess must be excellent for the method to prevail.

It doesn't have to be linear, you can accelerate the step if you start far from the final score.

Inspired by Don Daily (no less , I move gamma 0.16 pawns in the proper direction after the first probe. Then step 0.32, 0.64, etc points until passing over the score (fail high/fail low condition changes).

Knowing that we are now closer, I use step/=2 for each additional iteration, altering the direction if fail high/fail low changes again.


Most of the time, this zooms in on the final score pretty fast.

Except when it doesn't.

[bob]

If you can trust only scores that are inside the window, I would say that makes them essentially different , rather than essentially the same.

Never getting a score you can trust, in stead of always, seems of some relevance...

You do get a score you can trust, so I don't understand what you mean. If your n-1, n search fails high, and your n, n+1 search fails low, you know the exact score is n... And that is how you end an mtd(f) search...

Also note that the original PVS algorithm was done by Ken Thompson and he often got a single fail high after searching the first root move, and he did not do a re-search unless he got a second fail-high, which required a re-search to "break the tie"... I occasionally end a search on time with nothing more than a fail-high indication which doesn't seem to be a problem...

[bob]

mtd(f) is essentially an aspiration search where the aspiration window is always null. In that regard it is exactly the same except that it guarantees you at least 2 searches where normal aspiration might only need one.

right, same analyse

The only thing I could never do when I worked with it was consistently get smaller trees (sum of nodes searched) compared to PVS. Overall, for me, PVS searched a smaller number of nodes for the same depth... results were not different in any significant way other than that. Implementation details were _significantly_ different however.

[hgm]

If your n-1, n search fails high, and your n, n+1 search fails low, you know the exact score is n... And that is how you end an mtd(f) search...

I thought the whole point (originally raised by you) was that a score that fails high on a null window (alpha, alpha+1) cannot be trusted to score above alpha on a larger window (alpha, beta).

So the fact that (n-1,n) fails high, and (n,n+1) fails low, might very well mean that the score<<n-1.

BTW, no one seems to have answered my question how an MTD(f) implementation should handle the case where you fail high on (n-1,n), and fail low on (n,n+1) with upper-bound score n-800. Do you assume the score is n, or do you assume it is n-800?

[bob]

If your n-1, n search fails high, and your n, n+1 search fails low, you know the exact score is n... And that is how you end an mtd(f) search...

I thought the whole point (originally raised by you) was that a score that fails high on a null window (alpha, alpha+1) cannot be trusted to score above alpha on a larger window (alpha, beta).

So the fact that (n-1,n) fails high, and (n,n+1) fails low, might very well mean that the score<<n-1.

BTW, no one seems to have answered my question how an MTD(f) implementation should handle the case where you fail high on (n-1,n), and fail low on (n,n+1) with upper-bound score n-800. Do you assume the score is n, or do you assume it is n-800?

I was talking about the PVS framework, and yes, a fail high at the root on a null-window caused problems, but when I did mtd(f) experiments I did not notice this as much, probably because one uses a different hash implementation that stores two bounds so the fail high searches do not clobber fail-low results in case you step over the true score while trying to zero in...

mtd(f) tries to establish tighter and tighter upper/lower bounds. You make a good guess for the lower bound and search and hopefully fail high which means your guess was good. Now you make a good guess on the upper bound and search and hopefully fail low. Now you start to "narrow the window" until you get it down to zero where you are right on top of the real score.

If you fail high on n-1, n, then you proved the score is >= n. If you fail low on n, n+1, you proved the score is <= n. In the above case, you just proved that the score is exactly n and you are done.

There are interesting issues. Fail lows are more efficient than fail highs at the root, as only one ply-2 move is enough to make a root move fail low. So you want to stay below the score rather than stepping over it, until hopefully the last pass (this is nearly impossible to do, but a worthwhile goal)... A single mtd(f) pass is very efficient. But you can't ever do just one for an iteration, and therein lies the rub with me, I could not get mtd(f) to produce smaller trees than PVS, they were larger most of the time, which meant PVS was more efficient. I chose to stick with it. A well-done PVS with good aspiration ought to be just as efficient as mtd(f) or better... Unless you can find a way to reliably complete an iteration in 2-3 passes, which I could not do...

[hgm]

If you fail high on n-1, n, then you proved the score is >= n. If you fail low on n, n+1, you proved the score is <= n. In the above case, you just proved that the score is exactly n and you are done.

Well, this is exactly my concern, If I fail low on n, n+1 with a score upper-bound n-200, what exactly did I prove? Seems to me I only proved that something is very wrong. Or do people that use MTD(f) hide such search instabilities from view by always using fail hard?

Anyway, it seems to me that the 'proof' that the score is >= n with an (n-1,n) window and that it is <= n with an (n, n+1) window is a lot more shakey than a proof returning an n score from an (n-1, n+1) window. The latter cannot have used any null moves in its PV, and thus must have searched at least one branch to the nominbal depth. The two null-window searches could have used an arbitrary number of null moves in any branch, leading to a reduced search everywhare. So it is a bit like accepting the score of an early iteration as 'proof' for the score of a later iteration. Which of course would save a lot of time. But alas, no better play...