[creativity]
[identity][home][verbosity]
[transitivity]
creativity

Where the spirit does not
work with the hand,
there is no art.

- Leonardo da Vinci
1 0 1 0 1 0

[pps_solver]

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.

Solution Description

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.

  • Whenever the match progress is zero, any kings at the front of a row can be automatically removed with no loss of solution generality.
  • A rough approximation of the best possible values for the target variables (perfect matches, hearts, and score) can be quickly made at depth to avoid searching a branch which cannot possibly exceed the current best values found so far. This depth was determined empirically to occur ten moves into the search. Earlier in the search the cost of the approximation is not justified because it rarely leads to any pruning.
  • Pruning can also be done based on the number of "stuck pairs" remaining in the hand. These are pairs that require the use of a free cell to clear because they are both on the same side of the ladder in the same row. We can prune based on these pairs as well, but obviously we must wait until we have a reasonable chance of a pair being stuck, which occurs much deeper into the search tree.
  • The order of searching is also important to the search process time. Moves which are likely to yield the highest score are tried first so that later in the search process the likelihood of the sucess of other pruning techniques is increased.
    1. perfect matches are removed
    2. regular matches are removed
    3. pairs with both cards in free cells are removed
    4. kings are removed
    5. cards are moved to free cells

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.

. perfectpair.java

Optimization

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.

  • Multithreading - the major reason the algorithm performs so poorly is that it is doing depth-first search. This ends up forcing it to exhaust every possible move after the first guess at the first move before moving on to the second guess at the first move. If the best first move is to move a card to a free cell, this will be the last initial move tried. The algorithm will spend a lot of time searching branches which cannot lead to the best solution.

    Instead of a single thread checking all first moves, the C# code starts a new thread for each possible first move, giving each thread its own copy of the game board to work with. This is essentially an inital breadth-first search combined with depth-first searching. Searching can be pruned based on the best solution found by any of these threads, which eliminates fruitless branches much more efficiently.

    Implementation of multithreading is not quite trivial. The threads share a set of common data, including the best solution found so far. Simultaneous access to this data must be strictly controlled to prevent two threads from updating the best solution at the same time. This is done in C# using the lock(Object) method, which is pretty kludgy compared to Java and its synchronized method label. Threads may compare a solution against the current best without obtaining the lock on the data, but when updating the best solution they must wait while other threads are performing updates. I can't tell if the lock(Object) method is multiprocessor-safe, but it does a fine job of protecting multi-thread safety on a single processor.

  • Conditional Move Order - the Java algorithm blindly tries perfect pairs then regular pairs no matter what the current state of the pair counter. This can be improved slightly by trying regular pairs first when there are pairs on the pair counter and perfect pairs first when the pair counter is zero.

  • Prevent Equivalent Move Sequences - the Java algorithm tries each perfect pair and regular pair in order. It does a little bit to prevent trying equivalent move sequences multiple times by only matching the first card of a pair with a card in a row with a higher index number. However, it can do more to prevent other equivalent move sequences by also checking the last move that was made.

    Consider the situation where there is a perfect pair in both rows one and two. The java algorithm will first try clearing the perfect pair in row one, then on the next call it will try to clear pair two. After searching the entire subtree of moves beginning with the clearing of perfect pair one, it will then move on to try clearing pair two first. The very next recursive call will begin by clearing pair one!

    From an optimization perspective, the order of clearing these perfect pairs is irrelevant. Thus, we can eliminate this entire redundant search tree by simply checking that the last move made was not a perfect pair. If it was a perfect pair, the algorithm starts looking for the next perfect pair at the row number of the last pair instead of the first row.

    The same optimization can be done for regular pairs as well. If the previous move was a regular pair, we can eliminate certain pairs that we know have already been tried. the next pair chosen must satisfy one of the following two conditions:

    1. At least one of the cards in the pair is in the same row as one of the cards from the last move. This means that one of the cards was covered, and hence could not have been removed before the last pair removed.
    2. The row number of the current first card in the current match is greater than the row number of the first card in the previous match. This prevents a scenario similar to the example given for perfect match clearing.

  • Cutoff Timer - because the moves most likely to lead to the best score are tried first, after a certain point the algorithm starts checking branches that use more free cells early in the game. These very rarely lead to an improvement in score. Based on empirical evidence on an 850 MHz Mobile Pentium CPU, if sixty seconds have passed since the previous best solution was found then the final best score improves by no more than 10 points after exhausting the search tree. Often the improvement is much smaller or no better solutions are found at all!

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.

[ Previous]
[ Next]


[creativity]
[identity] [home] [verbosity]
[transitivity]

[comments/blog]

[ ]

[401valid]