An alternative pondering strategy

[sje]

The conventional wisdom is that the overall most effective ponder strategy is to run a regular search based on the second move in the predicted variation. But this goes against the possibility that the the predicted move might not be the best and that a different and better predicted move could be obtained by further search.

I suggest that a ponder search should not start until after some effort is made to further analyze the position on the board for better confidence in a predicted move. But how much extra effort?

The amount of extra effort could be based upon, in part, the estimated time available for a ponder search. One idea would be to take the average opponent response time and multiply it by some small factor like 0.2 or so and use this to search the board position to either verify the current predicted move or to come up with a better one. After this search, a regular ponder search would start using the (possibly changed) predicted move.

Alternatively, if many processors are available, one or more of them could be dedicated to producing better predicted moves in parallel with a regular ponder search.

[krazyken]

If you have N cores, and P is the probability of a ponder hit, and Q is the probability that your second choice is a ponder hit.

The work you get on average with traditional pondering is PN.

To get better results from split pondering you need:
PX + Q(N-X) > PN Where X is the number of cores you reserve for the primary ponder.
This is True only when Q > P so no gain can be had unless P is very low.

And I would think the effort to find the best reply to a move would be better spent before making the move.

If you come across a position where 2 best replies are equally likely you could play a safe bet by pondering both equally.

[sje]

A problem with your analysis is the assumption that the utility value of a P*N search is linear with respect to time. It is almost surely not true that the quality of a search taking 2*N units of time is twice as "good" as one taking only N units of time.

Ideally, we would have some magical probability estimation function mpe(x) (x:opponent move) where the available ponder time would be doled out to each move x-sub-n proportional to mpe(x-sub-n).

Possibly one could remember the relative refutation efforts for the different moves and use that for mpe(x), maybe adding a logarithmic transform to account for the lessened quality increase per unit time spent searching a single move.

[krazyken]

Well not necessarily assuming the value is linear. More along the assumption that extra depth more useful than extra breadth.

The biggest problem with any estimation is that the time available will be extremely difficult to approximate. Perhaps going about it the other way around makes more sense, full ponder 1 move for some time until the search is stable, and the returns are diminished, then consider alternatives.

[bob]

The conventional wisdom is that the overall most effective ponder strategy is to run a regular search based on the second move in the predicted variation. But this goes against the possibility that the the predicted move might not be the best and that a different and better predicted move could be obtained by further search.

I suggest that a ponder search should not start until after some effort is made to further analyze the position on the board for better confidence in a predicted move. But how much extra effort?

The amount of extra effort could be based upon, in part, the estimated time available for a ponder search. One idea would be to take the average opponent response time and multiply it by some small factor like 0.2 or so and use this to search the board position to either verify the current predicted move or to come up with a better one. After this search, a regular ponder search would start using the (possibly changed) predicted move.

Alternatively, if many processors are available, one or more of them could be dedicated to producing better predicted moves in parallel with a regular ponder search.

This is discussed every few years or so, but it just doesn't hold up when analyzed carefully.

For example, today's branching factor is about 2.0 typically. When you do a search to (say) 20 plies, you have a predicted move that is based on a 19 ply search (since you lop off the first ply when you play the move. How can you possibly do a better search than 19 plies, unless you use more than 1/2 the normal time you would use for a real search, which is not practical. So he predicted move is the best there is. For example, in the Rybka at the ACCA tournament, the game lasted 68 moves. Crafty predicted correctly 50 times. So what strategy could _possibly_ improve on that? The idea of using different processors to search different ponder moves is no good. Right now, 50/68 of the time I ponder the correct move with all processors, so that a ponder search reaches max depth and is useful 50/68 ths of the time. If you search two ponder moves instead, each one gets 1/2 as deep in the same time. I will get more ponder hits, but for each ponder hit I have to search 2x as long to reach the same depth.

The current approach really is the best there is, unless you can't predict at least 50% of the time. Against Symbolic, crafty predicted correctly 31 out of 43 moves played. Against ChessThinker, 34 out of 43, against slowchess, 49 out of 66, and against dirty 36 out of 53. Based on that, nothing will help...

[bob]

If you have N cores, and P is the probability of a ponder hit, and Q is the probability that your second choice is a ponder hit.

The work you get on average with traditional pondering is PN.

To get better results from split pondering you need:
PX + Q(N-X) > PN Where X is the number of cores you reserve for the primary ponder.
This is True only when Q > P so no gain can be had unless P is very low.

And I would think the effort to find the best reply to a move would be better spent before making the move.

If you come across a position where 2 best replies are equally likely you could play a safe bet by pondering both equally.

that fails. Here is why. If you ponder just one, you have a 50% probability of being right, and when your opponent moves you can move instantly in zero time. If you ponder both, now your probability of being right is 100%, but you have only spent 50% of the desired effort when your opponent moves. So you have to search the other 50% before making a move. These are equivalent. But if you can predict correctly more than 50% of the time, the second approach loses ground...

[Dirt]

As soon as I read your thread subject I thought you were going to suggest something else. I'll just give an example:

When you make your move your score is 10 cp in your favor. Once you've pondered one ply deeper in the game you find you are now ahead by 500 cp. This means there is a good chance you're going to win, but it also raises the probability that you're pondering the wrong move. Under these conditions it might make sense to save your PV, in case your opponent does make your predicted move, and start pondering an alternative.

Unfortunately, even if this helps I don't think this type of situation would occur often enough to matter.

[jwes]

The conventional wisdom is that the overall most effective ponder strategy is to run a regular search based on the second move in the predicted variation. But this goes against the possibility that the the predicted move might not be the best and that a different and better predicted move could be obtained by further search.

I suggest that a ponder search should not start until after some effort is made to further analyze the position on the board for better confidence in a predicted move. But how much extra effort?

The amount of extra effort could be based upon, in part, the estimated time available for a ponder search. One idea would be to take the average opponent response time and multiply it by some small factor like 0.2 or so and use this to search the board position to either verify the current predicted move or to come up with a better one. After this search, a regular ponder search would start using the (possibly changed) predicted move.

Alternatively, if many processors are available, one or more of them could be dedicated to producing better predicted moves in parallel with a regular ponder search.

This is discussed every few years or so, but it just doesn't hold up when analyzed carefully.

For example, today's branching factor is about 2.0 typically. When you do a search to (say) 20 plies, you have a predicted move that is based on a 19 ply search (since you lop off the first ply when you play the move. How can you possibly do a better search than 19 plies, unless you use more than 1/2 the normal time you would use for a real search, which is not practical. So he predicted move is the best there is. For example, in the Rybka at the ACCA tournament, the game lasted 68 moves. Crafty predicted correctly 50 times. So what strategy could _possibly_ improve on that? The idea of using different processors to search different ponder moves is no good. Right now, 50/68 of the time I ponder the correct move with all processors, so that a ponder search reaches max depth and is useful 50/68 ths of the time. If you search two ponder moves instead, each one gets 1/2 as deep in the same time. I will get more ponder hits, but for each ponder hit I have to search 2x as long to reach the same depth.

The current approach really is the best there is, unless you can't predict at least 50% of the time. Against Symbolic, crafty predicted correctly 31 out of 43 moves played. Against ChessThinker, 34 out of 43, against slowchess, 49 out of 66, and against dirty 36 out of 53. Based on that, nothing will help...

Reasons that you might not want to spend all your time pondering the expected move (from the clearest to the most arguable).
If after the expected move:
1. you have no legal moves.
2. the position now is an egtb hit.
3. the search returns an exact result (probably mate in n, possibly a draw).
4. the search returns what crafty calls an easy move, and has been pondered for significantly more time than would normally be spent on an easy move.
5. you have only one legal move.
6. the ponder search has lasted long enough that you would move instantly if the opponent makes the expected move.

[bob]

The conventional wisdom is that the overall most effective ponder strategy is to run a regular search based on the second move in the predicted variation. But this goes against the possibility that the the predicted move might not be the best and that a different and better predicted move could be obtained by further search.

I suggest that a ponder search should not start until after some effort is made to further analyze the position on the board for better confidence in a predicted move. But how much extra effort?

The amount of extra effort could be based upon, in part, the estimated time available for a ponder search. One idea would be to take the average opponent response time and multiply it by some small factor like 0.2 or so and use this to search the board position to either verify the current predicted move or to come up with a better one. After this search, a regular ponder search would start using the (possibly changed) predicted move.

Alternatively, if many processors are available, one or more of them could be dedicated to producing better predicted moves in parallel with a regular ponder search.

This is discussed every few years or so, but it just doesn't hold up when analyzed carefully.

For example, today's branching factor is about 2.0 typically. When you do a search to (say) 20 plies, you have a predicted move that is based on a 19 ply search (since you lop off the first ply when you play the move. How can you possibly do a better search than 19 plies, unless you use more than 1/2 the normal time you would use for a real search, which is not practical. So he predicted move is the best there is. For example, in the Rybka at the ACCA tournament, the game lasted 68 moves. Crafty predicted correctly 50 times. So what strategy could _possibly_ improve on that? The idea of using different processors to search different ponder moves is no good. Right now, 50/68 of the time I ponder the correct move with all processors, so that a ponder search reaches max depth and is useful 50/68 ths of the time. If you search two ponder moves instead, each one gets 1/2 as deep in the same time. I will get more ponder hits, but for each ponder hit I have to search 2x as long to reach the same depth.

The current approach really is the best there is, unless you can't predict at least 50% of the time. Against Symbolic, crafty predicted correctly 31 out of 43 moves played. Against ChessThinker, 34 out of 43, against slowchess, 49 out of 66, and against dirty 36 out of 53. Based on that, nothing will help...

Reasons that you might not want to spend all your time pondering the expected move (from the clearest to the most arguable).
If after the expected move:
1. you have no legal moves.
2. the position now is an egtb hit.
3. the search returns an exact result (probably mate in n, possibly a draw).
4. the search returns what crafty calls an easy move, and has been pondered for significantly more time than would normally be spent on an easy move.
5. you have only one legal move.
6. the ponder search has lasted long enough that you would move instantly if the opponent makes the expected move.

for 1-3 I would agree. But how often does that happen when compared to the rest of the searches where things go normally. You are introducing a different idea completely than what we were talking about, which is pondering more than one move at the same time using different nodes.

4-5 are obvious

6 is not so obvious. Do you not think you can still find an unexpected crushing move after you have already used a normal search time on a ponder? If you believe that move is best, I believe you should grind away as you might well find something better.

The only serious drawback that was not mentioned is that sometimes you start a ponder and your ponder move fails way high. Here you could legitimately quit and try to find something else to ponder, knowing that you can find this move should your opponent make the expected move, which you believe to be unlikely since he will probably see the problem you found so quickly also. And I have this on my to-do list, but the problem becomes finding a different move which is not easy to do as it took a deep search to find the move that now fails low for the opponent...

[hgm]

Indeed this subject was discussed before, and the conclusion was that it only pays to switch pondering to a second move after you are satisfied with the time you spend on your first move (so you could move instantly). Spending more time on that move would then not be very productive, as the quality of a move only increases logarithmicaly with the time spend on it. So if you already spent very long on a move, investing even more time in it will not contribute as much to a better game result asimroving your chances for getting some extra time for all subsequent moves in case the opponent plays a less likely alternative.