Solving a fail low situation at the root

[asanjuan]

Hi there.

I was debugging some strange moves made by the engine, and I came up debugging the very popular "fail low at the root" situation.

This is, in my aspiration code, the root search returns a value <= alpha, so none of the moves can improve alpha, and then the search window is widened.

Then, in the middle of the second (or third) search, we reach the end of our time allocation, and a (expected) bad move is returned as best move.

What I'm trying to solve this situation is to extend the allocated time each time I detect a fail low at the root. Something like this:

Code: Select all

int aspiration_count = 1;
bool outside_window = false;
do{
	
	result = search_root( depth, alpha, beta );					
		
	if &#40;result <= alpha || result>=beta&#41;
	&#123;
		
		outside_window=true;

		//time management, for fail low situations
		if &#40;result <= alpha&#41; info->solving_fail_low = true;
		else info->solving_fail_low = false;
		
								
		//time management, for fail low situations
		if &#40;info->solving_fail_low &&
			info->timed_search  
			&& search_info_elapsed_ms&#40;) > &#40;info->allocated_time /2&#41;
			) 
			info->allocated_time = min&#40; (&#40;info->allocated_time*175&#41;/100&#41;, info->max_allocated_time&#41;;
		
		if &#40;aspiration_count==1&#41; &#123;
			alpha = result-ASPIRATION_WINDOW_2; 
			beta = result+ASPIRATION_WINDOW_2;
		
		&#125;else &#123;
			alpha = -INF; 
			beta = INF;					
		&#125;
								
	&#125;else &#123;
		outside_window = false;
		alpha = result-ASPIRATION_WINDOW;
		beta = result+ASPIRATION_WINDOW;
	&#125;
	aspiration_count++;
	
&#125;while &#40;outside_window&#41;;

I'm running a test just now, but it doesn't seem to help much.
I wonder what others are doing so solve this problem.
Any input would be appreciated.

[hgm]

Set alpha = -INFINITY. Then you cannot possibly fail low.

[xmas79]

Set alpha = -INFINITY. Then you cannot possibly fail low.

Setting alpha to -INFINITY at first fail low can produce big penalty, isn't it? My undestanging is that he sets alpha to -INF on second fail low.

The problem I see is that on two fail low alpha will be set to -INF, but beta to +INF as well, and on two fail high beta will be set to +INF and alpha will be set to -INF as well. This will lead to sub-obtimal search, isn't it? I would change only alpha/beta upon fail low/high.

[Henk]

I also had much trouble with that and I don't even return the best move but store it in the TT table. So I checked if search was busy with a research or not and if search was not finished I did not store in the TT. It all looked very ugly so I removed the code and resigned.

[Stan Arts]

I simply try to finish every iteration/search all moves at the root at all cost even if nothing remarkable is happening. Only stopping if a huge amount of time is getting used and I'm getting in trouble.

Often times there might be a better move to be found late in the iteration but that's the whole point of searching deeper, so I want to take a look at every move. It's really improving the quality of moves on average. If nothing is to be found later moves tend to get disregarded quickly and cost little. Also when something good (fail high) or bad (fail low) is happening I want to finish search as well.
In my previous program still would interrupt if I timed out and the first move hadn't returned anything yet but that's wasted effort and adjusting time usage to finish every iteration that gets started on simply meant allocating slightly less time.

[hgm]

Setting alpha to -INFINITY at first fail low can produce big penalty, isn't it? My undestanging is that he sets alpha to -INF on second fail low.

Having to search three times also carries a big penalty...

The problem I see is that on two fail low alpha will be set to -INF, but beta to +INF as well, and on two fail high beta will be set to +INF and alpha will be set to -INF as well. This will lead to sub-obtimal search, isn't it? I would change only alpha/beta upon fail low/high.

It is only sub-optimal in a situation where you have a good idea what the score is. Then you can gain a little time by taking a narrow aspiration window around it. If you have no idea what the score is, being stingy on the window will just cause new fails and waste time.

In a stable search the aspiration of alpha gains you very little. You will follow the PV first, and when it is inside tha aspiration window, it immediately erases all memory of the root alpha. Only when it is unexpectedly bad (i.e. the previos iteration was headingtowards a disaster, which in the next ply materializes), it starts to vary a little bit with the moves very close to the leaves, and usually the problem can be dodged by taking a different move on the ply before, to get back in window. Only in this small sub-tree you would still feel the aspiration.

The whole idea of aspiration is that you are confident you will find a score close to that of the previous iteration, because the PV is realistic except for those unreliable final moves. If you would go in a completely different direction by deviating in an early move it would be completely accidental if the score was close to what you had before.

[bob]

Set alpha = -INFINITY. Then you cannot possibly fail low.

Setting alpha to -INFINITY at first fail low can produce big penalty, isn't it? My undestanging is that he sets alpha to -INF on second fail low.

The problem I see is that on two fail low alpha will be set to -INF, but beta to +INF as well, and on two fail high beta will be set to +INF and alpha will be set to -INF as well. This will lead to sub-obtimal search, isn't it? I would change only alpha/beta upon fail low/high.

A couple of issues:

(1) you should not play a "bad move" in that the move is random or whatever. You should always have a "best move" from previous iteration.

(2) extending time on a fail low is a good idea. How much is a good question. I allow up to 5x the normal target time. It is generally better to widen the window gradually, but most use a sort of quadratic function or something, such as alpha -= 16, then 32, then 64, then 128, etc... Use any multiple you like.

[asanjuan]

Well. I know that changing only alpha or beta independently will be more efficient. That is clear.
My question was related to time management regardless of the window size. I will change the question:
The problem is that if in a re-search (being more or less efficient doesn't matter in this case), the time allocated finishes withot having found a new best move, what do you do to solve the problem?
A) extend the allocated time (the patch currently being tested)
B) or what else?

[hgm]

Well, extending the time to make it forfeit definitely is not a good idea.

Most of my engines use 3 time limits:
1) for starting a new iteration
2) for trying new moves in the root because the old PV move dropped unacceptably much in score, and we haven't found any other move that brings us close to the score of the previous iteration
3) the 'cold-turkey' timeout, where you must move or lose.

The latter can be as much as 1/3 of all remaining time, even if there are still 20 moves to go. I guess getting fail lows in the current iteration puts you in phase (2). Which you only exit when you do find an acceptable move, finish the iteration (so you apply (1) again), or run into (3). In the latter case you play the best move you found in the current iteration (because if you found anything, it must be at least as good as the PV move of the previous iteration at this new depth, as you always search that first). And if you have none, play the old PV move, and hope for the best. You now know that it sucks, but perhaps the opponent will not see it.

[xmas79]

...Most of my engines use 3 time limits:
1) for starting a new iteration
2) for trying new moves in the root because the old PV move dropped unacceptably much in score, and we haven't found any other move that brings us close to the score of the previous iteration
3) the 'cold-turkey' timeout, where you must move or lose...."

This is more or less what I'm actually doing. I replace 2 with the classic "maximum allocated time per search", where I gracefully abort current iteration if I have already found a best move and time has expired. If a move is not found I keep searching until a hard time-out like 3) occurs or I found a best move.

The problem I have with this approach (admitting it is the way to go IHMO) is that:
1) works OK when you have a good predictable branching factor. My engine is not tuned, so passing from iteration N-1 to N, and from N to iteration N+1 can take a very different amount of time, so I cannot have a "stable" BF to calculate how much will take the next iteration. The consequence is that engine will not start a new iteration as soon as it "consumes" 50% of allocated time in the best case, often seeing it moving almost instantly because of a huge BF in the last iteration. Tried to smooth BF with averages or so, but the solution (and the results) seems to me sub-optimal, and I discharded it (everything then depends of the BF of the first iteration...)
2) causes my engine to go under time pressure too much. I suppose the problem is again related to the big BF the engine suffers.

When I cannot finish an iteration due to hitting 3) I play the best move from previous iteration.

I tried various other combo and tunings, then I gave up until I get a better move ordering and a smaller tree, making the engine more predictable on search times.