Iterative DTS

[bob]

Sorry. I was simply explaining the usual issue with an iterated search conversion. Your code was too long to look at on the older computer I was using at the time (a 1024 x 768 laptop with a small screen). It sounds like you did things the right way.

Next step would be to compare old vs new code to see what is drastically different... and it might work better on a 64 bit box where you have the extra 8 registers to handle the array subscripting stuff.

Making everything indirect on a pointer will have a cost, of course..

[LoopList]

At the moment I am satisfied with the iterative search speed. The main handycaps were too many indirect search phase calls via the switch-case-statement. Now I jump direct to the next search phase by using multiple "gotos". I only remember the return points.

Until now I was used to develop "clear" and "modern" code, but the new iterative search looks really ugly. As far as I understood the only advantage of DTS is the thread's possibility to choose its best split node from all possible active split nodes.

But I suppose it should be possible to do so in a recursive search environment, too!?

[Zach Wegner]

Here's a simplified version of my search. The explicit gotos make the compiler create a jump table. The macros also do quite a lot to insure maximum readability.

Code: Select all

#define SEARCH_CALL(d, p, a, b, fm, dn, nt, rp) \
    do { \
        search_call(sb, d, p, a, b, fm, dn, nt, rp); \
        sb++; \
        goto end; \
    } while (FALSE)
#define RETURN(r) \
    do { \
        sb->return_value = r; \
        sb--; \
        goto end; \
    } while (FALSE)

int search(SEARCH_BLOCK *sb)
{
    while(1)
    {
        switch (sb->return_point)
        {
            case SEARCH_START:
                goto search_start;
            case SEARCH_1:
                goto search_1;
            case SEARCH_RETURN:
                return (sb + 1)->return_value;
        }
search_start:
        nodes++;
        if (sb->ply >= MAX_PLY - 1)
            RETURN(evaluate());
        if (board.fifty_count >= 100 || is_repetition(sb->ply == 1 ? 3 : 2))
            RETURN(0);
        if &#40;sb->depth <= 0&#41;
            RETURN&#40;evaluate&#40;));

        score_moves&#40;sb&#41;;
        /* The main move loop. */
        while &#40;sb->move = select_move&#40;sb&#41;)
        &#123;
            if (!make_move&#40;sb->move&#41;)
                continue;
            sb->moves++;
            SEARCH_CALL&#40;sb->depth - PLY, sb->ply + 1, -sb->beta,
                -sb->alpha, sb->last_move, SEARCH_1&#41;;
search_1&#58;   r = -&#40;sb + 1&#41;->return_value;
            if &#40;r > sb->alpha&#41;
            &#123;
                 sb->alpha = r;
                 if &#40;r >= sb->beta&#41;
                     RETURN&#40;r&#41;;
            &#125;
        &#125;
        end&#58;
              ;
    &#125;
&#125;

[Dan Andersson]

A couple of links to analysis and techniques:
http://www.complang.tuwien.ac.at/forth/ ... -code.html
http://www.complang.tuwien.ac.at/forth/ ... ortability
http://compilers.iecc.com/comparch/article/07-05-044
http://www.complang.tuwien.ac.at/forth/ ... .html#jilp

MvH Dan Andersson

[Aleks Peshkov]

Jump table is generally slow, because it is not use modern processors' branch prediction heuristics.

[bob]

anything is possible, but it will be anything but easy. That's why I chose to stick with the recursive formulation of the search, it is more readable.

Cray Blitz was a mess in that regard.

[Pradu]

At the moment I am satisfied with the iterative search speed. The main handycaps were too many indirect search phase calls via the switch-case-statement. Now I jump direct to the next search phase by using multiple "gotos". I only remember the return points.

Until now I was used to develop "clear" and "modern" code, but the new iterative search looks really ugly. As far as I understood the only advantage of DTS is the thread's possibility to choose its best split node from all possible active split nodes.

But I suppose it should be possible to do so in a recursive search environment, too!?

Yes it's possible with recursive too but it'd be uglier and less efficient. You'd have to handle rolling back your call stack when a thread is expected to quit and you'd have to handle creating a new call stack every time you want to pass on your search stack to another thread.

[jswaff]

Definitely. I have started writing an iterative search, and it is just about the ugliest thing I've ever seen. I'm not finished, but as it stands now I have one jump out of the move loop and two jumps into the move loop. Yuck.

And it is definitely harder to read. :-/


--
James