recusive null move in iterative search

[Daniel Shawul]

How do you apply recursive stuff in non-recursive ( iterative) search?
i wrote an iterative version of alpha-beta and then wanted to add
recursive stuff like Null Move, Internal iterative deepening etc..
I can easily apply a non-recursive version of both just by copy-pasting
the code i have at two places.
But thinking about their equivalent recursive implementaions bursts my head!!
Can anybody give me a hint?
daniel

[David Weller]

Hi Daniel!

No thanks, my head hurts enough as it is! LOL

[sorry. I just thought this was funny. Hope someone else can help]

[Zach Wegner]

Hi Daniel,
I use an iterative search, and Andrew is pretty much right. Put all of your parameters to the search function in a struct, and keep one for each ply. Make some macros to make it easier. Here are some code excerpts from my search to make it clear:

Code: Select all

typedef enum { START, NULLSEARCH, IID1, SEARCH1, SEARCH2, SEARCH3, SEARCH4, RETURN } SP;
typedef struct
{
        int depth, ply, alpha, beta, best, donull, nodetype, moves, pvfound, next, ext, threat, rv;
        SP rp;
} SBLOCK;
#define SEARCH(d, p, a, b, dn, nt, r) \
        do { \
                searchc(sb, d, p, a, b, dn, nt, r); \
                sb++; \
                goto cont; \
        } while (0)
#define RET(r) \
        do { \
                sb->rv = (r); \
                sb--; \
                goto cont; \
        } while (0)
search(SBLOCK *sb)
{
        while(1)
        {
                switch (sb->rp)
                {
                        case START:
                                goto start;
                        case NULLSEARCH:
                                goto nullsearch;
                        case IID1:
                                goto iid1;
                        case SEARCH1:
                                goto search1;
                        case SEARCH2:
                                goto search2;
                        case SEARCH3:
                                goto search3;
                        case RETURN:
                                return (sb + 1)->rv;
                }

...

/*internal iterative deepening*/
                if (!board->hashmove[sb->ply] && sb->alpha + 1 != sb->beta && !board->threatm[sb->ply] && sb->depth > 2 * PLY && sb->donull)
                {
                        SEARCH(sb->depth - 2 * PLY, sb->ply, sb->alpha, sb->beta, 1, NODEPV, IID1);
iid1:                   val = (sb + 1)->rv;
                        if (val > sb->alpha && val < sb->beta)
                                board->hashmove[sb->ply] = MOVE(board->pv[sb->ply][sb->ply]);
                }

...

        }
}

So I "recurse" with the SEARCH macro, and back up a value with the RET macro. I use a search ID return point, in this example IID1, which is used to jump to where it "returns" to at iid1, with the return value copied into val.

Regards,
Zach

[Daniel Shawul]

Hi all

i use an iterative search, and Andrew is pretty much right. Put all of your parameters to the search function in a struct, and keep one for each ply. Make some macros to make it easier. Here are some code excerpts from my search to

i managed to add null move overnight by just generating null move along with the rest of the moves at alternate plies. But this is a very ugly way.
I don't know how i apply PVs if i go on this way.
YOur method is much cleaner and easier to understand.
i will study it.
BEst regards
daniel

[Dann Corbit]

I want to understand why you chose iterative search over recursive search to begin with.

I see no difference for threading implementations when you choose one style over the other.

What is the perceived value of a purely iterative search as opposed to a recursive implementation?

[Zach Wegner]

For SMP, iterative has a definite advantage. You can choose a split point anywhere along the path immediately, rather than just the current node, which is usually near the leaves. The threads are more independent. You don't have to have the original parent back up a value, which wastes memory and time when a board state is sitting around waiting to be backed up. This doesn't average out to much, but hey, it's chess programming . Surprisingly enough, it's easier for me to understand DTS than the way crafty does parallel search, and my code seems much cleaner. I have the search states WAIT and UNSPLIT, which I just stick on the bottom of the stack to easily control what a thread does when it backs up from a split point. Of course, I still haven't gotten the thing working right. Threaded programming is a bitch.

Regards,
Zach

[Daniel Shawul]

Hi dann
the only reason i am doing that is because i wanted to try
DTS like Zach. if i use recursive search (like i did in danchess)
i can only split at nodes near leafs or i have to do some more work.
This may not be a great advantage at all as compared to the code clarity but i will try it anyway since i got some time on my hands to spend.
best
daniel