out-of-time: what to do?

[flok]

Hi,

When doing iterative deepening, what to do when halfway a search time is up? E.g. I'm calculating depth=7 and halfway that depth time is up.
Should I completely discard any results for that depth?

[syzygy]

How about playing a better move if you found one?

[flok]

How about playing a better move if you found one?

You mean that it is not required to fully search the tree and that the biggest score is the best?

[Henk]

When out-of-time I throw an exception.
When exception is caught it ignores the result of the search (depth).
It memorizes the result of previous searches and it returns the best move found in search(depth-1).

[flok]

When out-of-time I throw an exception.
When exception is caught it ignores the result of the search (depth).
It memorizes the result of previous searches and it returns the best move found in search(depth-1).

Hmmm, if I understood this correctly this is different from what Ronald said. So this means that there's no known best way to go?

[bob]

How about playing a better move if you found one?

You mean that it is not required to fully search the tree and that the biggest score is the best?

All that is required is that you fully search a move before you play it. You can't stop half-way through a single move and back up the scores as though they are finalized. But any move/score backed up to the root before you run out of time should be played...

[bob]

When out-of-time I throw an exception.
When exception is caught it ignores the result of the search (depth).
It memorizes the result of previous searches and it returns the best move found in search(depth-1).

That's an ugly waste of information.

Supposed you have already searched the first move, found that it lost a piece, when you searched the third move in the list, you discover it doesn't lose anything, then you run out of time. Do you REALLY play the move from the last depth that you KNOW loses the game???

[elpapa]

How about playing a better move if you found one?

You mean that it is not required to fully search the tree and that the biggest score is the best?

Just make sure to always search the best move from the previous ply first.

[syzygy]

How about playing a better move if you found one?

You mean that it is not required to fully search the tree and that the biggest score is the best?

I assume that at iteration N the first move you search is the best move found by iteration N-1. If you had not started iteration N, then you would have played this first move.

Suppose the first move searched at iteration N gives a score of +1, and the second move searched at iteration N gives a score of +2. Now your time management code decides that time is up and a move has to be played.

Do you find it reasonable to even consider playing the first move, when you know for a fact that if you had completely finished iteration N, you would have had a better move (either the second move or a later move returning a still better score)?

The answer should be clear: this is not reasonable. It is self-evident that you should play the second move, or more generally, the best move of those that were searched. +2 > + 1, it is that simple. Just use common sense. (There are people that will refuse to answer 2 when asked to calculate 1+1, because they think it is a trick question. Those people should not attempt to program a chess engine.)

(The answer is more difficult if you use PVS and you only know that the second move has failed high. A research of the second move could result in a fail low. I am not considering such cases now. I am assuming that you have completed the search of the second move at iteration N.)

[Henk]

When out-of-time I throw an exception.
When exception is caught it ignores the result of the search (depth).
It memorizes the result of previous searches and it returns the best move found in search(depth-1).

That's an ugly waste of information.

Supposed you have already searched the first move, found that it lost a piece, when you searched the third move in the list, you discover it doesn't lose anything, then you run out of time. Do you REALLY play the move from the last depth that you KNOW loses the game???

Ok it needs a better solution. But if the differences in value are small it is not good to compare values of moves(dept-1) with values of moves (depth).

For instance if you have searched one move (depth) and found it is better than all the moves (depth-1) then that move can be a poor one if there were many more moves that were even better but were searched on (depth-1) while searching them on level depth would have given them a better value.

[edit] This does not hold if you always investigate the best move from the previous ply first. I do not know if that's always the case