Iterative Search

From Chessprogramming wiki
Revision as of 17:21, 27 June 2018 by GerdIsenberg (talk | contribs)
Jump to: navigation, search

Home * Search * Iterative Search

Spaghetti Code [1]

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.

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

Recursive vs. Iterative Search

Forums Posts

2005 ...

2010 ...

2015 ...

References

  1. 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
  2. Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6:293–326
  3. comp.lang.c FAQ list · Question 17.10
  4. Spaghetti code from Wikipedia
  5. Re: Interesting Scorpio design by H.G. Muller, Winboard Forum, November 05, 2008
  6. Re: DTS Structure by Onno Garms, CCC, May 28, 2010
  7. See remark on Recursion by Jean-Christophe Weill on recursive versus iterative implementation of ABDADA
  8. Re: Interesting Scorpio design by Teemu Pudas, Winboard Forum, November 05, 2008
  9. Re: DTS Structure by Zach Wegner, CCC, May 29, 2010
  10. Considered harmful from Wikipedia

Up one level