out-of-time: what to do?

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.
flok

out-of-time: what to do?

Post by flok » Fri Aug 09, 2013 8:44 pm

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
Posts: 4374
Joined: Tue Feb 28, 2012 10:56 pm

Re: out-of-time: what to do?

Post by syzygy » Fri Aug 09, 2013 9:05 pm

How about playing a better move if you found one?

flok

Re: out-of-time: what to do?

Post by flok » Fri Aug 09, 2013 9:14 pm

syzygy wrote: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
Posts: 5491
Joined: Mon May 27, 2013 8:31 am

Re: out-of-time: what to do?

Post by Henk » Fri Aug 09, 2013 9:19 pm

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

Re: out-of-time: what to do?

Post by flok » Fri Aug 09, 2013 10:05 pm

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

Re: out-of-time: what to do?

Post by bob » Fri Aug 09, 2013 10:15 pm

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

Re: out-of-time: what to do?

Post by bob » Fri Aug 09, 2013 10:16 pm

Henk wrote: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
Posts: 191
Joined: Sun Jan 18, 2009 10:27 pm
Location: Sweden
Full name: Patrik Karlsson

Re: out-of-time: what to do?

Post by elpapa » Fri Aug 09, 2013 10:56 pm

flok wrote:
syzygy wrote: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
Posts: 4374
Joined: Tue Feb 28, 2012 10:56 pm

Re: out-of-time: what to do?

Post by syzygy » Sat Aug 10, 2013 12:52 am

flok wrote:
syzygy wrote: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
Posts: 5491
Joined: Mon May 27, 2013 8:31 am

Re: out-of-time: what to do?

Post by Henk » Sat Aug 10, 2013 7:46 am

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

Post Reply