A non recursive search function!

[Michael Sherwin]

A nonrecursive alpha--beta search function
by Michael J Sherwin.
(unless someone has beat me to it)

int Search(alpha, beta, depth) {
int score;
int temp;
int ply;
int betaCut;

ply = 1;
betaCut = FALSE;

GenMoves();

while(ply) {
do {
if(betaCut || !MakeNextMove()) {
betaCut = FALSE;
goto noMoreMoves();
}
ply++;
temp = alpha;
alpha = -beta;
beta = -temp;
} while(depth-- && GenMoves());
score = Eval();
if(score > alpha) {
if(score >= beta)
betaCut = TRUE;
else
alpha = score;
}
noMoreMoves:
if(ply--) {
TakeBackMove();
depth++;
temp = alpha;
alpha = -beta;
beta = -temp;
}
}
return alpha;
}

Due to time restraints, I have not tested it.
See RomiChess, learn.c, LearnToHash() for a
similar approach.

[b]Any thoughts on this? [/b]

[Pradu]

pain

[Alessandro Scotti]

Hello Michael,
I would have expected some sort of ply-based "stack"...

P.S. IIRC both Zappa and Scorpio use non-recursive search. Also, an example appears in the original Knuth paper about alpha-beta.

[Michael Sherwin]

Alessandro Scotti wrote:

Hello Michael,
I would have expected some sort of ply-based "stack"...

P.S. IIRC both Zappa and Scorpio use non-recursive search. Also, an example appears in the original Knuth paper about alpha-beta.

***********************************************************
Hi Alessandro,
Thanks for the reply. I was not aware of the facts that you presented. I will have to check out the node rates of the programs mentioned. I think that non recursion would be faster.

Mike

[Uri Blass]

A nonrecursive alpha--beta search function
by Michael J Sherwin.
(unless someone has beat me to it)

int Search(alpha, beta, depth) {
int score;
int temp;
int ply;
int betaCut;

ply = 1;
betaCut = FALSE;

GenMoves();

while(ply) {
do {
if(betaCut || !MakeNextMove()) {
betaCut = FALSE;
goto noMoreMoves();
}
ply++;
temp = alpha;
alpha = -beta;
beta = -temp;
} while(depth-- && GenMoves());
score = Eval();
if(score > alpha) {
if(score >= beta)
betaCut = TRUE;
else
alpha = score;
}
noMoreMoves:
if(ply--) {
TakeBackMove();
depth++;
temp = alpha;
alpha = -beta;
beta = -temp;
}
}
return alpha;
}

Due to time restraints, I have not tested it.
See RomiChess, learn.c, LearnToHash() for a
similar approach.

Any thoughts on this?

I learned that you should never use goto
I got rid of goto in Movei by having boolean varaible for stop_search so I think that it is better to have some bolean variable no_more_moves and have in the right places
if (no_more_moves) break;

Uri

[Dann Corbit]

The cost of recursion is very small. It is (once per function) a push of parameters and return address. If you pass by reference or pointer, even a large object only occupies (sizeof address). Recursion is expensive if you pass large classes or structures by value, but that is a pretty rare occurance.

I would prefer to keep the function as simple as possible, and therefore easier to debug. I think it will be more profitable to do it that way. For that reason, I think I would leave alpha-beta as recursive search.

Many compilers can also eliminate tail recursion altogether. Alpha-beta search is not tail recursion, but that is something to keep in mind when you are considering writing an iterative version of something instead of a recursive version.

I once wrote a non-recursive version of ACM algorithm 347 in C and found it to be a big win (at the time) but the same code now is not stupendously faster. Also, since I maintained my own stack, I had to be super careful to not overflow the stack. That actually turned out to be a benefit because it forces you to do the right things like searching the smaller partition first and checking for degenerate conditions like already in order or already reverse sorted or things of that nature.

What speed difference do you see when you benchmark (on full optimization) your non-recursive search verses the same algorithm programmed recursively? I guess that the difference is less than 2%.

[Gerd Isenberg]

A nonrecursive alpha--beta search function
by Michael J Sherwin.
(unless someone has beat me to it)

Code: Select all

int Search(alpha, beta, depth) {
    int score;
    int temp;
    int ply;
    int betaCut;

    ply = 1;
    betaCut = FALSE;

    GenMoves();

    while(ply) {
        do {
            if(betaCut || !MakeNextMove()) {
                betaCut = FALSE;
                goto noMoreMoves();
            }
            ply++;
            temp = alpha;
            alpha = -beta;
            beta = -temp;
        } while(depth-- && GenMoves());
        score = Eval();
        if(score > alpha) {
            if(score >= beta)
                betaCut = TRUE;
            else
                alpha = score;
        }
noMoreMoves:
        if(ply--) {
            TakeBackMove();
            depth++;
            temp = alpha;
            alpha = -beta;
            beta = -temp;
        }
    }
    return alpha;   
}

Due to time restraints, I have not tested it.
See RomiChess, learn.c, LearnToHash() for a
similar approach.

Any thoughts on this?

Michael,
like Alessandro i miss some ply-based "stack" for some structures with alpha, beta and that like.

I learned that you should never use goto
I got rid of goto in Movei by having boolean varaible for stop_search so I think that it is better to have some bolean variable no_more_moves and have in the right places
if (no_more_moves) break;
Uri

Uri, don't take that too dogmatical nowadays. No need to jump criss-cross like spagetthi - but some rare gotos to common output labes or to pre-break a loop - specially in none recursive search is not that bad - and most often easier for the compiler as well - a additional boolean variable often implies additional register or even memory usage.

Gerd

[Michael Sherwin]

[code] How do I make this work, the code block that is?
code
// updated non recursive search function.
// an atempt
// just because.

int Search(alpha, beta, depth) {
int ply;
int score;
int betaCut;
int alpha[MAXDEPTH];
int beta[MAXDEPTH];

ply = 1;
betaCut = FALSE;
alpha[1] = alpha;
beta[1] = beta;

GenMoves();

do {
do {
if(betaCut || !MakeNextMove()) {
betaCut = FALSE;
goto noMoreMoves;
}
alpha[ply + 1] = -beta[ply];
beta[ply + 1] = -alpha[ply];
ply++;
} while(--depth && GenMoves());
if(!depth) score = Eval();
if(score > alpha[ply - 1]) {
if(score > beta[ply - 1]) {
betaCut = TRUE;
} else {
alpha[ply - 1] = score;
}
}
noMoreMoves:
if(--ply) {
TakeBack();
depth++;
}
} while(ply);
return alpha[1];
}
[/code][/code]

[Edsel Apostol]

Hi MIchael,

This is the way I think.

<code> your code here </code>

Just replace the <> with [].

[Zach Wegner]

I've been using non-recursion for a while, and I like it. Remember, the main benefit isn't from speed, it's from having access to previous plies' information and the ability to start and stop searches from anywhere. There is not much speed difference, but I use it for SMP(not quite implemented yet though ), and there isn't much reason to use it unless you are planning to use DTS.
But besides that, the macros I use make it just as easy to read. Also, I use a bunch of gotos. They aren't really a problem, if you know where they are going. I am planning on one day going open source, if/when I manage to get my program to an acceptable level, so everyone can see it.

[Uri Blass]

I've been using non-recursion for a while, and I like it. Remember, the main benefit isn't from speed, it's from having access to previous plies' information and the ability to start and stop searches from anywhere. There is not much speed difference, but I use it for SMP(not quite implemented yet though ), and there isn't much reason to use it unless you are planning to use DTS.
But besides that, the macros I use make it just as easy to read. Also, I use a bunch of gotos. They aren't really a problem, if you know where they are going. I am planning on one day going open source, if/when I manage to get my program to an acceptable level, so everyone can see it.

I do not understand the advantage that you talk about.

you can remember previous ply information in a stack so you have excess to previous ply information and it is exactly what I do in my recursive search when I have structs that include some numbers for every ply.

If you claim that having a stack is significantly slower than the main advantage is clearly speed.

I also do not think that stopping a search is a problem in recursive search and I have a variable stop_search and I have in many places in my code
if (stop_search)
{
undomove();
return 0;
}

Note that in the past I used goto similiar to tscp and did not use stop_search but I decided that it is a bad idea because it caused me problems later when I wanted to change the code and have special file for searching root moves.

Uri

[Daniel Shawul]

There is not much speed difference, but I use it for SMP(not quite implemented yet though ), and there isn't much reason to use it unless you are planning to use DTS.

I also started out for the same purpose, but so far i am stuck with a recursive parallel search.

If you claim that having a stack is significantly slower than the main advantage is clearly speed. I also do not think that stopping a search is a problem in recursive search and I have a variable stop_search and I have in many places in my code
if (stop_search)
{
undomove();
return 0;
}

But this only returns from the current ply. What if you want to return
to the root when you see that you have to stop search at ply 10. The way you do it it is done recursively. With non - recursive search you manage the stack yourself (not the OS) so you can go to any ply you like. DTS does this kind of thing which is why non-recursive is better suited.
daniel [/code]

[eric_oldre]

The cost of recursion is very small. It is (once per function) a push of parameters and return address. If you pass by reference or pointer, even a large object only occupies (sizeof address). Recursion is expensive if you pass large classes or structures by value, but that is a pretty rare occurance.

...

Dann, does the size of the local variables inside of the function affect performace much? Would you expect much of a difference for these two?

Eric

Code: Select all

int funcA(int i){
   char myvar[10];
   //do stuff
}

int funcB(int i){
   char myvar[2000];
   //do stuff
}


[Tony van Roon-Werten]

The cost of recursion is very small. It is (once per function) a push of parameters and return address. If you pass by reference or pointer, even a large object only occupies (sizeof address). Recursion is expensive if you pass large classes or structures by value, but that is a pretty rare occurance.

...

Dann, does the size of the local variables inside of the function affect performace much? Would you expect much of a difference for these two?

Eric

Code: Select all

int funcA(int i){
   char myvar[10];
   //do stuff
}

int funcB(int i){
   char myvar[2000];
   //do stuff
}


IIRC there is a difference once you go over 128 byte. But I don't know how much.

Tony

[H.G.Muller]

A nonrecursive alpha--beta search function
by Michael J Sherwin.
(unless someone has beat me to it)

It seems to me that you somehow just hid the recursion, in tacitly assuming that function like TakeBackMove() and MakeNextMove() know which move they should take back, or from which list of moves they should take the next move, and which move is actually the next on that ply.

After all, recursion is nothing more more than the fact that every instance of the routine that calls itself has its own set of local variables. (The fact that it knows where to return to after the routine finishes is only of minor importance: a negamax search is typically called only from two places, the recursive call and the one from the main program, and a simple branch (goto or loop end) could make the distinction based on the ply depth.)

One could rely on the stack structure set up by the compiler to allocate memory for these local variables, or maintain the stack yourself in one or more arrays, indexed by ply number. In the latter case it is indeed easier to dig deeper in the stack: If you would want to access local variables of a previous instance in a portable way in C, you would have to pass pointers (or organize them in a structure, and pass the pointer to that structure), which is rather cumbersome. (Assembler programmers or C hackers would simply access the older stack frames directly, making use of the fact that they know the size of the stack frame, and thus how deep they hav to dig into the stack to recover a certain variabe.)

[H.G.Muller]

Would you expect much of a difference for these two?

Eric

Code: Select all

int funcA(int i){
   char myvar[10];
   //do stuff
}

int funcB(int i){
   char myvar[2000];
   //do stuff
}


On modern CPU's there should hardly be any difference at all. The address of the active stack frame is kept in a register (the 'base pointer' %ebp in Intel Architecture), and all local variables are addressed through an offset to that register. If the offset is smaller than + 128 it can be encoded in a single byte in the instruction stream, otherwise 4 bytes are used. The execution times are exactly the same, the CPU has 2 or 3 specialized adders (Address Generation Units) to add the offset to the base pointer to calculate the actual address and always does this in a single clock cycle without taxing other resources (execution units) in the CPU, no matter how many bits there are in the offset. The code is more compact with the small offsets, though, which could rsult in a larger hit-rate of the instruction cache in cases where the entire code would fit in the I-cache with the small offsets, and would not fit in case of the long offsets.

In the case you give, where the local variable is an array, even that distinction disappears: the larger offset in that case purely comes from the index being large, and the index will not be encoded in the instruction but will be the content of some other register (which can always hold 32 bit). So obtaining the addres amounts to adding a small (1-byte) offset and two registers (one of which the base pointer). The AGUs can also do that in a single CPU clock, in parallel with other stuff.

So in the end the only thing that has a strong impact is the total amount of variable space that you use, if that fits in the level-1 data cache or not. If you have a D-cache of 16KB, and each instance of the recursively called routine uses 2KB, you run out of cache after 8 ply, while with only 200 bytes of local variables you could go to 80 ply... (Typically there is an overhead of 8 bytes on top of the variables you declare explicitly, to store the return address and the previous base pointer, while parameters simply count as local variables that happen to be initialized by the caller. The compiler might add a few temporary storage locations as well.)

[Alvaro Begue]

I also do not think that stopping a search is a problem in recursive search and I have a variable stop_search and I have in many places in my code
if (stop_search)
{
undomove();
return 0;
}

I have a couple of comments on this type of "stop_search" thing. The first one is that instead of calling domove() and undomove(), you can have an object that does the move in the constructor and undoes it in the destructor. This probably has no cost in CPU time (if everything is inlined) and the compiler will take care of undoing the move whenever the object goes out of scope. So you can now break out of the loop, return from the function of goto a place outside the loop, and undomove() will get called automatically.

The other thing I have to say is that for parallel algorithms, you might need to stop many, many searches, and you want to be fast about it. Breaking out of all the recursive calls might not be fast enough. In that case a non-recursive solution will be definitely better. Another alternative is using longjmp to go get out of the recursion in one step. I used this in an old checkers program, and it is kind of a "brutal" way of doing it, but it worked just fine.

I currently use a recursive search function, but I am planning on going non-recursive and implement DTS.

[Dann Corbit]

The cost of recursion is very small. It is (once per function) a push of parameters and return address. If you pass by reference or pointer, even a large object only occupies (sizeof address). Recursion is expensive if you pass large classes or structures by value, but that is a pretty rare occurance.

...

Dann, does the size of the local variables inside of the function affect performace much? Would you expect much of a difference for these two?

Eric

Code: Select all

int funcA(int i){
   char myvar[10];
   //do stuff
}

int funcB(int i){
   char myvar[2000];
   //do stuff
}


IIRC there is a difference once you go over 128 byte. But I don't know how much.

Tony

Not sure why there would be any difference for uninitialized auto variables.

Generally speaking, if you look at the assembly, stack frame variables are allocated with a simple subtraction against the stack. Big parameter varables (other than arrays which are passed by pointer) consume time because they also have to be duplicated (involving memcpy for sizeof object).

[Alvaro Begue]

Not sure why there would be any difference for uninitialized auto variables.

Generally speaking, if you look at the assembly, stack frame variables are allocated with a simple subtraction against the stack. Big parameter varables (other than arrays which are passed by pointer) consume time because they also have to be duplicated (involving memcpy for sizeof object).

It probably doesn't make a whole lot of difference, but if you have only a few local variables, the stack is more likely to fit in the cache completely. That's the difference I can see between small and large stack frames.