## Deconstructing Pair Solitaire

Pair Solitaire is a delightfully simple game which was released a couple of weeks ago on iOS (and eventually Android). Designed by Vitaliy Zlotskiy and featuring audio by Shannon Mason the game has a “instant classic” feel to it. I could just imagine my grandmother teaching it to be at her kitchen table with a physical deck of cards.

After a few dozen games on a recent flight I decided I was going to:

- Do an analysis of the game, and
- Teach my grandmother how to play with a physical deck of cards (likely at her kitchen table)

### How to play

When you start a game you are presented with a stack of playing cards.

The goal is to clear as many cards as possible. You can clear a card it it is exactly one card away from another card that matches it in rank or suit. so in the example screenshot you could clear the 7♣ because it is one away from another club (the 9♣). When you clear a card it goes away and the stack compresses. The game ends when you can’t clear any more cards. You get a score that is based on which cards you cleared, with higher ranks being worth more points, and a multiplier which is based on how many total cards you cleared.

### Beatability

Without knowing the developers or decompiling the source code I can’t tell for sure but it looks like each game is a randomly dealt stack of cards. My first questions were about beatability.

- Can any stack be beaten?
- Can every stack be beaten?

Answering the first question the first one was pretty obvious. I played a bunch of games and eventually got it down to two cards. There was one additional multiplier thingie so I would assume that if your final two cards matched you would get a perfect score.

The next question is a little trickier to answer. I have played plenty of games I failed to win. But in theory I might have been able to beat it had I played differently. To answer this I tried to find an initial shuffle that would have no possible matches.

1 |
A♠ K♠ 3♥ 2♥ A♣ Q♠ J♠ 5♥ 4♥ 10♠ 9♠ 7♥ 6♥ 8♠ 7♠ 9♥ 8♥ 6♠ 5♠ J♥ 10♥ 4♠ 3♠ K♥ Q♥ 2♠ A♥ A♦ K♦ 3♣ 2♣ Q♦ J♦ 5♣ 4♣ 10♦ 9♦ 7♣ 6♣ 8♦ 7♦ 9♣ 8♣ 6♦ 5♦ J♣ 10♣ 4♦ 3♦ K♣ Q♣ 2♦ |

If I was dealt this stack, I would 100% not be able to beat it.

It is possible that the game is not using a pure shuffle. They could be filtering out un-beatable shuffles or constructing the stack not via a shuffle algorithm.

### Solver

The next step, naturally, was to write an auto solver. My goal here was to see if I could write a program that could generate or input a sequence and output a series of moves which, if possible, beats the game.

I wrote a recursive solver in a couple of languages. Here is the relevant parts of the C# version:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
static public string checkStack(int[] stack, string trace) { Console.WriteLine(trace); if(stack.Length < 3) { return "end"; } else { for(int i = 0; i < stack.Length-3; i++) { if(tryMatch(stack[i], stack[i+2])) { int[] f = stack.Take(i).ToArray(); int[] b = stack.Skip(i + 1).Take(stack.Length - (i + 1)).ToArray(); int[] t = new int[f.Length + b.Length]; f.CopyTo(t, 0); b.CopyTo(t, f.Length); string temp = checkStack( t , trace+"-"+i); if(temp != "") { return i + "," + temp; } } } } return ""; } |

I represent the deck as an array of integers. The checkStack() function accepts an array of integers (which encode the rank and suit) and, if appropriate, it ‘makes a match’ (ie. remove the card from the array) and calls itself with the smaller array. It exits if there are no matches to be made.

If there are no matches to be made because it got to the end of the stack. It returns the string “end” which triggers the upstream functions to collate the sequence of moves that cleared the stack. If it exits because there are no moves left without winning, it returns an empty string which pops up the chain and continues the recursive search.

This is a pretty brute force approach. Assuming I implemented it correctly, it will find a winning solution if one exists. The problem is that so far I haven’t managed to run it long enough for it to finish.

### Stack Generator

As I wrote earlier, I don’t know how the stacks are being created. I decided to work up a few ways that the stacks could be generated.

**Pure shuffle**

This method is pretty simple. It works just like a physical deck of cards. You start out with an array of all 52 cards shuffle the cards. In my solver I used Fischer Yates shuffle to generate the stack. This approach has the advantage of being simple to implement and pretty cheap computationally.

The downside of this approach is that, as we established above it will sometimes produce un-beatable card arrangements. As a designer this wouldn’t bother me but I could imagine wanting to guarantee a beatable stack so that if a skilled player would always have an opportunity to win. If I wanted to make sure the stack was always beatable I would likely try one of the following approaches.

**Filtered shuffle**

This approach is the obvious but dumb approach.

- Do a pure shuffle
- Run a solver to see if it is beatable
- If it is not beatable, go to 1
- Otherwise you have a beatable stack

This approach has a few problems. First off we don’t have a solver that doesn’t take days to finish so each game would take a long time to start.

Setting aside that problem, even if we had some magical function that told us if the stack was beatable, this approach is *technically* still not guaranteed to finish. I don’t know how many of the possible arrangements of the deck are beatable but the random shuffle could keep randomly spitting out bad ones indefinitely. Practically speaking, this means that this algorithm could take milliseconds or it could take minutes. Since locking up the CPU on a mobile device for that long would likely crash it, and would also get it rejected form the app stores, this approach is not advisable.

**Perfect Sequence**

This approach is aims to generate a sequence with at least one way to beat it. That way we know that every stack is technically beatable.

You start with all of the 2’s in the deck (you could start with any rank)

1 |
2♥ 2♠ 2♣ 2♦ |

At this point the stack is completely solvable. For the next step you randomly pick another card from the set of remaining cards (lets say 9♣) and starting from the front you find the first spot that it would fit and still leave a beatable stack. In this example it would be between the 2♥ and the 2♠.

1 |
2♥ 9♣ 2♠ 2♣ 2♦ |

At this step the stack is still beatable. ( 9♣ -> then the 2’s)

If our next random card was a K♦ it would land between the 2♠ and 2♣

1 |
2♥ 9♣ 2♠ K♦ 2♣ 2♦ |

At this step the stack is beatable. (K♦ -> 9♣ -> then the 2’s)

This would continue until the entire deck is built. At every step of the process the stack is beatable. We can see that it produces stacks that have multiple solutions. If we look at the stack:

1 |
2♥ 9♣ 2♠ K♦ 2♣ 2♦ |

You could play: 2♥ > K♦ > 9♣ ... or K♦ > 9♣ > 2♥... and both would work. We can see that it also sets up failure states. You could select the 2♣ first and not be able to remove the 9♣. When designing these sort of systems it is important to check to see if you are making your puzzles trivially easy.

We can also see that from a performance perspective, this “Perfect Sequence” method is totally reasonable. It runs in linear time and since we could implement it without crazy stuff like recursion, it should have a tiny memory footprint.

**Why do this sort of analysis?**

As a working designer/developer with a company to run, why do this sort of analysis on someone else’s game?

One of the nice things about getting some years of experience under your belt is that you start to assemble a tool chest of design patterns. When you encounter a situation like ABC, one way to solve it is XYZ. This tool chest can make the design/development process easier and faster which is great. The risk is that you can slip into using those tools in situations when they might be sub optimal. This can send your design work into a rut where your design starts to feel same-y.

Doing this sort of analysis, besides being a fun brain teaser, helps to add new tools to the tool chest. It also gives me an opportunities to try my existing design patterns in novel situations. I see it as a way to “cross pollinate” my design practice without stating new side projects. I may never *need* to write a stack generator for Pair Solitaire but the approach of working backward through the game to make sure every step works could be useful in all sorts of other puzzle games. I may not have much use of an automatic solver but it is useful to think about the next time I need to write a hint system or AI.

**Grandma Analysis**

I ended up showing my Grandma the game on my iPad while I was home for the holidays. She got it right away, and the first game we played together broke my previous high score. 🙂

Brute force can never solve this problem(unless using some monster technique, e.g. quantum computer). One possible way is to calculate some local best solution to reduce the stack, e.g. think 15 steps ahead using Monte Carlo method.(if you try to derive a full tree of strategies, the depth will be limited to 5 – 7).

I used some of what you mentioned to try to beat the game – final 2 cards were both 2s, but that did not achieve the expected result of the perfect game.