Hi, I need to add iterative deepening to this AlphaBeta: But can seem to find any good sources. Anyone? Thanks, Ivan

There's nothing to it, the search function itself wouldn't necessarily be affected at all. Simply run it multiple times with increasing depths until you run out of time, then return the best move generated by the most recently completed search.

The tricky bit is actually terminating an ongoing search. Typically this means either polling the time from within the minimax function somewhere, or using an asynchronous method such as spawning and forcibly terminating a separate worker thread or using Unix alarm signals.

What, exactly, are you having trouble with?

should the ID code come in the ab routine or the main minimax function?

I've seen some pseudcode but I don't know how it would fit in minimax

Quote: Original post by cryo75
should the ID code come in the ab routine or the main minimax function?

Conceptually it's entirely separate from (that is built on top of) the minimax function, whether or not alpha-beta pruning is used. All you need to do is *call* your recursive minimax function with successively deeper cut-off values and return the latest result when you run out of time. E.g. something along these lines:

int InterativeDeepening(IBoard board, int timeout) { int depth = 1; int score; do  score = AlphaBeta(board, depth++, INT_MIN, INT_MAX); while(ElapsedTime() < timeout); return score;}

Except in practice you'll almost certainly want to stop searching in the middle of an alpha-beta call, so there's the added complexity of somehow stopping it mid-run.

Right. Normally, you'll do ID with two threads, one killing the other:

int best;void threadA(){    best = -1;    for(int depth=0; ; depth++)    {        best = AlphaBeta(board, depth, etc.);    }}int IterativeDeepening(...){    newThread(threadA);    sleep(5000);    killThread(threadA);    return best;}

Quote: Original post by Sneftel
Right. Normally, you'll do ID with two threads, one killing the other

Beware that some systems have issues with this though, most notably Win32 leaking memory. But I'm guessing that the OP is using Java or C# so it ought to be fine.

Good point. The solution is a volatile flag which AlphaBeta checks on a regular basis. The killer thread sets it to true after five seconds; when AlphaBeta sees it, it throws an exception out to the main thread function, which returns the result. (Meanwhile, the killer thread joins on the AlphaBeta thread to wait for that result.)

Quote: Original post by Sneftel
Good point. The solution is a volatile flag which AlphaBeta checks on a regular basis. The killer thread sets it to true after five seconds; when AlphaBeta sees it, it throws an exception out to the main thread function, which returns the result. (Meanwhile, the killer thread joins on the AlphaBeta thread to wait for that result.)

The volatile keyword (the C storage class, not the Java keyword) doesn't do much good here, you need a proper memory barrier of some sort. Still, if you're going to be polling anyway then you might as well just check the time every N iterations.

Too bad Win32 doesn't have asynchronous signals. In Unix you can just set up an alarm signal in N seconds and use a (sig)longjmp to abort the search, no theads needed :)
Perhaps there's something equivalent for Windows but I can't think of anything off the top of my head.

lol now I'm totally lost in translation!!

I'm already having headaches trying to use threads for the main minimax function call. I don't want more threads!

I understand (in theory) how the ID works but I don't see it materializing in my current code...

Quote: Original post by cryo75
lol now I'm totally lost in translation!!

I'm already having headaches trying to use threads for the main minimax function call. I don't want more threads!

I understand (in theory) how the ID works but I don't see it materializing in my current code...

Sorry, I didn't mean to go off on a tangent (well, I did, but I apologise anyway.)
You shouldn't have any problems with this in C#. Just use call Thead.abort() on the worker from the main thread and catch TheadAbortException in the iterative deepening loop to return the last result.