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.
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.
You can characterize All-In-A-Row as:
Find a permutation of the 52 cards such that:Black Hole is the same, except the permuation must begin with the Ace of Spades.
- Every pair of consecutive cards in the permutation have adjacent ranks.
- For every pair of cards the tableau where card A is above card B, card A preceeds card B in the permutation.
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).
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.
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.
The maximum number of direction changes is 38, as in this sequence:Numbers of Adjacent Permutations with N Direction Changes
A2A232323434545456567676787898989T9TJTJTJQJQKQKQKAKA
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.
| End Card |
Number of Permutations |
Percentage |
|---|---|---|
| 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% |
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).
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.
Game Winnable Percent
WinnableAverage Cards
RemovedBlack 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.
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.Numbers of Removable Cards in 1,000,000 Random Black Hole Games
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.
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.Numbers of Removable Cards in 1,000,000 Random All-In-A-Row Games
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.
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.
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.
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.
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.
I was particularly interested in the graph for Black Hole. In this set of experiments each datapoint is based on 100,000 games.
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.
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.