ArticlesI learnt a new Cheapass card game recently. It was an interesting and thought-provoking game, but I am not going to talk about the game-play today. I am going to talk about the initial set-up, and an unsolved puzzle it brings up.
Introduction to the Game Set-Up
Reverse-engineering the requirements, the game developers needed everyone to start with three equivalently-valued chips or tokens that are exchanged with other players thoughout the game. They also needed exactly one of the players to be secretly nominated with a special role (they arbitrarily call it the “Thief”). If the Thief spends their last chip, the game is over.
The simplest solution to nominating the thief is to deal out a short deck of cards equal to the number of players (I think it works with four to nine players) and the person who receives the Joker takes on the Thief role.
The game developers at Cheapass have optimised this slightly.
Firstly, they use the Ace of Spades instead of the Joker – presumably because some decks don’t have Jokers.
Secondly, they eschew chips, and instead deal three cards per player. The person with the Ace of Spades takes on the Thief role, and then the cards are used as chips. The thief should only spend the Ace of Spades as the last card (and hence end the game). If the card was given to another player in the middle of the game, the thief’s identity would be revealed, so it shouldn’t be done..
The Problem
The downside to this system is that the thief can accidentally reveal themselves by being cautious about which cards that they exchange. Similarly, non-thieves can give away their status by being cavalier about which cards they use.
Conventions Can Help
There are a couple of partial solutions that can be adopted by the players.
The first is to enforce a strict rule that, once play starts, cards must remain face down. This system is subject to both accidental and malicious reveals.
A similar method is a convention of how to place the thief card (always the leftmost card in your hand, or always the bottom of the pile on the table) and which card to spend (always the rightmost card in your hand or always the top card on the pile). In practice, the non-thieves forget to follow this convention strictly, even though it reduces the chances of both them and the thief that they will win.
The Puzzle: An Algorithmic Solution?
Here’s the puzzle:
Either come up with an function, f, that satisfies the following requirements, or prove that such an function is impossible:
- Each player is assigned publicly known unique number,
n, in the range1..N, whereNis the total number of players. - Each player is randomly dealt three random cards,
c1, c2, c3from a short-deck of3Ncards. - Each player is given the same publicly known function,
f({C1,C2,C3},n)– that is, the function takes a set of three cards and the player’s number. It returns a boolean. - No matter how the cards are dealt, when they are substituted into the function, it shall only return
Truefor one player, andFalsefor the others. - Each player is equally likely to be dealt the combination that returns
True. - It shall not be possible to determine the result of
f, without knowing all three card values. That is, knowing any two of the three cards belonging to a player shall not allow another player to determine the result off.
I’m pretty sure that the algorithm is impossible, but I haven’t finished proving it yet.
Comment by Alan Green on June 23, 2006
I can think of a simple f() that meets all of your requirements and works for n=2. Unfortunately, I suspect there is an unstated requirement to do with a guessing player already knowing the value of their own cards, plus any other cards that may have been revealed. Duh.
(And I think there is a fundamental problem with adding algorithmic thief assignment to existing rules. As the game progresses, each non-thief player will learn more and more about how the cards fell in the initial deal. Players will be encouraged to play in such a way as gain more information and/or block others from gaining the information, ultimately changing the flavour of the game.)
n=3 is interesting.
Comment by Julian on June 25, 2006
Alan,
You are right about the unstated rule. I originally began to state it, but then realised how horribly complex – or actually impossible – it made the algorithm so I dropped it.
Let’s take your case where n=2. You can deduce which three cards the other player has purely by looking at your own, so it doesn’t matter what f() is.
Even for larger values of n, it becomes far more complex when you can see two random cards of every player.
Nonetheless, the puzzle is tricky enough enough already without these Cluedo variants, so let’s ignore them.
Comment by Alan Green on June 27, 2006
Thinking about n=3 for a bit, the value of f() can’t depend on the order that cards are dealt to a particular player, only on the completed hand. Is that what you meant by the “{}” when you wrote “f({C1,C2,C3},n)”?
Comment by Julian on June 29, 2006
Here are the thought processes that went through my head when I read Alan’s comment.
1) Yes, it can’t depend on the order. The curly brackets indicate a set rather than a list.
2) Wait a moment…. What is Alan up to? What if he made the order that you received the cards important? Then, once you detected whether you were the thief, you could simply shuffle the cards in your hand, and hide whether you are the thief or not! Brilliant! I never thought of it from that angle. Alan has, once again, proven his true genius. From this day forward, when I refer to Alan, I shall refer to him as “Alan, this century’s greatest mind.”
3) Hold on…. If you consider one configuration of dealt cards, with exactly one player as the thief, and then shuffle the configuration so all the other players receive the same cards in the same order, but the would-be thief gets them in a different order and is no longer the thief, then you won’t have a thief. Did Alan, this century’s greatest mind, ever give that a moment’s thought? He’s no genius! He’s a fool! Imagine the gall of the man, expecting people to refer to him as “this century’s greatest mind”! What hubris – and in the bad sense of the word!
4) But…. what if you had two decks of similar looking cards.
For example, for n = 7, you could have one deck with one blue card and six green cards, and a second-deck with nine blue cards and five green cards. First, deal the first deck, and let everyone look at their own cards – blue = thief. Then, deal the other deck, and let people shuffle their hands.
(I’ll leave it to someone else to calculate how the odds of someone being a thief change once you learn that at least one of their cards is blue, but it isn’t a big difference.)
So by breaking two of the restrictions in the original puzzle problem (that order is not important, and that the cards are all distinctly labelled), we have a somewhat workable solution.
Hmm… I’d better not give any of the credit for this idea to that Alan guy. He’d let it go to his head.