So, the project was to complete a Checkers AI player in the language of your choice that can compete with the other players in the class in a time-controlled environment. Supplied to us was some template code in Java and a simple 4-piece endgame database and code to query it.
The endgame database was a big surprise to me, but then again I'd never seen Checkers AI players. Such databases don't really exist for other games due to a variety of reasons. The simple underlying principle is to calculate exactly who should win, given perfect play, for all possible configurations of k pieces, where k ranges from 2 up. The main advantages of an endgame database is the ability to stop searching whenever a position is found in the database. This means it is possible for a standard search algorithm to have exact (as opposed to heuristic) data on positions in the search tree, which greatly enhances play in the late game.
Unfortunately, the use of an endgame database in this way assumes that, once the player actually enters the endgame, he can acheive what the endgame says. For a lost position, this is easy :) for a draw it is also easy, but to win from an endgame-reported win is not easy. With a standard endgame database, this is generally a very time-consuming task, since all the database tells you is win, lose, or draw, and thus a nearly full search is required to find the correct move(s).
So, I decided to build my own, and instead of simply recording win, lose, or draw, I would record some additional information with each position to speed up the search process dramatically. Additionally, I wanted absolute perfect play, not merely a guarantee that a player in a won position could actually win - I wanted him to win in the minimal number of moves. This wasn't truly necessary, but I decided that if I was going to go through the effort of building my own DB, it would be worth something.
So, having set forth for myself a massive task, I set to doing it. I needed to compute, for every possible position with k or fewer pieces, win, loss, or draw, and, in addition, the number of moves to a win. I won't really go into this; it was a lot of work, and I ended up computing the 5-piece database 3 times, since I discovered subtle bugs in the first 2. The result is a distributed program in Java totaling more than 7,000 lines of code. The raw data from the computation for the 5-piece database is 300MB, and the in-memory compressed version is 75MB. Here is a link to a the output of test program using the database to compute perfect play from a well-known position in Checkers called First Position (a 4 piece position).
To use the DB once in the endgame, you at the very least need to make progress towards a win, otherwise you could just oscillate between "won" states. The only real way to do this is based on some monotonically decreasing metric. The simplest metric is number of pieces, which will never increase. Unfortunately, from first position, there is a sequence of 65 moves during which no piece is taken! This is unfathomably deeper than could possibly be searched, ever. Even with the best metric, involving pawn rank as well, there is a sequence of 20 moves during which the metric does not change. Therefore, it is impossible to move correctly for the win using a standard endgame database, and would give a losing player, armed with my enhanced database, a very good chance of drawing the game (only very good because there are interesting strategies for the winner to use even without a perfect play variation).
Anyway, it was fun but hard to build, interesting, and I may do some more work related to the variant of endgame databases I constructed.