Iterative version of Alpha-beta instead recursive

[Samuele Giraudo]

Usually, iterative programs are more efficient than recursive ones.

I wonder if an iterative version of the Alpha-Beta algorithm exists and if it is easy to implement.

Best regards,
Samuele Giraudo

[sje]

Any recursive algorithm can be transformed into an iterative algorithm. The converse is also true.

One publicly available example of iterative A/B is given in the Chess 0.5 Pascal source. It is not particularly easy to understand, however and is polluted with goto statements.

Hint: an iterative version of a recursive algorithm has no local variables except for a stack index. The stack index (the ply number in this case) selects a current record in an explicit stack. This record contains all the interesting variable for that ply: the current state selector, the window, the move index, etc.

[Kempelen]

Usually, iterative programs are more efficient than recursive ones.

If this is true I ask why 99% of chess programs dont use it. Simplicity?

[bob]

Usually, iterative programs are more efficient than recursive ones.

If this is true I ask why 99% of chess programs dont use it. Simplicity?

I don't even buy the "more efficient." I'd bet you can hardly measure any difference in the two. The released version of Cray Blitz source code is iterative. It has advantages for parallel alpha/beta search, to be sure. But it is much less clean in how it is implemented.

[hgm]

Minimax search is a very simple case of recursion: the recursive routine is only called from two places, from the main program (or from SearchRoot() if you have a separate routin for that) and from itself. The return from the call is thus very simple to implement with a 99.99999% accurately predicted branch based on the ply level: only when you return from the root you have to continue with the stuff of main(), in all other cases you stay in Search(). This is why you don't lose any efficiency on making it recursive.

In the more general case, where a recursive routine is called from several places, and the pattern of where to return is not easily predicted, iterative implementation is much less efficient because of branch mis-predictions. The return-stack hardware in the CPU branch predictor solves this problem when you use true recursion.

Advantage of an iterative implementation is that you have automatic access to local variables of each node along the current branch. (But a recursive implementation can be set up to allow this as well, by using global arrays in stead of local variables.) Another advantage is that it is easy to do non-local gotos, e.g. for aborting a search. The iterative implementation also does not waste space on the machine stack for return addresses (which are always the same execept in the root, and are thus redundant information). This is only important if memory is very cramped (e.g. if you are writing an engine for a micro-controller with only 256 bytes of RAM).

Advantage of a recursive implementation is that the machine code can be optimized by unrolling the loop over moves without performance loss due to return mis-predictions.