Iterative Deepening Question

[tttony]

Take a look at this: https://web.archive.org/web/20071031095 ... ration.htm

[Sven]

I meant "ID loop", of course, not "IID loop".

[bob]

Thanks Mr. Hyatt!
Yes, that's what how my Alpha-Beta function is called normally.
And what about failing high\low at the root...what to do in that situation?

Thanks again,
David Cimbalista

If you fail high at the root, there are several possible choices.

Most common is to simply increase beta and re-search the move. Repeatedly until the fail highs stop and you get an exact score. An alternative is to just move on with the rest of the root moves. If nothing else fails high, you can just play the fail high move and move on. But if a second move fails high, now you are at a key point where you don't know which is best. So you can relax beta, and re-search the first move, get a good score (which gives you a good new beta value, then you re-search the second. If it fails low, you are done, if it fails high, you have to remember that as your best move and again you can keep on searching until the iteration ends or another move fails high...

I personally immediately re-search with a ramped-up beta bound as I want to know what the real score is before I move on.

Fail lows are just as problematic...

[bob]

Hi,
I had a question about iterative deepening.
Basically, at the root, when I get a fail-low and a fail-high what should I do?
I've tried in pseudocode:

Code: Select all

if(Score > beta)
Raise beta by x centipawns and move onto the next root move
if&#40;Score < alpha&#41;
Lower alpha by x centipawns and move onto the next root move

Where x is some arbitrary value(I've tried values of 100, 200, and infinity).
The reason I'm bringing this up is the strange output from my engine when I tell it to move after g3 e5 a3 Qh4--white should be winning by about 800 centipawns. Yet here is the output from the engine:
[...]
I'm thinking I'm doing something wrong when it sees It's winning a queen after one root move and then when the next move is only better by about 20 centipawns, it's doing something screwy with alpha and beta!?

Also, I have one more question:
In iterative deepening should I be calling alpha beta like this:

Code: Select all

int Score = AlphaBeta(rootAlpha, rootBeta, depth - 1);

Or like this:

Code: Select all

int Score = -AlphaBeta(-rootAlpha, -rootBeta, depth - 1);

Or something else?
And how should I be handling the value returned from the Alpha-Beta search(should I check for greater than beta, less than alpha, or some other way)?

Thanks for the help!
David Cimbalista

In general you reverse the sign AND interchange alpha and beta.

So more like:

score = -AlphaBeta(-beta, -alpha, depth - 1)

assuming your AlphaBeta function looks like this:

int AlphaBeta(int alpha, int beta, int depth)

I don't think this is right in his case. I understood he was talking about the iterative deepening loop, not about the search function itself. In the ID loop where we are still at root we call:

Code: Select all

score = AlphaBeta(rootAlpha, rootBeta, depth);

while in the full-width search function (at root as well as below) we call:

Code: Select all

score = -AlphaBeta(-beta, -alpha, depth - 1);

Regarding the other question, the typical handling within the ID loop looks similar to this:

Code: Select all

for (depth = 1, stop = false; !stop; ++depth) {
    rootAlpha = score - WindowSize;
    rootBeta = score + WindowSize;
    score = AlphaBeta(rootAlpha, rootBeta, depth);
    if (score >= rootBeta) {
        score = AlphaBeta(rootAlpha, +INFINITY, depth);
    } else
    if &#40;score <= rootAlpha&#41; &#123;
        score = AlphaBeta&#40;-INFINITY, rootBeta, depth&#41;;
    &#125;
&#125;

I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.

When someone says "iterative deepening" I use the traditional definition, which is what is done at the root. "internal iterative deepening" is a different topic and there you are correct. Only question is, which is he talking about???

[Sven]

Hi,
I had a question about iterative deepening.
Basically, at the root, when I get a fail-low and a fail-high what should I do?
I've tried in pseudocode:

Code: Select all

if(Score > beta)
Raise beta by x centipawns and move onto the next root move
if&#40;Score < alpha&#41;
Lower alpha by x centipawns and move onto the next root move

Where x is some arbitrary value(I've tried values of 100, 200, and infinity).
The reason I'm bringing this up is the strange output from my engine when I tell it to move after g3 e5 a3 Qh4--white should be winning by about 800 centipawns. Yet here is the output from the engine:
[...]
I'm thinking I'm doing something wrong when it sees It's winning a queen after one root move and then when the next move is only better by about 20 centipawns, it's doing something screwy with alpha and beta!?

Also, I have one more question:
In iterative deepening should I be calling alpha beta like this:

Code: Select all

int Score = AlphaBeta(rootAlpha, rootBeta, depth - 1);

Or like this:

Code: Select all

int Score = -AlphaBeta(-rootAlpha, -rootBeta, depth - 1);

Or something else?
And how should I be handling the value returned from the Alpha-Beta search(should I check for greater than beta, less than alpha, or some other way)?

Thanks for the help!
David Cimbalista

In general you reverse the sign AND interchange alpha and beta.

So more like:

score = -AlphaBeta(-beta, -alpha, depth - 1)

assuming your AlphaBeta function looks like this:

int AlphaBeta(int alpha, int beta, int depth)

I don't think this is right in his case. I understood he was talking about the iterative deepening loop, not about the search function itself. In the ID loop where we are still at root we call:

Code: Select all

score = AlphaBeta(rootAlpha, rootBeta, depth);

while in the full-width search function (at root as well as below) we call:

Code: Select all

score = -AlphaBeta(-beta, -alpha, depth - 1);

Regarding the other question, the typical handling within the ID loop looks similar to this:

Code: Select all

for (depth = 1, stop = false; !stop; ++depth) {
    rootAlpha = score - WindowSize;
    rootBeta = score + WindowSize;
    score = AlphaBeta(rootAlpha, rootBeta, depth);
    if (score >= rootBeta) {
        score = AlphaBeta(rootAlpha, +INFINITY, depth);
    } else
    if &#40;score <= rootAlpha&#41; &#123;
        score = AlphaBeta&#40;-INFINITY, rootBeta, depth&#41;;
    &#125;
&#125;

I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.

When someone says "iterative deepening" I use the traditional definition, which is what is done at the root. "internal iterative deepening" is a different topic and there you are correct. Only question is, which is he talking about???

He is not talking about "internal iterative deepening", and nor am I. What you call "traditional definition" (of iterative deepening) seems to be different from what other people think about it. Talking about Crafty, we are at "iterate.c" level (but with aspiration window - I did not look into recent Crafty code to check whether that is present there but older Crafty did not have it as far as I know).

[theturk1234]

I'm only using ID, not IID. I'll take a look at all the suggestions... thank you again!

David

[theturk1234]

Also, you're right, I'm not using PVS... it's literally next on my list!

[bob]

Hi,
I had a question about iterative deepening.
Basically, at the root, when I get a fail-low and a fail-high what should I do?
I've tried in pseudocode:

Code: Select all

if(Score > beta)
Raise beta by x centipawns and move onto the next root move
if&#40;Score < alpha&#41;
Lower alpha by x centipawns and move onto the next root move

Where x is some arbitrary value(I've tried values of 100, 200, and infinity).
The reason I'm bringing this up is the strange output from my engine when I tell it to move after g3 e5 a3 Qh4--white should be winning by about 800 centipawns. Yet here is the output from the engine:
[...]
I'm thinking I'm doing something wrong when it sees It's winning a queen after one root move and then when the next move is only better by about 20 centipawns, it's doing something screwy with alpha and beta!?

Also, I have one more question:
In iterative deepening should I be calling alpha beta like this:

Code: Select all

int Score = AlphaBeta(rootAlpha, rootBeta, depth - 1);

Or like this:

Code: Select all

int Score = -AlphaBeta(-rootAlpha, -rootBeta, depth - 1);

Or something else?
And how should I be handling the value returned from the Alpha-Beta search(should I check for greater than beta, less than alpha, or some other way)?

Thanks for the help!
David Cimbalista

In general you reverse the sign AND interchange alpha and beta.

So more like:

score = -AlphaBeta(-beta, -alpha, depth - 1)

assuming your AlphaBeta function looks like this:

int AlphaBeta(int alpha, int beta, int depth)

I don't think this is right in his case. I understood he was talking about the iterative deepening loop, not about the search function itself. In the ID loop where we are still at root we call:

Code: Select all

score = AlphaBeta(rootAlpha, rootBeta, depth);

while in the full-width search function (at root as well as below) we call:

Code: Select all

score = -AlphaBeta(-beta, -alpha, depth - 1);

Regarding the other question, the typical handling within the ID loop looks similar to this:

Code: Select all

for (depth = 1, stop = false; !stop; ++depth) {
    rootAlpha = score - WindowSize;
    rootBeta = score + WindowSize;
    score = AlphaBeta(rootAlpha, rootBeta, depth);
    if (score >= rootBeta) {
        score = AlphaBeta(rootAlpha, +INFINITY, depth);
    } else
    if &#40;score <= rootAlpha&#41; &#123;
        score = AlphaBeta&#40;-INFINITY, rootBeta, depth&#41;;
    &#125;
&#125;

I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.

When someone says "iterative deepening" I use the traditional definition, which is what is done at the root. "internal iterative deepening" is a different topic and there you are correct. Only question is, which is he talking about???

He is not talking about "internal iterative deepening", and nor am I. What you call "traditional definition" (of iterative deepening) seems to be different from what other people think about it. Talking about Crafty, we are at "iterate.c" level (but with aspiration window - I did not look into recent Crafty code to check whether that is present there but older Crafty did not have it as far as I know).

Iterative deepening is exactly what goes on in iterate.c, and yes, I have used aspiration windows in every version of Crafty that was distributed. As has PVS always been there. That is what I call "iterative deepening" which was as defined by Slate in chess 4.x...

[hgm]

This is right in principle when using PVS (which I believe does not apply in the given case) but you don't need to handle that in the IID loop, at least if your normal search function implements PVS correctly. The top level ID loop only triggers the root search once per depth, and possibly more than once with a larger window if the first call failed high or low. Certainly there are also more advanced ways of doing it but the above is the basic idea.

Even if you put the deepening loop outside the search function, I don't think it changes much: when a move fails high compared to the aspirated window, the search function gets a beta cutoff and returns immediately. The move causing the cutoff presumably became hash move, so recalling the search function with increased beta will amount to a re-search of the move that failed high. Any moves that were already searched at that depth and failed low will still fail low compared to the new window, (especially after the re-search has increased alpha to a value above the old beta), and will be satisfied from the hash table.

[Sven]

This is right in principle when using PVS (which I believe does not apply in the given case) but you don't need to handle that in the IID loop, at least if your normal search function implements PVS correctly. The top level ID loop only triggers the root search once per depth, and possibly more than once with a larger window if the first call failed high or low. Certainly there are also more advanced ways of doing it but the above is the basic idea.

Even if you put the deepening loop outside the search function, I don't think it changes much: when a move fails high compared to the aspirated window, the search function gets a beta cutoff and returns immediately. The move causing the cutoff presumably became hash move, so recalling the search function with increased beta will amount to a re-search of the move that failed high. Any moves that were already searched at that depth and failed low will still fail low compared to the new window, (especially after the re-search has increased alpha to a value above the old beta), and will be satisfied from the hash table.

I don't "put the deepening loop outside the search function", being outside is the standard. If you do it differently then this is probably caused by using IID in your code. Apart from that, what you write is correct but I don't see where I claimed the opposite of that ...