Experimental Analysis of
Trigon Solitaire

Jan Wolter
April 10, 2013

[General Introduction]

The Game

Trigon Solitaire is an easy to play variation of Klondike, where you build in the same suit and can make unlimited passes through the stock, dealing one card at a time. You can read the rules or play the game on politaire.com or many other places.

The fact that you are allowed unlimited passes through the stock, one card at a time, effectively means that all stock/waste cards are always playable. You might as well just fan them out in front of you and grab any one you want instead of fooling with all the endless card dealing.

If it is possible to play a card on to another in the tableau, then there is never any reason not to do so. You aren't forgoing the opportunity of playing another card there, because with one deck and building in suit, there is only one card that can be played there. You aren't preventing the card you play on from being moved to another tableau pile, because stacks of cards can be moved. You aren't blocking any card from being moved to the foundation, because the foundation is also built in suit. So for the most part there are no choices to make. You just make every possible move and hope to win.

The exception to this is when you play a card into an empty space on the tableau. Only kings may be moved into spaces, but there are four kings and if you have only one empty space then you may need to make a choice about which king to play. A wrong choice could lose you the game.

Thus, this is, over all, an almost completely mindless game, but one that is relatively easy to study.

Solver

I started by programming a depth-first-search solver for Trigon in C. This is not particularly a difficult task, the search tree is typically small and branch points only occur when there is an empty space into which more than one king could be played. 79% of winnable games and 49% of unwinnable games were solved without ever needing to backtrack. (For winnable games we stop when we find a solution, for unwinnable games we must explore the entire tree.) The solver never needed to backtrack more than 6 times to complete the analysis of any game. Obviously no heuristic search is needed, and blind exploration of the entire search tree suffices to solve all games quickly.

Random Deals

I ran the solver on the first million Politaire games, seeds zero through 999999. All cards were removed for 160,076 games, so 16% of games were solvable. Since the game is so easy, human players can expect about the same success rate.

An average of 16.2 cards could be removed to the foundation in each hand. In 12,296 games (1.2%), no cards could be removed. The histogram below shows the full distribution of the numbers of cards which could be removed.

Numbers of Removable Cards in One Million Random Trigon Games

Natural Shuffling of Gathered Cards

If the game is played with real cards instead of on a computer, then it is unlikely that the cards will be completely randomized between games. So we consider the case where the following procedure is followed after each game:
  1. The various remaining piles of cards from the previous game are gathered up one at a time.

    The foundation piles and waste are stacked and flipped face down (reversing their order). The stock is added to the stack (it's already face down so it is not reversed). The faceup cards on the tableau are gathered, one pile at a time, and flipped face down, reversing them. Finally the face-down cards on the tableau are gathered, one pile at a time, and added to the stack.

  2. The deck is riffle-shuffled n times.
  3. The deck is cut once.
  4. The new tableau is dealt out, column by column.
Clearly if the number of shuffles, n is large then the result should be identical to playing with fully randomized decks. But if the player is less thorough about shuffling, then some amount of ordering will survive from the previous game, and this can be expected to impact the play of the new game.

For each number of shuffles from one to ten I ran the solver on one million games. The first game used a fully randomized deck, and after that the procedure above was followed to produce the deck for the next game.

The resulting win rates are shown in the graph below:

Trigon Win Rate with n Riffle Shuffles of Cards Gathered from Previous Game
Red line is win rate with fully randomized deck

It appears that Trigon players who shuffle three or more times between games will see win rates similar to those using fully randomized decks. Those who shuffle only once or twice will see substantially higher win rates.

Note that win rate with four shuffles is actually slightly lower than with a fully randomized deck. The effect is negligible here, but we'll see it more clearly in the next section.

I also ran the same test using overhand shuffles instead of riffle shuffles. In an overhand shuffle, packets of cards are taken off the top of the deck and stacked up in reverse order to form a "shuffled" deck. It's a widely used shuffling technique, but not a good one. Our computer-simulated overhand shuffle forms a break between packets with a probability of 1/4, meaning a 52-card deck is typically split into around twelve or thirteen packets. This is typical of people who do overhand shuffles reasonably well, but many people do much worse. Note also that in these tests we did not cut the deck after shuffling, as we did with the riffle shuffles above.

So here's our win rate with overhand shuffling, note that we've stretched the vertical scale of this graph by a factor of two in comparison to the graph above.

Trigon Win Rate with n Overhand Shuffles of Cards Gathered from Previous Game
Red line is win rate with fully randomized deck

The sinusoidal nature of this curve is typical of overhand shuffles. Even-numbered shuffles have a certain tendency to undo what little was accomplished on the odd-numbered shuffles.

Convergence to randomness is much slower than with the riffle shuffle. The only good thing you can say for it is that one overhand shuffle seems to be better than one riffle shuffle.

Natural Shuffling of Ordered Decks

In the previous experiment two effects were interacting. First there was the question of how the win rate is impacted by order in the deck, and, second, there was the question of how much the deck is ordered by playing the game.

When we win the game, we completely sort the deck in increasing order, but most Trigon games are not winnable. Incomplete games leave some low cards on the foundation sorted in increasing order, and some higher cards on the tableau sorted in decreasing order. (See the introduction for the definitions of "order" I am using here.) So often we will not really be imparting much consistent order to the sequence of cards.

To be able to more clearly see the impact of sortedness on the win rate of Trigon, I ran tests using a different shuffling strategy. In this case, we always start with an ordered deck (each suit in increasing order), or a reversed deck (each suit in decreasing order). We then shuffle this sorted deck n times, and cut once.

Trigon Win Rate with n Shuffles of a Ordered/Reversed Deck
Red line is win rate with fully randomized deck

So if we start with a deck sorted in increasing order (blue line) and shuffle only once, we win 80% of the time. This drops rapidly with each additional shuffle until we reach 16% after seven shuffles.

If we start with a deck sorted in decreasing order (green line) and shuffle only once, our win rate is even higher, 95%, but it drops fast with additional shuffles, and with three shuffles it is 11%, substantially lower than the win rate with a fully randomized deck. It then climbs slowly with additional shuffling until it reaches 16% after seven shuffles.

We can get some indication of the reason for this if we consider a single unsolvable tableau pile. Suppose the top card of the pile is the 7♠. The pile is unsolvable if both of the following conditions are true:

  1. The 8♠ is in the pile, and
  2. At least one lower spade, A♠ through 6♠, is in the pile.
To solve the pile we need first move the 7♠. The only places it can move to are (1) another tableau pile, in which case we need the 8♠, or (2) to the foundation, in which case we need all the lower spades to build the foundation pile for spades high enough. If the conditions above both hold, then neither of these is possible and the pile cannot be solved.

There is a fundamental asymmetry to these conditions, and I think that is probably the origin of the strange behavior we see in our graph.

Suppose we start with a reversed deck that has only been shuffled a once, so it still contains many descending sequences, and deal a tableau pile. Dealing reverses the sequences so there is a high probability that the 7♠ will be on top of the 8♠, and condition one almost certainly occurs. Condition two, on the other hand is very rare. For a deck that started sorted in increasing order the opposite is true. The pile is only unsolvable if both conditions are true though, so the win rate is very high in either case.

The games are likely to play very differently in the two cases though. With the ordered deck, we will be moving a lot of cards directly to the foundation, building our sequences there. With the reversed deck will will be building our sequences mostly on the tableau before moving them to the foundation.

As we shuffle the originally reversed deck more, the probability of condition one increases, while the probability of condition two drops much more more slowly, because there are so many more ways that it can happen. Thus the probability of both conditions being true drops very fast, and the likelihood of condition two remains high long after the likelihood of condition one has dropped to a nearly normal level, so our win rate is lower than normal.

With the originally ordered deck, we have the opposite effect. Condition one becomes less likely much faster than condition two becomes more likely, so our likelihood of both being true remains elevated through several shuffles.

Of course, not every unsolvable game has a single unsolvable stack. The knot of insolvability frequently involves multiple stacks in more complex ways, but the fact remains that it is easier to build down on the tableau than up on the foundations, because there are fewer prerequisite cards needed.