JVMerlino wrote: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.