out-of-time: what to do?

[syzygy]

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

Read again. At iteration N everybody first searches the move that was best at iteration N-1. Nobody is comparing scores from iteration N with scores from iteration N-1 when selecting a move to play.

[Henk]

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

Read again. At depth = N everybody first searches the move that was best at depth = N-1. Nobody is comparing scores at depth = N with scores at depth = N - 1.

Yes you are right. I hope everybody first searches the move that was best at depth = N-1. At least I did not.

[hgm]

The whole point of iterative deepening is to get a likely g\best-move candidate, so you can search it first. Even micro-Max does that...

[Henk]

The whole point of iterative deepening is to get a likely g\best-move candidate, so you can search it first. Even micro-Max does that...

I do not do iterative deepening when not PV. Also I compute a best move from N-2 not N-1. Also a good capture, if there is one, is almost always the best move.

[hgm]

Well, iff you start with the previous best move, even if the iteration does not finish, as long as it finishes one move, you could play the move of that unfinished iteration safely. As in the worst case it is still the best of the previous iteration, and you miss a possibility to let a later move supercede it.

'Out of time' is a relative notion at most time controls; both incremental/sudden-death and classical TC allow you to be flexible. So my engines have two time limits: one where it does not even start a new iteration because it will almost certainly not be able to finish even a single move of it within the target time. And another, tested after every root move, where it can abort the iteration if it is happy with the score. ANd then I have a third 'never-exceed' limit, tested during search, which catches cases where the search'gets stuck', and anything is better than a time loss.

[Sven]

The whole point of iterative deepening is to get a likely g\best-move candidate, so you can search it first. Even micro-Max does that...

I do not do iterative deepening when not PV.

You do use iterative deepening since you are talking about iterations all the time (what else is your depth=N-2, depth=N-1, depth=N ?). What you mean is that you do not use IID (Internal Iterative Deepening) when not in a PV node. IID is not the same as ID, both also have something on common but IID is a special thing. You could use IID to improve move ordering at non-PV nodes where you also do not have a TT move.

Also I compute a best move from N-2 not N-1.

I do not understand this sentence, can you explain it, please?

Also a good capture, if there is one, is almost always the best move.

This is wrong in the sense of "almost always", there are many cases where the best move is a quiet move. You are right when stating that it is good to search good captures as early as possible, but the PV move as well as the TT move are moves that should always be tried first.

But even if it were right, what do you want to say? That it is not necessary to search the PV move first in the next iteration? Well, then test it with a couple of different positions to see in which case the overall tree size is smaller ...

Sven

[Henk]

I mean to say that I do not compute the best move from the previous iteration but from the one before if possible, if no hash move exists. The best move of a previous iteration may not be necessary if there is a good capture that already causes a cutoff (but forget about this)

[Sven]

I mean to say that I do not compute the best move from the previous iteration but from the one before if possible, if no hash move exists. The best move of a previous iteration may not be necessary if there is a good capture that already causes a cutoff (but forget about this)

So should I better do what I put in bold?

Your search code for the root node will most probably contain a part like this within the move loop:

Code: Select all

makeMove(move);
int score = -search(...);
unmakeMove(move);
if (score > bestScore) {
    bestScore = score;
    bestMove = move;
    if (score >= beta) break;
    if (bestScore > alpha) {
        // update PV and print PV info ...
    }
}

So you permanently compute a candidate for the best move of the current iteration by updating "bestMove" whenever the search of the current root move returns with a new best score. If that best score finally turns out to stay within the alpha/beta window then "bestMove" actually becomes your (new or old) best move of the iteration, otherwise you research with a wider window (in case you use an aspiration window). A chess engine that uses iterative deepening should always have a "best move candidate" that it would play if the search were stopped.

Therefore I still don't get the meaning of your statement "I do not compute the best move from the previous iteration but from the one before if possible, if no hash move exists". It is possible that we are not talking about the same thing ...

Sven

[Henk]

I mean to say that I do not compute the best move from the previous iteration but from the one before if possible, if no hash move exists. The best move of a previous iteration may not be necessary if there is a good capture that already causes a cutoff (but forget about this)

So should I better do what I put in bold?

Your search code for the root node will most probably contain a part like this within the move loop:

Code: Select all

makeMove(move);
int score = -search(...);
unmakeMove(move);
if (score > bestScore) {
    bestScore = score;
    bestMove = move;
    if (score >= beta) break;
    if (bestScore > alpha) {
        // update PV and print PV info ...
    }
}

So you permanently compute a candidate for the best move of the current iteration by updating "bestMove" whenever the search of the current root move returns with a new best score. If that best score finally turns out to stay within the alpha/beta window then "bestMove" actually becomes your (new or old) best move of the iteration, otherwise you research with a wider window (in case you use an aspiration window). A chess engine that uses iterative deepening should always have a "best move candidate" that it would play if the search were stopped.

Therefore I still don't get the meaning of your statement "I do not compute the best move from the previous iteration but from the one before if possible, if no hash move exists". It is possible that we are not talking about the same thing ...

Sven

With best move I mean first move tried. (One tries the best candidate move first). I compute this from search(depth -200) or search(depth -100) when 0 < depth < 300, if I cannot get it from hash table.

But forget about this I'm talking in my sleep, dreaming of fast chess programs forgetting all the stupid mistakes, bugs, errors and misunderstandings.

[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???

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

You are not comparing different depths.

You have the score for the best move at depth D-1. If you complete searching the first move at depth D, you now have a more accurate score than the depth D-1 score. If any moves are proven to be better than the depth D score, you should play the one with the best score, and all you are comparing are depth D to depth D scores. You don't have scores for ALL root moves, but you don't need them to decide if move 3 is better than move 1 at depth=D.