Ahino

by Hew Wolff

Ahino is a solitaire card game I invented sometime in the 1980s. I think it's pronounced ah-HEE-no. It's a cross between the common games called Klondike (see here or here), and Tower of Hanoi (see here or here). The rules are very simple, but it does not seem to be trivial.

Rules.

Deal the whole deck face up into five piles, called the main piles. Each pile has a top card. Spread each pile downward so that you can see all the cards. (Note that, confusingly, this puts the top card at the bottom of your view.)

There are also four foundation piles, one for each suit as usual, and the goal is to move all the cards into these piles. There are two ways to move the cards:

In a foundation move, you can move a top card onto a foundation pile to build up that suit in order.

In a main move, you can move a top card onto another top card whose value is larger, or onto an empty main pile. The order is ace, two, three, and so on up to king. This means that a king can be moved only onto an empty main pile (or a foundation pile).

756Q
KQJJK
K10910
96Q
8KQ
7J
10
9
8

That's all there is to it. For example, take this position from the end of a game, where the foundation piles are on top, and the main piles are spread out underneath. The top cards are 7, 8, 9, J, and Q. We can't move any of these to a foundation pile. But if we move 7 onto Q (say), then 8 is now on top, and we can move it onto its foundation pile, and then 9 right on top of it. The 10 is harder to get to, being buried under two queens. You could start by clearing away the third pile to move K there.

Exercise. Win this game. I suggest using a real deck of cards.

I find that I win about 25% of the time. When I lose, to feel better I can still score myself by the number of cards in the foundation piles (only around 6 on average). Here's a question: how bad can a position get? It's pretty easy to see that you can always make a main move as long as there are any cards left in the main piles, so you can't get completely stuck. But you can still get stuck for all practical purposes:

Exercise. Find an initial position from which you can never make any foundation moves.

On the other hand, there are a lot of really good positions:

Exercise. Show that if each main pile is in decreasing order (from largest on the bottom to smallest on the top), then you can win the game using only foundation moves.

There are a couple of useful ideas lurking here. First, instead of thinking just about the top card of a main pile, you can look at a top pile, that is, a sequence of cards sitting on top of the pile. Second, a top pile is especially interesting when it is "decreasing" in the sense above. Each main pile has a largest decreasing top pile. I'll call the cards in this top pile the loose cards.

Any top card is obviously loose, but sometimes there are a lot more loose cards underneath as well. For example, in the first main pile shown above, the loose cards are K, 9, 8, and 7. The loose cards are generally easy to work with. Basically, your goal is to manage the loosening of all the cards. When you uncover a card, you often loosen it; and a loose card stays loose until you move it to a foundation pile. The exercise above says that once all your cards are loose, you've won.

Here's another example. Look back at the sample position above: suppose you wanted to clear the top pile 987 off of K. One way to do this is to move this top pile onto J. This is pretty easy to do using only Q as a waystation, because the the cards in the top pile are loose and fairly small -- try it. In fact, you can often use this idea to move a top pile of loose cards as if it was a single card:

Fact. Suppose you have a main pile A with a top pile X of loose cards. And suppose that (1) the cards in X are smaller than the card just under X; (2) the cards in X are also smaller than the top cards of two other main piles, B and C. Then you can move X from the top of A to the top of B using only main moves between these three piles.

Proof. This is basically just the original Tower of Hanoi problem. You can prove it using mathematical induction: assume that it's true for any top pile X with n cards, and use this assumption to prove it when X has n + 1 cards.

It may seem like cheating, but once you're convinced of it, you can use this trick to make the game go quite a bit faster.

Actually, a little more is true in the Fact above. For example, even if X is the same as A (that is, there are no cards under X), the result is still true, because any card can be moved onto an empty pile. To include such cases, I'll adjust the rules slightly. We will consider that each pile has a special infinite card on the bottom, which is larger than all the normal cards, and never gets moved. This is a trick which makes it easier to talk about the game, as long as you keep the special "cards" in the back of your mind. I will use it from now on. I will still call a pile "empty", though, if it has only the infinite card.

8897
9KJ8Q
10Q9KJ
10JKQ10
K109
Q
J

When playing a game, it's good to know when you have to give up. For example, take this position. If you play with it a bit, you see that it has too many loose queens. (No social comment should be inferred here.) You can move the queens around, but because you can't put a queen onto another queen, you can't get past them to the cards you really need.

Or can you? Here's a handy test.

Fact. Suppose that all the cards with value V are loose. Then, if you make only main moves, you cannot move any card with value greater than V.

Proof. Suppose you've made a sequence of main moves, and now you have a pile with a top card X which is larger than V. All the V cards must still be loose, which means that each of the 4 other piles contains one V card. But then each of those other piles has a top card which is smaller than X, which means you can't move X with a main move.

Using this Fact with the position above, it's easy to see that all of the cards you need for foundation moves are trapped under cards larger than queens (namely kings), and so you can't get to any of them. So you really are stuck.

Here's something I wondered about for a while: is it possible to make a mistake that loses the game? That is, can you have a winnable position, but make a bad move and end up in a non-winnable position? It's often clear that making a single main move cannot be reversed -- the discussion of "loosening" above makes it clear that it's a one-way process in which cards never become unloosened -- but it's not so easy to prove that this can lose the game.

KKKK
QQQQ
JJJJ
10101010
9999
8888
7777
6666
5555
4444
AAAA
3333
222
2

Fact. There are winnable positions in which a single main move makes the position non-winnable.

Proof. In the position shown, you can win by moving the 3 to the empty pile, then making foundation moves with all the diamond cards in order, then handling the remaining piles similarly. But if you move the 2 onto the 3, you're stuck.

Finally, just for fun:

Exercise. Figure out why the game is called Ahino.