# The Orchard Game

Last week, during an appointment with my oncologist, Dr Andrew Coveler, he told me about game he played with his kids called The Orchard. He knows I like to write about games like that on my blog, so asked me about an analysis of the game. I’d never heard about the game before, but he briefly explained the rules, and this evening I looked it up.
It appears there are two versions of the game, and it is German in origin (like so many other great board games), originally called Obstgarten. The first version is a simple game, called in English, My First Orchard, aimed at children aged 2+. The second, slightly more complex variant, is just called The Orchard Game. The game is over 30 years old, and has sold close to 3 million copies.
Both games are available on Amazon.

## Game Mechanics

The rules of the game are pretty simple; collaboratively, players need to harvest fruit before it is eaten by a hungry raven. There is an orchard with four kinds of fruit trees (apples, pears, cherries, and plums), each with a corresponding color (green, yellow, red, blue). There is a six-sided die with matching colors. On your turn, you roll the die, and if you roll the appropriate color, and there is corresponding fruit still on that tree, you can harvest one piece and place it in your basket. In addition to the four fruits, there are two other faces on the die. The first is a fruit basket. If you roll the fruit basket you can harvest any piece of fruit from the tree of your choice.
The final face of the die is a raven. If you roll the raven, he advances one step towards the fruit. If he gets to the fruit before it is fully harvested, you lose. If you roll a fruit, and that particular fruit is already fully harvested, you simply pass; there are no negative consequences.
In the simple game there are four of each kind of fruit to harvest, and the raven takes five steps before devouring the fruit. In the advanced version there are ten pieces of each fruit and the twist that, if you roll the basket, you can harvest any two pieces of fruit.
It’s a collaborative game; if all the fruit is harvested before the raven gets to the orchard, everyone wins. If the raven gets there first, everyone loses. ## Strategy

It’s a pretty simple game, and there’s practically no strategy as most of the time players are following what is rolled on the die. The only player decision point is what to do when a basket is rolled. It should not be too hard to convince yourself that the optimal strategy, when given a choice, is to select a fruit to that is most popular still on the tree (or randomly select from the selection if there is more than one fruit of that count).

## Modeling the Game

What we want to determine is the percentage of the time the game is won.
The game moves through a series of states before getting to one of the two conclusions. At any time we can model the state of the game by the parameters that change with the moves, these are:
• Steps taken by Raven [R].
• Quantity of Apples in basket [f1].
• Quantity of Pears in basket [f2].
• Quantity of Cherries in basket [f3].
• Quantity of Plums in basket [f4].
We can uniquely define each game state with these parameters, and what we want to determine is the probability of a win from that state:
Pr(R, f1, f2, f3, f4)
There are a couple of trivial (sentinel/boundary) cases we can get for free. (We’ll start with the simpler version of the game where the raven needs to advance five spaces, and there are four of each fruit).
Pr(5,?,?,?,?) = 0
If the raven in position five, it’s game over (zero chance of winning).
Pr(?R≠5,4,4,4,4) = 1
If there are four of each fruit in the basket, then it’s a win for the players.
Using these boundary cases, and some simple stochastic mathematics, we can work out the probabilities of winning from other states knowing that something happens on each roll, and the probabilities of these transitions. Setting aside (just for now) the case where a player rolls a fruit for a tree is empty (pass the dice), then one of six possible things can happen when the player starts from state (R, f1, f2, f3, f4).
Pr(R, f1, f2, f3, f4) =
1/6 × Pr(R+1, f1, f2, f3, f4) +
1/6 × Pr(R, f1+1, f2, f3, f4) +
1/6 × Pr(R, f1, f2+1, f3, f4) +
1/6 × Pr(R, f1, f2, f3+1, f4) +
1/6 × Pr(R, f1, f2, f3, f4+1) +
1/6 × Pr(R, fs = min(f1, f2, f3, f4) [+1])
There’s a one sixth chance of rolling the raven. There’s a one sixth chance of rolling any of the four fruits, and there’s a one sixth chance of rolling the fruit basket where we get to pick a fruit of choice. In the last case we determine which of the basket fruit counts is the lowest, and pick that type of fruit.

## Empty Tree

If we can solve what to do when the player rolls an empty tree, then we have all the equations we need to calculate determine the probability of winning from any state. It’s not actually that much harder to calculate. If a player rolls a fruit for which a tree is empty, it’s just like the equivalent of re-roll, and you are back where you started from. In the example above, one of the fruits is already saturated, so there is a 1/6 chance, if we roll that fruit, that we’ll be back to exactly where we started. We can write the formula as a self-referential formula in which the probability appears on both sides (We used this technique earlier this month in an article about rolling dice). Simple algebra allows us to rearrange the formula to get the answer we need. As simple example:
Pr(win_from_this_state) =
Pr(all_other_things) +
1/6 × Pr(win_from_this_state)

Pr (win_from_this_state) = 6/5 × Pr(all_other_things)
Using this technique allows a calculation of the probability for any state. The same technique applies when there is more than one saturated fruit; a roll of which would simply be a re-roll where the chance of the winning is the same.
As a concrete example, imagine the state where the raven is in position 4, and we only need one more plum (4,4,4,4,3).
Pr(4,4,4,4,3) =
1/6 × Pr(5,4,4,4,3) +  roll raven
1/6 × Pr(4,4,4,4,4) +  roll plum
3/6 × Pr(4,4,4,4,3) +  roll fruits we already have
1/6 × Pr(4,4,4,4,4)   roll fruit basket
Rolling the fruit basket gives us a free choice, and we’d pick the plum, so that’s the same as rolling the plum, which would take us to (4,4,4,4,4) which is sure win. Rolling a Raven takes us to (5,4,4,4,3) which is a sure loss. Rolling any other fruit takes us back to where we started.
Pr(4,4,4,4,3) = (1/6 × 0) + (2/6 × 1) + (3/6 × Pr(4,4,4,4,3) )
Pr(4,4,4,4,3) = 2/3
If we are down to just one fruit left, and the raven is one space away, the chance of the players winning is 2/3rds.

## Recursion

Now that we have formulas for any state, we can calculate the probability of winning the game from the start by calculating Pr(0,0,0,0,0)
Pr(0,0,0,0,0) = ?
The calculation of this requires the calculation of all the nested branches of all the possible outcomes, which in turn, requires the calculation of all the possible outcomes from all these states, which … and so on until we reach the sentinel (gimmie) values at the edge. There are thousands of calculations to perform, recursively. Thankfully, this is what computers are very good at doing!
As mentioned, this is a recursive problem (to solve any state, you need a superposition of self-similar state problems, which in turn are based on self-similar problems of state … all nested like a set of Matryoshka dolls). However, if you attempt to code a solution to this using simple recursion, you’re going to have a really bad day! Simple recursion is hellishly inefficient because you are re-calculating the same problem over and over again (and for answers deeper in tree, a massive number of times). A better solution is to using Dynamic Programming.
(There is much symmetry that could be used to simplify the calculations; without loss of generality, all the fruits are equivalent, but this adds complexity to the code (increasing the chance of errors), and the answer is calculated so fast, that I treated all fruits as distinct).

## Results

Using the above technique, I calculated the value of Pr(0,0,0,0,0) for the First Orchard Game (five Raven steps, four of each fruit).
Pr(0,0,0,0,0) ≈ 0.631357
On average, 63.1% of games will be successful.

## Big Brother

What about the more advanced version of the game? (nine raven, ten fruits). This is a little more complex because with a fruit basket roll you get to pick two fruits. Again, the optimal technique is to pick fruits that are least popular in your basket, but these might be two different fruits. To correctly model you need to redetermine what the least popular fruit is after selecting the first of the two. Also, there’s a little gotcha in that you have to account for the fact that you might not need to draw two fruit right at the end of the game (it’s possible to win with a basket roll when there is only fruit left in a tree).