MTDF - what am I doing wrong?

[jauska]

Hi, I'm having some problems with MTDF and I was hoping someone could help. It's probably just one character in one line that I've got wrong but you know how it is sometimes when you're staring at your own code for hours, and the bugs start to blend in.

Anyway, I have a fairly straightforward alpha-beta algorithm with quiescence, null move pruning and transposition table lookups. It works perfectly fine, as far as I can tell, and is even reasonably fast now. I'm currently trying to wrap it in MTDF so I can do iterative deepening, but it's giving me weird results.

Using this test position: "rn1qkb1r/ppp1pppp/8/3p2B1/3Pn1b1/4PN1P/PPP2PP1/RN1QKB1R b KQkq - 0 5". It's just a simple tactic, the correct move is Bxf3 with +3 or so eval (for the moving side).

My code:

If I run findBestMove(position, depth = 4), I get this result:

Code: Select all

298480 nodes searched in 2.07s (143984.56 NPS) [cutoffs: 36657, qNodes: 148633, nullCutoffs: 20829, tpLookups: 25725]
[[Bxf3, 270], [Bh5, -4], [Bf5, -16], [Nxg5, -23], [Bd7, -26], [Be6, -30], [Bc8, -47], [f6, -50], [Qc8, -73], [Nxf2, -234], [f5, -246], [Bxh3, -249], [Qd7, -278], [Qd6, -282], [Nc6, -297], [Nf6, -305], [Nd7, -310], [c5, -320], [a6, -323], [h6, -328], [c6, -330], [h5, -332], [Nd6, -343], [g6, -347], [a5, -358], [Ng3, -361], [Rg8, -362], [Na6, -366], [Nd2, -367], [b6, -369], [b5, -386], [Nc3, -392], [Nc5, -394], [Kd7, -394], [e5, -769], [e6, -785]]
[Bxf3, 270]

which is basically correct

If I run mtdf(position, 0, depth = 4), I get:

Code: Select all

MTDF pass 1
20766 nodes searched in 0.22s (93540.54 NPS) [cutoffs: 2584, qNodes: 9347, nullCutoffs: 1459, tpLookups: 1532]
[[Bxf3, 1], [c6, 0], [Nxf2, 0], [Bxh3, 0], [e5, 0], [Nc6, 0], [Ng3, 0], [e6, 0], [Nd7, 0], [c5, 0], [f5, 0], [Nxg5, 0], [f6, 0], [h6, 0], [a6, 0], [h5, 0], [Na6, 0], [a5, 0], [Qd6, 0], [Bf5, 0], [Rg8, 0], [b6, 0], [g6, 0], [Nd2, 0], [b5, 0], [Qd7, 0], [Be6, 0], [Bh5, 0], [Bd7, 0], [Nd6, 0], [Nf6, 0], [Qc8, 0], [Bc8, 0], [Nc3, 0], [Kd7, 0], [Nc5, 0]]
MTDF pass 2

8498 nodes searched in 0.05s (163423.08 NPS) [cutoffs: 437, qNodes: 2738, nullCutoffs: 823, tpLookups: 8401]
[[Bxf3, 1], [c6, -2], [Nxf2, -2], [Bxh3, -2], [e5, -2], [Nc6, -2], [Ng3, -2], [e6, -2], [Nd7, -2], [c5, -2], [f5, -2], [Nxg5, -2], [f6, -2], [h6, -2], [a6, -2], [h5, -2], [Na6, -2], [a5, -2], [Qd6, -2], [Bf5, -2], [Rg8, -2], [b6, -2], [g6, -2], [Nd2, -2], [b5, -2], [Qd7, -2], [Be6, -2], [Bh5, -2], [Bd7, -2], [Nd6, -2], [Nf6, -2], [Qc8, -2], [Bc8, -2], [Nc3, -2], [Kd7, -2], [Nc5, -2]]

[Bxf3, 1]

Although I get the right move, the scores of all the moves are obviously wrong. Whatever position I put in, I get the same sort of thing happening - only ever 2 MTDF passes, and a load of scores within 3 points of each other. The problem seems to be in giving my findBestMove function a window other than [-inf, inf], but it's all just "book" code as far as I can tell, so I can't figure out what's wrong.

My evaluation functions are all fine and everything works fine until I use mtdf.

Thanks in advance, sorry for the wall of text

[Dann Corbit]

Can you post also a header so I can compile it?
I would use some compilers like lint.

[Dann Corbit]

p.s.
What is dart?
It looks like C or C++ to me.

[jauska]

Dart is a newish google language that mostly goes with flutter (cross platform mobile sdk). It's pretty nice! Basically it's not much different to java with a bit of syntactical sugar.

There's lots more code and meta-things you would need to compile it, I didn't post everything because I didn't want to overcomplicate things and I doubted anyone else would be using dart here anyway.

I think I'm just misunderstanding how MTDF works somehow. Am I supposed to get move ratings back from it or is it normal that it just returns one move above threshold and the others below?

[Dann Corbit]

MTD(f) is a quirky bird.
It approaches the true value like an inchworm.
I have always had something of a distaste for it.
Now C* search, on the other hand, is a sort of binary search which takes alpha and beta and used the midpoint.
To me, it seems a lot more logical and scientific.
I believe Diep used MTD(f) for a while and another fairly strong program whose name escapes me right now {either the program or author started with the letter 'A', but it has been a while and I cannot even remember which}.
But most experiments with MDT(f) seem to end in frustration.
I think it is one of those things that sound great theoretically, but in practical terms do not quite deliver on the promise.

Some things that MTD(f) implementations have to fiddle with of importance are the resolution of the steps. Big mistake, for instance to use a double because you will never narrow down far enough. The size of each step towards the goal is another fiddly thing. The starting and ending point are another.

You are not going to find a lot of successful MTD(f) implementations because there aren't many (any?)

But I am not asking you to abandon it. You might be the first one to make a big bang with it, and then everyone else will follow suit.

[Tord]

I believe Diep used MTD(f) for a while and another fairly strong program whose name escapes me right now {either the program or author started with the letter 'A', but it has been a while and I cannot even remember which}.

Probably AnMon (Christian Barreteau). SOS (Rudolf Huber) and PostModernist (Andrew Williams) are two other notable examples. Don Dailey also used MTD for a while (I can't remember what name he used for his engine at the time), as did I.

But most experiments with MDT(f) seem to end in frustration.
I think it is one of those things that sound great theoretically, but in practical terms do not quite deliver on the promise.

I thought it was a great educational experience to play with MTD. Because it is relatively unusual, it forces you to think more. You can't just copy many search tricks used in mainstream chess engines, you have to think carefully about how they work and understand them perfectly in order to figure out how to best adapt them to MTD search. I think this has greatly improved my general understanding of computer chess.

[Gerd Isenberg]

I believe Diep used MTD(f) for a while and another fairly strong program whose name escapes me right now {either the program or author started with the letter 'A', but it has been a while and I cannot even remember which}.

Probably AnMon (Christian Barreteau). SOS (Rudolf Huber) and PostModernist (Andrew Williams) are two other notable examples. Don Dailey also used MTD for a while (I can't remember what name he used for his engine at the time), as did I.

I guess it was CilkChess by Leiserson, Dailey et al. and Plaat also listed as co-autor:
https://www.game-ai-forum.org/icga-tour ... .php?id=56

KnightCap was MTD(f) as well.

[Dann Corbit]

The one I was thinking of was PostModernist by Andrew Williams.

[duncan]

Probably AnMon (Christian Barreteau). SOS (Rudolf Huber) and PostModernist (Andrew Williams) are two other notable examples. Don Dailey also used MTD for a while

If you want to know if there is any forced material capture in the first N moves is Mtd the quickest way to find out.?

[Mike Sherwin]

MTD(f) is a quirky bird.
It approaches the true value like an inchworm.
I have always had something of a distaste for it.
Now C* search, on the other hand, is a sort of binary search which takes alpha and beta and used the midpoint.
To me, it seems a lot more logical and scientific.
I believe Diep used MTD(f) for a while and another fairly strong program whose name escapes me right now {either the program or author started with the letter 'A', but it has been a while and I cannot even remember which}.
But most experiments with MDT(f) seem to end in frustration.
I think it is one of those things that sound great theoretically, but in practical terms do not quite deliver on the promise.

Some things that MTD(f) implementations have to fiddle with of importance are the resolution of the steps. Big mistake, for instance to use a double because you will never narrow down far enough. The size of each step towards the goal is another fiddly thing. The starting and ending point are another.

You are not going to find a lot of successful MTD(f) implementations because there aren't many (any?)

But I am not asking you to abandon it. You might be the first one to make a big bang with it, and then everyone else will follow suit.

Alessandro Scotti
Either Kiwi or Hamsters was MTD(f).