Experimental Analysis of
Indefatigable Solitaire and
Royal Family Solitaire

The Game

Royal Family Solitaire is the identical game, except we build downward on the foundation, starting from the four kings initially dealt there, and we only have one redeal instead of two. The fact that we build down instead of up on the foundation obviously makes no difference to the likelihood of winning. From an analytical point of view, Royal Family is just Indefatigable with one redeal instead of two.

You can read the rules for Indefatigable or Royal Family, or play Indefatigable or Royal Family on politaire.com.

These are both quite easy games. I have played hundreds of randomly generated games of Indefatigable without having found a single one that I couldn't win. It nearly always seems to be possible to win, although it typically does need some thought and planning to solve any particular game. Many games can be won without a redeal.

But it is obviously possible for an unwinnable deal to occur. It is easy to construct such a game. For example, consider the game of Indefatigable below (here the cards at the bottoms of the columns are the playable cards on the tops of the stacks):

As you can see, no moves can be played here, because none of the "top" cards (which are on the bottoms of the columns) can be played on any other, and no twos are available, so nothing can be moved to the foundation. So the only option is to redeal, which gets us this:

There are again no moves, so we need to redeal again:

And there are no moves here either so the deal is thoroughly unsolvable.

Solver

The initial version of the solver did not do redeals. The second version did limited redeals, allowing a redeal only after the best solution to the previous tableau had been found. The third version allowed redeals at any time.

Without Redeals

The distribution of the number of cards moved to the foundation is shown in the tablea below:

Note that I do not include the four aces dealt to the foundation in the counts of removable cards. So it appears that when the game is unsolvable, it is almost always because few or no cards can be removed. In my experience, you can nearly always win any game where a column can be emptied. Game 68696, however, seems to be a counter example to this. Though a column can be opened, my solver could remove no more than 14 cards (not counting the aces) without a redeal, and I could do no better.

With Redeals

In my next test I modified the solver to be able to do redeals in a limited way. It would find the maximum number of cards it could remove from the initial tableau, then it would pick randomly one of the "dead end" states where that number of cards had been removed, and redeal from that state. It would then start anew solving the redealt tableau. It would never backtrack to undo the redeal, and try redealing from a different end state.

Running this on the first 100,000 Politaire seeds, this solver was able to win 99250 Royal Family games, and 99,957 Indefatigable games. That is to say that it won all but 750 Royal Family games and all but 43 Indefatigable games, for win rates of 99.25% and 99.96% respectively.

This does not mean that those 43 Indefatigable games are actually insolvable however. The best time to redeal is not necessarily when the most cards are off. So the actual percentages of winnable games are presumably higher still.

So I wrote a third version of the solver, which allows redeals to be performed at any time, even when there are legal moves that can still be made. This adds some complexity to the solver, because not only does it have to be able to do and undo redeals in the course of its search, but it loses the advantage of "safe moves". Normally some moves, like moves of cards to the foundation, are safe moves. You can just perform them without considering alternatives. But if we are allowing redeals at any point in the game, then redealing is always an alternative, and no move is completely safe. Also, because this is a depth-first solver, it tends to find "deep" solutions, not the shortest solution, so it tends to use all available redeals in every game it plays, whether they are needed or not.

I ran the full solver on the first million Politaire seeds. For the Royal Family game, it was able to win 998,011 games out of a million, failing on 1,989 games, a 99.8% win rate.

For Indefatigable, it was able to win 999,977 games out of the first million, failing on only 23 games, for a 99.998% win rate. The complete list of unsolvable seeds is below:

As usual, the unsolvable games turn out to be ones where very few, if any, cards can be removed. One of them, game #602357, is similar to the hand-constructed example at the begining of this report - not only can no cards be removed, but none can even be moved.