Perfect Pair Solitaire is a Club Pogo Exclusive belonging to the family of card games that requires removing pairs of cards that add up to thirteen. Aces are one, jacks are eleven, queens are twelve, and kings are removed on their own. PPS is a simple candidate for analysis because it is a game of perfect information - every single card in the hand is exposed before even one move must be made.
Game Rule Set Description
Even when Pogo programmers coopt an existing solitaire game, they usually add special bonus minigames or side goals that involve earning tokens or increasing certain stats that are tracked for each player. Clever devils, those Pogo marketers, appealing to our competitive nature the way they do.
Because of these additional rules, Pogo's versions of these games are more interesting from a problem solving perspective because they become optimization problems instead of simple depth-first searches. If all that was necessary in Perfect Pair was to remove all of the cards, it's mind-numbingly simple to write an algorithm that finds a solution for every puzzle (those that are solvable, anyway). Instead, there are three separate variables to be optimized for any given puzzle.
One of these variables is the number of perfect matches earned during the game, where a perfect match is a pair removed from the same deck on each side of the ladder shaft. Pogo tracks the largest number of perfect pairs that each player has made in a single game, so one of the goals is to beat the previous record if it is possible to do so. The number of possible perfect pairs for a given hand can be easily defined recursively for each deck prior to the solution process, though this number might not actually be attainable depending on the order in which cards must be removed. If a new record can't possibly be attained for the hand, this attribute is ignored in optimization and very quickly becomes obsolete. It is extremely rare to find a hand with more than twelve possible perfect pairs, and even such a hand does not guarantee all twelve to be obtainable.
Another variable is the total number of hearts earned for the hand. One heart is earned for a perfect match or for completing four regular matches in a row without removing a king (heartbreaker) card. When the game debuted, Pogo actually recorded additional hearts beyond the ten available on the "lovemeter". However, it is now only possible to earn ten hearts per hand for statistical purposes. Hence, optimization on this variable need only bring the total number of hearts to ten, though it is theoretically possible to earn twenty-four in an optimal hand.
The final critical variable, which is somewhat dependent on the other two, is the hand score. This score is translated directly into tokens which are essentially meaningless except for the sake of stat-whoring. Two points are earned for a single pair, four additional points for a subsequent pair, six points for the next pair, and finally eight points for the fourth pair needed to earn a heart. Ten points are earned for a perfect match, which resets the count of regular pairs. No points are earned for removing a king, which also resets the count of regular pairs. An additional ten points are earned for every heart obtained after reaching ten. Obviously, to maximize the score it is best to time perfect pair and king removal such that the pair counter is already zero. It is also beneficial to maximize the number of hearts even though more than ten are not recorded because of the way these additional hearts increase the total score.
It is of course still necessary to win the game by removing all of the cards. This is made easier by the existence of free cells which may be used up to six times in a given game. Most rule sets allow only one free cell, but one makes two available. Each of the six is worth five additional points if it is unused, so the ideal game would not make use of any free cells.
Both the branching factor and the depth of solving are fairly small. A maximum of thirty-six moves may be made in the worst case, and for each turn roughly three moves are possible on average. Brute force solving with no pruning finds a first solution very quickly, usually in less than a second, but to completely exhaust the search tree can take hours or days. Many pruning techniques were employed to eliminate branches from the search and accelerate the solution process tremendously.
This Java implementation performs inadequately on a 1 GHz Mobile Pentium CPU, if one is actually trying to use it to play the game in real time. I can usually find a solution manually that is better than the one the computer has already found about half of the time, especially when there are two free cells available.
I recently ported this code into C# as a comparative exercise. Unsurprisingly, the code performed almost identically in both languages. However, in the intervening period between writing the original Java code and porting it to C#, I thought of a few more optimization techniques to improve the performance.
I'm hesitant to post this optimized code. It is conceivable that someone might try to use it to play the game instead of just using the grape like the rest of us do. Using this program probably violates the Pogo ToS, and I don't want to be responsible for someone losing his account for being an idiot. It takes longer to type in the cards on the board than it takes to play through a whole game, anyway, let alone waiting for the solver to finish. However, if you're interested in seeing the C# or the optimizations, drop me a line and I'll consider it.