# How to Debug MTD(f)

This topic is 4876 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello together, I have tried to implement the MTD(f) algorithem. AlphaBeta function worked befor, but now, after reaching a certain depth with iterative deepening, the following happens: First window: -1 to 0. Alpha beta returns 0 Next Window: 0 to 1 Alpha beta returns 1 Next window 1 to 2 Alpha beta retusn 2 Next window 2 to 3 ... you get the Idea. I know, that the correct value at that point is 0! I looked through the code, trying to understand what happens, I used a debugger but I just do not understand what is happening. Now My question: How would you debbug such a problem? How do you in general debug not-working alpha beta code? Thanks!!!

##### Share on other sites
If you can reproduce the problem with a search that consists of only a few nodes (say less than 10K), you can add some code to dump debugging information to a log and then analyze the log. It is hard to go through the loads of information that such a procedure generates, but it can be very informative.

Just one idea...

##### Share on other sites

Testing around with my sourcecode, I relized, that there is something I do not understand about MTD(f):
The AlphaBeta function never returns anything outside the boundings of alpha-beta, in case of MTD(f, this means that everytime either beta-1 or beta is returned.
I know, that the firstguess should be s accurate as possible, but of course I can not know an absolute accurate MiniMax value at that time!
But what if my first guess is off by about 500 (500 means a small capture for my evaluation function).
Than, (assuming the correct value is 0) MTD(f) first uses the window:
499-500
than
498-499
e.t.c.
So it takes 500 passes!
On http://www.cs.vu.nl/~aske/mtdf.html it says, it should take about 5 to 15 passes.
I seem to have totaly missed something!
Can somebody explain a little to me?
Thanks!

##### Share on other sites
Binary search

As an example.. suppose all scores must fall within the range MinScore = -10000 to MaxScore = +10000

At the start you know the TrueScore is somewhere between MinScore and MaxScore so you test:

TestScore = (MinScore + MaxScore) / 2

After one pass of MTD(f) you learn if the TrueScore is above or below TestScore and you can modify your new MinScore or MaxScore for the next pass.. say MTD(f) fails low.. you know TrueScore is then somewhere between 0 and +10000..

TestScore then becomes 5000.. rince and repeat

The obvious optimisation is to try to make a good first guess at MinScore and MaxScore instead of giving it the full range of legal score values.. you then of course have to handle the condition where the TrueScore falls outside your guess range and rerun with a wider binary search window..

##### Share on other sites
Quote:
 Original post by LonelyStar...Next Window: 0 to 1Alpha beta returns 1Next window 1 to 2Alpha beta retusn 2Next window 2 to 3 ... you get the Idea.I know, that the correct value at that point is 0!

There should be an error in your alpha-beta code. With a window 0,1 and a correct value of 0 it should return 0, not 1. Try to make it as simple as possible, disable Transposition tables (a very common place for errors when MTD is used), make a log file with alpha,beta,value_before_cutting,value_after_cutting, disable even alpha-beta if possible (reduce to plain minimax) ...

Hope it helps

##### Share on other sites
Quote:
 Original post by LonelyStarThe AlphaBeta function never returns anything outside the boundings of alpha-beta, in case of MTD(f, this means that everytime either beta-1 or beta is returned.I know, that the firstguess should be s accurate as possible, but of course I can not know an absolute accurate MiniMax value at that time!But what if my first guess is off by about 500 (500 means a small capture for my evaluation function).Than, (assuming the correct value is 0) MTD(f) first uses the window:499-500than498-499e.t.c.So it takes 500 passes!On http://www.cs.vu.nl/~aske/mtdf.html it says, it should take about 5 to 15 passes.I seem to have totaly missed something!Can somebody explain a little to me?Thanks!

You have a mistake here. Alpha-beta will return a value outside the bounds, so shortening the path to the correct value.

Let's use a tree of only one leaf [totally] with a value greater than beta ... and a small pseudocode ...
// ... for every move do ...{    // do the move    val=-NegaMax(-beta,-alpha);    // undo move    if (val>alpha)    {	alpha=val;            // a leaf value > beta is obviously > alpha                              // alpha will take this greater value	if (alpha>=beta)      	{	    break;            // the loop broken	}    }} // ... end of loopreturn alpha;                 // and this gretaer value returned to main caller

As you can easily see, the returned value will be greater than beta.

Hope it helps

[Edited by - DeepButi on February 11, 2005 3:55:35 AM]

##### Share on other sites
For those interested: The Problem with my source where two things!

- I stopped searching, when I've searched a certain number of nodes. At that moment, a wrong AlphaBeta was returned but my programm did not always relize that it had to ignore the last AlphaBeta value.

- DeepButis post made me realize: If I have a beta cutt-off, I am returning more information if I return the value that caused the beta cutt-off and not beta itself.

Thank you! My AI is beginning to get cool :)
Happy coding,
Nathan

• 38
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631365
• Total Posts
2999585
×