MTD(f) experiences

[Don]

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.

My scheme in Cilkchess was to gradually increase the movement, starting at 2 (I only used even scores), but if I kept getting failures in the same direction I incremented by ever increasing values. The amount of increment I believe was reset if a failure switched from upper to lower or visa versa.

I think this is a bit of a black art and would depend very much on your specific implementation and probably needs significant testing. The optimum algorithm may not necessarily be the fastest, but probably one that minimizes the effects of the worst case.

One thing is sure, this is different. There were some positions that take longer to search than PVS, however MOST positions were faster. The ones that took a long time to search were usually not a big problem for chess strength because it usually didn't prevent your program from playing the correct move. The "incrementing increments" pretty much solved this problem for me anyway.

There were some problems that mtd(f) solved dramatically faster than PVS too. I think PVS has it's pathological cases too, but we just don't notice them as much. You notice it with mtd(f) because you see many more researches that are painful to observe, but with normal alpha beta we are used to seeing the first move take a long time and don't realize that the process is similar - it's just sorting through a lot of garbage.

[hgm]

Another question, as I know you like variants: have you ever considered equiping Glaurung with a capability to play Knightmate? It is so boring for JokerKM to be 350 Elo above all its competitors.

Would be fun. In principle it could probably be done in a minute or two, simply by swapping the arrays used for attack generation for kings and knights. Making it play decently would also require some changes in the evaluation function, but it still wouldn't be a lot of work. The only real problem is that I would also need a Knightmate compatible version of PolyGlot. I'm not sure how hard that would be.

I am not really a Polyglot expert, but a quick glance at the source suggests that it would be sufficient to let move_is_legal() always return true. There seems no need for Polyglot to check the moves, if the engine is OK. The WB 'variant' command seems to be ignored anyway (if the variant is not 'fischerandom'). We could add a command UCI_Knightmate.

[bob]

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

How can you do that? Once you fail high on n-1, n, if you fail low there would be no way to get a score < N since your final search should be N, N+1. I did not have any instability problems since every search fails high or low and there is no such thing as an EXACT hash entry. I just couldn't get the trees small enough to make it worthwhile...

[bob]

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.

I tried a ton of ways to accelerate the thing, but it doesn't take many re-searches to pass the effort the normal PVS search expends, and that was where I could not make progress. I don't remember specifically now, but there was some number N that I needed to be below in terms of how many re-searches to "zero in" and unfortunately N was very small, which made it difficult to pull off.

[hgm]

How can you do that? Once you fail high on n-1, n, if you fail low there would be no way to get a score < N since your final search should be N, N+1.

With fail soft I do get scores < n, and they then represent upper bounds to the true score, which might be even lower.

[bob]

How can you do that? Once you fail high on n-1, n, if you fail low there would be no way to get a score < N since your final search should be N, N+1.

With fail soft I do get scores < n, and they then represent upper bounds to the true score, which might be even lower.

The only place those can come from are your evaluation procedure in mtd(f), so I don't see how this would be an issue unless you have a true random component in your evaluation...

[bob]

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

I don't know how you do it, I don't even have time for that.
Since GTA IV took all my time away from programming in the past weeks.

I'm still playing call of duty 4 (crafty48 on xbox live).

It can be addictive at times.

[hgm]

The only place those can come from are your evaluation procedure in mtd(f), so I don't see how this would be an issue unless you have a true random component in your evaluation...

Yes, scores come from evaluations in some end leaf. But I typically get such instabilities not because the evaluation is random, but because it is the evaluation of a totally different node that backs up to the root. E.g. because in the n-1,n search null moves were able to make you fail high, but compared to the window (n,n+1) the can't, and the score thus comes from a non-null branch, which is deeper, and runs into all kinds of disasters there.