Iteration in pondering

[Chang]

Hi,

In pondering mode, while human player thinking, the program starts pondering by making a guessing move, let’s say move X, then going deeper in iteration starting from depth 1. Suppose a situation, after finishing depth 10 while going through depth 11, human player input move X. My question is, on its turn to move, should the program start calculating at depth 1 as usual or depth 10 in stead?

Thanks for any advices.

Best regards,
Teerapong

[mar]

Hi,

In pondering mode, while human player thinking, the program starts pondering by making a guessing move, let’s say move X, then going deeper in iteration starting from depth 1. Suppose a situation, after finishing depth 10 while going through depth 11, human player input move X. My question is, on its turn to move, should the program start calculating at depth 1 as usual or depth 10 in stead?

Thanks for any advices.

Best regards,
Teerapong

No what you describe is a ponderhit and the program simply continues searching. Only if it misses the guessed move (pondermiss) it aborts and restarts from depth 1.

Martin

[Evert]

Shouldn't really matter, since the search will burn through the lower plies very quickly because of deep entries stored in the transposition table.

[Sven]

Hi,

In pondering mode, while human player thinking, the program starts pondering by making a guessing move, let’s say move X, then going deeper in iteration starting from depth 1. Suppose a situation, after finishing depth 10 while going through depth 11, human player input move X. My question is, on its turn to move, should the program start calculating at depth 1 as usual or depth 10 in stead?

Thanks for any advices.

Best regards,
Teerapong

No what you describe is a ponderhit and the program simply continues searching. Only if it misses the guessed move (pondermiss) it aborts and restarts from depth 1.

Hi Martin,

I think it slightly depends on the implementation whether you can "simply" continue the search or not. If you do then you need to ensure that your search infrastructure can handle this correctly (although it is not really difficult to achieve it). The following points might be considered, beneath others:
- "pondering mode" switched into "thinking mode"
- time control issues (e.g.: how to handle the clock, should it be reset or not?)
- node counting and other statistical tools (do the nodes searched in "pondering mode" count, or do you reset the node counter?)
- display issues

In general I believe that restarting at depth 1 would also be an option that might keep the whole pondering implementation as simple as possible, relying on the working hash table which quickly brings you back to the iteration level where you stopped pondering. It is certainly some overhead, though. But on the other hand it would allow to avoid the mess of implementing all the details that are necessary to correctly switch a running search from "pondering" into "thinking" mode without stopping it, and therefore might be a good alternative way to get a bug-free pondering implementation up and running quickly before optimizing it later on.

I assume that many engines work as you described.

Sven

[mar]

Hi Martin,

I think it slightly depends on the implementation whether you can "simply" continue the search or not. If you do then you need to ensure that your search infrastructure can handle this correctly (although it is not really difficult to achieve it). The following points might be considered, beneath others:
- "pondering mode" switched into "thinking mode"
- time control issues (e.g.: how to handle the clock, should it be reset or not?)
- node counting and other statistical tools (do the nodes searched in "pondering mode" count, or do you reset the node counter?)
- display issues

In general I believe that restarting at depth 1 would also be an option that might keep the whole pondering implementation as simple as possible, relying on the working hash table which quickly brings you back to the iteration level where you stopped pondering. It is certainly some overhead, though. But on the other hand it would allow to avoid the mess of implementing all the details that are necessary to correctly switch a running search from "pondering" into "thinking" mode without stopping it, and therefore might be a good alternative way to get a bug-free pondering implementation up and running quickly before optimizing it later on.

I assume that many engines work as you described.

Sven

Hi Sven,

I really don't see a problem with continuing the search (note that this is only valid for a ponderhit).
As for switching from pondering to thinking, you simply change one variable (i don't have SMP but my search runs in a separate thread so not a big deal).
Time control: i don't know how this is done in xboard but in uci the gui sends the time along with the ponder flag to start pondering, i.e. "go wtime xxxx btime xxxx ponder" so no problem here at all.
node counting: no problem either as you simply continue the search.
display issues: not sure what you meant.

Martin

[hgm]

What Sven probably means is that you have to decide how long to continue thinking after the ponder hit. You could already have searched for longer than what you would normally do, considering the initial time on your clock, but since your clock was not running, it is not obvious that you should apply the same stop criterion as when it had been runing.

E.g. when I have 20 sec on my clock left for two moves, after having used 19 sec on the first I would probably panic, abort the search, and play the best move, fail low or not. However, after having pondered 30 sec in the opponent's time, there is no reason to panic immediately, and using some of the remaing 20 sec to resolve the fail low might be very rewarding.

[mar]

What Sven probably means is that you have to decide how long to continue thinking after the ponder hit. You could already have searched for longer than what you would normally do, considering the initial time on your clock, but since your clock was not running, it is not obvious that you should apply the same stop criterion as when it had been runing.

E.g. when I have 20 sec on my clock left for two moves, after having used 19 sec on the first I would probably panic, abort the search, and play the best move, fail low or not. However, after having pondered 30 sec in the opponent's time, there is no reason to panic immediately, and using some of the remaing 20 sec to resolve the fail low might be very rewarding.

Yes I understand that. Of course I don't abort search due to timeout when in ponder mode. But the clock is running as I count time elapsed since the start of the search and i have a timelimit. So there's no issue with this either. Because as soon as I get a ponderhit I switch to normal mode. Then if my timecounter is < timelimit, i simply continue searching. Otherwise I simply return and play the move ASAP (in which case I save a lot of time which is the point of pondering IMO).
Note that this only works when pondering is done correctly (which uci enforces btw.), i.e. playing the expected opponent's move and pondering from my point of view.

[tpetzke]

Hi Sven,

I think it is simpler and more efficient to continue the search. When a ponderhit occurs I just tell the time control to start our clock. When in ponder mode TimeControl will never respond true when it gets a isTimeUp() call, now it starts comparing allocated and passed time. That's all.

TimeControl is however allocating a bit more move time per move when the engine is allowed to ponder as we are optimistic and guess we can get some additional thinking time for some moves.

When pondering terminates (not via UCI ponderhit or UCI stop) but because the search is done (e.g. the shortest path to a mate is found) you are however not allowed to output anything (as you would when your time was running).

Thomas...

[hgm]

Yes I understand that. Of course I don't abort search due to timeout when in ponder mode. But the clock is running as I count time elapsed since the start of the search and i have a timelimit.

But that was the entire point: A time limit that you calculate in advance would be sub-optimal, because you don't knw how long you will be allowed to ponder yet. In the example I gave the 'never-exceed' limit would be 19 sec, and applying it after 30-sec pondering would make you abort the search immediately. Even when you had still plenty of time to resolve the fail low.

Relating the never-exceed limit to the time left on your clock also seems sub-optimal; Given that you already thought 30 sec on the move, and already know a best move from the iteration that took, (say) 20 sec, you probably would not want the time for the last move to drop below 10 sec in a critical situation. So you might want to set the tile limit 10 sec.

The point is that you must weigh the improvement you could expect from spending (say) an extra second to the current move against the loss of quality you will get on the remaining move(s). Thinking in your own time, after 19 sec the remaining move would have only 1 sec, and even thinking 0.1 sec longer (which is not likely going to help much, it is just 0.5% extra) would take 10% of the time for that move. While after 30 sec of pondering, spending an extra second on the move (3% extra) only reduces the time for the last move by 5%. So it is a close call, and when you know for certain the 3% is going to help a lot by finishing an iteration or resolving a fail low, while the 5% extra the other move has could very well fall in an improductive 'time window' of just starting a new iteration, spending the extra second might on average be more profitable.

So there's no issue with this either. Because as soon as I get a ponderhit I switch to normal mode. Then if my timecounter is < timelimit, i simply continue searching. Otherwise I simply return and play the move ASAP (in which case I save a lot of time which is the point of pondering IMO).
Note that this only works when pondering is done correctly (which uci enforces btw.), i.e. playing the expected opponent's move and pondering from my point of view.

[lucasart]

Hi,

In pondering mode, while human player thinking, the program starts pondering by making a guessing move, let’s say move X, then going deeper in iteration starting from depth 1. Suppose a situation, after finishing depth 10 while going through depth 11, human player input move X. My question is, on its turn to move, should the program start calculating at depth 1 as usual or depth 10 in stead?

Thanks for any advices.

Best regards,
Teerapong

No what you describe is a ponderhit and the program simply continues searching. Only if it misses the guessed move (pondermiss) it aborts and restarts from depth 1.

Martin

Agreed. Also I would add that it doesn't matter! Thanks to hash tables you'll see that if you search 10 depth, and then start again from depth 1, you'll reach depth 10 almost immediately, even if the hash table is not used for pruning at the root node itself (assuming a correct implementation of hash table pruning of course)