I'm on the preliminary stages of a MDT(f) minimax alpha-beta algorithm. It works perfectly well ... but (there's always a "but"!) ... although it finds the correct value I'm not able to find the correct moves associated. The problem is not on the minimax (I can get the value AND the solution) but on the way I handle the Transposition Tables. I mean, minimax without TT finds both, but minimax with TT is making me nervous . I have not been able to find any example of handling the solution on Internet, all examples are about minimax "without memory" or on handling alpha-beta values, but nothing about the way to staore/retrieve moves. Anyone knows a good link about it or has any experience with TT? Thanks in advance

Hola

I'm not 100% sure what you are asking, but in my implementation the best move (if there is one) for each node is stored in the TT, so when the search has terminated the move that should be returned can be found in the TT record for the root node. Hope this helps.

I don't have any experience with MTD(f), but I have used TT for a long time. I always write a separate function for analyzing the root node. That function should give you the best move, together with the score, and TT should not interfere with that mechanism at all.

You probably need to track the Principle Variation using a separate data structure (like a stack). If you use your TT to hold your PV, you are going to run into problems if two positions hash to the same bucket, erasing the previous entry, if that entry was part of the PV.

If you're doing chess programming, it pays to have fast access to the PV anyways, since it can help your move ordering tredmendously (always analyze moves in the PV before others - the rational is that if a move was good enough to make the PV in a previous search, it's probably still good.)

I haven't yet seen convincing evidence that MDT(f) is better than plain alpha beta with sensible move ordering. What you gain in speed you lose in being granularity of positional evaluation. Since play strength increases logrithmically to execution speed (in most chess programs, doubling processor speed increases strength by only 200 points), this is not a clear win. Though if you find out otherwise, I'd love to hear about it.

Thanks to all answers.

Telamon,
it's not a chess game, it's a trick tacking card game (bridge-like) and MDT(f) proves to be really worthfull. Still working on the best move ordering, but at the present stage with 10 tricks (40 ply) it outperforms alpha-beta by a 1/30 ratio or better with a reasonable guess. Even with a bad guess it outperforms alpha-beta. Probably this is due to the fact that the scores lie in a limited range (-72/+72). The evaluation function is always "exact" and the number of iterations of MTD(f) is really small. I will keep you informed when the move ordering will be finished ... and when I reach the desired 12 tricks (48 ply) that at the moment is out of question due to performance issues.

All,
my alpha-beta returns always correct best value, just wondering on how do I get the path to get it. I take care of TT collisions, no problem here; I'm absolutely sure the retrieved position on the TT is the one I'm looking for because I store the unique position identifier (not the hash key, the position itself and this one is always unique) and check it before getting any value from the table. TT also contains the "best" path from the position to the end of game, so I retrieve also it ... but this seems to fail because the final path is not what expected. Since move ordering is not yet done, I'm not using best move from TT, I get the whole path to the end.

Unsure if I've been able to make it clear :-) ... I can get the best first move, I can get the best value, but I want to get the whole best path for the whole game ... and it seems to me that this could be done, but unable to get it work. If using alpha-beta without TT, the whole path is OK, so the problem is clearly on the TT handling of the path.

Anyway, thanks a lot for all answers.

The expected path from the root to a leaf is called the principal variation (PV). I guess this is what you want. The problem is that you dont get a PV with a null-window search like MTD(f), since at every second level all nodes will fail low. This is one reason many people prefer negascout.

[Edited by - Scientifish on September 14, 2004 5:09:02 AM]

Scientifish,
thanks. I missunderstood MTD(f) at this point; I believed -erroneously- that last search would give a PV. I will give a try at NegaScout even if I doubt it will outperform MTD(f) on this kind of games where you need 4 ply to find a really different move (leading card is by far most important than others).

Telamon,
with move ordering (not yet finished, but good enough), MTD(f) still outperforms alpha-beta but not so dramatically as before. Preliminary tests show a 1/3 ratio. As it is implemented with only a few code lines, MTD(f) seems still a good choice.

Thanks to everybody.

Quote: Original post by Telamon
I haven't yet seen convincing evidence that MDT(f) is better than plain alpha beta with sensible move ordering. What you gain in speed you lose in being granularity of positional evaluation. Since play strength increases logrithmically to execution speed (in most chess programs, doubling processor speed increases strength by only 200 points), this is not a clear win. Though if you find out otherwise, I'd love to hear about it.

After a 1.000 games test and for my particular situation, MTD(f) with a perfect guess (obtained from previous NegaScout :-) )evaluates 54% of nodes (and takes 54% of time) than NegaScout, with 991 better situations and only 9 worse; even MTD(f) with a "poor" guess is at 98% of NegaScout, with 737 better and 273 worse. Now working on a good guess function, that logically would be in between.
Alpha-beta alone is out of question (>300% of NegaScout).
All tests share sensible move ordering, TT size and logic, forward prunning and evaluation function.
Currently I don't need the PV, probably adding code to get it would penalize MTD(f) a little bit.