Iterative Deepening Question

[theturk1234]

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:

Code: Select all

Chess 230716
A chess engine by David Cimbalista
Copyright (c) 2015
position startpos
moves g2g3 e7e5 a2a3 d8h4
go wtime 30000 btime 30000
info depth 1
info multipv 1 depth 1 seldepth 4 score cp 760 hashfull 4 pv g3h4 time 320 nodes
 123204 nps 383000
info depth 2
info multipv 1 depth 2 seldepth 5 score cp 760 hashfull 4 pv g3h4 time 324 nodes
 123264 nps 379000
info depth 3
info multipv 1 depth 3 seldepth 6 score cp 0 hashfull 4 pv a1a2 time 328 nodes 1
23536 nps 375000
info depth 4
info multipv 1 depth 4 seldepth 7 score cp 5 hashfull 5 pv c2c4 b8a6 g1h3 time 3
40 nodes 124797 nps 365000
info depth 5
info multipv 1 depth 5 seldepth 8 score cp 5 hashfull 5 pv c2c4 b8a6 g1h3 time 3
50 nodes 125243 nps 356000
info depth 6
info multipv 1 depth 6 seldepth 9 score cp 25 hashfull 7 pv c2c4 h4h3 d2d3 b8a6
c1h6 time 368 nodes 128692 nps 348000
info depth 7
info multipv 1 depth 7 seldepth 10 score cp 5 hashfull 11 pv c2c4 h4h3 d2d3 h3g2
 g1h3 b8a6 time 406 nodes 144188 nps 354000
info depth 8
info multipv 1 depth 8 seldepth 11 score cp 0 hashfull 34 pv c2c4 h4h3 d2d3 h3g4
 f2f3 b8a6 g1h3 time 543 nodes 200917 nps 369000
info depth 9
bestmove c2c4

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

[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:

Code: Select all

Chess 230716
A chess engine by David Cimbalista
Copyright (c) 2015
position startpos
moves g2g3 e7e5 a2a3 d8h4
go wtime 30000 btime 30000
info depth 1
info multipv 1 depth 1 seldepth 4 score cp 760 hashfull 4 pv g3h4 time 320 nodes
 123204 nps 383000
info depth 2
info multipv 1 depth 2 seldepth 5 score cp 760 hashfull 4 pv g3h4 time 324 nodes
 123264 nps 379000
info depth 3
info multipv 1 depth 3 seldepth 6 score cp 0 hashfull 4 pv a1a2 time 328 nodes 1
23536 nps 375000
info depth 4
info multipv 1 depth 4 seldepth 7 score cp 5 hashfull 5 pv c2c4 b8a6 g1h3 time 3
40 nodes 124797 nps 365000
info depth 5
info multipv 1 depth 5 seldepth 8 score cp 5 hashfull 5 pv c2c4 b8a6 g1h3 time 3
50 nodes 125243 nps 356000
info depth 6
info multipv 1 depth 6 seldepth 9 score cp 25 hashfull 7 pv c2c4 h4h3 d2d3 b8a6
c1h6 time 368 nodes 128692 nps 348000
info depth 7
info multipv 1 depth 7 seldepth 10 score cp 5 hashfull 11 pv c2c4 h4h3 d2d3 h3g2
 g1h3 b8a6 time 406 nodes 144188 nps 354000
info depth 8
info multipv 1 depth 8 seldepth 11 score cp 0 hashfull 34 pv c2c4 h4h3 d2d3 h3g4
 f2f3 b8a6 g1h3 time 543 nodes 200917 nps 369000
info depth 9
bestmove c2c4

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)

[theturk1234]

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

[hgm]

This seems a question about aspiration ratherthan iterative deepening. Normally beta would be +INFINITE in the root, so you would never score >= beta.

For aspiration, when a search fails high or low, you would not start a new iteraton before you resolved that by redoing the same iteration with a larger window. When a move fails high you would redo it immediately,with raised beta, until it does not fail high anymore. Then you would set a null window on its scorefor the remaining movesof that iteration (PVS). When a move fails low you would just continue with the next move. Only when all moves fail low, you would redo the iteration with lowered alpha.

[theturk1234]

OK, I think I'm beginning to understand! I just thought that an immediate research of a root move would be WAY too wasteful(think like at depth 20): it might take a couple of seconds, so that's really what I should be doing?

Thanks,
David

[hgm]

What else could you do? The score would be just a lower bound. If you would continue to search other moves with the same window you would have to push their score lower than actually needed, which might waste time. If you rais the window without knowing howmuch you should raise it, you might raiseit too much, and the results could be useless.

[theturk1234]

Ok, that sounds logical. That would explain the strange behavior I'm getting.

Thanks for the help!

David Cimbalista

[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.

[Sven]

This seems a question about aspiration rather than iterative deepening. Normally beta would be +INFINITE in the root, so you would never score >= beta.

Yes, without aspiration, but the OP clearly is using an aspiration window (and also no PVS).

For aspiration, when a search fails high or low, you would not start a new iteraton before you resolved that by redoing the same iteration with a larger window. When a move fails high you would redo it immediately,with raised beta, until it does not fail high anymore. Then you would set a null window on its scorefor the remaining movesof that iteration (PVS). When a move fails low you would just continue with the next move. Only when all moves fail low, you would redo the iteration with lowered alpha.

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.

[Sven]

Ok, that sounds logical. That would explain the strange behavior I'm getting.

It doesn't, IMO. See my reply to Bob's post, maybe there is some clue for you in it. The ID loop does not deal with searching single root moves, it only triggers a whole root search. So your problem might be a different one.