Jerry Bryan's Web Pages
Baker's Game, Nuances in Recent Programming
-
Every newly created position is converted to a canonical form. To
create the canonical form, the
Free Cells are sorted ascending according to the representation of the
cards that are contained within the Free Cells.
The board columns (also called stack columns) are sorted according to
the representation of the
base card of each column. The use of canonical forms makes it
much easier to reduce the size of the search space by eliminating
equivalent positions. That is, many
equivalent positions are reduced to the same canonical form. However,
the use of canonical forms make it difficult to document an exact sequence
of moves that will solve a particular game. Indeed, my program does
not even try to document the solution it found. The program just counts
wins and losses.
-
Every newly created position is simplified immediately by moving
all possible cards to the home cells (also called payoff cells). When
the cards are moved to the home cells in this manner,
the collection of such moves is treated as all one move. The
version of FreeCell that is distributed with Windows does the same thing.
However, there are two differences. One difference is that the process of playing
off exposed cards to the home cells is easier with Baker's Game than it is
with FreeCell. The other difference is that my program does it right,
and the FreeCell that comes with Windows fails to make some obvious payoff
moves that it really ought to make.
-
An STL set container is maintained in a particular order, and the position
that is processed by my program
first for each move is the first position in the
container. My program provides a compare routine to the STL so that
the positions that are closest to being won will in general be stored closest to
the beginning of the container (hopefully!). The
compare routine gives preference to positions that have more cards
in the home cells and to positions that have fewer cards in the Free Cells.
-
The program is surprisingly fast. It can solve about eight games
per second, rather than taking hours per game as sometimes happened
back in 1981.
-
None of my Baker's Game programs have ever had any graphics capability at
all, nor do they have any capability of inputting a particular game to
solve. Rather, the programs just generate a bunch of random games
and solve them.
This page last edited on 18 Apr 2009.