Speculative deep pondering

[hgm]

I am thinking about how to make use of all those extra cores in my PC without going through the drudgery of making all my engines SMP. One way would be to implement 'deep pondering', i.e. use the extra cores to think on positions that, according to earlier PVs, will occur after 3, 5, 7, ... ply during the opponent's turn (where the engine that just moved is pondering on the position 1 ply later, as usual), or after 2, 4, 6, ... ply during your own turn (where the 'active' engine is thinking on the current position). For each of this an independent single-core engine process could be started.

I understand that the 2007 WCCC participant GridChess did something like that, but I could not find an exact description so far on how it selects what to ponder about.

Obviously every move (opponent as well as own) gives an opportunity for a ponder miss, making the searches on positions reached through that move useless when another move is played, so that the corresponding processes can be aborted and returned to an 'idle' state, waiting to be re-assigned. To decide what to make them work on next, one could examine the PVs of the engines that are still thinking on 'valid' positions (i.e. still reachable). There must be at least one such engine thinking on the current game position, or just having produced the move leading to it. In the case where this was just started because of a 'global ponder miss' where the opponent just did a move that was expected by none of the searching engines, one could delay, say, 10% of the nominal search time to obtain a PV of reasonable depth for the current position.

We can then assign searches to all of the positions along this PV where we have the move, in so far they were not being searched already. It is possible that we have multiple candidates for a certain future position, though. E.g. the process that just moved might predict another reply than the 4th move of the PV for the position 2 ply earlier (on which we set a process thinking at the time). It would probably be a waste to just abort that because the prediction changed, as it accumulated a lot of search time already, and the opponent might still play that move. So probbaly we would want to make the engine that just moved ponder about its own predicted reply, increasing our chances for a ponder hit. Similarly, the deep ponder for the position 3 ply from now could be based on the first 4 moves of the PV of the process that just moved. But if there already is already a process thinking on the position after the first 2 moves of that PV, we might take its first 2 PV moves instead.

Anyway, what I would want to make is a general adapter that behaves towards the GUI like an engine, but actually runs multiple engine processes. It would have to be in command of time management, so it would just set the engines analyzing positions predicted from the PVs produced by the analysis of earlier positions. When it decides it is time to move, it would then abort the analysis of positions that are no longer relevant after the move, and assign any idle engines to new positions that are. If the engines would print a PV for every improvement they get for the root move, as well as print when they start a new iteration, it should be possible to do a pretty advanced time management externally (i.e. giving extra time in case of disastrous fail lows, etc.).

The advantage is that I could use that same adapter for all my engines. And especially in mini-Shogi the ponder-hit rate seems very high, so that positions further along the PV have a pretty high chance of indeed materializing.

[TimoK]

Hi Harm Geert,

this is an excellent idea to build such a general adapter like you described it! I spent some time experimenting with Kai's implementation "GridChess" two or three years ago. Actually there is a lot of potential in the idea of optimistic pondering. But Kai is very short on time these days so it's difficult for him to further work on this project.

If you are interested in his ideas described in his dissertation, I can bring my copy of the book to Leiden (ICGA games): http://www.shaker.de/de/content/catalog ... 440-0803-6

Best regards
Timo

[hgm]

I would be grateful if you could do that! I would be interested to have a peek at how he selects the positions to ponder about.

As I have only a quad core for use at the Olympiad, I will probably be limited to pretty basic choices anyway. But with more cores it becomes interesting.

[Dann Corbit]

I am thinking about how to make use of all those extra cores in my PC without going through the drudgery of making all my engines SMP. One way would be to implement 'deep pondering', i.e. use the extra cores to think on positions that, according to earlier PVs, will occur after 3, 5, 7, ... ply during the opponent's turn (where the engine that just moved is pondering on the position 1 ply later, as usual), or after 2, 4, 6, ... ply during your own turn (where the 'active' engine is thinking on the current position). For each of this an independent single-core engine process could be started.

I understand that the 2007 WCCC participant GridChess did something like that, but I could not find an exact description so far on how it selects what to ponder about.

Obviously every move (opponent as well as own) gives an opportunity for a ponder miss, making the searches on positions reached through that move useless when another move is played, so that the corresponding processes can be aborted and returned to an 'idle' state, waiting to be re-assigned. To decide what to make them work on next, one could examine the PVs of the engines that are still thinking on 'valid' positions (i.e. still reachable). There must be at least one such engine thinking on the current game position, or just having produced the move leading to it. In the case where this was just started because of a 'global ponder miss' where the opponent just did a move that was expected by none of the searching engines, one could delay, say, 10% of the nominal search time to obtain a PV of reasonable depth for the current position.

We can then assign searches to all of the positions along this PV where we have the move, in so far they were not being searched already. It is possible that we have multiple candidates for a certain future position, though. E.g. the process that just moved might predict another reply than the 4th move of the PV for the position 2 ply earlier (on which we set a process thinking at the time). It would probably be a waste to just abort that because the prediction changed, as it accumulated a lot of search time already, and the opponent might still play that move. So probbaly we would want to make the engine that just moved ponder about its own predicted reply, increasing our chances for a ponder hit. Similarly, the deep ponder for the position 3 ply from now could be based on the first 4 moves of the PV of the process that just moved. But if there already is already a process thinking on the position after the first 2 moves of that PV, we might take its first 2 PV moves instead.

Anyway, what I would want to make is a general adapter that behaves towards the GUI like an engine, but actually runs multiple engine processes. It would have to be in command of time management, so it would just set the engines analyzing positions predicted from the PVs produced by the analysis of earlier positions. When it decides it is time to move, it would then abort the analysis of positions that are no longer relevant after the move, and assign any idle engines to new positions that are. If the engines would print a PV for every improvement they get for the root move, as well as print when they start a new iteration, it should be possible to do a pretty advanced time management externally (i.e. giving extra time in case of disastrous fail lows, etc.).

The advantage is that I could use that same adapter for all my engines. And especially in mini-Shogi the ponder-hit rate seems very high, so that positions further along the PV have a pretty high chance of indeed materializing.

The Idea search of Aquarium Chess Gui is much like your idea.

You could have a number of interesting things to test.

Hardening the pv with forward analysis along the pv nodes is an interesting idea. In some sense, the 1 node at a time pv advancement of the Exchess search does this implicitly. Similar also to making forward guesses when pondering.

You could have sampling of the most interesting forward positions, and throw additional effort to those threads that show the most promise. A sort of Monte Carlo guided search.

You could have mate searches running on branches that show threats.

You could have merit based search, which operates as a function of a number of parameters (score at the root, king safety threats, positional merit and tactical merit, for instance). More threads of execution would be given to the node paths with greatest merit.

You could find goal positions and work backwards.

The real challenge will be to keep it efficient, so that the new search techniques enable superior efficiency rather than greater SMP loss.

[JoshPettus]

That sounds really fascinating Harm! Good luck in the Olympiad!