So, for the past couple of days, I’ve been working on fixing the WLD database lookup code in Milhouse, in an attempt to get it to handle endgame positions properly. There is a tiny bit of subtlety which I haven’t seen explained anywhere else, so I think I’ll take a moment here to explain it.

The Chinook database that I am using contains WLD for all positions with six pieces or less. But that’s not actually true: it actually doesn’t include information for any positions which are captures. Why? To shrink the size of the database. Roughly half of the positions (if I recall) are capture positions. Chinook works better if we look those up in the smaller database that results after the jump, rather than here. That’s all very well and good. We could just do a quiescence sort of search: jump out your own captures, and see what the resulting positions are.

But there is a further wrinkle: Chinook deletes not only positions where not only the moving side has no captures, but the other side has none either. Again, this deletes about half the remaining positions from the database, so it’s good, but now you really need to be somewhat clever.

Basically, you end up writing a little minimax search engine, but instead of running the evaluation function at the leaves, you do database lookups. You have to keep recursing down until both the moving side and the non moving side have no captures, then you can do the lookup. If any of your children are a loss for the other side, then you return a win. If all of your children are wins for the other side, then you’ve loss. Otherwise, you are drawn. (Implement that logic carefully, I botched it once, which led to an evening of debugging.) The algorithm always terminates because one or both sides is removing at least once checker for each pair of plies.

And, it appears to be working!

Frankly, using a WLD for only six pieces seems kind of odd. If we stored a “distance-to-conversion” or perfect play database, we’d take up more space, but it woud be trivial to get the program to play out difficult endgames, effectively adding dozens of ply to the search engine with relatively little complication. I think that’s next on my list. I’ve begun trying to decipher Appendix B in Schaeffer’s “Solving Large Retrograde Problems” paper, but the calculation of MaxWP is confusing, to say the least. I’ll have to work through it myself.

Addendum: Actually, it’s interesting to note that three quarters of the entire database are locations which are captures. It seems like that can’t possibly be true in actual play (actual captures are quite rare in end games). Is this an exploitable feature? Martin Fierz hints that it might be in his “Stepping Stone” project suggestion. I’ll have to think about it some more.

Addendum²: Sigh. There is an infinite loop condition which appears not to be caught. Not sure what the deal is with that yet. I’ll have to think about it more. I think it is because you don’t make any headway if the opposing side has a capture, so you play a move which removes the capture, then he plays a move which restores the capture, and so on… Not sure how to catch that. If we play two non-capture moves in a row, does that mean that we are drawn? Perchance.

I was surfing over at Bob Newell’s “Checker Maven” website, and found this awesme collection of PDN files for download. I have a table of challenging positions compiled into milhouse, which I use for debugging and testing, so I decided to hack a simple parser to input some of the positions into Milhouse. The “Gem Problems” file contain 162 positions, some all of which are quite challenging. Consider this one:

Red to move and win.

It takes around a 55 ply search to find the winning line, but a reasonably skilled checker player would be expected to play this line out without mistakes. Milhouse still finds some positions like this challenging, since it typically maxes out around 40 ply or so before grinding to a halt. I suspect this reveals a deep flaw in my move ordering, and I think it might be difficult to fix it. But I’ll think about it some more.