time usage

[metax]

Maybe in those situations it is better just to choose randomly from the best bad moves that we have found, instead to use more time. In a human against human game, if we found that we loose a pawn, for sample, why to loose a lot of time trying to save it? Even the clock is a piece (IMHO) so i think that saving time is better than searching in a "degenerated" tree, hoping to find something not so bad.

Choosing randomly maybe can "surprise" the other program, so that it don't play the move already in pondering... and that will give us another little gain in time.

My question in fact is: if the branching factor is not the ones we expect, do to no good moves found, how can we think to find a better move with this unckown BF?

In a human vs human match, it is not unlikely that the opponent (unless he is the world champion or very strong) makes a mistake, so the loss of a pawn may not be decisive. In contrast to that, most engines will exploit the advantage and win the game, so I think you cannot compare that very well.

[stegemma]

...In a human vs human match, it is not unlikely that the opponent (unless he is the world champion or very strong) makes a mistake, so the loss of a pawn may not be decisive. In contrast to that, most engines will exploit the advantage and win the game, so I think you cannot compare that very well.

Yes, but because we really don't know how to deal with this situation, in our program, maybe the "human euristic" (don't loose time, if you already are in a lost position) can help us to solve the problem or just give us a hint.

[yoshiharu]

I don't understand this, you already said :

"Usually the EBF goes up when move ordering goes bad."

So it would seem that you just need to measure the EBF, for instance the ratio between searched nodes in the last iteration and searched node in the previous one.

If it is above a certain thresold it means we have a problem according to this idea.

Am I missing something ?

This is just my thought, but maybe when EBF goes up it's already late: perhaps there could be some indicator that EBF is going to overshoot...

Cheers, Mauro

[jhaglund]

What should be done:

int time_usage,clock,time, m, mpg,time_control, last_turn_to_move_eval, this_turn_to_move_eval, game_time, eval_diff;
clock = m // m = minutes per game
mpg = 40; //default moves per game
time_control = mpg;
time = clock / time_control;

if(last_turn_to_move_eval < 0 && this_turn_to_move_eval < 0)
eval_diff = (this_turn_to_move_eval*-1) - (last_turn_to_move_eval*-1);

if(this_turn_to_move_eval < 0 && last_turn_to_move_eval > 0)
eval_diff = last_turn_to_move_eval - this_turn_to_move_eval;

if(last_turn_to_move_eval > 0 && this_turn_to_move_eval > last_turn_to_move_eval)
gain_time = time_usage *1;

if(this_turn_to_move_eval > 0 && this_turn_to_move_eval > last_turn_to_move_eval)
gain_time = time_usage *1;

if(this_turn_to_move_eval < 0 && this_turn_to_move_eval < last_turn_to_move_eval)
eval_diff = last_turn_to_move_eval - this_turn_to_move_eval;

if(last_turn_to_move_eval < 0 && this_turn_to_move_eval < last_turn_to_move_eval)
eval_diff = last_turn_to_move_eval - this_turn_to_move_eval;

//pick your change of evaluation sensitivity

if(eval_diff >= 0 && eval_diff > .05)
gain_time = time_usage *1;
if(eval_diff >= .05 && eval_diff > .1)
gain_time = time_usage *1.1
if(eval_diff >= .1 && eval_diff > .2)
gain_time = time_usage * 1.2;
if(eval_diff >= .2 && eval_diff > .3)
gain_time = time_usage * 1.4;
if(eval_diff >= .3 && eval_diff > .4)
gain_time = time_usage * 1.6;
if(eval_diff >= .4 && eval_diff > .5)
gain_time = time_usage * 1.8;
if(eval_diff >= .5 && eval_diff > 1)
gain_time = time_usage * 2;
if(eval_diff > 1)
gain_time = time_usage * 4;

time_usage = time + gain_time;

I hope this idea is clear for everyone

Joshua D. Haglund

[jarkkop]

Sometimes it really takes 10 times more to resolve next ply. Have tried
restarting search if it exceeds about 2.5(or something constant of your choosing) normal expected search time?

[bob]

That's the easy part (testing). A more difficult question is "How to determine that things are turning south in the game and more time is justified?"

I don't understand this, you already said :

"Usually the EBF goes up when move ordering goes bad."

So it would seem that you just need to measure the EBF, for instance the ratio between searched nodes in the last iteration and searched node in the previous one.

If it is above a certain thresold it means we have a problem according to this idea.

Am I missing something ?

Yes. "Usually"



(not _Always_)

[bob]

One example from the mid 70's in my program, is the idea of a fail-low forcing you to use more time to avoid a tactical problem. And it works well.

Stockfish also uses this idea, but instead of researching with bigger window, it goes directly searching for alternatives for the first move. If aspiration window is small enough, this behaviour should somewhat prevent the EBF explosion, and is a good indicator that we should allocate more time.

Thoughts???

The problem is that if we know that have a very bad EBF, an extra iteration can be very costly. It could take ages just to complete the first move. I'm not saying that this couldn't work, but it's very tricky to decide how much extra time you are willing to spend before giving up.

I am going to address this specific issue once and for all before long. I have tried lots of approaches over the years. In the late 70's we used to use the approach you are describing. There are two cases:

(1) you fail high. There is no need to resolve the fail high, unless a second move fails high. If that happened, we relaxed beta, searched the first move to get a better score, then searched the second move (the second that failed high) again with a null-window search, but now based on the new best score. If it fails low, the first move is best. If it fails high, we do not need to re-search it unless another move fails high. This has a problem. By not re-searching and getting a score, the hash table is not complete with respect to the search of this move, which means the next iteration will start off with missing data, since every other ply won't have a best (PV) move.

(2) you fail low. Here you have several choices:

(a) re-search immediately to determine how bad the move really is.

(b) just continue searching with original alpha/beta window and hope one of the remaining moves will fall inside and produce a PV. If not, you just wasted a ton of time and still have to go back and re-search the first move again.

(c) start the search over at iteration 1. SInce the best move thru the first N iterations failed low at N+1, that hash entry will continue to make it fail low, and you find a new best move, but you find it iteratively rather than having to start at depth=n with no move ordering info in the hash table. Drawback is that the hash entry for the fail-low can be overwritten. Or other moves look worse at iterations 1-N so that the original best move is still best. And you just wasted a ton of time.

Which is best? It's really time to pose that question to the cluster and find out exactly.

[bob]

What should be done:

int time_usage,clock,time, m, mpg,time_control, last_turn_to_move_eval, this_turn_to_move_eval, game_time, eval_diff;
clock = m // m = minutes per game
mpg = 40; //default moves per game
time_control = mpg;
time = clock / time_control;

if(last_turn_to_move_eval < 0 && this_turn_to_move_eval < 0)
eval_diff = (this_turn_to_move_eval*-1) - (last_turn_to_move_eval*-1);

if(this_turn_to_move_eval < 0 && last_turn_to_move_eval > 0)
eval_diff = last_turn_to_move_eval - this_turn_to_move_eval;

if(last_turn_to_move_eval > 0 && this_turn_to_move_eval > last_turn_to_move_eval)
gain_time = time_usage *1;

if(this_turn_to_move_eval > 0 && this_turn_to_move_eval > last_turn_to_move_eval)
gain_time = time_usage *1;

if(this_turn_to_move_eval < 0 && this_turn_to_move_eval < last_turn_to_move_eval)
eval_diff = last_turn_to_move_eval - this_turn_to_move_eval;

if(last_turn_to_move_eval < 0 && this_turn_to_move_eval < last_turn_to_move_eval)
eval_diff = last_turn_to_move_eval - this_turn_to_move_eval;

//pick your change of evaluation sensitivity

if(eval_diff >= 0 && eval_diff > .05)
gain_time = time_usage *1;
if(eval_diff >= .05 && eval_diff > .1)
gain_time = time_usage *1.1
if(eval_diff >= .1 && eval_diff > .2)
gain_time = time_usage * 1.2;
if(eval_diff >= .2 && eval_diff > .3)
gain_time = time_usage * 1.4;
if(eval_diff >= .3 && eval_diff > .4)
gain_time = time_usage * 1.6;
if(eval_diff >= .4 && eval_diff > .5)
gain_time = time_usage * 1.8;
if(eval_diff >= .5 && eval_diff > 1)
gain_time = time_usage * 2;
if(eval_diff > 1)
gain_time = time_usage * 4;

time_usage = time + gain_time;

I hope this idea is clear for everyone

Joshua D. Haglund

The problem is what to do on a fail low? You don't have a current eval, which is the main problem being discussed. You just know it is a little worse than the previous iteration's score, at best, and possibly a whole lot worse. But until you search the move, you don't know. And more importantly, you don't extend the time until you see the problem. Hsu's idea was to use more time when you get a hint that something is happening, _before_ you fail low (where it is, often enough, something that can now not be avoided).

[jhaglund]

Sometimes it really takes 10 times more to resolve next ply. Have tried
restarting search if it exceeds about 2.5(or something constant of your choosing) normal expected search time?

This doesn't have to be done during a search, but a comparison after the move has been played.

Store the evaluation for that particular PV line.
Compare it on your next turn PV Line.

After it reaches the time_usage, compare at this point and add gain_time.

ex: 1.e2e4 e7e5 g1f3 b8c6 +.22

Movelist
1.e2e4 c7c5

2. g1f3 d7d6 d2d4 c5d4 f3d4 + .43

So here is what is suppose to go on:

First move difference, time_usageX1; //no added time

.43-22= .21 =second move difference, which is time_usage X 1.2. //20%

ex:

Movelist
1.e2e4 c7c6

2. d2d4 d7d5 b1c3 g8f6 g1f3 +.12

So here is what is suppose to go on:

.22 - .12 = eval_diff of .10 = time_usage x 1.1. //10%

Those gain_time numbers are not written in stone remember...

Search time for me is:

time_usage = time_remaining / (mpg - move_number)+gain_time;
time_usage = time + gain_time; //simplified.

Joshua

[jhaglund]

The problem is what to do on a fail low? You don't have a current eval, which is the main problem being discussed. You just know it is a little worse than the previous iteration's score, at best, and possibly a whole lot worse. But until you search the move, you don't know. And more importantly, you don't extend the time until you see the problem. Hsu's idea was to use more time when you get a hint that something is happening, _before_ you fail low (where it is, often enough, something that can now not be avoided).

I would suggest a FailLowCheck();

If(faillow)
fail_low_mode();
else
time_usage();

fail_low_mode() could be pretty much exactly the same as time_usage().
//time_usage being my original post.

fail_low_mode() would have to be within the search. This would detect it before it became the Principal Variation...

Do a FailLowCheck() every X nodes or something in that nature.

I would rely on the search evaluation comparisons after each move for your basic time_usage.