<\/p>\n
Clock Solitaire<\/a> (also known as Clockwork Patience) has got to be the stupidest card game ever invented.<\/p>\n Actually, come to think of it, Beggar My Neighbour<\/a> is worse. <\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n As an undergraduate, pondering various data structures, I started thinking about this game, and how it would be optimally implemented.<\/p>\n 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.<\/p>\n 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.<\/p>\n But here is the interesting step… stick with me and we will come back to it later.<\/p>\n We don’t actually need to deal out the cards to the various piles beforehand!<\/strong><\/p>\n 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.<\/p>\n 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.<\/p>\n The whole game boils down to that last card, so that’s the only one you really need to deal out. <\/p>\n The optimal implementation is a random number generator that returns True one time in thirteen!<\/p>\n 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.<\/p>\n To my surprise, they disagreed with my insight. They argued that the “interesting step” wasn’t valid.<\/p>\n There was a Gedankenexperiment<\/a> that highlighted our differences in opinion.<\/p>\n 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.<\/p>\n I argued that, you should have no objection. From an expected value<\/em> 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.<\/p>\n 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.<\/p>\n 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.]<\/p>\n 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.<\/p>\n It went further, however. Not only did they believe that my analysis<\/em> was wrong, but they believed my conclusion<\/em> was wrong. They believed that, in their experience, it came out more often than once in every thirteen games.<\/p>\n There was only one resolution possible – the Monte Carlo method<\/a> – like backtracking (which I have dismissed before<\/a>), the Monte Carlo method skips the niceties of logical analysis to use sheer brute force to solve a problem. <\/p>\n 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.<\/p>\n The result? Everyone lost. <\/p>\n The opponents lost because the experiment proved that Clock Solitaire came out, on average, one time in thirteen.<\/p>\n 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.<\/p>\n","protected":false},"excerpt":{"rendered":" An analysis of Clock Solitaire – beyond merely “stupid”<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"","footnotes":""},"categories":[23,35,33,34],"tags":[55,69,54],"class_list":["post-25","post","type-post","status-publish","format-standard","hentry","category-based-on-a-true-story","category-heroic-failures","category-puzzle-solving","category-software-development","tag-puzzle","tag-software","tag-solution"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/25","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=25"}],"version-history":[{"count":0,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/25\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=25"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=25"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=25"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}The Rules<\/h3>\n
The Optimal Implementation<\/h3>\n
The Controversy<\/h3>\n
The Experiment<\/h3>\n
The Result<\/h3>\n