FreeCell

From Wikipedia, the free encyclopedia

FreeCell is a solitaire card game played with a 52-card standard deck. Although implementations vary, most versions label the hands with a number (derived from the random number seed used to generate the hand). FreeCell is fundamentally different from most solitaire games in that most deals can be solved (for example, see the Windows version).

Contents 1 Rules 2 History 3 Strategies 4 Difficulty 5 Solvers 6 References

[edit] Rules

Construction and layout:

• One standard 52-card deck is used.
• There are four open cells and four open foundations. Some alternate rules use between one to ten cells.
• Cards are dealt evenly into eight cascades. Some alternate rules will use between four to ten cascades.

Building during play:

• The top card of each cascade begins a tableau.
• Tableaus must be built down by alternating colors.
• Foundations are built up by suit.

Moves:

• Any cell card or top card of any cascade may be moved to build on a tableau, or moved to an empty cell, an empty cascade, or its foundation.
• Complete or partial tableaus may be moved to build on existing tableaus, or moved to empty cascades, by recursively placing and removing cards through intermediate locations. While computer implementations often show this motion, players using physical decks typically move the tableau at once.

Victory:

• The game is won after all cards are moved to their foundation piles.

For games with the standard layout (four open cells and eight cascades) most games are easily solved. The Windows version article contains a section that discusses unsolved games.

[edit] History

One of the oldest ancestors of FreeCell is Eight Off. In the June 1968 edition of Scientific American, Martin Gardner described in his "Mathematical Games" column a game by C. L. Baker that is similar to FreeCell, except that cards on the tableau are built by suit rather than by alternate colors. This variant is now called Baker's Game. FreeCell's origins may date back even further to 1945 and a Scandinavian game called Napoleon in St. Helena (not the game Napoleon at St. Helena, also known as Forty Thieves).^[1]

Paul Alfille changed Baker's Game by making cards build according to alternate colors, thus creating FreeCell. He implemented the first computerised version of it in the TUTOR programming language for the PLATO educational computer system in 1978. Paul managed to display easily recognisable graphical images of playing cards on the 512×512 monochrome display on the PLATO systems.^[2]

This original FreeCell environment allowed games with 4–10 columns and 1–10 cells in addition to the standard 8×4 game. For each variant, the program stored a ranked list of the players with the longest winning streaks. There was also a tournament system that allowed people to compete to win difficult hand-picked deals. Paul Alfille describes this early FreeCell environment in more detail in an interview from 2000.^[3]

[edit] Strategies

• The basic strategy is to use the four free cells as temporary locations for cards: Cards should never (or seldom) be moved to a free cell without having a plan to move them away again.

• A sequence of several cards with alternating colors can be moved at once by moving cards to vacant free cells and/or temporarily placing them in empty columns. If the move involves temporarily placing a card in an empty column it is called a supermove in FreeCell terminology.

• Empty free cells and/or empty columns can also be used to sort cards in a column into the correct order. For example if one has the cards 10♦, 7♣, 6♦, 8♦, and 9♣ in a column and four empty free cells, one can move 7♣, 6♦, 8♦, and 9♣ to the free cells, and then back onto the 10♦ in the correct order.

• A card can be safely moved to the foundations, without a chance of being needed later in the game, if either of the following conditions apply: (a) the values of the foundations of the different color are at least this card's face value minus 1; (b) the values of the foundations of the different color are at least this card's face value minus 2, and the value of the other foundation of the same color is at least this card's face value minus 3. For example, if the spade foundation pile currently goes up to 5♠, and the 6♠ card is available, it is safe to move this 6♠ to the spade pile as long as the other foundation piles either include 5♥ 5♦, or include 4♥ 4♦ 3♣.

• Once a card has been moved to a foundation, it cannot be moved back into the playing area, so don't be too anxious to move too many cards of just one particular suit to a foundation (this is called "stacking up"). For example, if you start stacking up clubs (a black suit) in a foundation, you are going to end up with more red-suit cards than black-suit ones in the playing area, and this is going to cause you problems. However, it is generally safe stack up two different-colour suits in tandem. For example, if you have low-value diamonds and clubs that can be moved to the foundations, you may safely stack up these two suits immediately. Stacking up two suits of opposite colours will still leave an equal number of red-suit and black-suit cards in the playing area, so you won't be stuck with too many suits of a single colour.

• Also, do not put all royals in the cells. For example, if you have in one column a black king, red queen, red jack, the other red jack, and a red king followed by an ace, wait before you go ahead and get the ace.

• Do not go straight for the aces if they are all up top. Clear out some columns before you may go for the aces. You might get stuck with the cells full and no available moves, therefore ending the game.

[edit] Difficulty

The FreeCell game, by allowing a finite number of possible games, can be trivially solved in exponential time. Like Minesweeper, a generalized version of the FreeCell game with 4×n cards is provably hard (NP-complete). This result was proven in 2000 and first published in 2001.^[4] The result implies that writing a computer algorithm that finds solutions for arbitrary FreeCell configurations of the generalized version quickly would be a major scientific breakthrough. A perfect FreeCell playing program running in polynomial time would earn the discoverer a $1,000,000 prize for solving one of the Clay Mathematics Institute's Millennium Prize Problems. However, most researchers believe that no such efficient solution procedure exists.

[edit] Solvers

One of the passions of several FreeCell enthusiasts was to construct computer programs that could automatically solve FreeCell. Don Woods wrote a solver for FreeCell and several similar games as early as 1997.

Another known solver is Patsolve of Tom Holroyd. Patsolve uses atomic moves, and since version 3.0 incorporated a weighting function based on the results of a genetic algorithm that made it much faster.

Shlomi Fish started his own solver beginning in March 2000. This solver was simply dubbed "Freecell Solver".

Gary Campbell wrote a solver for FreeCell for DOS in 8086 Assembly. This solver weighs in at 12 kilobytes, and is quite fast.

[edit] References

1. ^ FreeCell FAQ
2. ^ Kaye, Ellen. "One Down, 31,999 to Go: Surrendering to a Solitary Obsession", New York Times, 2002-10-17. 
3. ^ Interview with Paul Alfille
4. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.