How likely are you to beat the Raven?

Last year I spent quite a bit of time playing with and studying two puzzles: Rush Hour and Rubik’s cube. However, the game I have played the most in recent years is Haba’s First Orchard!

First Orchard is a cooperative game with simple rules and a beautiful design. The wooden fruits are heavy, sturdy, and a tactile pleasure for kids. I have seen my kids literally develop while playing this game. They have learned to take turns, correctly associate a die roll with an action, learn the names of colors and fruits, and understand winning strategies.

The objective of the game is to collect the fruits before the raven reaches the garden. The raven advances one square if the die rolls the raven image. Each time the die lands on a color (yellow, green, red, or blue), one of the corresponding fruits is picked. The remaining die face is a basket, which acts as a wildcard and allows players to pick any fruit. The game ends when all the fruits have been picked (win) or when the raven has advanced five squares and arrived at the garden (lose).

This game may not be the most mathematically interesting, but the following questions keep popping in my head:

• What is the probability of winning?
• Is there a winning strategy?
• Can the probability of winning be controlled in some way?
• What is the longest possible game? Not because I’m bored, but out of pure scientific curiosity. 😉

Finding the probability of winning is straightforward. I ran a simple simulation. The only factor that influences the probability outcome is deciding which fruit to pick when the wildcard is rolled, i.e., adopting a policy or strategy.

import random

RAVEN, WILDCARD = 4, 5

def game(strategy: str="random") -> bool:
    fruits = [4, 4, 4, 4] # trees stocks
    raven = 5 

    while True:
        die = random.randint(0, 5)

        if die == WILDCARD:
            if strategy == "max":
                idx = fruits.index(max(fruits)) # select tree with most fruit
            elif strategy == "min":
                idx = fruits.index(min([f for f in fruits if f > 0])) # select tree with the least fruit
            elif strategy == "random":
                idx = random.choice([i for i in range(4) if fruits[i] > 0])
            else:
                continue # ignore, do nothing

            if fruits[idx] > 0:
                fruits[idx] -= 1

        elif die == RAVEN:
            raven -= 1

        else: # die lands in one of the colors representing the 4 fruits
            if fruits[die] > 0:
                fruits[die] -= 1

        if sum(fruits) == 0: # all fruit picked
            return True
        
        if raven == 0: # Oh no! The raven reached the garden and ate the remaining fruit!
            return False

After running this function 1 million times and averaging, these are the probabilities I obtain.

I know that code is not the most efficient, especially if you have to run it many times. However, it turns out that a Monte Carlo simulation is not necessary to find these probabilities. This is an instance of a Markov chain with absorbing states (see chapter 11 of this this reference), and the exact probabilities can be found using an analytical or quasi-analytical method.

The probability of winning is given by $P(s)$, where $s$ is the state. $s=\{\text{fruits}, \text{raven}\}$, the four fruit stocks plus the raven position.

From a non-terminal state, the win probability of the current state is the average of the win probabilities of the states that can be reached from it.

Here, $s'$ represents the state after a particular face is rolled.

This formula is implemented by the recursive Python function below.

The last term represents the wasted rolls when a tree is already empty. Solving for $P(s)$:

from fractions import Fraction
from functools import lru_cache

N_FRUITS = 4  # number of trees (die faces 0-3)
FRUIT_STOCK = 4  # fruit on each tree
RAVEN_STEPS = 5  # raven steps

@lru_cache(maxsize=None)
def game(fruits: tuple[int, ...], raven: int, strategy: str) -> Fraction:
    """returns probability of winning"""

    # End states; base cases.
    if all(f == 0 for f in fruits):
        return Fraction(1) # Probability of winning is 1, we win!
    if raven == RAVEN_STEPS:
        return Fraction(0) # Probability of winning is 0, we lose :(

    empty = sum(1 for f in fruits if f == 0)
    nonempty = [i for i, f in enumerate(fruits) if f > 0]

    def pick(t: int) -> tuple[int, ...]:
        """pick(t) produces the successor state: when a fruit is picked from tree t.
        """
        nxt = list(fruits)
        nxt[t] -= 1
        return tuple(sorted(nxt)) # sort to reduce cached entries. Order of trees doesn't matter.

    # Fruit rolls on the four trees
    fruit_rolls = sum((game(pick(i), raven, strategy) for i in nonempty), Fraction(0))

    total = fruit_rolls
    total += game(fruits, raven + 1, strategy)  # raven roll

    # The wildcard (basket face) picks fruit according to the policy or strategy we implement
    if strategy == "max":
        j = max(nonempty, key=lambda i: fruits[i])
        total += game(pick(j), raven, strategy)
    elif strategy == "min":
        j = min(nonempty, key=lambda i: fruits[i])
        total += game(pick(j), raven, strategy)
    elif strategy == "random":
        total += fruit_rolls / len(nonempty)  # average over the non-empty trees
    else:
        raise ValueError(f"unknown strategy: {strategy!r}")

    return total / (N_FRUITS + 2 - empty)

In a way, this recursive function counts outcomes, which is not surprising, of course. As Richard McElreath points out in his wonderful book, probability is precisely that, a calculus for counting outcomes.

The exact probabilities $p_e$ obtained with the recursive formulation are shown below:

The wildcard is important. For example, when we ignore it, as we sometimes do, the probability of winning falls to $0.32$.

I told my son about the winning strategy, and now he picks a fruit from the tree with the most fruit. My daughter, on the other hand, doesn’t care much about probabilities and just picks any fruit she likes. What is the probability of winning with this mixed strategy?

The number of players doesn’t matter. This mixed strategy is equivalent to having one player who, whenever he rolls the basket, picks the tree with the most fruit two-thirds of the time and picks at random one-third of the time. In this case, the probability of winning drops to $0.62$.

I didn’t really answer the last question about the duration of the longest possible game. That’s left as an exercise for the reader.