The Math of Who Took the Apple?

Last Nordic Game Jam I designed a physical card game called Who Took the Apple? The game is a four player game, involving giant sized cards, 4 beers, a bucket and an apple… oh – and it is played backwards in time!

The game feature beautiful artwork by Simon Gustafsson from RedGrim and you can download it, print and play it right now.

Some people find the mechanics somewhat perplexing, which has made me write this blog post. I have to warn you, this will be rather lengthy; involve a good deal of economic game theory a dash of temporal logic and constant references to apples, buckets and beers. In the end though, I think writing this made me realize a thing or two about why some board games works, even though they in “theory” shouldn’t. So please continue reading:

First the rules of the game:

Rules

Setup:
Deal the cards to the players. Each player receives a set of four cards in the same color.

Place an apple under a bucket. All players form a circle around the bucket.

Play:
Player one and three are a team competing against player two and four. The goal of the game is to be the team who took the apple.

Player four plays a card face up on the ground. Remember this game is played backwards, first card played will be last action happening!

Now going counter clockwise (backwards in time) each player plays a card face up on the top of the stack of played cards. The player states loud and clear “Before that, I…” followed by the action printed on the card.

Ending the game:
Once all cards are played each player takes a beer and holds on to it. Go through the deck from top to bottom and carry out the actions printed on the cards. If an action is identified as impossible to carry out, everybody cries “Paradox!” and that card will be ignored to restore space/time logic.

The game ends the moment a player takes the apple.

I don’t know how I exactly came up with the mechanics, I think I were inspired by two things:

Inspiration 1

At Nordic Game Jam Marek Plichta gave a talk about his physical game Ordnungswissenschaft, and how they were inspired by autonomous automata, performative play and generative art while designing the game. In Ordnungswissenschaft four players carry out a set of instructions moving boxes around in the circle. The players have to execute the instructions in the given order, they can only decide when to execute, not what to execute.  The goal of the game is to get rid of all boxes next to you.

Ordnungswissenschaft seems extremely chaotic and random, but after a number of playthroughs patterns start to emerge. Players cannot expect the same events to happen in every game, to there is a certain underlying rhythm which is possible to pickup, anticipate and manipulate. One thing that really intrigued me about Ordnungswissenschaft was the performative elements. Players create a spectacle while playing: they move big boxes around, stumble with giant towers in their hands and collide while passing boxes. The commotion alone invites spectators and new players in.

Inspiration 2

I have been playing Vlaada Chvátil brilliant collaborative board game Space Alert a lot. In Space Alert five players all plan their actions for twelve turns at the same time in the hectic first phase of the game. In the second phase of the game, the players go through all the actions again, and resolves what actually happened. Small mistakes in the beginning often trigger chain reactions of catastrophic events.

When the players plan their actions they all have a mental model of the game, but these mental models might differ because of lack of communication, wrong calculations and temporal misunderstandings which causes breakdowns in the logic. Often losing in Space Alert is at least as funny as winning.

The Game

The preprogrammed actions of Ordnungswissenschaft somehow got me thinking about Space Alert. I figured that in theory it wouldn’t be impossible to plan all your actions in Space Alert backwards, not impossible, but probably extremely hard and confusing.

The starting state of Who Took the Apple? is that every player holds 1 beer in their hand and an apple is placed on the ground under a bucket. Players have the same four cards each, and the only choice is to figure out the order in which to play them:

1. Take that Apple (You need one free hand. The bucket must not be over the apple.)
2. Put the Bucket over the head of the Person to your Right (You need two free hands. A Person with the bucket over their head cannot do anything.)
3. Hand a Beer to the Person to the Right (The Person to your right needs at least one free hand.)
4. Give all your Beers to the Person to your Left (The Person receiving the Beers needs one free hand per Beer, otherwise no Beers are given.)

In order to win, the player needs to take the apple, in order to take the apple somebody needs to remove the bucket and in order to remove the bucket the players needs to get rid of their beers. Because everybody else is trying to do the same time becomes an important factor. A typical game will play something like this:

Player 4 plays “Take the apple” (remember first card played is last action happening)

Player 3 plays “Take the apple” (this means that player 3 will take the apple before player 4)

Player 2 plays “Pass 1 beer to the left” (player 3 can only take the apple if she has a free hand. If player 3 gets a beer from player 2 she might not be able to take the apple)

Player 1 plays “Take the bucket and place it over the head of the player to your right” (this puts the bucket over the head of player 4 which makes it impossible for him to take the apple)

Player 4 plays “Pass 1 beer to the left” (player 1 needs both hands to move the bucket, but if player 4 manage to give her a beer right before, she will fail putting the bucket over his head)

Player 3 plays “Take the bucket and place it over the head of the player to your right” (if player 3 manage to do this, it will make player 2’s earlier action impossible, which would then make it possible for player 3 to take the apple before player 4.

…and so on. The game continues until all cards a played.

The paradox

As you probably can read, the game becomes rather perplexing; players have to juggle multiple potential game states in their head if they want to make informed choices. I have had an equal number of players telling me that the game is broken because it is based on pure luck and broken because it is simply solvable and deterministic. I hope it lands somewhat between.

Yes formally the game has perfect and complete information. There is no simultaneous actions, no chance moves, no bluffing, the game is mathematically solvable, so why would I claim that the game isn’t broken? Let’s look at a simpler version of the game to try to understand it. In this game, lets call it Simple Apple each players only have two cards, A: “Take the Apple” and B: “Remove the bucket”. The game played forward can be modeled like this:

Each node represents a decision point. The number next to the node identifies who makes the decision. The number to the far right of the decision tree are potential outcomes: (1 , 0) means the team with player 1 and 3 wins, (0 , 1) means player 2 and 4 wins. Note that all players have to play each of their cards which are why there are four decision points without any decisions in the end of each branch (they each have one card left to play).

Every time a player takes a choice in the game they split the tree in two and eliminate half of the possible outcomes. For example could player 1 start the game by playing card A removing all the lower possible outcomes:

If player 2 also plays A she removes the lower half of the outcomes left:

Then player 3 could play B and remove the top two outcomes.

And finally player 4 has to choose between the two only outcomes left, in this case he would probably chose A, giving his team a victory.

Every time a player takes a decision, they project forward and try to steer the branch towards their most optimal outcome. In Simple Apple this is pretty straight forward, player 1 and 3 have lost from the beginning: If player 1 starts the game by removing the bucket, player 2 would immediately grab the apple. If player 1 waits and plays “take the apple” in the beginning, player 2 can force the result up in the upper quarter of the tree by also taking the apple. Up there player 3 can either remove the bucket straight away or play the apple card but both strategies will lead player 4 to take the apple. Finding an optimal strategy like this is pretty straightforward using a technique called backward induction.

Backward / forward

Simple Apple, played forward is broken, like Tick Tack Toe, once you realize the optimal strategy; there is no reason to play. Now what happens if you play Simple Apple backwards?

Player 4 takes the decision first and removes half of all possible outcomes, but the tree is not split from bottom up but from top down:

In some winning states player 4 ends the game by playing A while in other he ends the game by playing B, it is not entirely obvious what he has to do. The game is still solvable and in theory still broken. One could actually just write a flipped tree starting with player 4’s choice and ending with player 1’s. But the problem is that since the rules are formulated forward in time, the outcomes becomes harder to compute. In Simple Apple played forward the formal rule of victory is this:

The first player who takes the apple after the bucket is removed wins.

Formulating that backwards would be something like:

The player wins if she is the last player to take the apple as long as the bucket is removed at least once after she takes it.

If you are totally fluent in temporal logic and negating causality, this shouldn’t be a problem to figure out, the rest of us have to think for a moment or two before we understand how it works.

Who took that Apple?

Going back to Who Took the Apple? we see that the decision space is much larger. In Simple Apple there were 2 *2*2*2*1*1*1*1 = 16 possible outcomes, in Who Tooke the Apple? there are 4*4*4*4*3*3*3*3*2*2*2*2*1*1*1*1 = 331.776, which is indeed a lot more.

Nevertheless, played forward I guess the optimal strategy would pretty quickly emerge. But trying to reverse the temporal logic of the rules of all the four cards and how they interact is simply impossible to do in the head. This is why you have to fall back to the next best strategy while playing the game: Understanding the rules forward but trying to maintain a few possible branches in the head while playing. Often each team has their own understanding of how the game is going to play, and they fight each other in order to make their possible world the actual one.

Yes there are a dominant strategy somewhere between the 331.776 and somebody can probably find it writing some software bruteforcing the solution. But until then I think Who Took the Apple? to some extend has reached the sweetspot of good games of perfect information like Chess and Go where the optimal strategy is impossible to play and one have to act according to limited tactical concerns, gut feelings, rules of thumbs and intuition.

…oh and just as a failsafe: In the advanced rules I introduce three new cards (chug a beer, put the bucket back and plant a decoy beer). Each player secretly picks one card to include in their deck. This creates a simultaneous double blind decision point which David Sirlin swear to as a key component of well balanced multiplayer games. These games of imperfect information are a whole other ballgame when calculating optimal strategies. Basically the optimal strategy is often a mixed strategy of picking a random choice every turn, but humans are really bad at randomizing, and psychological factors like bluffing, risk willingness and play style starts making everything a mess. I hope that will prolong the lifetime of Who Took the Apple, even if somebody do manage to “break” the basic game.

Questions

Writing this blog post raised a bunch of questions for me.

• Is it possible to find a dominant strategy for Who Took the Apple? – what is the best strategy for finding such a strategy?
• If we find an optimal strategy will that break the game? I guess that depends on whether the strategy is trivial and easy to remember or not.
• If we find an optimal strategy, did my failsafe work? Do the three new cards create a rock/paper/scissors like choice or is one of the three also clearly dominating the other options?
• Is there design techniques and methods to employ when developing and balancing perfect information games which ensures the games not being easily solvable while not needlessly chaotic?

I would love to write a new post, trying to answer some of these questions, but it would be easier if someone did manage to break my game before. Please send me a solution of an unbeatable strategy and explain how you found it – I will sponsor a crate of beers to the first person who comes up with such a solution.