Crafty (and others?) time management question

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
JVMerlino
Posts: 979
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Crafty (and others?) time management question

Post by JVMerlino » Tue Apr 14, 2009 1:43 am

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
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Crafty (and others?) time management question

Post by bob » Tue Apr 14, 2009 5:05 am

JVMerlino wrote: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...

User avatar
JVMerlino
Posts: 979
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Crafty (and others?) time management question

Post by JVMerlino » Tue Apr 14, 2009 5:56 pm

bob wrote:
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

Post Reply