🔒 Locked

How to Debug MTD(f)

Started by LonelyStar Feb 8, 2005 at 8:25 AM 5 replies 2.7k views

Original Post

Feb 8, 2005 at 8:25 AM

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

alvaro

Feb 8, 2005 at 8:24 PM

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

LonelyStar

Feb 9, 2005 at 8:02 AM

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!

DeepButi

Feb 11, 2005 at 2:29 AM

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

DeepButi

Feb 11, 2005 at 2:55 AM

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

LonelyStar

Feb 11, 2005 at 8:30 AM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.