25,161
edits
Changes
Created page with "'''Home * Search * Iterative Search''' border|right|thumb|Spaghetti Code <ref>[[Arts#Potthoff|Irmgard Potthoff - Keine Schonkost,..."
'''[[Main Page|Home]] * [[Search]] * Iterative Search'''
[[FILE:SpaghettiCode.JPG|border|right|thumb|Spaghetti Code <ref>[[Arts#Potthoff|Irmgard Potthoff]] - Keine Schonkost, 2010, Überschriften aus Tageszeitungen, Teller, Messer, Gabel, Tisch (headlines from daily newspapers, plate, knife, fork, table), [http://flottmann-hallen.de/event/884/flottmann-30-hoch Flottmann 30 hoch] - 30 years anniversary exhibition, [[Arts#Flottmann|Flottmann-Hallen]] in [https://en.wikipedia.org/wiki/Herne,_North_Rhine-Westphalia Herne], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], [https://en.wikipedia.org/wiki/Germany Germany], part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area], Photo by [[Gerd Isenberg]], September 18, 2016</ref> ]]
The more common search structure is the [[Recursion|recursive]] [[Depth-First|depth-first search]], as used in the [[Negamax|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|stack]].
=Introduction=
[[Donald Knuth|Knuth]] and Moore already introduced an [[Knuth-iterative|iterative solution]] of [[Alpha-Beta]] in 1975 <ref>[[Donald Knuth]], [http://dblp.uni-trier.de/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''An analysis of alpha-beta pruning.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], 6:293–326</ref>:
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 ([[C#Goto|goto]], break, continue) within the function itself <ref>[http://c-faq.com/style/stylewars.html comp.lang.c FAQ list · Question 17.10]</ref>. 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 <ref>[https://en.wikipedia.org/wiki/Spaghetti_code Spaghetti code from Wikipedia]</ref>.
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''') <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476#p187458 Re: Interesting Scorpio design] by [[Harm Geert Muller|H.G. Muller]], [[Computer Chess Forums|Winboard Forum]], November 05, 2008</ref> 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''') <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=351576&t=34561 Re: DTS Structure] by [[Onno Garms]], [[CCC]], May 28, 2010</ref> said that the Iterative Search favors [[Profiling]], as avoids all the cycles in the call tree.
==Parallel Search==
Especially for the [[Parallel Search|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 <ref>[[ABDADA#Recursion|See remark on Recursion]] by [[Jean-Christophe Weill]] on [[Recursion|recursive]] versus [[Iteration|iterative]] implementation of [[ABDADA]]</ref>. 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==
<span id="Onno"></span>[[Onno Garms]] suggests the use of [[C#Goto|goto]] with a [[C#Switch|switch]] at the bottom to jump to the label specified in ret_addr as applied in his engine [[Onno]]:
<pre>
namespace Label
{
enum _ {after_scout, after_research, ...};
}
class Node
{
int alpha, beta;
Move move;
MoveList moves;
int value;
Label::_ ret_addr;
};
search ()
{
Node* node = &d_nodes[0];
Node* child = node+1;
recurse:
node->moves.init();
while ((node->move = node->moves.next()))
{
child->alpha = ...
child->beta = ...
child->ret_addr = Label::after_scout;
++node;
++child;
goto recurse;
// when we return here, node and child have their original values
// and child is evaluated
after_scout:
if (child->value < -node->alpha)
{
child->alpha = ...
child->beta = ...
child->ret_addr = Label::after_research;
++node
++child;
goto recurse;
after_research:
...
}
if (cutoff)
{
node->value = ...
goto node_done;
}
}
node_done:
--node;
--child;
switch (child->ret_addr)
{
case Label::after_research:
goto after_research;
...
}
}
</pre>
[[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 <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476#p187476 Re: Interesting Scorpio design] by [[Teemu Pudas]], [[Computer Chess Forums|Winboard Forum]], November 05, 2008</ref>:
<pre>
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)
inline int 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++;
}
}
}
</pre>
[[Zach Wegner]], the author of [[ZCT]] uses a large switch branch spanning across the search function with labels for every return point <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=351606&t=34561 Re: DTS Structure] by [[Zach Wegner]], [[CCC]], May 29, 2010</ref>.
=See also=
* [[ABDADA]]
: [[ABDADA#Recursion|Recursive vs. Iterative Search]]
* [[Backtracking#8QinBitboards|Backtracking - Eight Queens puzzle with Bitboards]]
* [[Donald Knuth|Knuth's]] [[Knuth-iterative|Iterative Solution] of [[Alpha-Beta]]
* [[Iteration]]
* [[Parallel Search]]
* [[Recursion]]
=Forums Posts=
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2071 recusive null move in iterative search] by [[Daniel Shawul]], [[Computer Chess Forums|Winboard Forum]], March 25, 2005 » [[Null Move Pruning]]
* [https://www.stmintz.com/ccc/index.php?id=478627 Iterative alpha-beta search?] by [[Andrew Wagner]], [[CCC]], January 11, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=14832 Iterative DTS] by [[Fritz Reul]], [[CCC]], July 02, 2007
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476 Interesting Scorpio design] by Kerwin, [[Computer Chess Forums|Winboard Forum]], November 05, 2008
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=264977 Iterative version of Alpha-beta instead recursive] by Samuele Giraudo, [[CCC]], May 02, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34561 DTS Structure] by [[Edmund Moshammer]], [[CCC]], May 28, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=46175 True iterative search...] by [[Jens Bæk Nielsen]], [[CCC]], November 27, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48812&start=6 Re: goto thread (split)] by [[Steven Edwards]], [[CCC]], August 01, 2013 » [[Symbolic]] <ref>[https://en.wikipedia.org/wiki/Considered_harmful Considered harmful from Wikipedia]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=53408 Non recursive perft()] by [[Steven Edwards]], [[CCC]], August 24, 2014 » [[Perft]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55563 Parallel iterative search function] by [[Fabio Gobbato]], [[CCC]], March 05, 2015 » [[Parallel Search]]
=References=
<references />
'''[[Search|Up one level]]'''
[[FILE:SpaghettiCode.JPG|border|right|thumb|Spaghetti Code <ref>[[Arts#Potthoff|Irmgard Potthoff]] - Keine Schonkost, 2010, Überschriften aus Tageszeitungen, Teller, Messer, Gabel, Tisch (headlines from daily newspapers, plate, knife, fork, table), [http://flottmann-hallen.de/event/884/flottmann-30-hoch Flottmann 30 hoch] - 30 years anniversary exhibition, [[Arts#Flottmann|Flottmann-Hallen]] in [https://en.wikipedia.org/wiki/Herne,_North_Rhine-Westphalia Herne], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], [https://en.wikipedia.org/wiki/Germany Germany], part of [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area], Photo by [[Gerd Isenberg]], September 18, 2016</ref> ]]
The more common search structure is the [[Recursion|recursive]] [[Depth-First|depth-first search]], as used in the [[Negamax|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|stack]].
=Introduction=
[[Donald Knuth|Knuth]] and Moore already introduced an [[Knuth-iterative|iterative solution]] of [[Alpha-Beta]] in 1975 <ref>[[Donald Knuth]], [http://dblp.uni-trier.de/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''An analysis of alpha-beta pruning.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], 6:293–326</ref>:
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 ([[C#Goto|goto]], break, continue) within the function itself <ref>[http://c-faq.com/style/stylewars.html comp.lang.c FAQ list · Question 17.10]</ref>. 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 <ref>[https://en.wikipedia.org/wiki/Spaghetti_code Spaghetti code from Wikipedia]</ref>.
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''') <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476#p187458 Re: Interesting Scorpio design] by [[Harm Geert Muller|H.G. Muller]], [[Computer Chess Forums|Winboard Forum]], November 05, 2008</ref> 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''') <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=351576&t=34561 Re: DTS Structure] by [[Onno Garms]], [[CCC]], May 28, 2010</ref> said that the Iterative Search favors [[Profiling]], as avoids all the cycles in the call tree.
==Parallel Search==
Especially for the [[Parallel Search|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 <ref>[[ABDADA#Recursion|See remark on Recursion]] by [[Jean-Christophe Weill]] on [[Recursion|recursive]] versus [[Iteration|iterative]] implementation of [[ABDADA]]</ref>. 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==
<span id="Onno"></span>[[Onno Garms]] suggests the use of [[C#Goto|goto]] with a [[C#Switch|switch]] at the bottom to jump to the label specified in ret_addr as applied in his engine [[Onno]]:
<pre>
namespace Label
{
enum _ {after_scout, after_research, ...};
}
class Node
{
int alpha, beta;
Move move;
MoveList moves;
int value;
Label::_ ret_addr;
};
search ()
{
Node* node = &d_nodes[0];
Node* child = node+1;
recurse:
node->moves.init();
while ((node->move = node->moves.next()))
{
child->alpha = ...
child->beta = ...
child->ret_addr = Label::after_scout;
++node;
++child;
goto recurse;
// when we return here, node and child have their original values
// and child is evaluated
after_scout:
if (child->value < -node->alpha)
{
child->alpha = ...
child->beta = ...
child->ret_addr = Label::after_research;
++node
++child;
goto recurse;
after_research:
...
}
if (cutoff)
{
node->value = ...
goto node_done;
}
}
node_done:
--node;
--child;
switch (child->ret_addr)
{
case Label::after_research:
goto after_research;
...
}
}
</pre>
[[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 <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476#p187476 Re: Interesting Scorpio design] by [[Teemu Pudas]], [[Computer Chess Forums|Winboard Forum]], November 05, 2008</ref>:
<pre>
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)
inline int 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++;
}
}
}
</pre>
[[Zach Wegner]], the author of [[ZCT]] uses a large switch branch spanning across the search function with labels for every return point <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=351606&t=34561 Re: DTS Structure] by [[Zach Wegner]], [[CCC]], May 29, 2010</ref>.
=See also=
* [[ABDADA]]
: [[ABDADA#Recursion|Recursive vs. Iterative Search]]
* [[Backtracking#8QinBitboards|Backtracking - Eight Queens puzzle with Bitboards]]
* [[Donald Knuth|Knuth's]] [[Knuth-iterative|Iterative Solution] of [[Alpha-Beta]]
* [[Iteration]]
* [[Parallel Search]]
* [[Recursion]]
=Forums Posts=
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2071 recusive null move in iterative search] by [[Daniel Shawul]], [[Computer Chess Forums|Winboard Forum]], March 25, 2005 » [[Null Move Pruning]]
* [https://www.stmintz.com/ccc/index.php?id=478627 Iterative alpha-beta search?] by [[Andrew Wagner]], [[CCC]], January 11, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=14832 Iterative DTS] by [[Fritz Reul]], [[CCC]], July 02, 2007
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476 Interesting Scorpio design] by Kerwin, [[Computer Chess Forums|Winboard Forum]], November 05, 2008
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=264977 Iterative version of Alpha-beta instead recursive] by Samuele Giraudo, [[CCC]], May 02, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34561 DTS Structure] by [[Edmund Moshammer]], [[CCC]], May 28, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=46175 True iterative search...] by [[Jens Bæk Nielsen]], [[CCC]], November 27, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48812&start=6 Re: goto thread (split)] by [[Steven Edwards]], [[CCC]], August 01, 2013 » [[Symbolic]] <ref>[https://en.wikipedia.org/wiki/Considered_harmful Considered harmful from Wikipedia]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=53408 Non recursive perft()] by [[Steven Edwards]], [[CCC]], August 24, 2014 » [[Perft]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55563 Parallel iterative search function] by [[Fabio Gobbato]], [[CCC]], March 05, 2015 » [[Parallel Search]]
=References=
<references />
'''[[Search|Up one level]]'''
