Iterative DTS

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Iterative DTS

Post by bob » Tue Jul 03, 2007 3:26 pm

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

Re: Iterative DTS

Post by LoopList » Tue Jul 03, 2007 5:44 pm

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!?

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Iterative DTS

Post by Zach Wegner » Tue Jul 03, 2007 6:18 pm

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;


Aleks Peshkov
Posts: 866
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: Iterative DTS

Post by Aleks Peshkov » Tue Jul 03, 2007 7:04 pm

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

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Iterative DTS

Post by bob » Tue Jul 03, 2007 8:37 pm

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
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Iterative DTS

Post by Pradu » Tue Jul 03, 2007 9:03 pm

LoopList wrote: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

Re: Iterative DTS

Post by jswaff » Fri Jul 13, 2007 9:03 pm

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

Post Reply