Iterative search is also useful for YBW. Also, it helps profiling because you don't have cycles in the call tree.Edmund wrote:A main difference moving to the Dynamic Tree Splitting Algorithm is that the whole search has to be laid out iterative instead of recursive. Now my question is, how can this be achieved best?
I personally don't like the macro based solutions for iterative search from other programs.
EDIT: because I dislike macros in general and try to minimize their use. I also dislike a huge case switch. The latter was fine for qsearch, but as a case switch cannot jump into the middle of loops, it requires ugly adaptions of the code.
I thought quite a long time, how to write a readable iterative search. I found a macro free solution. The price are - gotos. I hadn't used goto since my youth with C64 BASIC (not counting jumping out of nested loops) but for an iterative search I found gotos really useful.
Search looks like this:
Code: Select all
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 (node->ret_addr)
{
case Label after_research:
goto after_research;
...
}
}
