OddThinking

A blog for odd things and odd thoughts.

Beating the Clock Solitaire


The Game of Clock Solitaire

Clock Solitaire (also known as Clockwork Patience) has got to be the stupidest card game ever invented.

Actually, come to think of it, Beggar My Neighbour is worse.

Both of them are completely mechanical games. There is no skill. There is not even any opportunity to make a choice! However, at least, Clock Solitaire is guaranteed to finish in 52 moves or less. Beggar My Neighbour (also known as Strip Jack Naked) can last forever, and wastes the time of two people.

The Rules

Clock Solitaire is set-up by dealing 12 face-down piles of four cards in a circle. The piles are numbered 1 – 12, like a clock face. The remaining four cards are left in a pile in the centre. Play begins by turning over the top card of the centre pile.

The face-up card is moved to the pile corresponding to the face value of the card (A=1, J=11, Q=12, K=centre pile). The card is placed at the bottom of the pile, face-up, and the top-card is turned over, and play continues with that card.

When the fourth King finally turns up, there are no more moves possible, and the game stops. If all the other piles are completed (only face-up cards left) then you win, otherwise you lose.

The Optimal Implementation

As an undergraduate, pondering various data structures, I started thinking about this game, and how it would be optimally implemented.

The obvious implementation would consist of 13 arrays of 4 cards. We can ignore suits – they are irrelevant, so each card is a single integer, ranging from 1 to 13.

However, once the card is actually placed in the appropriate pile, we don’t care about it anymore. We can dispose of any record of it – the pile is empty when there are no cards in it. So we don’t really need arrays – we can use bounded-size queues (max length = 4), which could well be faster because there is no need to rotate all the cards.

But here is the interesting step… stick with me and we will come back to it later.

We don’t actually need to deal out the cards to the various piles beforehand!

We could have a central pile of cards, ready to be dealt out, and as a card is needed, we can ask the central pile of cards to provide the next card. Just think of the time we will save by not actually wasting time moving the cards to the various decks when we start! Now each pile is just a counter telling us how many there are in the pile.

But now that we have made this optimisation – this change in the way we look at the cards – we can see another short-cut. You lose the game if the final king appears anywhere but the last card in the centralised pile. Conversely, you only win if the last card in the centralised pile is a King.

The whole game boils down to that last card, so that’s the only one you really need to deal out.

The optimal implementation is a random number generator that returns True one time in thirteen!

The Controversy

I was very impressed with how a little bit of thought saved a whole lot of implementation effort, and I mentioned it to some fellow students.

To my surprise, they disagreed with my insight. They argued that the “interesting step” wasn’t valid.

There was a Gedankenexperiment that highlighted our differences in opinion.

Imagine you dealt out a deck and you started playing for the final round of the Clock Solitaire championships. Halfway through the exciting game, a judge stops you and asks you to pick up the remaining face-down cards, shuffle them well, and re-deal them to the same locations.

I argued that, you should have no objection. From an expected value perspective, the game is unchanged. Once you accept that, it is a small step to accepting “lazy-evaluation dealing”, where you don’t deal a card until you absolutely need to, and the rest of the analysis holds.

My friends argured that shuffling the cards would change the outcome. It would be a different game and you should object to having to re-shuffle them mid-game.

I tried to explain that the chance of the outcome being made worse and being made better was equal, and there was no issue. For the same reason, if I am playing a multi-player card game, I don’t care who actually deals the cards, and which order the piles are passed out to the players, as long as I trust the people shuffling and dealing the cards not to cheat. [In many games, however, it is important to track who is the nominal dealer (as opposed to the actual dealer), in order to decide who starts playing.]

I failed to be convincing. The room was split, as it so often is, between the people who agreed with me wholeheartedly, and the people who were just plain wrong.

It went further, however. Not only did they believe that my analysis was wrong, but they believed my conclusion was wrong. They believed that, in their experience, it came out more often than once in every thirteen games.

The Experiment

There was only one resolution possible – the Monte Carlo method – like backtracking (which I have dismissed before), the Monte Carlo method skips the niceties of logical analysis to use sheer brute force to solve a problem.

I wrote an implementation to play the obvious way. The code was carefully reviewed by my opponents. It was then set to run 10,000 times, and tally the results.

The Result

The result? Everyone lost.

The opponents lost because the experiment proved that Clock Solitaire came out, on average, one time in thirteen.

I lost because all of my superior optimisations that implemented Clock Solitaire in a single line of code were useless because no-one believed in them. I ended up implementing the whole thing long and slow way. I hadn’t even really proven that my analysis was correct; merely that my conclusion was right and their memory of their experiences were not consistent with what would be expected.


Comments

  1. Your random number generator doesn’t provide the full experience; you don’t know how close you would have gotten to winning before having your hopes dashed. Instead, you need to generate four random numbers, mod 52, 51, 50 and 49. These tell you how far up the deck the last king was.

    You can then include a clock (configurable for your average play speed) which tells you how much time you would have wasted before winning a game. The actual gameplay can be done by computer much faster, saving you time in which you can watch Survivor:Antarctic.

    On a different note, I must agree with your friends on the “shuffling halfway through” issue; there is a small but non-zero probability that the reason you are being offered a shuffle is that the person offering it has detected that you are going to win, but has bet on your opponent. Your analysis, as you note, is correct if you trust everyone involved.

  2. Andrew,

    You haven’t taken into account the chance that the judge has bet on you and has detected that you are going to lose. Given you are likely to lose more often than you win, perhaps this could be considered more likely?

    If we are taking this sort of issue into account, I would object to being asked to shuffle on completely different grounds. I have wasted enough time getting to the finals of this silly competition, and I wouldn’t be impressed by any delaying tactics that prevent me from getting back to viewing Survivor: Antarctic.

  3. WOW! What are you an undergraduate in?

    Obviously have too much time on your hands but i really enjoyed reading it and i like the way you think!
    and from now on i’m not going to be wasting my time dealing out the cards in 13 separate piles of 4 but instead just use the pile of 52 cards i have in my hand!

    or better still, play classic solitaire instead!

  4. Beggar My Neighbour (also known as Strip Jack Naked) can last forever

    Here’s an article that discusses this (and also briefly, the probability of Klondike being solvable.)

  5. [For the record, there was a crude troll comment posted, which I have removed because it lowered the tone too much. However, lest I am accused of suppressing criticism, suffice to say someone calling themselves Chloe doesn't like me much because I was rude about Clockwork patience. - Julian]

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <br> <code> <del datetime=""> <dd> <dl> <dt> <em> <i> <ins datetime="" cite=""> <li> <ol> <p> <q cite=""> <strike> <strong> <sub> <sup> <u> <ul>

Web Mentions

  1. OddThinking » Shuffling and Ownage

  2. OddThinking » Analysis of Captive Queens