A question that keeps me up at night is “What is the theoretical best you can do in Mysterium?” I’m exaggerating a bit, but it is a pointless question about a silly board game that I nonetheless spent too long thinking about. I went so far as to watch a series of lectures about information theory–listening to it in the background while in dance class, as one does. I never solved the problem, but let me at least explain what the problem is.

Mysterium

Mysterium is a cooperative board game where the players are trying to solve a murder mystery via psychic communication with the victim. One player takes the role of the ghost, and the rest take the role of psychic mediums. The ghost is not allowed to speak, and may only communicate through cryptic visions. The visions are represented by cards with surreal artwork. For example, one card has two people climbing into a giant fish mouth, another has a tarantula-like thing over a chandelier. After the mediums receive their visions, they discuss what they mean and make their guesses; and the whole time the ghost giggles about how wrong they are.

Mechanically, the ghost has a hand of seven cards. Each turn, the ghost gives one or more cards to a medium, and then draws back up to seven. There are other rules but I’m going to ignore them, because the problem is already too difficult as it is.

Suppose that the medium is deciding between seven different suspects. One strategy that the ghost could use is to totally ignore the card illustrations, and give the medium a number of cards equal to the index of the correct suspect. So if the medium receives one card, it’s the first suspect; if they receive two cards, it’s the second suspect; and so on.

This is obviously not the way the game is intended to be played. It’s a boring and abusive strategy that would totally break the game. Let us not pretend for a moment that mathematically solving this problem has any relevance to how the game is actually played. We’re not playing board games here, we’re just doing math for math’s sake.

So, as a lower bound, the ghost could help the medium choose between seven options. But the ghost could do even better by considering the content of each vision. The challenge is that it’s not deterministic what cards the ghost even has available. The ghost has a hand of seven cards, out of 84 cards in the deck. If there’s one card that would perfectly communicate what the ghost wants to say, but that card isn’t in the ghost’s hand, then it’s no use. Furthermore, the medium does not know which cards the ghost has available.

Noisy Channel Coding

This problem may be situated within information theory, and more specifically the theory of noisy channel coding. Suppose that we want to communicate some amount of data through a wire, but the wire introduces some noise. We can think of the data as a series of bits, ones and zeros, but the wire occasionally flips a bit. One way to correct for error is to send three copies of the data. So if one bit is flipped, you can still extract the correct data from the other two copies. Unless, of course, two bits are flipped, then there’s still an error. So maybe send five copies of the data. But you’re still not completely eliminating the error, and you’re blowing up the size of the data you need to send.

As we try to solve this problem, we’re making tradeoffs between two objectives. First, we’d like to reduce the error rate. Second, we’d like to communicate the data quickly. The wire can communicate a certain number of bits per second, and we’d like to communicate some number of megabytes of data as fast as possible, with error rate under some threshold. How do we do it?

It turns out that we don’t need to worry about the tradeoff, because it’s possible to bring the error rate arbitrarily close to zero. According to the Shannon-Hartley theorem, there exist strategies with nearly zero error rate, but a finite communication rate. This communication rate is called the channel capacity.

In Mysterium, the ghost is essentially communicating over a noisy channel. Each turn, the ghost can send basically 7 bits, since they have seven cards, and for each card they can choose whether or not to send it. However, the bits get garbled, and transformed into a series of surreal images.

To illustrate the process, imagine that we’ve numbered each card (and there are 84 of them, so they’re numbered 1 to 84). Suppose the ghost has cards numbered 1, 6, 26, 51, 57, 63, and 64. The ghost wants to point the finger at a particular suspect, and this message gets encoded into a series of 7 bits: “0101011”. So ghost passes the cards numbered 6, 51, 63, and 64. The psychic medium only sees this series of numbers, and does not know what cards the ghost had to choose from. How many bits of information can the ghost communicate without error per turn?

The Channel Capacity of Mysterium

This question is too hard, so I’d like to simplify even further by considering the case where the ghost only has two cards in hand. The ghost is required to pass at least one card, leaving three options: pass both cards, pass the lower card, or pass the higher card. We can denote each of these options with bits: “11”, “10”, and “01”. When there are three options of equal probability, the number of bits is equal to log₂(3), or about 1.58 bits. However, when the psychic medium sees a single card, they will not know whether it was the higher card or lower card in the ghost’s hand. The best that the psychic can do is guess that if the card is 42 or below, then it was the lower card; and if the card is 43 or above, then it was the higher card.

As a result, when the ghost passes a single card, 25% of the time the medium will be mistaken about whether it was the higher or lower card. 25% of the time, a “01” will be misinterpreted as a “10”, and 25% of the time, a “10” will be misinterpreted as a “01”.

The Shannon-Hartley theorem is a non-constructive theorem, meaning it won’t tell you how to attain the channel capacity. However, we can at least calculate the channel capacity. The channel capacity is equal to the maximum possible mutual information between the input and the output. I’d rather not go through all the math, (lest I reveal how shaky my own understanding is), but I’ll share the answer I got from making estimates in excel. The channel capacity is about 1.097 bits per turn. In order to attain this capacity, the ghost should use the message “11” about 47% of the time. About 91% of the information is conveyed through the number of cards, and only 9% of the information is conveyed through the choice of which card.

(In answering this question, there was one factor that I did not know how to account for. In the typical noisy channel problem, we assume that the noise is random and unpredictable. However, in this case, the ghost actually knows exactly what the noise is before choosing what message to send. How does this affect the calculation? I don’t even know.)

What about larger hand sizes? Gosh, solving it with two cards was hard enough. To do more cards, I’d need to calculate an exponentially large confusion matrix, and solve multiple logarithmic equations simultaneously. I think a good math scholar could solve it and write a paper about it, but it’s above my paygrade. There’s a phrase that math folks use in a situation like this: “Left as an exercise to the reader.”