Implementing smart time control

[Rohan Padhye]

Hello, I am a developer of an amateur chess engine. I have been able to get it to work crudely with time control but I want it to be a little smarter. I need some suggestions. Here is how my engine works now:

Let's say the engine looks at the current clock, current move count, and the time level (X moves in Y minutes) and finally calculates a number (say T seconds) to spend on this move. My approach is thus: ]

Start searching with iterative deepening from d=2 to d=maxDepth. Also, schedule a timed task that will interrupt the search and retreive the best move possible after T seconds (provided that the search has not already finished upto maxDepth early, or the user has not forced the AI to move now using the '?' command).

My timer works perfectly, nicely interrupting the ongoing search of depth D after T seconds and returning the bestMoveSoFar from the D-1 search. But my problem is this:

Let's say for example, I have calculated and decided I should spend at most T=40sec on this move. My engine searches to 6 ply in about 20 seconds. Now, the search of depth 7 ply would have completed after around 1:30. So after 40 seconds the timer task interrupts the search and returns the bestMoveSoFar of depth 6 as expected. But then, I have wasted the last 20 seconds on searching to a deep level which would have never finished anyway. I want to know how I can minimize this wastage. I would like someone to point out a good way of deciding before hand "Will a deeper search complete within the given time frame? Or should I save that extra time and just return now?".

Thanks for any help...

[Edmund]

The average branching factor of the top engines nowadays is about 2. This means one iteration examines about two times as many nodes as the previous iteration. So what you can do is to only start a new iteration, if at least two times of the previous iteration's time are still left. A further addition could be not to interrupt the search after the given movetime if the iteration hasn't finished so far, but allocate more time for this iteration. Or you only cut if a PV has already been returned which didn't fail low.

But the first step for you would be to decide on a proper average branching factor for your engine.

[H.G.Muller]

It is indeed more efficient to not start iterations that you are pretty sure you will not be able to finish. So what I do if the target time is 40 sec, and I know that my engine takes about 3 times longer for every subequent iteration (on average), I don't start a new iteration when it has already searched for 20 sec or more. This means that sometimes it searches for 21 sec, sometimes for 60. But on the average that is about 40 sec. You just have to be careful to built in a sizable safety margin at the last moves just before the time control, as sometimes an iteration can take unexpectedly long.

A somewhat more refined way, which requires a smaller safety margin, is to test the time not after every completed iteration, but after every move in the root, and already stop before it finishes a complete iteration if some fraction of the target time is exceeded. Then the variablity of the search time is about 2-3 times smaller than when you alwas complete the iteration.

If you use this latter method, you can refine it further by giving the engine a (limited) amount of extra time in a case where the best move of the iteration it is working on has a score that is much lower than the score of the previous iteration. This means you were about to commit a blunder, which you found out on deeper search, and giving extra time on how to rescue the situation by some other move is very well invested. So you could for intance allow it to think upto twice the target time if the score is too low, or until the score approches that of the previous iteration, whichever occurs earlier.

It would in all cases be good to have an emergency abort like the one you are currently using, to make sure that the engine never loses on time, even in very averse circumstnces.

[Rohan Padhye]

But the first step for you would be to decide on a proper average branching factor for your engine.

I am assuming the average branching factor is not platform-dependent right? If so, does one usually sit and draw conclusions out of manual observation of branching factors or should I let the engine calculate that for itself (from previous moves and previous iterations). The latter should be more effective, but also difficult to implement and of course error prone. For example, if the previous move was say a check evasion where the branching factor is low (since therer are few legal moves) the results could be wrong.

A somewhat more refined way, which requires a smaller safety margin, is to test the time not after every completed iteration, but after every move in the root, and already stop before it finishes a complete iteration if some fraction of the target time is exceeded. Then the variablity of the search time is about 2-3 times smaller than when you alwas complete the iteration.

If you use this latter method, you can refine it further by giving the engine a (limited) amount of extra time in a case where the best move of the iteration it is working on has a score that is much lower than the score of the previous iteration. This means you were about to commit a blunder, which you found out on deeper search, and giving extra time on how to rescue the situation by some other move is very well invested. So you could for intance allow it to think upto twice the target time if the score is too low, or until the score approches that of the previous iteration, whichever occurs earlier.

This seems like a nice idea, but I'm afraid that extra time could add up and cause problems in the future, if not implemented sparingly. Also, I suppose the last few moves of the session (in tournament mode) should be given no extra time otherwise there will be a real time crunch.

I'll see what I can implement, though. Thank you very much for your help

PS: What is the average branching factor for amateur engines? I know strong engines would get it down to 2-4 or so... But my engine has a branching factor of around 8. Is that like "Hmmm, your search algorithms need to be improved" or "Arrrghhh! Toss your program out the window"?

[Edmund]

The branching factor is platform independent. It mainly depends on the quality of move ordering and pruning techniques used. The example you mention with the limited number of legal moves is not quite accurate as in each iteration you will still be faced with the same number of moves. Irregular branching factors occur if you have too many fail-highs/lows in a search. Anyway there is not much to do about that.

I would suggest to calculate the branching factors automatically for a couple of games and analyze them. So in the end you can find an appropriate average.

if you always consider "moves to next timecontrol" + 1 and restrict the movetime to less than 2 times the actual movetime you won't have any problems.
eg:
if you have 2 moves to go, 6 min are left and each move takes the full time + extension:
move 1: [6 / (2+1)] * 2 = 4min
move 2: [2 / (1+1)] * 2 = 2min


Concerning the average branching factor.
Just minimax has a branching factor of about 36. Thats about the average number of moves in each position.
Alpha beta can reduce that to the square-root .. 6. But this would require perfect move ordering.
Other ways to enhance this is through pruning and early cutoffs. Most commonly used: Transposition tables, Nullmove pruning and Late Move Reduction.

A Branching Factor of 8 indeed seems a little bit too high. What time of search algorithm are you using? What type of prunings are implemented?

[Rohan Padhye]

if you always consider "moves to next timecontrol" + 1 and restrict the movetime to less than 2 times the actual movetime you won't have any problems.
eg:
if you have 2 moves to go, 6 min are left and each move takes the full time + extension:
move 1: [6 / (2+1)] * 2 = 4min
move 2: [2 / (1+1)] * 2 = 2min

This seems like a good idea, since the last move in the session will always take a maximum of the amount of time left. I'll try implementing this.

A Branching Factor of 8 indeed seems a little bit too high. What time of search algorithm are you using? What type of prunings are implemented?

I just about started development right now, so I have only implemented Alpha-Beta and transposition tables. I need to first clean out bugs, if any, and sort out the irregularities of the engine before optimizing the search and improving the evaluation function.

I am having a lot of trouble finding the best method of move ordering - Specifically whether to sort the entire move list once, or keep it unsorted and remove the next best one at a time, or tune the move generator to generate moves in an ordered fashion in the first place...

[Edmund]

I am having a lot of trouble finding the best method of move ordering - Specifically whether to sort the entire move list once, or keep it unsorted and remove the next best one at a time, or tune the move generator to generate moves in an ordered fashion in the first place...

First of all, if you have a TT-move .. just play it .. even before generating the moves. This saves you a lot of time in case it brings a cutoff, what is often the case.

Next .. please consider that as your engine gets stronger the ratio of positions where the first move results in a cutoff approaches 80-90%. So doing an quicksort for example at every node is very expensive. Most engines just always pick the next best move from the list.

Anyway, thats not what I meant by good move ordering. It is much more important how you determine the value of a move. Some strategies are SEE, Killer moves, Piece-Square-Tables, History Heuristic.

[Rohan Padhye]

What about a weight strategy that some programs (i think REBEL) use? Assign a 'weight' to each move after generating them. This can be done in O(n) time. Then the selectBestMove() goes through the entire list and picks the heaviest move. Assuming that the cut-off occurs after k moves this will be a further O(kn)... If k < log(n) [around 5] then this is faster than sorting the entire list at once. I havn't tried this out yet, but I'm assuming my analysis is at least correct, if not optimal.

Anyway, thats not what I meant by good move ordering. It is much more important how you determine the value of a move. Some strategies are SEE, Killer moves, Piece-Square-Tables, History Heuristic.

I am currently using transposition tables and SEE. Soon to implement killer moves and history heuristic. I use piece-square-tables in my evaluation function, not in move ordering

[Edmund]

Next .. please consider that as your engine gets stronger the ratio of positions where the first move results in a cutoff approaches 80-90%. So doing an quicksort for example at every node is very expensive. Most engines just always pick the next best move from the list.

Actually I agreed with you on this already

Piece-Square-Tables involve not much effort and are very effective .. you should give it a try