SMP and pondering

[JVMerlino]

I apologize in advance if this topic has ever been discussed.

So I was finally able to successfully implement Dan Homan's "Lazy SMP" in Myrddin and the results are reasonably encouraging (roughly +50 elo for 2 CPU). My results are not as good as others because I'm also an extremely lazy programmer. So perhaps my implementation is Lazy^2 SMP.

Anyway, this process led me to a thought about SMP combined with pondering.

I assume (perhaps incorrectly) that most SMP implementations handle pondering with all threads/processes the same way -- assume that the opponent is going to make the ponder move and search from there. But has anybody tried devoting some subset of the threads, maybe one out of every four, or maybe half of them, to searching the position BEFORE the ponder move (i.e. the position resulting from the move your engine just made) to better prepare if you don't get a ponder hit?

This is kind of like Dan Homan's lazy SMP work sharing, except applying it to safeguarding against not getting a ponder it.

Is this a stupid idea? I wouldn't trust the validity of the idea to just the results I might get from my engine, although I'll definitely give it a try if this turns out to be a novel idea.

jm

[jdart]

That is a novel idea as far as I know.

It is kind of technically hard to do in my program, since each search gets its own hashtable and other global variables.

--Jon

[bob]

I apologize in advance if this topic has ever been discussed.

So I was finally able to successfully implement Dan Homan's "Lazy SMP" in Myrddin and the results are reasonably encouraging (roughly +50 elo for 2 CPU). My results are not as good as others because I'm also an extremely lazy programmer. So perhaps my implementation is Lazy^2 SMP.

Anyway, this process led me to a thought about SMP combined with pondering.

I assume (perhaps incorrectly) that most SMP implementations handle pondering with all threads/processes the same way -- assume that the opponent is going to make the ponder move and search from there. But has anybody tried devoting some subset of the threads, maybe one out of every four, or maybe half of them, to searching the position BEFORE the ponder move (i.e. the position resulting from the move your engine just made) to better prepare if you don't get a ponder hit?

This is kind of like Dan Homan's lazy SMP work sharing, except applying it to safeguarding against not getting a ponder it.

Is this a stupid idea? I wouldn't trust the validity of the idea to just the results I might get from my engine, although I'll definitely give it a try if this turns out to be a novel idea.

jm

I won't say it is a stupid idea, but it is a bad idea. Here is some simple math to illustrate why.

A typical chess engine will correctly predict the opponent's move at least 50% of the time.

Suppose you have two cpus.

If you ponder two different moves, you are spending 1/2 the normal search time on each, and you are GUARANTEEING that one of the two searches is completely wasted since both predicted moves can't be right. If your target time is 3 minutes, and you ponder for 3 minutes before your opponent moves, you will never spend more than 1.5 minutes during the ponder search since the other half was wasted. You STILL have to search longer to get back to your normal target.

With a normal search and ponder, when your opponent moves, you are ready to move instantly as you have used all of your computing power on your opponent's move. If you mis-predict, you save nothing. So at a modest 50% correct prediction rate, 1/2 of your moves can be played instantly. With your "ponder one move per cpu" idea, your prediction rate will go up a bit, but you will never make an instant move and save a lot of time. You will have to search longer (50% longer than the search already done during pondering) to use the right amount of time.

In short, you end up losing time even though your prediction rate goes up a bit. I just checked a few of Crafty's recent logs. 4 games. In the first, Crafty correctly predicted 49 out of 80 moves, in the second, 48 out of 67, in the third 43 out of 76 and in the fourth 38 out of 56. Well above 50% in all 4. If you start to drop significantly below 50%, this might change, but I've not seen such numbers except against VERY weak opponents where you win easily anyway.

The only thing I hate to see in my current "ponder just best move" algorithm is the fail-high case. If you fail high while pondering, you can safely assume your opponent will fail low unless he is much worse (where this becomes moot anyway). Now you are pondering on a move your opponent likely will not play. I am before long going to save the current results when the score jumps significantly, and then search for something else to ponder instead. Only problem is, what move to ponder? It is hard to discover that the current move is bad, so it will be quite hard to find a better move to ponder. Each time I have tried to do this thing, that becomes the stumbling block. Yes the current move is no good, but how to pick something reasonable from the remaining n-1 moves. Occasionally this move is still best, it is just failing low along with everything else, so you still see a win with the normal pondering. But more often you know you are just wasting cpu cycles, but it is hard to figure out what you ought to be doing instead.

BTW others have proposed a different alternative. Instead of actually pondering, just switch sides and search for the opponent's best move until he moves. If he does, you at least have searched the played move to some depth, saving some time. But when I tried, it was almost as bad as not pondering at all. Not quite, but fairly close.

I do have a possible suggestion for pondering in general. If you are in book, make a not of all the book alternatives you have that you consider to be playable for the opponent, so that you know you have an instantly ready book move ready if he plays any of those moves. Now search the remaining non-book moves for your opponent, and find the best. Do this with a short search (maybe 1/10 the normal target time). Then if your opponent plays a non-book move, you have a reasonable chance that you are already pondering the non-book move he plays. This I do in Crafty and it works well.

[hgm]

A typical chess engine will correctly predict the opponent's move at least 50% of the time.

That is a meaningless statistic. You could have 50% ponder hits, and still hardly get any time gain from pondering at all. If the opponent implemented 'easy move' in his time management, and thinks 10 times shorter on an easy move, and 50% are easy moves, and (of course) you predicted those 100% correctly, (and thus none of the others), you would gain only 9% (1/11) in time. Having a 25% hit rate on both the difficult and the easy moves (so 25% overall, halving the hit rate) would save you 25% overall (tripling the effectivity).

Ponder hits are more likely on opponent 'easy moves', but they also gain little time here. You want ponder hits on the difficult moves, where he thinks long. What you should measure is not hit rate, but time saved by pondering (= hit rate weighted by ponder time on that move).

[JVMerlino]

BTW others have proposed a different alternative. Instead of actually pondering, just switch sides and search for the opponent's best move until he moves. If he does, you at least have searched the played move to some depth, saving some time. But when I tried, it was almost as bad as not pondering at all. Not quite, but fairly close.

As I was expecting, it was probably a fruitless idea, particularly as an engine gets stronger.

It was actually this "different alternative" that I was suggesting, although it surprises me somewhat that it is only slightly better than not pondering at all.

[bob]

A typical chess engine will correctly predict the opponent's move at least 50% of the time.

That is a meaningless statistic. You could have 50% ponder hits, and still hardly get any time gain from pondering at all. If the opponent implemented 'easy move' in his time management, and thinks 10 times shorter on an easy move, and 50% are easy moves, and (of course) you predicted those 100% correctly, (and thus none of the others), you would gain only 9% (1/11) in time. Having a 25% hit rate on both the difficult and the easy moves (so 25% overall, halving the hit rate) would save you 25% overall (tripling the effectivity).

Ponder hits are more likely on opponent 'easy moves', but they also gain little time here. You want ponder hits on the difficult moves, where he thinks long. What you should measure is not hit rate, but time saved by pondering (= hit rate weighted by ponder time on that move).

I've done that, actually. But it is STILL difficult to produce a meaningful number, because ponder hit rate is not fixed. The 4 games I gave data for were against the same opponent, same time control, yet the numbers were not consistent. As far as "easy moves" go (for those that still use such a thing) there are not that many. Most are re-captures and most re-captures don't have just one way to recap anyway. I can probably find some good data from old log files where Crafty did use the old "easy move" technique. I think that is much less of a problem than the problem where your opponent also ponders, and if he predicts correctly when you did not, you search the normal time to make a move that he is pondering, you then start pondering the right reply but he moves instantly, so you save no time. That is a much more serious problem than the easy-move issue, and it can see you with a really significant ponder hit rate but no time saved at all.

[bob]

BTW others have proposed a different alternative. Instead of actually pondering, just switch sides and search for the opponent's best move until he moves. If he does, you at least have searched the played move to some depth, saving some time. But when I tried, it was almost as bad as not pondering at all. Not quite, but fairly close.

As I was expecting, it was probably a fruitless idea, particularly as an engine gets stronger.

It was actually this "different alternative" that I was suggesting, although it surprises me somewhat that it is only slightly better than not pondering at all.

The problem is that you want to spend "target time" finding the best move in reply to your opponent. If you search from his perspective, you are spending time on a lot more than just the move he actually plays...

[Evert]

I've always thought that it would be interesting to utilise some of that extra CPU power to different search strategies: for instance a search with fewer reductions running in parallel to a heavily reduced search, or even a multi-PV search (the latter might be interesting for a ponder search if you don't know what the best move to ponder on is: a multi-PV search for the opponent, with some sort of non-PV reduction applied to other moves so you don't waste too much time on them and stay "close" to the "standard" ponder search, where you assume that the opponent played what you think is the best move).

I suspect that these things may start to pay off when the number of cores becomes so high that you can no longer use them as efficiently to speed up an YBW search, but I don't know where the break-even point would be (somewhere beyond 30 cores, I would expect: ~the number of moves you can search in parallel in a single ALL-node in the middle game). Obviously I've never tried it.

[JVMerlino]

I've always thought that it would be interesting to utilise some of that extra CPU power to different search strategies: for instance a search with fewer reductions running in parallel to a heavily reduced search...

I also had this thought. Not that I would ever be able to adequately test it. I leave that to the SF folks.

[bob]

I've always thought that it would be interesting to utilise some of that extra CPU power to different search strategies: for instance a search with fewer reductions running in parallel to a heavily reduced search, or even a multi-PV search (the latter might be interesting for a ponder search if you don't know what the best move to ponder on is: a multi-PV search for the opponent, with some sort of non-PV reduction applied to other moves so you don't waste too much time on them and stay "close" to the "standard" ponder search, where you assume that the opponent played what you think is the best move).

I suspect that these things may start to pay off when the number of cores becomes so high that you can no longer use them as efficiently to speed up an YBW search, but I don't know where the break-even point would be (somewhere beyond 30 cores, I would expect: ~the number of moves you can search in parallel in a single ALL-node in the middle game). Obviously I've never tried it.

One note. NOTHING says you have to use ALL cores at a single split point. I don't. In fact, I have a limit that is used for that very reason. I can only say I would not change given 64 cores, because I have run on a 64 core Itanium box in the past and the parallel speedup still works pretty well at least to that point.