Lincke’s Thesis: Exploring the Computational Limits of Large Exhaustive Search Problems

Thomas Lincke invented a technique called “drop-out-expansion” for the automatic construction of opening books. That seemed like a pretty nifty thing: it’s used by Martin Fierze’s Cake program to compute a vast database of opening positions in checkers. I wanted to know what it was about, and my Google Fu revealed this thesis:

Exploring the Computational Limits of Large Exhaustive Search Problems


Technorati Tags:

Another paper on endgame databases in Checkers…

Dodgen and Trice talk about their 7 piece perfect play endgame database, which can be used to guarantee wins or stall defeats as long as possible when confronted by positions having 7 or fewer pieces. Most endgame databases contain only the game theoretic value for positions, and therefore might have difficulty actually finding the winning combinations even though they “know” that the position is a win. I was beginning to think about this, so it was interesting to find this paper.

WCC_Database.pdf (application/pdf Object)

I’ve got about half of my bitboard based move generator for checkers working. Once I get it finished, it should only take me an evening or so to get a basic checkers implementation working. The code was about half-machine generated, which made getting it correct much simpler than had I tried to do so by hand.

Technorati Tags: ,