Pondering? Yes. Ponder move? Maybe not.

[Dann Corbit]

Before I switched to "pondering on the move" I tried to do some anlaysis.
I could be well of the mark though...


Assuming the total time taken for all moves in a game is T.
Type I - ponder on the move
Type II - ponder on position (simpler one)

case I) very well predicted moves like obvious recapture, single replies and other forced moves. --> 10% of all moves
Here Type I has no significant advantage over Type II because 95% of the time is spent on the singular move.
So it is 10% * 5% * T = 0.005T time advantage for Type I.

Case II) well predicted moves. Assume 60% prediction rate (that will be 10 + 60 = 70% overall, a bit generous i suppose)
Here let us assume 50% of the time is spen on the first move. That means 50% is wasted by II so
70% * 50% * T = 0.35T time advantage for Type I.

Case III) prediction failure (30% of the moves). This is where I think Type II's advantage comes from. Type I is completely lost here while
II has some information on every move. So *disregarding previous search* that will be 100% advantage for II.
That will be 30% * 100% * T = 0.3T


So in summary we are roughly looking at 0.355T time advantage to I , as compared to 0.3T for II. Of course all of this depends
on the assumptions I made above but I think it is safe to say I tends to win over all.

I am wondering...

If we have a pv search with zero windows for non pv moves, it seems to me that searching the current position instead of the predicted move will actually produce about the same hash table in real-life anyway.

After all, the root move's current predicted move (pm) will get the full window slot and all the others will search with a brief zero-window scan. So unless the root pv choice changes *for your engine* the hash table entries will be dominated by the move you were going to ponder anyway.

The only place where the "ponder on the root move instead of the expected response" seems to produce an actual benefit (in my gedankenexperiment anyway) is when your own engine was going to switch after just a little more analysis on the root position anyway and the move your engine was about to switch to is the same as the one the opponent makes. So I guess that this is almost never.

It would make an interesting experiment.

[Desperado]

Hi Robert.

Well, i believe what you are saying. One will loose 1 or 2 plies when doing
a mpv-pondering.
But the idea that came to me is the following (theoretically).

While a normal search has to decide for a best move, the best move
should be examined as deep as possible.

But when pondering, there hasnt to be made any decision. So
why shouldnt examine the _width_ of the tree a bit more, to collect data? This may help later for selectivity, and could re-gain the lost of speed (plies). It may improve the quality of the following search.

while a decision-based search should be as accurate(deep) as possible , a non-decision-based(i mean pondering) search may have some other goals.

but no doubt, you are very experienced and so i think you are simply right by argueing that it doesnt profits.

[Don]

An idea:

Let's assume that a chess program, capable of pondering, stores nearly all of its search results in a traditional transposition table. The usual ponder technique is to take the second move of the predicted variation, execute that move, and start an indefinitely lasting ponder search assuming that the opponent will make the predicted move. If the opponent makes the move, then everything's fine, the ponder search is converted into a direct search, and no work was wasted. But if a different move was made by the opponent, then a new direct search has to be started and much work was done for nothing.

How about NOT making the predicted move prior to a ponder search? Instead, just start a search with the opponent on the move. When the opponent actually makes a move, the ponder search is killed, but all of its goodness remains in the transposition table. That data is used on the direct search and there should be a good amount of valuable data there regardless of what move the opponent actually made.

This is simply flawed, although it gets suggested about once every year or so.

Here's why:

Current approach results in at _least_ 50% ponder hits. That means that 50% of the time you ponder correctly, and can probably make a move in zero time, which saves 50% of your time for use on other moves.

If you just flip sides, you will search just as deeply as normal in a given amount of time, and find the best move for the opponent. But when time runs out, you are one ply short of the depth you would have reached. So you can not stop the search after the opponent moves, you are a ply short, so you have to use your own time as well, to make up that ply, and you don't save a thing.

Bob,

I think it's not as simple as that. I think this kind of pondering is not as good, but it's not that bad either.

Most of the search effort is spent on the primary move anyway - so what you have is just a somewhat inefficient version of normal pondering. It may even have some compensating advantages - such as anticipating a better response given an unusually long think by the opponent.

It's almost certainly not quite as good though.

[Dann Corbit]

Suppose that we do a full width search on the current position (the one the opponent is currently analyzing). By doing a full width search for each possible choice {otherwise we will see little, if any, benefit if the opponent does choose some move we did not imagine} then we have cut our search depth by 2 * opponent_possible_moves. On average, I believe that 35 is the average figure. So we will search about 70 times less effectively, I guess. Since we would have done a zero width search for the non-pv nodes, the real figure will probably be closer to 40 or 50 times less effectively {but the multiplier of 2 is almost surely an underestimate unless you have an elite engine with a branch factor of 2}.

I suspect that no engine will ever benefit from trying to ponder the position verses the predicted move unless it guesses horribly (and even then, the opponent's moves would also have to be *better* than the guess moves as well -- if the opponent chooses different moves but the moves are inferior -- so much the better).

I did not perform the experiment anywhere except my mind, but I am pretty sure about it anyway.

Consider also that analyzing the wrong position is not a complete waste since many future entries will be transpositions anyway.

I guess that the average benefit from pondering the guess move verses pondering the current position is approximately equal to the branching factor of the engine.

[Don]

Suppose that we do a full width search on the current position (the one the opponent is currently analyzing). By doing a full width search for each possible choice {otherwise we will see little, if any, benefit if the opponent does choose some move we did not imagine} then we have cut our search depth by 2 * opponent_possible_moves. On average, I believe that 35 is the average figure. So we will search about 70 times less effectively, I guess. Since we would have done a zero width search for the non-pv nodes, the real figure will probably be closer to 40 or 50 times less effectively {but the multiplier of 2 is almost surely an underestimate unless you have an elite engine with a branch factor of 2}.

I suspect that no engine will ever benefit from trying to ponder the position verses the predicted move unless it guesses horribly (and even then, the opponent's moves would also have to be *better* than the guess moves as well -- if the opponent chooses different moves but the moves are inferior -- so much the better).

I did not perform the experiment anywhere except my mind, but I am pretty sure about it anyway.

Consider also that analyzing the wrong position is not a complete waste since many future entries will be transpositions anyway.

I guess that the average benefit from pondering the guess move verses pondering the current position is approximately equal to the branching factor of the engine.

This can be tested. Just run some position and simulate pondering vs not pondering.

I have a test harness that makes it easy to do that. I may try it. I would assume each player is taking exact N seconds to make his move.

It would be interesting to see the difference in benefit for the case where the move is predicted correctly (where it is the second move in the initial PV.)

But I suggest that the benefit is a little more than just that. I think the position method will return less benefit when the move is predicted, but MORE benefit when it is not.

[bob]

Hi Robert.

Well, i believe what you are saying. One will loose 1 or 2 plies when doing
a mpv-pondering.
But the idea that came to me is the following (theoretically).

While a normal search has to decide for a best move, the best move
should be examined as deep as possible.

But when pondering, there hasnt to be made any decision. So
why shouldnt examine the _width_ of the tree a bit more, to collect data? This may help later for selectivity, and could re-gain the lost of speed (plies). It may improve the quality of the following search.

while a decision-based search should be as accurate(deep) as possible , a non-decision-based(i mean pondering) search may have some other goals.

but no doubt, you are very experienced and so i think you are simply right by argueing that it doesnt profits.

My goal, when playing a game, is to search as deeply as possible on each move I have to make, so that I can minimize tactical mistakes on my part and discover tactical mistakes on my opponent's part.

The current way of pondering is the _only_ way to maximize depth. Now if you can't predict your opponent's move 50% of the time, then other approaches can be better. But I carefully measure this statistic in every game Crafty plays and it is always over 50%. The stronger the opponent the better the prediction rate is...

[Dann Corbit]

Suppose that we do a full width search on the current position (the one the opponent is currently analyzing). By doing a full width search for each possible choice {otherwise we will see little, if any, benefit if the opponent does choose some move we did not imagine} then we have cut our search depth by 2 * opponent_possible_moves. On average, I believe that 35 is the average figure. So we will search about 70 times less effectively, I guess. Since we would have done a zero width search for the non-pv nodes, the real figure will probably be closer to 40 or 50 times less effectively {but the multiplier of 2 is almost surely an underestimate unless you have an elite engine with a branch factor of 2}.

I suspect that no engine will ever benefit from trying to ponder the position verses the predicted move unless it guesses horribly (and even then, the opponent's moves would also have to be *better* than the guess moves as well -- if the opponent chooses different moves but the moves are inferior -- so much the better).

I did not perform the experiment anywhere except my mind, but I am pretty sure about it anyway.

Consider also that analyzing the wrong position is not a complete waste since many future entries will be transpositions anyway.

I guess that the average benefit from pondering the guess move verses pondering the current position is approximately equal to the branching factor of the engine.

This can be tested. Just run some position and simulate pondering vs not pondering.

I have a test harness that makes it easy to do that. I may try it. I would assume each player is taking exact N seconds to make his move.

It would be interesting to see the difference in benefit for the case where the move is predicted correctly (where it is the second move in the initial PV.)

But I suggest that the benefit is a little more than just that. I think the position method will return less benefit when the move is predicted, but MORE benefit when it is not.

I think that fast games would be fine (e.g. game in one minute + 1 second or something) and against a variety of opponents of within +/- 100 Elo would be best.

32 games against each engine times 20 engines would give a pretty certain result, I think.

that would be 640 games * 2 settings = 1280 games. I think it would take a setup like Dr. Hyatt's to be able to test it in a reasonable time.

[MattieShoes]

In theory, there is some ponder hit rate at which the two methods are equal, yes?

If one could devise a scheme where one could estimate the likelihood of each move, one could only search the moves above a certain threshhold of likelihood. Perhaps one might get the benefit of both systems that way...

Of course, I don't know a way to estimate likelihood of a ponder hit, especially since you probably only have alpha bounds scores for the non-PV moves.

*sigh*

[bob]

In theory, there is some ponder hit rate at which the two methods are equal, yes?

I'll have to think about it for a minute. The two schemes are:

(1) use the predicted move, which is right well over 50% of the time. But assume 50% for argument's sake right now. 50% of the moves you do a search on your opponent's time, and when he moves you are ready with an instant response. So for every two moves you ponder, you get one free move and one wasted ponder search. You search each move to depth N while this is going on, although as the game progresses the depth goes up by one ply since you are saving the time used for every other move giving you more time for the remaining moves...

(2) ponder the position for the opponent to move. You search to depth N in the same time, but since you are searching from the opponent's perspective, your real search result is only to depth N-1 for you, so you have to search an extra ply, which would seem to kill this idea completely, since every move does the same thing every time, and you end up having to use your normal search time to reach that extra ply to catch up with (1) above.

I don't see how this idea even warrants consideration unless someone can give me a convincing explanation of how it helps. Searching to depth N+1 typically takes 2x as long as searching to depth N, making this a lose-lose every time. You could not even ponder at all, and _still_ do your normal depth N search and burn all your search time. So where's the advantage?

It seems like a simple approach but with zero benefit...

If one could devise a scheme where one could estimate the likelihood of each move, one could only search the moves above a certain threshhold of likelihood. Perhaps one might get the benefit of both systems that way...

Of course, I don't know a way to estimate likelihood of a ponder hit, especially since you probably only have alpha bounds scores for the non-PV moves.

*sigh*

That's a problem since we only know that move X is best, and all other moves are < X.

This discussion comes up reasonably often, but the "ponder the predicted move" makes the most sense. Here are a few prediction statistics from games vs good opponents: 35/55, 62/116, 46/63, 42/51, 96/138, 51/72, 57/96, 45/68, 36/50, 58/84, 39/60, 41/63, 25/37, 39/58.

So it seems that 50% is easily beatable, Which makes any other strategy look pretty unusable.

[hgm]

Logically, pondering on the projected move is a benefit if you can guess the right move at least 50% of the time. Statistically, it appears that most engines achieve at least that hit rate for ponder against all peers:
...

This subject was indeed discussed before, and the conclusion then was that the ponder-hit rate was a meaningless statistic: an engine can have 60% ponder hits, and pondering the move can still be inferior, as the ponder hits occur when the the opponent moves fast or immediate, and the misses when he thinks long. So predicting 60% of the ponder moves correct can still mean that 90% of your pondering time is wasted, pondering the wrong move...