Crafty (and others?) time management question

[JVMerlino]

Here's my newbie question of the week, specifically relating to code in Crafty, but may be relevant to any number of other engines.

Generally speaking, programs decide to add more time to their search if they experience a drop in score for the current iteration (call it ply N) compared to the score for ply N-1.

When checking to see if the engine should think longer than the originally allotted time, Crafty first (or, rather, very nearly first) checks to see if there is any score at the root of the search for ply N. If there isn't one, then Crafty feels that it's ok to bail on the search. After this check, it goes through several other checks that compare the score for ply N compared to ply N-1, as well the amount of time used, as I expected.

However, isn't this initial check potentially dangerous, depending on the relative scores of ply N-1 and N-2? If ply N-1 showed a horrible drop in score, but the search was completed for that ply, can you really trust that the chosen move is the best? Wouldn't you rather allocate more time for the same reason that you would for comparing ply N against ply N-1?

Or is this method of bailing out safe once you have reached a solid enough search/evaluation implementation (meaning, a lot better than what I have now)?

I hope that made sense....

jm (n00b)

[bob]

Here's my newbie question of the week, specifically relating to code in Crafty, but may be relevant to any number of other engines.

Generally speaking, programs decide to add more time to their search if they experience a drop in score for the current iteration (call it ply N) compared to the score for ply N-1.

When checking to see if the engine should think longer than the originally allotted time, Crafty first (or, rather, very nearly first) checks to see if there is any score at the root of the search for ply N. If there isn't one, then Crafty feels that it's ok to bail on the search. After this check, it goes through several other checks that compare the score for ply N compared to ply N-1, as well the amount of time used, as I expected.

However, isn't this initial check potentially dangerous, depending on the relative scores of ply N-1 and N-2? If ply N-1 showed a horrible drop in score, but the search was completed for that ply, can you really trust that the chosen move is the best? Wouldn't you rather allocate more time for the same reason that you would for comparing ply N against ply N-1?

Or is this method of bailing out safe once you have reached a solid enough search/evaluation implementation (meaning, a lot better than what I have now)?

I hope that made sense....

jm (n00b)

Good question. My basic approach has been to deal with two issue.

(1) When I start a new iteration, once I get a best score back, before I decide to give up when time runs out, I compare this score to the previous iteration's score as you mentioned. If this score is worse, then the extra ply has shown me that my previous best move might well have a problem one ply shallower could not see. I want to search longer to see if a move further down in the move list can solve this. It is possible that the best move fails low to a deeper tactical threat that the current search sees, and that another move won't have that problem. It is also quite possible, but not as probable, that all moves will look bad once we get to this depth, and extra time won't help.

(2) before I time out, I never do so until the current root move has been searched,. I do this because the first move takes the longest, and once is has been completed, the rest of the moves fly by. UNLESS a new move is going to rise to the top and become best. When time runs out, I set a note to this effect, but continue searching until I either complete the current root move, or until the 2x time limit is reached where I immediately give up. This prevents quitting just before a new move becomes best. If time runs out and I have not yet got a score for the first move back, I quit instantly, assuming I have not failed low at the root, as there is not a lot of hope that even a 2x time extension will be enough to help.

I am not sure I see a point in searching iteration N+1, assuming iteration N ends with a poor score. If depth N saw a problem, it is likely that depth N+1 will see the same problem or even worse...

[JVMerlino]

Good question. My basic approach has been to deal with two issue.

(1) When I start a new iteration, once I get a best score back, before I decide to give up when time runs out, I compare this score to the previous iteration's score as you mentioned. If this score is worse, then the extra ply has shown me that my previous best move might well have a problem one ply shallower could not see. I want to search longer to see if a move further down in the move list can solve this. It is possible that the best move fails low to a deeper tactical threat that the current search sees, and that another move won't have that problem. It is also quite possible, but not as probable, that all moves will look bad once we get to this depth, and extra time won't help.

(2) before I time out, I never do so until the current root move has been searched,. I do this because the first move takes the longest, and once is has been completed, the rest of the moves fly by. UNLESS a new move is going to rise to the top and become best. When time runs out, I set a note to this effect, but continue searching until I either complete the current root move, or until the 2x time limit is reached where I immediately give up. This prevents quitting just before a new move becomes best. If time runs out and I have not yet got a score for the first move back, I quit instantly, assuming I have not failed low at the root, as there is not a lot of hope that even a 2x time extension will be enough to help.

I am not sure I see a point in searching iteration N+1, assuming iteration N ends with a poor score. If depth N saw a problem, it is likely that depth N+1 will see the same problem or even worse...

Ok, I understand. I've implemented something similar to what Crafty has (although the details are different) with the exception of waiting to finish the current root move before bailing. Right now I just unwind the tree.

Thanks, Bob!

jm