Difference between revisions of "Iterative Search"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Search]] * Iterative Search''' | '''[[Main Page|Home]] * [[Search]] * Iterative Search''' | ||
− | [[FILE:SpaghettiCode.JPG|border|right|thumb|Spaghetti Code <ref>[[:Category:Irmgard 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, [[:Category: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 [[:Category:Industrial | + | [[FILE:SpaghettiCode.JPG|border|right|thumb|Spaghetti Code <ref>[[:Category:Irmgard 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, [[:Category: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 [[:Category:Industrial Heritage Trail|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]]. | 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]]. | ||
Line 163: | Line 163: | ||
* [https://www.stmintz.com/ccc/index.php?id=478627 Iterative alpha-beta search?] by [[Andrew Wagner]], [[CCC]], January 11, 2006 | * [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.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.open-aurec.com/wbforum/viewtopic.php?f=4&t=49618&p=187476 Interesting Scorpio design] by [[Kerwin Medina]], [[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 | * [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 ...== | ==2010 ...== | ||
Line 178: | Line 178: | ||
'''[[Search|Up one level]]''' | '''[[Search|Up one level]]''' | ||
[[Category:Flottmann]] | [[Category:Flottmann]] | ||
− | [[Category:Industrial | + | [[Category:Industrial Heritage Trail]] |
[[Category:Irmgard Potthoff]] | [[Category:Irmgard Potthoff]] |
Latest revision as of 15:30, 25 December 2020
Home * Search * Iterative Search
The more common search structure is the recursive depth-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.
Contents
Introduction
Knuth and Moore already introduced an iterative solution of Alpha-Beta in 1975 [2]:
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 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:
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; ... } }
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) 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++; } } }
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
- Backtracking - Eight Queens puzzle with Bitboards
- Knuth's Iterative Solution of Alpha-Beta
- Iteration
- Parallel Search
- Recursion
Forums Posts
2005 ...
- recusive null move in iterative search by Daniel Shawul, Winboard Forum, March 25, 2005 » Null Move Pruning
- Iterative alpha-beta search? by Andrew Wagner, CCC, January 11, 2006
- Iterative DTS by Fritz Reul, CCC, July 02, 2007
- Interesting Scorpio design by Kerwin Medina, Winboard Forum, November 05, 2008
- Iterative version of Alpha-beta instead recursive by Samuele Giraudo, CCC, May 02, 2009
2010 ...
- DTS Structure by Edmund Moshammer, CCC, May 28, 2010
- True iterative search... by Jens Bæk Nielsen, CCC, November 27, 2012
- Re: goto thread (split) by Steven Edwards, CCC, August 01, 2013 » Symbolic [10]
- Non recursive perft() by Steven Edwards, CCC, August 24, 2014 » Perft
2015 ...
- Parallel iterative search function by Fabio Gobbato, CCC, March 05, 2015 » Parallel Search
References
- ↑ Irmgard Potthoff - Keine Schonkost, 2010, Überschriften aus Tageszeitungen, Teller, Messer, Gabel, Tisch (headlines from daily newspapers, plate, knife, fork, table), Flottmann 30 hoch - 30 years anniversary exhibition, Flottmann-Hallen in Herne, North Rhine-Westphalia, Germany, part of The Industrial Heritage Trail of the Ruhr area, Photo by Gerd Isenberg, September 18, 2016
- ↑ Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6:293–326
- ↑ comp.lang.c FAQ list · Question 17.10
- ↑ Spaghetti code from Wikipedia
- ↑ Re: Interesting Scorpio design by H.G. Muller, Winboard Forum, November 05, 2008
- ↑ Re: DTS Structure by Onno Garms, CCC, May 28, 2010
- ↑ See remark on Recursion by Jean-Christophe Weill on recursive versus iterative implementation of ABDADA
- ↑ Re: Interesting Scorpio design by Teemu Pudas, Winboard Forum, November 05, 2008
- ↑ Re: DTS Structure by Zach Wegner, CCC, May 29, 2010
- ↑ Considered harmful from Wikipedia