| Bakers Game | ||
| ... OR ... | ||
Bakers Game, and it's variant Bakers Game Easy, is a perfect information solitaire card game; the placement of all 52 cards is known at the start of the game. However, the virtue of perfect information does not mean every board is solvable, nor does it specify the ease of producing such a solution. However, Bakers Game does lend itself to easy analysis.
Play begins with all 52 cards placed on the tableau into 8 columns. The first four columns will have 7 cards and the remaining four will have 6. At the top of the "board" are four reserve spaces and four foundation piles. To win, the cards must be moved from the tableau to the foundations starting from ACE and ending with KING.
Each foundation pile is reserved for one suit (clubs, diamonds, hearts, spades). Moving an ACE to a foundation pile will start that suit's pile; the next card added to the pile must be the TWO of that suit, then the THREE, and so on.
Any card may be played from the tableau to any open reserve space. A reserve space may hold only one card. Cards may be moved from a reserve space to a foundation pile, provided they are, in fact, the next card to be added to that pile.
Single cards at the bottom of the columns may be moved to a foundation pile, to an open reserve space, or to an open tableau space. They may also be moved onto the lowest card of another column if that card is the next higher value card of the same suit; in other words, the SEVEN OF HEARTS card can be placed atop the EIGHT OR HEARTS card - but not onto a NINE OF HEARTS or EIGHT OF CLUBS.
In the Easy variant an entire column of cards of descending value of the same suit may be moved together - in other words, a stack of SEVEN OF HEARTS, SIX OF HEARTS, FIVE OF HEARTS could be moved together and placed on the EIGHT OF HEARTS, assuming the EIGHT OF HEARTS was at the bottom of its column. In the standard variant, though, cards can only be moved one at a time - there must be sufficient open reserve space or empty tableau columns to support moving a "stack", as such.
When all of the cards have been moved to their foundation piles then the game has been "won".
Notice: The solver is still in-progress - watch GitHub for updates!
A depth-first search through the game spaces provides the best overall memory footprint. This consumes a "mostly constant" number of potential moves for each move considered, versus a breadth-first search which would exponentially explode on moves that, if a winning move was found, would not be considered anyway.
Exiting at the first solution does not guarantee the shortest solution; in fact is quite possible to "beat" the computer's solution. This is not really a problem in game play - humans like feeling superior to the computer!
An optimization opportunity exists by keeping track of those game states that have already been seen. Executing multiple moves in a different order can result in an identical board state - so such tracking will reduce both the memory footprint and the number of states to process.
The analysis has not yet been completed.