recusive null move in iterative search

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

recusive null move in iterative search

Postby Daniel Shawul » 24 Mar 2005, 13:59

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: recusive null move in iterative search

Postby David Weller » 24 Mar 2005, 15:20

Hi Daniel!

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

[sorry. I just thought this was funny. Hope someone else can help]
User avatar
David Weller
 
Posts: 135
Joined: 26 Sep 2004, 20:30
Location: USA

Re: recusive null move in iterative search

Postby Zach Wegner » 25 Mar 2005, 02:02

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
User avatar
Zach Wegner
 
Posts: 182
Joined: 26 Sep 2004, 22:02
Location: Austin, Texas, USA

Re: recusive null move in iterative search

Postby Daniel Shawul » 25 Mar 2005, 05:46

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia

Re: recusive null move in iterative search

Postby Dann Corbit » 25 Mar 2005, 18:06

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?
Dann Corbit
 

Re: recusive null move in iterative search

Postby Zach Wegner » 25 Mar 2005, 21:22

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
User avatar
Zach Wegner
 
Posts: 182
Joined: 26 Sep 2004, 22:02
Location: Austin, Texas, USA

Re: recusive null move in iterative search

Postby Daniel Shawul » 26 Mar 2005, 12:38

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
User avatar
Daniel Shawul
 
Posts: 366
Joined: 28 Sep 2004, 09:33
Location: Ethiopia


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 4 guests