Sign in to follow this  

How to Debug MTD(f)

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites
Thanks for you answer alvaro!

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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Quote:
Original post by LonelyStar
...
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!

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 this post


Link to post
Share on other sites
Quote:
Original post by LonelyStar
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!


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 loop
return 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 this post


Link to post
Share on other sites
Thanks for all your answers, I understand a lot more now!
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

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this