The more common search structure is the recursivedepth-first search, as used in the Negamax algorithm example. The function calls itself with a decremented depth parameter until depth reaches zero. Opposed to that the Iterative Search always remains on the same layer on the call stack.
It is interesting to convert this recursive procedure to an iterative (non-recursive) form by a sequence of mechanical transformations, and to apply simple optimizations which preserve program correctness. The resulting procedure is surprisingly simple, but not as easy to prove correct as the recursive form.
Considerations
Generally every Recursive Function can also be converted into an Iterative Search by means of replacing the function calls by jumps (goto, break, continue) within the function itself [3]. The result is usually more efficient as the calling of a function is slower than just jumps within the function. The main downside however is the increased complexity and decreased readability [4].
In the Recursive Search the function can store local values, this doesn't work for the Iterative Structure, as all plies are using the same function. As a result a separate structure has to be maintained with all the relevant information for each ply. Harm Geert Muller (2008) [5] also pointed out that this gives more control to the programmer as to where the stack data maps in cache, allowing for more efficient implementations. Furthermore Onno Garms (2010) [6] said that the Iterative Search favors Profiling, as avoids all the cycles in the call tree.
Parallel Search
Especially for the Parallel Search AlgorithmDynamic Tree Splitting having an Iterative Search Structure is essential. It relies on threads frequently changing ownership of certain nodes, which requires full control over search stacks [7]. Furthermore it gives more flexibility in the selection of Split Points as the information on nodes in the current search branch is freely available.
Implementations
Goto
Onno Garms suggests the use of goto with a switch at the bottom to jump to the label specified in ret_addr as applied in his engine Onno:
Edmund Moshammer suggested to use a branch table, which at the beginning gets filled with addresses of all return points. The difference to the code shown by Onno Garms is that this would avoid the additional indirection of the switch statement in the end.
Switch
Teemu Pudas suggests a way how to use switch statements hiding behinds macros that emulate the typical function calls [8]:
enum{ RETURN, NEW_NODE };#define be_recursive() \
switch (state) { \
case NEW_NODE#define end_recursion() \
default:assert(false); return best; }#define return(foo) return best = foo, RETURN#define recurse() return(best), NEW_NODE#define search(depth,alpha,beta) do { \
next->init(NEW_NODE,depth,alpha,beta); \
state = __LINE__; \
recurse(); \
case __LINE__:; } while (0)inlineint Node::do_search(){// any variable not declared inside this function is a member of Node
Node *const next =this+1;
be_recursive():// Please.
gen_moves(list);if(list.empty())return(in_check ? MATE_IN_ONE : DRAW);while(move = list.next()){
make(move);
search(depth-1,-beta,-alpha);
unmake();if(ret_val > best){
best = ret_val;if(best >= beta)return(best);}}return(best);
end_recursion();}int drive_search(int depth, int alpha, int beta){// called from root_search()
Node stack[MaxPly];
Node *node =&stack[1];// stack[0] would be root
node->init(NEW_NODE,depth,alpha,beta);while(true){switch(node->do_search()){case RETURN:
node--;
node->ret_val =-node[1].best;if(node == stack)return node->ret_val;break;case NEW_NODE:
node++;}}}
Zach Wegner, the author of ZCT uses a large switch branch spanning across the search function with labels for every return point [9].
Table of Contents
Introduction
Knuth and Moore already introduced an iterative solution of Alpha-Beta in 1975 [2]:Considerations
Generally every Recursive Function can also be converted into an Iterative Search by means of replacing the function calls by jumps (goto, break, continue) within the function itself [3]. The result is usually more efficient as the calling of a function is slower than just jumps within the function. The main downside however is the increased complexity and decreased readability [4].In the Recursive Search the function can store local values, this doesn't work for the Iterative Structure, as all plies are using the same function. As a result a separate structure has to be maintained with all the relevant information for each ply. Harm Geert Muller (2008) [5] also pointed out that this gives more control to the programmer as to where the stack data maps in cache, allowing for more efficient implementations. Furthermore Onno Garms (2010) [6] said that the Iterative Search favors Profiling, as avoids all the cycles in the call tree.
Parallel Search
Especially for the Parallel Search Algorithm Dynamic Tree Splitting having an Iterative Search Structure is essential. It relies on threads frequently changing ownership of certain nodes, which requires full control over search stacks [7]. Furthermore it gives more flexibility in the selection of Split Points as the information on nodes in the current search branch is freely available.Implementations
Goto
Onno Garms suggests the use of goto with a switch at the bottom to jump to the label specified in ret_addr as applied in his engine Onno:Edmund Moshammer suggested to use a branch table, which at the beginning gets filled with addresses of all return points. The difference to the code shown by Onno Garms is that this would avoid the additional indirection of the switch statement in the end.
Switch
Teemu Pudas suggests a way how to use switch statements hiding behinds macros that emulate the typical function calls [8]:Zach Wegner, the author of ZCT uses a large switch branch spanning across the search function with labels for every return point [9].
See also
Recursive vs. Iterative Search
Forums Posts
2005 ...
2010 ...
2015 ...
References
What links here?
Up one level