Iteration in pondering

[tpetzke]

I see no reason to do any time allocation when starting to ponder, since the engine's clock from the external view is not running, just as in a game of human players where you analyze the position while it is the opponent's move.

Usually within your engine you have a rule set that determines how much time you allocate for a move before you start searching. It might involve the game state, how much time you have left, whether there is an time increment or whether this game is played with Ponder ON.

You have probably good reasons to allocated the time in your engine the way you do it.

There might also be good reasons where it is useful to extend the time you previously have allocated (e.g. when you see a sudden drop in the score for the move you considered best so far, when you are close to finish your iteration ...).

Not having spent my own time on the move because I was in ponder mode I consider a rather bad reason to violate my own allocation rule set in spending more time on it. Maybe the gained time is at another point in the game much more useful.

So if my engine allocates 1 minute for a move and starts the search in ponder mode then it stops the search after a ponderhit command or 1 minute, whatever comes last.

This might trigger an immediate move response after the opponent moved and so not letting the opponent ponder on its own on my time.

Thomas...

[Sven]

I see no reason to do any time allocation when starting to ponder, since the engine's clock from the external view is not running, just as in a game of human players where you analyze the position while it is the opponent's move.

Usually within your engine you have a rule set that determines how much time you allocate for a move before you start searching. It might involve the game state, how much time you have left, whether there is an time increment or whether this game is played with Ponder ON.

You have probably good reasons to allocated the time in your engine the way you do it.

There might also be good reasons where it is useful to extend the time you previously have allocated (e.g. when you see a sudden drop in the score for the move you considered best so far, when you are close to finish your iteration ...).

Not having spent my own time on the move because I was in ponder mode I consider a rather bad reason to violate my own allocation rule set in spending more time on it. Maybe the gained time is at another point in the game much more useful.

So if my engine allocates 1 minute for a move and starts the search in ponder mode then it stops the search after a ponderhit command or 1 minute, whatever comes last.

This might trigger an immediate move response after the opponent moved and so not letting the opponent ponder on its own on my time.

Searching itself does not inherently require time allocation in advance, it is only the need to stop searching at some point that creates that requirement. Allocating time means to define time limits (actually one but I think many engines have something like a "hard" and a "soft" time limit, at least). But those limits are never exceeded during pondering. Either you never check against those limits, or you check but always ignore it when in pondering mode. I think it is sufficient to only define those limits at the moment when a ponderhit occurs, possibly taking into account the time you were searching in pondering mode. This is also independent from the original question of this thread "continue search on ponderhit, or start over at the root?", it can be done in both cases. So you can still decide at that point to allocate as much time as you want, in your example either the remainder of one minute minus the elapsed pondering time, or even "zero" if pondering time already exceeded one minute.

Defining unused time limits when you start pondering appears illogical to me. It may have implementation reasons, of course, to do so, but I'd consider it a "hack" I know that chess programming is full of hacks, unfortunately ...

Sven

[tpetzke]

Hi,

Defining unused time limits when you start pondering appears illogical to me. It may have implementation reasons, of course, to do so, but I'd consider it a "hack" I know that chess programming is full of hacks, unfortunately ...

or the other way around (not doing so would be a hack and not doing so increases the complexity of the ponder implementation)

When the GUI sends the engin to ponder it sends the time control data along with that command. So why not using it to setup the time control right away with it. The "ponderhit" command comes with no additional data as it is just meant to signal the engin that now its running on its own time.

To come back to the original question, the UCI protocol is designed to continue the search when the ponderhit is received. You are allowed to do whatever you want even ponder on a different move than the GUI sends but then the ponder implementation starts getting complex, otherwise it is really simple.

Thomas...

[Sven]

Hi,

Defining unused time limits when you start pondering appears illogical to me. It may have implementation reasons, of course, to do so, but I'd consider it a "hack" I know that chess programming is full of hacks, unfortunately ...

or the other way around (not doing so would be a hack and not doing so increases the complexity of the ponder implementation)

When the GUI sends the engin to ponder it sends the time control data along with that command. So why not using it to setup the time control right away with it. The "ponderhit" command comes with no additional data as it is just meant to signal the engin that now its running on its own time.

To come back to the original question, the UCI protocol is designed to continue the search when the ponderhit is received. You are allowed to do whatever you want even ponder on a different move than the GUI sends but then the ponder implementation starts getting complex, otherwise it is really simple.

"Continue the search" from the protocol viewpoint does not mean anything for the internal implementation. From an outside view my proposal does of course continue the search.

Btw, implementing the pondering feature in an engine is also possible for WinBoard engines So we are not automatically bound to UCI with this topic ...

UCI of course needs to pass these time control parameters together with the "ponder" keyword, there will be no later point in time to do that. But noone prevents an engine to actually use these parameters only at the point where they really have to be used, and this can be designed in the one or the other way, as we now have agreed upon

Thanks for the interesting discussion. I hope we did not confuse the OP too much.

Sven

[micron]

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

This is not necessarily true. In my engine, a second search (of the same position) is not significantly faster than the first.
I tracked this strange disappointment to the treatment of TT cutoffs in PV nodes.

After changing
if ( !pvNode && TTScoreIsOKForCutoff() ) return ttScore; // !pvNode condition is worth ≈20 Elo
to
if ( TTScoreIsOKForCutoff() ) return ttScore;
re-searching the same position becomes virtually instantaneous.

Code: Select all

go depth 19
...[first time]
info score cp 24 time 6988 depth 18 nodes 32070147 pv e2e4 e7e5 g1f3 g8f6 f3e5 d8e7 e5f3 e7e4 
info score cp 24 time 13797 depth 19 nodes 63713233 pv e2e4 e7e5 g1f3 g8f6 f3e5 d8e7 e5f3 e7e4 f1e2 f8e7 e1g1 e8g8 b1c3 e4g4 f1e1 f8e8 d2d4 b8c6 c1g5 d7d6 
bestmove e2e4 ponder e7e5

go depth 19
...[second time]
info score cp 24 time 0 depth 18 nodes 644 pv e2e4 
info score cp 24 time 0 depth 19 nodes 682 pv e2e4 
bestmove e2e4

[Desperado]

Just my 2 cents...

Repeating the search on a ponderhit may be an _easy_ solution, but
imho is certainly not a very good idea. The reasons i consider are:

* overhead is certain (maybe small, but it exists)

* search instabilities, transposition table handling will strongly
influence, if the overhead is costly or not. There is _absolutelely_
no guarantee to get a cheap research.

eg: set Hash to 1MB , search to fix depth n (what your engine is
able to do in some seconds) from the startpos.
now repeat the search n-times. You will see a behaviour like this:
nodecout: drop,drop,raise,drop,raise,raise,drop, .... or
any other random sequence.

* ponder time was for example 30 min, and your time managment
wants to play a move in 10 min, so are you sure you even reach the
same level ?

* finally, the argument to have an _easy_ solution, which can be handled
clean, is not that strong as one could think, because there are existing
other _trivial_ solutions which match much more with the whole
purpose.

eg: just move what you have on ponderhit !

of course this isnt an optimal solution too, but is has absolutely no
overhead and it avoids the above mentioned problems.

So, my suggestion is, to spend some time for a clean implementation,
which goes hand in hand with the own time-management, or if someone
really wants to circumvent all these puzzling implementation details,
just move what you have found so far (or finish iteration at least, which
is also another easy, clean way to solve the thing)

Michael

[hgm]

* ponder time was for example 30 min, and your time managment
wants to play a move in 10 min, so are you sure you even reach the
same level ?

Well, you certainly will reach the same level: the hash hit in the root node will give you that after searching 1 node. And if you don't probe there, the 35-or-so hash hits at the 1-ply level will repeat your last finished iteration in a 36-node search.

Unless you would be so foolish to allow overwriting of the 36 deepest entries in your hash table...

[Desperado]

* ponder time was for example 30 min, and your time managment
wants to play a move in 10 min, so are you sure you even reach the
same level ?

Well, you certainly will reach the same level: the hash hit in the root node will give you that after searching 1 node. And if you don't probe there, the 35-or-so hash hits at the 1-ply level will repeat your last finished iteration in a 36-node search.

Unless you would be so foolish to allow overwriting of the 36 deepest entries in your hash table...

Sorry HG, but i dont think this is "100%" true. Maybe not even 10%

As i already mentioned the transposition table handling _can_ play a role.
This also includes the replacement scheme, which can in its simple form
be a always replace technique. now, depending on the hash size of course,
the chance is high each slot will be overwritten several times.
Think of search depths which produce much more nodes than slots are
available. Even if you have a 2 Gig table, with todays nps, a 30 min
search will overwrite everything.

Or even the other way around, because a pv-node will be researched
with another window, so the pv will be researched and somewhere
in the tree because of different hash table content,it leads to a fail lo/hi
at this pv-node, and suddenly all this leads to
another decision at the root.
Now will the new pv really get the same level
because of some search instabilities ?

Well, i am pretty sure that you dont get 100% the same pv (in general)
each time you research the node, and even not always the same
best-move. And if the search will decide for another pv,
the chance it will reach the same level (10 mins vs 30 mins) is unrealistic,
compared to the level of the pv produced in ponder mode.

So,I dont think you have a guarantee to reach the same level (in general).

Michael

[bob]

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

I do what you suggest in Crafty. But it is not clear that it makes that much difference. Ostensibly, if I search to depth 20 and make a move, and start pondering, I predict the second move in the PV, so the resulting position should be able to use all the hash entries (if they were not overwritten) to quickly complete depth 18 (which I had really already completed since I did 20, played a move and assumed a move).

I start at 19 in Crafty, just because it seems like the right thing to do. And it helps on infrequent occasions, and can rarely hurt, so...

[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

I do what you suggest in Crafty. But it is not clear that it makes that much difference. Ostensibly, if I search to depth 20 and make a move, and start pondering, I predict the second move in the PV, so the resulting position should be able to use all the hash entries (if they were not overwritten) to quickly complete depth 18 (which I had really already completed since I did 20, played a move and assumed a move).

I start at 19 in Crafty, just because it seems like the right thing to do. And it helps on infrequent occasions, and can rarely hurt, so...

The question, as well as the discussion we already had about it, was how to react on a ponderhit. It seems you are talking about how you start pondering.

Sven