Experimental Analysis of
Black Hole and All-In-A-Row Solitaire

Jan Wolter
December 7, 2014

[General Introduction]

1. The Games

Black Hole and All-In-A-Row are two closely related solitaire games very similar to Golf. Like Golf, the goal is to build an up-and-down sequence on the foundation. Unlike Golf, there is no stock, so all cards must go into a single sequence.

Black Hole was invented by David Parlett. To play Black Hole, find the Ace of Spades and use that to start the foundation. Create the tableau by dealing the remaining 51 cards into 17 stacks of three cards each.

The only cards that can be played are the top cards of the 17 tableau stacks. The only place they can be played to is the single foundation pile. A tableau card can be played to the foundation if it is one higher or one lower than the top card of the foundation. Suits do not matter. You may play Aces on Kings, or Kings on Aces. (The game would be impossible if these were forbidden as they are in Golf). The goal is to move all cards to the foundation.

All-In-A-Row is the same, except the foundation starts empty, so you can start it with any playable card, and the tableau begins with 13 stacks of four cards each.

You can play Black Hole or All-In-A-Row at politaire.com, or on many other sites.

Politaire's original implementation of Blackhole had a subtle bug. Instead of always starting with an Ace of Spades on the foundation, it would simply take the first Ace it found in the shuffled deck. Since suit doesn't matter in this game, this seemed harmless, and it would have been if I had pulled the Ace out before shuffling. But doing it after shuffling meant that the chances of an Ace appearing in the first part of the deck were lowered below what you'd find in a randomly shuffled deck. This didn't have much effect on the win rate if you dealt the tableau column-by-column but if you dealt it row-by-row then the win rate was about 1% lower than it should be.

2. Previous Solvers

Shlomi Fish has previously built a solver for these two games and has made source code for his solver available on line. Mr. Fish ran his solver on the first million PySol seeds, and reported that 86.9% of Black Hole games were winnable, and 67.1% of All-In-A-Row games were winnable after running the solver on a million games.

There has also been a paper by Ian Gent and others which proves a generalized version fo Black Hole to be NP-complete and describes the construction of several different solvers, with the intent of comparing different techniques for building AI solvers. They report an 87.5% win rate for Black Hole, apparantly after running only 2,500 games.

The fact that some previous work has been done on these games makes my construction of another solver somewhat redundant, however, the basic solver was just a simple variation of my previously written solver for Golf, and nobody had really done any analysis of the results of their solvers, beyond reporting expected win rates, which aren't even in very good agreement.

3. Analysis

These games are, in a way, much simpler than typical Solitaire games like Klondike or FreeCell, because they don't involve re-arranging the cards. The only move is to remove cards to the foundation. This makes them much easier to describe mathematically.

You can characterize All-In-A-Row as:

Find a permutation of the 52 cards such that:
  1. Every pair of consecutive cards in the permutation have adjacent ranks.
  2. For every pair of cards the tableau where card A is above card B, card A preceeds card B in the permutation.
Black Hole is the same, except the permuation must begin with the Ace of Spades.

I suspect it would be possible to do quite a bit of mathematical analysis of these games. They certainly work quite naturally as a constraint satisfaction problems (which Gent's group has done).

3.1. Adjacent Permutations

The first of the two conditions listed above is interesting on it's own. How many permutations exist that satisfy the adjacency property? The obvious one is the one with no direction changes, which goes from Ace to King four times, as in the diagram below:

But more complicated permutations exist that also satisfy the adjacency property:

Note that the end card doesn't need to be adjacent to the start card.

Since I'm a better programmer than a mathematician, I wrote a program to enumerate the permutations that have the adjacency property. If we have 13 ranks and 4 suits, there are 212,047,876 possible permutations. This is actually a rather small number.

If we could figure out how many of the 212 million permutations satisfy the ordering constraints imposed by the stacking of the cards on the tableau, then we could compute the actual probability of winning. But this is a bit harder than it first appears because ordering constraints include suit. If the seven of hearts is on top of the three of diamonds, then it is the seven of hearts that must preceed the three of diamonds in the sequence. If we count sequences as different if the suits are different, then there are many more sequences -- 876,488,338,465,357,824 times as many, in fact, and that's a big number.

3.1.1. Direction Changes

In David Parlett's description of Black Hole, he suggests that it is generally advisable to avoid too many direction changes. A direction change is when you switch from incrementing to decrementing, as when you have a subsequence like "767" or "454". In my diagrams above, the first included no direction changes, while the last included five.

I'm not actually sure this is good advice, because the vast majority of adjacent permutations have a lot of direction changes. Here's the numbers of distinct sequences that exist with each number of direction changes. It looks like a typical bell curve, except even numbers are slightly more common than odd numbers.

Numbers of Adjacent Permutations with N Direction Changes
The maximum number of direction changes is 38, as in this sequence:

It would seem that players limiting themselves to sequences with only a few direction changes are missing out on a lot of options - nearly all of them, in fact. But direction changes do introduce complexity to play. If you perform a 232 direction change, then you've removed more 2's than 3's and you are going to have to do something to even out the counts, like starting or ending the sequence with a 3 or performing a 323 or 434 direction change. Perhaps keeping the number of direction changes you need to keep track of low is a good strategy for mortal players.

There are, after all, only 34 ordering constraints in Black Hole (two from each of the 17 card piles) so very likely there are lots of sequences matching any given set of ordering constraints, so limiting yourself to simpler sequences may not be that bad a strategy.

3.1.2. Final Card

What's the last card in the sequence? It can be anything, but not all end cards are equally common. Assuming the start card is an Ace, here are the frequences for the different end cards:
Number of
A 6,374,376 3.01%
2 23,914,844 11.28%
3 9,559,134 4.51%
4 21,789,078 10.27%
5 12,734,820 6.01%
6 18,954,720 8.94%
7 15,884,154 7.49%
8 15,884,154 7.49%
9 18,954,720 8.94%
10 12,734,820 6.01%
J 21,789,078 10.27%
Q 9,559,134 4.51%
K 23,914,844 11.28%
Note that 22.56% of sequences are actually circular, ending on a card adjacent to the starting card.

3.2. Invertability

An interesting property of these games is that they are easily invertable. Suppose you rearrange a game of All-In-A-Row by reversing the order of all thirteen tableau piles, so the a pile like "8 A J 3" becomes "3 J A 8". It's obvious that this new deal is solvable if and only if the original game was solvable, because the permutation used to solve the new game can simply be reversed to solve the original game.

You can invert Black Hole games too, except you need to allow the player of the inverted game to start with any card and require them to finish with an Two or a King (so the Ace of Spades can be played).

4. My Solver

My initial solvers for these games were minor variations of my Golf solver. The only significant change is that the heuristic function was changed to prefer avoiding direction changes. If multiple cards of the same rank were available, then it would prefer the one on the taller piles. Though I have my doubts about the usefulness of minimizing direction changes, that heuristic function did seem to give a slight performance improvement.

The first version of these solvers wasn't particularly great. The All-In-A-Row solver could resolve all but a few games, but the Black Hole solver failed on about 0.2% of games - that is, it was unable to either win the game or prove it unwinnable before it ran out of memory.

I found that I could resolve 90% of the unresolved games by simply running the solver on the inverted problem. Inverted problems aren't particularly easy, but many games that are hard to solve forward are easier to solve backwards. Of course, doing this gives no data on the maximum number of cards that could be removed from the original game, so it wasn't a technique I used much.

In the second version of the solvers, I added checks so that (1) the solver never considers removing the last card from a pile if there is a card of the same rank on top of a pile containing more than one card, and (2) if there are multiple one-card piles with the same top card rank, only one of them is considered. This pruned away a lot of redundant branches of the search tree, made the solvers noticably faster, and reduced the number of unresolved Black Hole games to around 0.005%.

My solver can also optionally detect cases where the ranks become disconnected. This is an idea borrowed from Shlomi Fish's solver. If you ever have a situation where there are no Threes or Sevens, but there are still Fives and Tens, then the game is clearly unsolvable, because there is no way to for the sequence to pick up both the Fives and Tens without passing through Three or Seven. Any move that creates such a situation can be rejected. This makes the solver significantly faster and reduces the number of unresolved games to around 0.002% This check, however, was not used in most of my test runs, because I wanted to know the maximum number of cards that could be removed in each deal, and this kind of pruning often ends the search before the best incomplete solution is found.

Source code is available for the Black Hole and All-In-A-Row solvers.

The existence of Shlomi Fish's open source solver was also convenient because it allowed me to check the correctness of my solver. I built an interface to feed deals generated from my seeds my to his solver, and was able to confirm that it was finding the same deals to be winnable or unwinnable.

5. Random Deals

I ran the solvers on the first million Politaire games, seeds zero through 999999. The results are below:

Game Winnable Percent
Average Cards
Black Hole 869,979 87.0% 46.27
All-In-A-Row 671,057 67.1% 47.68

Actually, there were 53 Black Hole games among the million where my Black Hole solver was unable to decide if they were visible or not. However, I ran the solver on the inverted versions of those 53 games, and it was able to prove 4 winnable and the other 49 unwinnable, resulting in the final count shown above. All All-In-A-Row games were resolved on the first pass.

These results are in very good agreement with Shlomi Fish's results, and not far from the Gent group's results, which were (probably) based on a smaller data set.

5.1. Removable Cards in Black Hole

The distribution of the maximum number of tableau cards that were removable in Black Hole is shown on the graph below. There are only 51 cards on the tableau, and the column for 51 cards removed has been omitted because with 869,979 games it is too tall for our graph.
Numbers of Removable Cards in 1,000,000 Random Black Hole Games
This graph has several interesting features. First, it is bimodal. Clearly there are two situations in which games prove unwinnable. In some games, you can't really get started. Maybe you can remove a few cards, but you quickly hit a tangle that cannot be resolved. In other games the problem is removing the last few cards. Maybe you have a Four left, but have used up all your Threes and Fives. Note also that none of the intervening values are zeros. Though it is most common, by far, to be stuck at the beginning or end, you can get stuck in the middle.

Second, there seem to be oddly few games where only 1 card can be removed. In 2.8% of games no cards can be removed. In 1.5% of games only two cards can be removed. But there are only 0.90% of games where only 1 card can be removed. In fact, there seems to be some waviness on the left end of distribution: odd numbered bars are shorter, and even numbered bars are taller than you'd expect if the curve were smooth. The amplitude of this wave seems to fade as the number of removed cards increases.

I don't really have a fully developed theory on why this occurs. But if only one card can be removed, it must be a Two or a King, so there are 8 possible cards that can be played. In either case, there are then only 7 possibilities for the second card to remove, because one Ace is already on the foundation. I think the fact that the number of options shrinks as sequences double back on themselves may account for this even-odd wave phenomenon.

The case where no cards are removable is exactly the case where among the 17 top cards there are no Kings or Twos. It's easy to calculate that we'd expect that to happen 28,513 times in a million deals. In our experiment we saw 28,325 such cases.

5.2. Removable Cards in All-In-A-Row

Here is the distribution for All-In-A-Row. In this case, no cards start on the foundation, so a win is 52 cards off, but we omit that column because, with 671,057 games, it is too tall.
Numbers of Removable Cards in 1,000,000 Random All-In-A-Row Games
This shows the same bimodality as Black Hole, and the same even-odd waviness is visible on the left side of the graph. The waviness is actually easier to see here, because the graph is otherwise flatter.

The biggest difference, aside from the larger number of winnable games, is is that the left hump is so much smaller. There are, of course, no games where zero cards are removable, because any card can be moved to the initially empty foundation. Only four games were found where none of the possible first cards opened an opportunity for a second card (seeds 50038, 318639, 368686 and 667866), and no games were found at all where only two cards could be removed (though it is certainly possible to contrive such a deal). Clearly having a choice of starting points makes the beginning of the game much easier, so that making things come out right in the end with no left over cards becomes the dominant obstacle to winning.

6. Natural Shuffling of Gathered Cards

If we were playing this game with cards instead of a computer, then after each game we would gather up the cards, shuffle them a few times, cut the deck and deal them out for another game. If we shuffle a lot, then we'd expect pretty much the same outcomes as with a fully randomized deck, but if we shuffle only a few times, we might not.

I simulated that using the GSR model of card shuffling (see Introduction). I always gathered any remaining cards on the tableau one column at a time, but I did separate tests where the tableau cards were dealt either column-by-column or row-by-row, since this seemed likely to make a big difference when the deck was not fully randomized.

6.1. Black Hole

In these tests, I varied the number of shuffles, n, from one to seven. For each number of shuffles, the program played 100,000 Black Hole games, starting each game with the cards from the previous game, gathered and shuffled with n riffle shuffles, followed by one cut. The win rates with different numbers of shuffles are shown on the graph below.

Note that my solver did not manage to resolve all games. For a few deals it ran out of memory before finding an optimal solution, so it just gathered the cards from the best solution it found. However this happened in less than 0.01% of deals in all cases except the case where we were doing one shuffle and dealing by columns, in which case 0.05% of deals were unresolved. Overall, this is not enough to make any significant difference to our results.

Note also that I've clipped off the bottom of the graph.

Black Hole Win Rate with n Shuffles of a Gathered Deck
Dealing by Columns or Rows

Red line is win rate with fully randomized deck
The most surprising feature of this graph is that the green, deal-by-rows line dips for the two shuffle case. Why does shuffling twice give a much lower win rate than shuffling one or three times? I'll discuss the reason for this in the next section.

The other interesting feature is that the blue, deal-by-columns line converges to 87% much more quickly than the green, deal-by-rows line. When dealing by columsn, four shuffles seems to be sufficient to give the same 87% win rate as in a fully randomized deal, and three shuffles comes very close. You need six or more shuffles to achieve the same effect if you deal by rows.

If we deal by columns, then the main situation in which I'd expect residual order to help is in increasing that chance that when you play a card, the uncovered card will be adjacent to the card you played. Even inserting just one card between two formerly consecutive cards is enough to prevent this from happening, and riffle shuffles are quite good at inserting cards between cards.

If you deal by rows then even if some cards are inserted between two cards, they are still both likely to be among the top cards of the 17 piles. It takes a lot more shuffling to allow formerly adjacent cards to get far enough apart so that they don't both end up in the same row.

6.1. All-In-A-Row

Here's the same graph for All-In-A-Row. 100,000 games were played with each number of shuffles.
All-In-A-Row Win Rate with n Shuffles of a Gathered Deck
Dealing by Columns or Rows

Red line is win rate with fully randomized deck
Here we see even more clearly that even low numbers of shuffles suffice if you are dealing by columns, but if you deal by rows you need to do several more shuffles to erase the advantage resulting from lingering order in the deck.

These graphs aren't really a good representation of what would happen if you played these games with real cards and shuffled minimally, because if you were playing with real cards you wouldn't have an "undo" button and would be unlikely to achieve the win rates my program did, which means that each game would inject less order into the deck. Still, players of All-In-A-Row, at least, would typically be able to get a lot of cards sorted in many deals, and so may well see elevated win rates if they are doing only two to four shuffles and if they are dealing by rows.

7. Natural Shuffling of Ordered Deck

To get a clearer picture of what is going on in the previous tests, I ran a series of tests where, instead of starting with the cards gathered from the previous game, we always start with a sorted deck, so before shuffling the cards are always in four Ace-through-King sequences. We give this deck n riffle shuffles, cut once, and deal.

I was particularly interested in the graph for Black Hole. In this set of experiments each datapoint is based on 100,000 games.

Black Hole Win Rate with n Shuffles of a Sorted Deck
Dealing by Columns or Rows

Red line is win rate with fully randomized deck
In this graph the weird shape of the deal-by-rows graph is even clearer. If you start with a sorted deck and shuffle only once, your win rate is much higher than normal. But if you shuffle twice it is much lower. Three shuffles and it's higher again.

Here's why: To play the first card of a Black Hole game, you need a King or a Two. In a sorted deck, there is a Two near the beginning, and a King at the end. There is also a King and a Two at about a quarter of the way through the deck, halfway through the deck, and three quarters of the way through the deck.

Mathematically, two standard riffle shuffles are equivalent to one "four-shuffle." To do a four-shuffle, you need four hands. Instead of splitting the deck into two chunks, you split it into four, and, holding one quarter-deck in each of your four hands, you riffle them all together simultaneously.

So when we split our sorted deck into four chunks, there is a high probability that all the Twos and Kings will be near the tops of or bottoms of their chunks, because they all started near the most likely chunk boundaries. Riffle those four decks together, and you have all the Twos and Kings near the top and bottom of the resulting deck. Cut the deck and then they are all in a cluster in the middle. If we deal by columns, part of that cluster is likely to be exposed, but if we deal by rows, there is a good chance that the whole cluster will be buried in the second row, leaving no Kings or Twos accessible to start the game with. We don't see this happening in All-In-A-Row, because we have a choice of starting cards, so the Kings and Twos have no special importance. A third shuffle tends to move the Kings and Twos back out to the ends of the deck, and by the fourth shuffle they will be dispersed enough not to be as big a problem.

Many solitaire games basically sort the deck. Probably shuffling twice (or three times for a 2-deck game) is best avoided in many games.

Of course, when we were playing with cards gathered from the previous game, the cards could be in any of the many possible adjacent sequences, but my solver prefers to minimize direction changes and so probably produces mostly sorted decks fairly often. Thus we saw a less spectacular version of the same dip in that graph.

8. Related Games

Thomas Warfield invented another Blackhole variant that he calls "Binary Star." In this game, two decks of cards are used and there are two foundation piles, one starting with the Ace of Spades, the other with the King of Hearts. The tableau contains 17 piles of six cards each.

I modified my Black Hole solver to play Binary Star, but, as expected, the result wasn't too great. Since the game uses two decks, the search tree is potentially twice as deep as the search tree for Black Hole, so it is much more difficult to prove a game unwinnable.

Luckily, the game is actually pretty easy. Most games are winnable and the search heuristics do a reasonably good job of finding a solution when there is one. Among the first 10,000 Politaire seeds, my solver was able to win 89.5% of games, while proving 8.0% unwinnable. The remaining 2.5% were unresolved. Turning on pruning raised the win rate to 90.0%, but didn't increase the number of game proven unwinnable. So somewhere between 90% and 92% of Binary Star games are winnable. On average it was able to remove 96.1 of the 104 cards, including the two cards that started on the tableau.