|
FreeCell is a solitaire card game superficially similar to Klondike. However, it is thought of as a game of skill, not luck. Although implementations vary, nearly all hands in common software versions of FreeCell are winnable, though some may be very difficult. This is in contrast to Klondike and other solitaire games where many hands are unwinnable even if the player's moves are flawless. Rules The terms in italics are defined in solitaire terminology. 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. 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 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. 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. * The game gained worldwide popularity thanks to Jim Horne, who learned the game from the PLATO system and implemented a version of the game with color graphics for Windows. It was first included with Microsoft Win32s as a test program, but was made a part of Windows 95 and has been included with every version of Windows since. Today, there are many other FreeCell implementations for every modern system, some of them as part of solitaire suites. However, it is estimated that as of 2003, the Microsoft version remains the most popular, despite the fact that it is very limited in player assistance features, such as retraction of moves. Strategies Difficulty Like Minesweeper, FreeCell is a provably hard (NP-complete) game. This result was proved in 2000 and first published in 2001. The result implies that writing a computer algorithm that finds solutions for arbitrary FreeCell configurations 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. 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. This solver was later enhanced by Wilson Callan and Adrian Ettlinger and was incorporated into their Freecell Pro software. 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 starting of March 2000. This solver was simply dubbed Freecell Solver. This solver is unique because it can use meta-moves, groups of moves that aim to achieve a certain end. Gary Campbell wrote a solver for FreeCell for DOS in x86 assembly. This solver weighs in at 12 kilobytes, and is quite fast. It gives short (generally well under 100 steps), quick solutions to the first million FreeCell games (using the standard game numbering scheme). For more information, or to download this solver, follow one of the preceding links. In addition to giving correct solutions to the first million games, it accepts the entire 8-billion standard game numbers plus 3 "bonus" games numbered -1, -2, and -3. The most comprehensive list of solvers known contains links to other solvers. New solvers are constantly being written as part of assignments or projects for some university courses. The Internet FreeCell Project by Dave Ring, which was finished in October 1995, took on the problem. Ring assigned 100 consecutive games chunks across volunteering human solvers and collected the games that they reported to be unsolvable, and assigned them to other people. This elegant project used the power of multiprocessing, where the processors were human brains, to quickly converge on the answer. Only one game defied every human player's attempt: Windows versions While there are actually 52!(!=factorial), or approximately 8.07×1067, possible games, some games may be similar to others because suits assigned to cards are arbitrary. When a card is black, for example, it may be assigned to clubs or spades. The original Microsoft package includes 32,000, generated by a 15-bit random number seed. These games are known as the "Microsoft 32,000". Later versions of Microsoft FreeCell include more games, of which the original 32,000 are a subset. The original Help file remains through modern Microsoft versions: "It is believed (although not proven) that every game is winnable." This was known at the time to be untrue in its strictest sense. Games numbered -1 and -2 were included as a kind of easter egg to demonstrate that there were some possible card combinations that clearly could not be won. Nevertheless it started a flurry of interest in the question of whether all of the Microsoft 32,000 could be beaten. Smart players could win most games most of the time, but that wasn’t proof either way. In later implementations of FreeCell in Microsoft Windows, there are 1,000,000 games. Of these 1,000,000 games, 8 have been found to be unsolvable. They are games No. 11,982, No. 146,692, No. 186,216, No. 455,889, No. 495,505, No. 512,118, No. 517,776 One way to "win" at any Microsoft FreeCell game was added as a way to help the original software testers; push Ctrl-Shift-F10 at any time during the game. Click Abort to win, Retry to lose, or Ignore to cancel. Double-click any card for the results. This does not actually solve the game, however. | |||||||
|
| ||||||||
 |
|
| |