Probability of winning a game for toddlers

Question

Recently, my son got a game called Little Cooperation. The rules (see here) are very simple:

We have 4 animals that need to travel from an ice flow to a safe igloo. Between a flow and an igloo there is an ice bridge that stands on 6 pillars. What you can do is determined by a 6-sided die with 2 bridges, 2 igloos, and 2 ice cubes on it:

• "bridge" means, you can move one animal from an ice flow onto a bridge.
• "igloo" means, you can move one animal from a bridge to an igloo.
• "ice cube" means that one of the pillars collapses.

The goal is to move all the animals from the ice flow to an igloo before the bridge collapses (ignore physics, gravity and so on, and assume it collapses when its last pillar falls).

Now, what is a probability of winning?

I ran some simulations, so I'm pretty sure I know the answer but I wonder if it's possible to calculate it with pen and paper?

Answer 1

The method is simple, but a pencil-and-paper calculation would take some time.

The possible states of the game can be described by non-negative triples $(n,f,b)$ representing, in turn, the numbers of pillars $n,$ the number of animals on the floe $f,$ and the number of animals on the bridge $b.$ (The number of animals in the igloo is determined by $4-f-b.$)

• When a state of the form $(0,*,*)$ is reached, the game is lost. Its value to us is zero.

• When a state of the form $(n,0,0)$ with $n\gt 0$ is reached, the game is won. Its value to us is $1.$

The expected value is the sum of the values times their chances, which equals the sum of all chances of winning: that's what we want to compute.

The possible moves are

1. An "ice cube" changes $(n,f,b)$ to $(n-1,f,b),$ provided $n\gt 0.$

2. A "bridge" changes $(n,f,b)$ to $(n,f-1,b+1)$ provided $f \gt 0.$

3. An "igloo" changes $(n,f,b)$ to $(n,f,b-1)$ provided $b \gt 0.$

The method is to work backwards from the winning or losing states to compute the expectations for earlier states in the game.

Usually, each move is made with a chance of $1/3.$ As a shortcut, it helps to observe that in some states, not all moves are possible. For instance, from the initial state $(6,4,0),$ when "igloo" is rolled, nothing happens. The effect is to move eventually to either the state $(5,4,0)$ or $(5,3,1),$ each with probability $1/2.$ (This implies, by the way, that the answer must be a fraction whose denominator is a product of a power of $3$ and a power of $2.$)

The pencil-and-paper calculation could proceed in this fashion:

• The value of $(1,0,0)$ is $1.$

• The value of $(1,0,1)$ is $1/2,$ because there's a $1/2$ chance of moving to $(0,0,1)$ (with a value of $0$) and a $1/2$ chance of moving to $(1,0,0)$ (with its value of $1$).

• The values of $(1,0,2)$ and $(1,1,0)$ similarly are $1/4,$ because there are even chances of moving to $(1,0,1)$ or to a loss.

• The value of $(1,1,1)$ is $(0)/3 + (1/4)/3 + (1/4)/3 = 1/6$ because there are equal chances of moving to $(0,1,1),$ $(1,0,2),$ and $(1,1,0)$ with values $0,$ $1/4,$ and $1/4,$ as previously computed.

• Etc., etc.

Proceeding (patiently!) through all $104$ possible states, we wind up with a value of $$148901 / 314928 = (61\times 2441) / (3^9\times 2^4) \approx 0.47281,$$ a little less than a $50\%$ chance of winning, for the initial state $(6,4,0).$

---

Using a computer helps. Here is the R program I used for the calculations. It is set up to evaluate other versions of this game, starting from any initial position, using obvious and minor modifications. It could be a useful tool to design a similar game with any desired winning probability. For instance, you can accommodate a player with a shorter attention span by using $n=4$ pillars and starting with just $f=2$ animals (winning chances: $57\%$); or you can give a player an advantage by starting some animals on the bridge. E.g., starting with two animals on the bridge (initial state $(6,2,2)$) has a $69\%$ chance of winning.

An optional array DEPTH tracks how many moves (using the shortcut previously described) are needed to reach each state. The maximum depth is $8+6-1=13,$ because after that many moves either all animals reach the igloo (eight moves) or all pillars collapse (six moves).

#
# Describe the game.
#
moves <- rbind(`ice cube`=c(n=-1,f=0,b=0), # Pillar collapses
               `bridge`=  c(0,    -1,  1), # Move from floe to bridge
               `igloo`=   c(0,     0, -1)) # Move off the bridge
do.move <- function(state, move) {
  newstate <- state + move
  newstate[newstate < 0] <- NA # Invalid move
  newstate
}
to.name <- function(state) paste(state, collapse="|")
#
# Find all states of the game and the chances of winning from them.
#
STATES <- list()
DEPTHS <- list(`NA` = -1) # Optional calculation of search depth
VERBOSE <- FALSE          # To display progress
evaluate <- function(state, previous=NA) {
  if (any(is.na(state))) return(NA) # Ignore invalid moves
  
  s <- to.name(state)
  DEPTHS[[s]] <<- DEPTHS[[to.name(previous)]] + 1 # Optional
  
  if (is.null(STATES[[s]])) {
    if(state[1] <= 0) {
      value <- 0 # No pillars left
    } else if(all(state[-1]==0)) {
      value <- 1 # Some pillars left; no pieces on the floe or bridge
    } else {
      if(isTRUE(VERBOSE)) cat("Evaluating ", s, " at depth ", DEPTHS[[s]], "\n")
      options <- apply(moves, 1, function(move) evaluate(do.move(state, move), state))
      value <- mean(options, na.rm=TRUE)
    }
    if(isTRUE(VERBOSE)) cat("Caching ", s, " at depth ", DEPTHS[[s]], "\n")
    STATES[[s]] <<- value
  }
  STATES[[s]]
}
(value <- evaluate(c(n=6, floe=4, bridge=0)))
```