Baker's Game History

My master's thesis in 1981 was a Baker's Game solver.  Baker's Game was the precursor to the FreeCell game that is so ubiquitous on today's PC's.  Baker's Game was invented by the mathematician C. L. Baker.  I first heard about Baker's game in a 1968 article in Scientific American by Martin Gardner.

The rules for Baker's Game are the same as the rules for FreeCell, except that in FreeCell you build columns of cards down by alternating colors, and in Baker's Game you build columns of cards down by suit.  For example, in FreeCell you may place the eight of diamonds on either the nine of clubs or on the nine of spades.  In Baker's game you may only place the eight of diamonds on the nine of diamonds.

Baker's Game is a much more difficult game for human players than is FreeCell.  I have seen estimates on the Internet that perhaps only about 10% of initial Baker's Game positions can be won.  However, the correct figure is about 75%.  By contrast, nearly 100% of initial FreeCell positions can be won.

Good FreeCell players can readily win well over 90% of their games, coming close to the theoretical maximum of close to 100%.  It is much more difficult for good Baker's Game players to reach the theoretical maximum of about 75%.

At the time I wrote my original Baker's Game solver, I was only able to use 128KB of memory.  As a consequence, I used a depth first search of the search space to minimize memory usage.  It was very difficult to get the program to run fast enough to produce useful results in such a memory constrained environment.  In addition, machines were not very fast in 1981.

The main thrust of my thesis was a series of little lemmas by which various positions that were not exactly equal were proven to be equivalent.  The positions in question were potentially far apart in the search space.  The program was speeded up by eliminating all but one of each collection of equivalent positions.  Without eliminating such equivalent positions, the program probably would never have solved even one game.

I was only able to use my original Baker's game solver to attempt to solve three hundred games because the program ran so long and because it ran on a mainframe with limited time available.  The solver was able to win about 75% of the games.  The solver was able to demonstrate that about 15% of the games were unwinnable.  The remaining 10% of the games could not be decided because of time and space limitations in the technology of 1981.  There were strong indications that the last 10% of the games were positions that were unwinnable, suggesting that the 75% figure was about right as the correct figure for the percentage of games that could be won overall.  However, a sample size of 300 has a confidence interval of about 4.9%.  So I was left with being able to say that the percentage of games that could be won was high, probably somewhere in range of 75% plus or minus 4.9%.