When is it save to quit search?

[Guetti]

Ok, here's another question.
I'm currently pondering when it's best to quit the search to be able to use the results of the current search without trouble.
The scenario is like this: We search to a (slightly flexible) timelimit. The search started a new iteration but runs out of time. But we want to use the current information searched on this iteration. What do we do?
I'm thinking that if the search didn't find a best move yet, it's probably best to delay the quitting (if possible) or not use the information for the current iteration and stick with the previous iterations. When we completed to search the PV at the current iteration, we can safely quit and use the new score and PV. Is my thinking correct?

I usually test to quit the search after checking for fail high and updating the PV:

Code: Select all

		// Check for a fail high
			if (score >= beta)
				return beta;
			
			// Check if we have a new best move
			if (score > alpha)
			{
				alpha = score;
				foundPV = true;
				
				searcher->mPVline[ply][ply] = cmove;
				int c;
				for (c = ply+1; searcher->mPVline[ply+1][c] != 0; c++)
					searcher->mPVline[ply][c] = searcher->mPVline[ply+1][c];
				searcher->mPVline[ply][c] = 0;
			}
		
		
	-->		// Check if we should abort the search
			if (crew->mSCStopSearch == true)
				return alpha;
		

Should I change the last part to:

Code: Select all

          // Check if we should abort the search
			if (crew->mSCStopSearch == true && foundPV == true)
				return alpha;

[Tony]

You either break off search and don't use information from current search, or you finish it and do use it. Only that is safe.

If there was a point where you could safely break it off, we would already use that (and call it pruning) but still continue search, saving a lot of time.

Tony

[Harald Johnsen]

...
The scenario is like this: We search to a (slightly flexible) timelimit. The search started a new iteration but runs out of time. But we want to use the current information searched on this iteration. What do we do?
I'm thinking that if the search didn't find a best move yet, it's probably best to delay the quitting (if possible) or not use the information for the current iteration and stick with the previous iterations. When we completed to search the PV at the current iteration, we can safely quit and use the new score and PV. Is my thinking correct?

1) You can only use the result of the search when you are at the root, if you are not at the root you have no move, backing up incomplete search to the root is useless and incorrect. What makes you think that your incomplete 55 ms search is better than your last 25 seconds search ?
2) don't start a new iteration if you don't have enought time to do anything interesting.
3) you won't be able to complete the search of your PV, because this is what usually takes the most time, not the other 45 moves. You can not extend the time when you have a time out while looking at the pv because you have *no* idea how long that search will take.

HJ.

[Guetti]

Ok, seems that I can't use the information of an incomplete iteration. I thought that maybe after searching the Hashmove, all the good captures it's probably reasonably safe to stop the search because the probability that a better moves pops up is rather low. I want to stop at the root only.

But if I finish the first move, then it' s probably worth to invest additional time (if possible) to complete the iteration, because it will not take very long.

[Guetti]

...
The scenario is like this: We search to a (slightly flexible) timelimit. The search started a new iteration but runs out of time. But we want to use the current information searched on this iteration. What do we do?
I'm thinking that if the search didn't find a best move yet, it's probably best to delay the quitting (if possible) or not use the information for the current iteration and stick with the previous iterations. When we completed to search the PV at the current iteration, we can safely quit and use the new score and PV. Is my thinking correct?

1) You can only use the result of the search when you are at the root, if you are not at the root you have no move, backing up incomplete search to the root is useless and incorrect. What makes you think that your incomplete 55 ms search is better than your last 25 seconds search ?
2) don't start a new iteration if you don't have enought time to do anything interesting.
3) you won't be able to complete the search of your PV, because this is what usually takes the most time, not the other 45 moves. You can not extend the time when you have a time out while looking at the pv because you have *no* idea how long that search will take.

HJ.

Yes, I was talking about to stop at the root. Sorry for not making that clearer.

[Uri Blass]

<snipped>

Ok, seems that I can't use the information of an incomplete iteration.

This is not exactly correct that you cannot use information of incomplete iteration.
You cannot use the information of incomplete search of root move but you can use information of incomplete iteration.

If you failed high on a move and did not search the rest of the moves then it is still better to play the move that failed high.

If you have the following scores
1.e4 0.40/8
1.e4 0.2/9
1.d4 fail high and you did not complete iteration 9 then assuming that you have no wrong fail high it is better to play 1.d4 and not 1.e4 even if you did not complete iteration 9.

If you finished to search the move d4 and solved the fail high and found that it has better score than 0.2 then it is obvious that it is better to play it and not to play e4

Uri

[bob]

Ok, here's another question.
I'm currently pondering when it's best to quit the search to be able to use the results of the current search without trouble.
The scenario is like this: We search to a (slightly flexible) timelimit. The search started a new iteration but runs out of time. But we want to use the current information searched on this iteration. What do we do?
I'm thinking that if the search didn't find a best move yet, it's probably best to delay the quitting (if possible) or not use the information for the current iteration and stick with the previous iterations. When we completed to search the PV at the current iteration, we can safely quit and use the new score and PV. Is my thinking correct?

I usually test to quit the search after checking for fail high and updating the PV:

Code: Select all

		// Check for a fail high
			if (score >= beta)
				return beta;
			
			// Check if we have a new best move
			if (score > alpha)
			{
				alpha = score;
				foundPV = true;
				
				searcher->mPVline[ply][ply] = cmove;
				int c;
				for (c = ply+1; searcher->mPVline[ply+1][c] != 0; c++)
					searcher->mPVline[ply][c] = searcher->mPVline[ply+1][c];
				searcher->mPVline[ply][c] = 0;
			}
		
		
	-->		// Check if we should abort the search
			if (crew->mSCStopSearch == true)
				return alpha;
		

Should I change the last part to:

Code: Select all

          // Check if we should abort the search
			if (crew->mSCStopSearch == true && foundPV == true)
				return alpha;

Don't know if you have looked at crafty, so here's a summary...

Whenever time runs out, one thing crafty does that many do not is it _never_ stops the search until all currently-being-searched-moves have been examined, unless a absolute max search time is passed (about 2x the target if I remember). This avoids terminating a search, using the best move so far, when you are just about to discover that a new move is best.

If you have used the target time, and the first move has not yet been searched, you probably should quit on the spot, otherwise you will lose the benefit of pondering (saving time) and probably still won't get a score back.

You can always use the best move found so far, even if you don't complete the search, you just have to be certain that when time runs out, you do not back up anything after that point. Anything already backed up to the root is OK to use, but once time runs out and the search starts unwinding, it can not back up anything else or you will have problems.
-

[Tony]

Ok, seems that I can't use the information of an incomplete iteration. I thought that maybe after searching the Hashmove, all the good captures it's probably reasonably safe to stop the search because the probability that a better moves pops up is rather low. I want to stop at the root only.

But if I finish the first move, then it' s probably worth to invest additional time (if possible) to complete the iteration, because it will not take very long.

Well, you can use the result, it's just not as safe.

Having searched half the moves at ply 10, is not as safe as having searched all moves at ply 10. Question is how unsafe.

In XiniX, if time runs out I quit searching if: I did not finish the first move yet OR (the first move didn't fail low (dropped 20 cp) and no move failed high (above previous score-20 cp)) OR time spend > panic time (3 x normal time).

Else I continue the iteration until the end or one of the above conditions are met.

Tony

[Chan Rasjid]

I have something like these that may be ok:-

1) if at root and before starting on the next iteration,decide not to if 70% of allocated time has been used. If there is too little time that only the previous PV move may be searched, then there is no change to the move that will be played.

Code: Select all

        j = getMilliSecFrom(&searchInfo->timeb_start);

        if (100 * j >= 70 * searchInfo->timeAlloc
&& bestscore > 30  
&& best > game_running_score - 20) {
            goto HASH_AND_RETURN;
        }

2) before searching the 2nd move, disable timeout if the previous score of the 2nd move is close to that of the PV in which case the 2nd move also has a high probability of being the PV. Then there is at least 2 moves to compare if there is a better PV. But this can be done only if we use an aspiration window that can keep track of some fail-low "exact" score, say 1/2 a pawn below alpha.

Code: Select all

            searchInfo->disable_timeout = (iteration > 0 && move_is_2nd_move
                                         && move->score + v12Pawn > bestMove->score);
/* do search at root*/
                score = -search(board, ss + 1, searchInfo, incheck, pDoHashkey, xside, followPV, moveN);

Rasjid