Calculating Branch Factor

[verminox]

I want to calculate the branching factor at each search within the iterative deepning framework so that I can estimate whether or not to search the next depth with the given time constraint.

A simple approach would be:

Code: Select all

search(depth++)
time = now()
dt = time - time_old
branch_factor = dt / dt_old
if( (time() + (dt_new * branch_factor)) > move_time() )
  STOP
time_old = time
dt_old = dt
REPEAT

Is this enough? Or should there be interpolating of branch factors with branch factors of previous depths (that is, an average)?

Also, should branch factors be saved and used as the initial branch factor of the next search (this i feel is a bad idea because the next search may have a completely different state and BF can change drastically over the two moves played between searches)? If not, what should be the initial branch factor (I don't think this is much relevant because upto around depth=4 a timeout won't occur anyway)?

[MattieShoes]

Depending on position and extensions, you can get a situation where ply N+1 can take the same time when N is even and take way longer when N is odd... Or maybe I have that reversed. But there can be even/odd effects. Also other things can cause search tree explosion -- long capture sequences that suddenly fall within the horizon, check sequences, etc.

If you handle partial search results and search the PV first, you may get a PV change after searching only two root moves -- say the PV move suddenly looks worse due to some tactic, and the second move searched is now better.

[Aleks Peshkov]

It may be better to predict time to search the first root move and be able to terminate search after any of the root moves.

If the first move does not worsen its value significantly it is safe to abort search, otherwise it is good time to spend extra time on searching alternatives.

[hgm]

If you don't clear the hash before your search, it is impossible to predict the duration of the next iteration from that of the previous iterations.

Micro-Max can reach 10 ply in a micro-second (because of hash hits) and then take 5 min for the 11th ply to complete.

[verminox]

So then how does one ever decide whether or not to search the next ply? I understand all above posts on how branching factor is not easily decided... but there must be SOME criteria to estimate whether it is good enough to search another ply (other than time out interrupts which can be wasteful)

[hgm]

Basically one hopes for the best. Do not start a new iteration if you already have used more than half your target average time per move. And build in an emergency break, fo it will regularly happen that you will not even be able to finish searching the first move f an iteration within 2 or 3 times this target time (on average once or twice per game). Especially if you ponder.

[Aleks Peshkov]

It is not sure that searching in whole ply steps is optimal.
Idea of LMR is exactly opposite.

[bob]

So then how does one ever decide whether or not to search the next ply? I understand all above posts on how branching factor is not easily decided... but there must be SOME criteria to estimate whether it is good enough to search another ply (other than time out interrupts which can be wasteful)

Two choices.

(1) just start the search and continue until time runs out. Even if you can't finish the next ply before time runes out, you can learn several things;;; (a) if the search fails low, you now know you need to spend extra time to try to avoid the problem caused by the best move so far, and fail lows happen very quickly compared to fail highs; (2) you might get the PV back even if you can't search all moves; (c) if neither of those happens, you still fill the hash table with good information you can use on the succeeding ponder search.

(2) use some simple formula to decide when there is too little time left, and stop searching when you reach the point where the formula says you have little chance of completing the next search.

I have alyways used (1) and it works well.

[verminox]

(1) just start the search and continue until time runs out. Even if you can't finish the next ply before time runes out, you can learn several things;;; (a) if the search fails low, you now know you need to spend extra time to try to avoid the problem caused by the best move so far, and fail lows happen very quickly compared to fail highs; (2) you might get the PV back even if you can't search all moves; (c) if neither of those happens, you still fill the hash table with good information you can use on the succeeding ponder search.

I see, that sounds reasonable. If there was a change in PV before the timeout interrupt occurs the new PV and hashtable info does get saved, so that works for me. Although I don't understand how the search at the root would fail low, unless you mean aspiration windows in which case the only thing I can do about it is re-search the whole thing for which there may not be time!!! Or did you mean something else?

[bob]

(1) just start the search and continue until time runs out. Even if you can't finish the next ply before time runes out, you can learn several things;;; (a) if the search fails low, you now know you need to spend extra time to try to avoid the problem caused by the best move so far, and fail lows happen very quickly compared to fail highs; (2) you might get the PV back even if you can't search all moves; (c) if neither of those happens, you still fill the hash table with good information you can use on the succeeding ponder search.

I see, that sounds reasonable. If there was a change in PV before the timeout interrupt occurs the new PV and hashtable info does get saved, so that works for me. Although I don't understand how the search at the root would fail low, unless you mean aspiration windows in which case the only thing I can do about it is re-search the whole thing for which there may not be time!!! Or did you mean something else?

I do aspiration search at the root. It is possible that the first root move will fail low. I don't continue searching in Crafty, if the first move fails low, I back out, lower alpha, and re-search. But the main idea is, once it fails low, I know there is a problem and can use more time to try to solve it.