Iterative Deepening Question
Moderators: hgm, Rebel, chrisw
-
- Posts: 268
- Joined: Sun Apr 24, 2011 12:33 am
Re: Iterative Deepening Question
Take a look at this: https://web.archive.org/web/20071031095 ... ration.htm
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Iterative Deepening Question
I meant "ID loop", of course, not "IID loop".
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Iterative Deepening Question
If you fail high at the root, there are several possible choices.theturk1234 wrote: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
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...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Iterative Deepening Question
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 Schüle wrote: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:bob wrote:In general you reverse the sign AND interchange alpha and beta.theturk1234 wrote: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:Where x is some arbitrary value(I've tried values of 100, 200, and infinity).Code: Select all
if(Score > beta) Raise beta by x centipawns and move onto the next root move if(Score < alpha) Lower alpha by x centipawns and move onto the next root move
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:Or like this:Code: Select all
int Score = AlphaBeta(rootAlpha, rootBeta, depth - 1);
Or something else?Code: Select all
int Score = -AlphaBeta(-rootAlpha, -rootBeta, depth - 1);
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
So more like:
score = -AlphaBeta(-beta, -alpha, depth - 1)
assuming your AlphaBeta function looks like this:
int AlphaBeta(int alpha, int beta, int depth)while in the full-width search function (at root as well as below) we call:Code: Select all
score = AlphaBeta(rootAlpha, rootBeta, depth);
Regarding the other question, the typical handling within the ID loop looks similar to this:Code: Select all
score = -AlphaBeta(-beta, -alpha, depth - 1);
I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.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 (score <= rootAlpha) { score = AlphaBeta(-INFINITY, rootBeta, depth); } }
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Iterative Deepening Question
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).bob wrote: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 Schüle wrote: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:bob wrote:In general you reverse the sign AND interchange alpha and beta.theturk1234 wrote: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:Where x is some arbitrary value(I've tried values of 100, 200, and infinity).Code: Select all
if(Score > beta) Raise beta by x centipawns and move onto the next root move if(Score < alpha) Lower alpha by x centipawns and move onto the next root move
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:Or like this:Code: Select all
int Score = AlphaBeta(rootAlpha, rootBeta, depth - 1);
Or something else?Code: Select all
int Score = -AlphaBeta(-rootAlpha, -rootBeta, depth - 1);
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
So more like:
score = -AlphaBeta(-beta, -alpha, depth - 1)
assuming your AlphaBeta function looks like this:
int AlphaBeta(int alpha, int beta, int depth)while in the full-width search function (at root as well as below) we call:Code: Select all
score = AlphaBeta(rootAlpha, rootBeta, depth);
Regarding the other question, the typical handling within the ID loop looks similar to this:Code: Select all
score = -AlphaBeta(-beta, -alpha, depth - 1);
I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.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 (score <= rootAlpha) { score = AlphaBeta(-INFINITY, rootBeta, depth); } }
-
- Posts: 52
- Joined: Tue Jul 12, 2016 5:28 am
Re: Iterative Deepening Question
I'm only using ID, not IID. I'll take a look at all the suggestions... thank you again!
David
David
-
- Posts: 52
- Joined: Tue Jul 12, 2016 5:28 am
Re: Iterative Deepening Question
Also, you're right, I'm not using PVS... it's literally next on my list!
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Iterative Deepening Question
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...Sven Schüle wrote: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).bob wrote: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 Schüle wrote: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:bob wrote:In general you reverse the sign AND interchange alpha and beta.theturk1234 wrote: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:Where x is some arbitrary value(I've tried values of 100, 200, and infinity).Code: Select all
if(Score > beta) Raise beta by x centipawns and move onto the next root move if(Score < alpha) Lower alpha by x centipawns and move onto the next root move
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:Or like this:Code: Select all
int Score = AlphaBeta(rootAlpha, rootBeta, depth - 1);
Or something else?Code: Select all
int Score = -AlphaBeta(-rootAlpha, -rootBeta, depth - 1);
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
So more like:
score = -AlphaBeta(-beta, -alpha, depth - 1)
assuming your AlphaBeta function looks like this:
int AlphaBeta(int alpha, int beta, int depth)while in the full-width search function (at root as well as below) we call:Code: Select all
score = AlphaBeta(rootAlpha, rootBeta, depth);
Regarding the other question, the typical handling within the ID loop looks similar to this:Code: Select all
score = -AlphaBeta(-beta, -alpha, depth - 1);
I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.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 (score <= rootAlpha) { score = AlphaBeta(-INFINITY, rootBeta, depth); } }
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Iterative Deepening Question
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 Schüle wrote: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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Iterative Deepening Question
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 ...hgm wrote: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 Schüle wrote: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.