Recursion or Iteration?

[Fritz Reul]

Is it necessary to use an iterative search environment in order to perform YBWC or are classical alpha-beta-recursions better?

My first test results with a simple iterative perft-iteration are not very good. The iteration works well but not very fast. I need much labels and gotos - looks ugly

What are your options?

[Stan Arts]

Is it necessary to use an iterative search environment in order to perform YBWC or are classical alpha-beta-recursions better?

My first test results with a simple iterative perft-iteration are not very good. The iteration works well but not very fast. I need much labels and gotos - looks ugly

What are your options?

Hi,

I haven't experimented with parallel search (yet, maybe) but I do have something else then a recursive alpha-beta function in my program, and I don't need labels and goto's. (but I do need a conditional loop.)

In some sort of pseudo Pascal:

Code: Select all


variables : NumberOfMoves , AtMoveNumber : array[1..maxtreedepth] of Integer;
            DoNextMove : array[1..maxtreedepth] of Boolean;
            SearchTreeStart , InTreePlyCounter : Integer;
            SearchTreeEnd : Boolean;

{root}
NumberOfMoves[1]:=Generatemoves;
AtMoveNumber[1]:=0;
DoNextMove[1]:=False;
SearchTreeStart:=2;
NumberOfMoves[2..maxtreedepth]:=0;
AtMoveNumber[2..maxtreedepth]:=NumberOfMoves+1;

{iterate over searchtree once}
SearchTreeEnd:=False;
InTreePlyCounter:=SearchTreeStart;

Repeat

If AtMoveNumber[InTreePlyCounter] > NumberOfMoves[InTreePlyCounter] then
Begin     
 MakeMove ( InTreePlyCounter-1 ) ;  {Make move on previous depth in the searchtree}
 NumberOfMoves[InTreePlyCounter]:=Generatemoves;
 DoNextMove[InTreePlyCounter]:=False;
 If HaveALegalMove then AtMoveNumber[InTreePlyCounter]:=0
  Else AtMoveNumber[InTreePlyCounter]:=NumberOfMoves[InTreePlyCounter]+1;
end;

If DoNextMove[InTreePlyCounter] = True then
Begin 
 Inc ( AtMoveNumber[InTreePlyCounter] ) ;
 DoNextMove[InTreePlyCounter]:=False;
end;

If AtMoveNumber[InTreePlyCounter] > NumberOfMoves[InTreePlyCounter] then
Begin 
 DoNextMove[InTreePlyCounter-1]:=True;
 SearchTreeStart:=InTreePlyCounter-1;
 SearchTreeEnd:=True;
 MinimaxValueUp;
end;

Inc ( InTreePlyCounter );

Until SearchTreeEnd=True;



I have the iteration in another Repeat - Until loop that iterates over the tree a certain amount of times/nodes or the root is done or something else happened before checking for the time or update anything else.

I don't know how fast this is compared to other structures, but hope it's helpfull.

Stan

[Gerd Isenberg]

Is it necessary to use an iterative search environment in order to perform YBWC or are classical alpha-beta-recursions better?

My first test results with a simple iterative perft-iteration are not very good. The iteration works well but not very fast. I need much labels and gotos - looks ugly

What are your options?

Hi Fritz,

have you read the old threads in CCC about this issue?
http://www.stmintz.com/ccc/
search for "Recursive search versus Iterative search" or similar.

Cheers,
Gerd

[Zach Wegner]

Is it necessary to use an iterative search environment in order to perform YBWC or are classical alpha-beta-recursions better?

Not at all--See Crafty and Glaurung for YBW with recursion. It's not really an issue of what is better, it's more about taste: code quality vs. speedup. Iterative search is ugly, it's simply unavoidable. Just look at this highly simplified code I posted at the new CCC a while back:

Code: Select all

#define SEARCH_CALL(d, p, a, b, fm, rp) \
    do { \
        search_call(sb, d, p, a, b, fm, rp); \
        sb++; \
        goto end; \
    } while (0)

#define RETURN(r) \
    do { \
        sb->return_value = r; \
        sb--; \
        goto end; \
    } while (0)

void search_call(SEARCH_BLOCK *sb, int depth, int ply, int alpha, int beta,
    MOVE *first_move, SEARCH_STATE rp)
{
    sb->return_point = rp;
    sb++;
    sb->return_point = SEARCH_START;
    sb->depth = depth;
    sb->ply = ply;
    sb->alpha = alpha;
    sb->beta = beta;
    sb->first_move = first_move;
    sb->last_move = first_move;
}

int search(SEARCH_BLOCK *sb)
{
    while(1)
    {
        switch (sb->return_point)
        {
            case SEARCH_START:
                goto start;
            case SEARCH_1:
                goto search_1;
            case SEARCH_RETURN:
                return (sb+1)->return_value;
        }
start:
        if (sb->depth <= 0)
            RETURN(evaluate());
        sb->moves = 0;
        sb->last_move = generate_moves(sb->first_move);
        while (sb->move = next_move(sb))
        {
            make_move(sb->move);
            SEARCH_CALL(sb->depth - 1, sb->ply + 1, -sb->beta,
                -sb->alpha, sb->last_move, SEARCH_1);
search_1:   r = -(sb + 1)->return_value;
            unmake_move();
            if (r > sb->alpha)
                sb->alpha = r;
            if (r >= sb->beta)
                RETURN(r);
        }
        RETURN(sb->alpha);
end:
    }
}

The advantage of iterative over recursive is a slightly improved speedup. I would recommend doing a recursive YBW, and then trying out iterative if you are not satisfied.

Zach

[Fritz Reul]

Thanks Gerd!

[Tony van Roon-Werten]

I disagree. (well slightly)

With an iterative search you can choose your splitpoints better than with recursion.

It might not matter too much now, but with more processors (ie 2 years) it could make a big difference.

Unfortunately, iterative is not the way most programmers are used to think. So there's quite some effort involved.

Tony