*July 2015*

Lately we've been playing a lot of the game Camel Up (or Camel Cup?), and it leads to some interesting math problems.

First let's start with the basics. There are five camels, and each one starts on a random square from 1-3. Every leg, each camel moves either 1, 2, or 3 squares, and the game is over when a camel reaches square 16. (there are stacking rules, but let's ignore those for now)

So the first question is: **How many legs does a game take on average?**

For one camel this doesn't seem to hard - on average they start on square 2, and on average they move 2 squares per turn. But with five camels, the game is over as soon as the fastest camel gets to square 16 - how can we count this?

This seems like a tricky problem, so my first approach was just to write up some Python to simulate 20000 races and try it out. (for all of these approaches I just let all the camels start at square -1, then subtract one from the final number of legs) Here's what `simulateRace()`

looks like in Python (see the bottom of the post for the actual code):

```
def simulateRace(numCamels, numSquares):
totalSteps = 0
ITERATIONS = 20000
for i in range(ITERATIONS):
camelPositions = [-1] * numCamels
while (max(camelPositions) < numSquares):
for j in range(numCamels):
camelPositions[j] += random.randint(MIN_CAMELSTEP, MAX_CAMELSTEP)
totalSteps += 1
return float(totalSteps) / ITERATIONS
```

This is pretty straightforward. There are a few problems, though:

**How many iterations are enough?**Good question! I don't realy know, although I guess you could try a number, run it a few times and see if you get consistent results. For these purposes 20000 does seem to be enough.**It's kind of slow.**If \(c\) is the number of camels and \(s\) is the number of steps they have to go, then this takes \(O(cs)\) time and \(O(c)\) space. (and there's a pretty large constant factor for the time!**It's only an approximation.**Which is fine for all practical purposes, but I like exact results!

My next thought was to use a dynamic programming approach where the subproblems are the positions of all the camels. This was the best I could think of - the positions of all the camels matters, because the state where one camel is at 16 and the rest are at 8 is very different than if they're all at 16 (for example). Here's what the code looks like:

```
cache = {}
def getAdder(length):
return itertools.product(range(MIN_CAMELSTEP, MAX_CAMELSTEP+1), repeat=length)
def cycleThroughStates(camelState, adder):
l = len(camelState)
for a in adder:
newState = list(camelState)
for i in range(l):
newState[i] += a[i]
yield newState
# takes in a camel state (list of camel positions) and returns
# the expected value of how many moves are left
def calculateRaceDynamicImpl(camelState, adder):
if (max(camelState) >= numSquares):
return 0
camelState.sort()
if (tuple(camelState) in cache):
return cache[tuple(camelState)]
bigTotal = 0
count = 0
for newState in cycleThroughStates(camelState, adder):
bigTotal += calculateRaceDynamicImpl(newState, adder, numSquares)
count += 1
answer = bigTotal/float(count) + 1.0
cache[tuple(camelState)] = answer
return answer
def calculateRaceDynamic(numCamels, numSquares):
adder = list(getAdder(numCamels))
cache = {}
return calculateRaceDynamicImpl([-1] * numCamels, adder, numSquares)
```

This also works, but is time and memory-intensive - since there are \(s^c\) states, it takes \(O(s^c)\) space and time! (not all of the states are reachable, but I think enough of them are that it's still \(O(s^c)\).)

So this was disappointing. I thought there must be a better way, maybe involving standard deviation or something. But after brunch and a conversation with David, inspiration struck!

This uses dynamic programming to calculate the probability that one camel will finish in less than a given number of legs. It does this by using a state of [number of squares left, die rolls left], which is pretty straightforward. Then it uses this result to figure out the same thing for \(c\) camels with some math. Here's how it looks:

```
def probFinishLessThanEqualDieRollsIter(curState, cached):
if curState in cached:
return cached[curState]
numSquares = curState[0]
dieRollsLeft = curState[1]
if (numSquares <= 0):
return 1.0
if (dieRollsLeft <= 0):
return 0.0
totalProb = 0.0
for step in range(MIN_CAMELSTEP, MAX_CAMELSTEP+1):
totalProb += probFinishLessThanEqualDieRollsIter((numSquares - step, dieRollsLeft - 1), cached)
totalProb *= 1.0 / (MAX_CAMELSTEP + 1 - MIN_CAMELSTEP)
cached[curState] = totalProb
return totalProb
# Calculates the probability that one camel will finish in
# less than or equal to this many die rolls.
def probFinishLessThanEqualDieRolls(numSquares, dieRolls, cached):
state = (numSquares, dieRolls)
return probFinishLessThanEqualDieRollsIter(state, cached)
def calculateRaceByDieRolls(numCamels, numSquares, returnDistribution=False):
# the camels effectively start at square -1, so they actually have to go one extra square
numSquares = numSquares + 1
# figure out the range of die rolls that are possible
minDieRolls = math.ceil(numSquares/MAX_CAMELSTEP)
maxDieRolls = math.ceil(numSquares/MIN_CAMELSTEP)
expected = 0.0
lastProb = 0.0
cached = {}
listOfProbs = []
for d in range(minDieRolls, maxDieRolls+1):
prob = probFinishLessThanEqualDieRolls(numSquares, d, cached)
probLEQThisWithAnyCamel = 1.0 - math.pow(1.0-prob, numCamels)
assert probLEQThisWithAnyCamel <= 1.0
probExactlyThisManyWithAnyCamel = probLEQThisWithAnyCamel - lastProb
lastProb = probLEQThisWithAnyCamel
expected += d * probExactlyThisManyWithAnyCamel
return expected
```

This works well. There are \(O(s^2)\) states so it takes \(O(s^2)\) space and \(O(s^2)\) time, which is pretty good for an exact solution!

Here's a summary of the performance of the different solutions - remember, \(s\) is the number of squares and \(c\) is the number of camels:

s=16,c=5 | s=16,c=100 | s=50,c=5 | |
---|---|---|---|

Approach 1 | 1.5 sec | 28.2 sec | 6.1 sec |

Approach 2 | 4.6 sec | (runs out of memory) | 598.9 secs |

Approach 3 | 0.0 sec | 0.0 sec | 0.0 sec |

Behold the power of Approach 3! I'm actually a little surprised it's so much faster than Approach 1 - I guess there really is a big constant factor hidden in that \(O()\) notation!

With s=16,c=5 it takes an average of **6.53** legs.

Here's a graph of the probability of a race with s=16,c=5 ending after the given number of legs:

And here's a graph of the expected number of legs to finish a s=16 race versus number of camels:

As I mentioned above, one of the interesting aspects of the game that we've ignored until now is stacking. When there's more than one camel on a square, they stack, and when a camel moves, it brings all the camels above it along with it. When a camel lands on a square with an existing camel, it lands on top of that camel.

The stacking rules make the game much more exciting and unpredictable, so let's look at what they do to the average length of a game!

Yeah, I have no idea how to do this other than simulation. (if anyone has any mathy ideas, let me know!) Here's what the code looks like:

```
def simulateRaceWithStacking(numCamels, numSquares):
totalSteps = 0
ITERATIONS = 20000
for i in range(ITERATIONS):
# extra slack for the last leg
boardPosition = [[] for i in range(numSquares + MAX_CAMELSTEP * numCamels)]
camelPositions = [-1] * numCamels
# first initialize, they don't move with stacking on the first turn
totalSteps += 1
for i in range(numCamels):
camelPositions[i] += random.randint(MIN_CAMELSTEP, MAX_CAMELSTEP)
boardPosition[camelPositions[i]].append(i)
while (max(camelPositions) < numSquares):
camelOrder = list(range(numCamels))
random.shuffle(camelOrder)
# first camel in list is on the bottom
for camelNum in camelOrder:
curPosition = camelPositions[camelNum]
newPosition = curPosition + random.randint(MIN_CAMELSTEP, MAX_CAMELSTEP)
positionInStack = boardPosition[curPosition].index(camelNum)
camelsToMove = boardPosition[curPosition][positionInStack:]
boardPosition[curPosition] = boardPosition[curPosition][:positionInStack]
assert len(camelsToMove) >= 1
for c in camelsToMove:
camelPositions[c] = newPosition
boardPosition[newPosition].append(c)
totalSteps += 1
return float(totalSteps) / ITERATIONS
```

Pretty straightforward, although we keep track of both the board state and which square each camel is in (for efficiency).

With s=16,c=5 it takes an average of **4.73** legs, which is almost 2 whole legs less than without stacking! Here's the distribution graph - notice that it's possible for the game to end in 2 legs!

And here's a graph of the expected number of legs to finish a s=16 race versus number of camels:

Now that I had the ability to simulate a leg, I thought I'd set up some common scenarios and figure out the probabilities for the first and second place camels.

The most likely winner of the leg is **bolded**.

Scenario: (this means that camel 1 is on top of camel 0)

10 |

Camel 0 | Camel 1 | |
---|---|---|

First place | 33% | 67% |

Second place | 67% | 33% |

Scenario: (this means that camel 1 is one square ahead of camel 0)

0 | 1 |

Camel 0 | Camel 1 | |
---|---|---|

First place | 39% | 61% |

Second place | 61% | 39% |

Scenario: (this means that camel 1 is on top of camel 0, and camel 2 is one square ahead)

10 | 2 |

Camel 0 | Camel 1 | Camel 2 | |
---|---|---|---|

First place | 21% | 49% | 30% |

Second place | 32% | 25% | 43% |

Scenario:

1 0 | 2 |

Camel 0 | Camel 1 | Camel 2 | |
---|---|---|---|

First place | 13% | 39% | 48% |

Second place | 30% | 30% | 40% |

Scenario:

21 0 | 3 |

Camel 0 | Camel 1 | Camel 2 | Camel 3 | |
---|---|---|---|---|

First place | 13% | 28% | 43% | 16% |

Second place | 18% | 30% | 24% | 28% |

Scenario:

21 0 | 3 |

Camel 0 | Camel 1 | Camel 2 | Camel 3 | |
---|---|---|---|---|

First place | 10% | 24% | 38% | 28% |

Second place | 15% | 26% | 24% | 35% |

Scenario:

10 | 2 | 3 |

Camel 0 | Camel 1 | Camel 2 | Camel 3 | |
---|---|---|---|---|

First place | 13% | 37% | 18% | 32% |

Second place | 19% | 22% | 27% | 32% |

Scenario:

1 0 | 32 | 4 |

Camel 0 | Camel 1 | Camel 2 | Camel 3 | Camel 4 | |
---|---|---|---|---|---|

First place | 12% | 29% | 13% | 30% | 16% |

Second place | 13% | 19% | 19% | 24% | 25% |

Scenario:

21 0 | 3 | 4 |

Camel 0 | Camel 1 | Camel 2 | Camel 3 | Camel 4 | |
---|---|---|---|---|---|

First place | 12% | 24% | 35% | 11% | 18% |

Second place | 12% | 23% | 21% | 18% | 26% |

Interesting stuff! As I suspected, being on top of a stack is very beneficial for a camel. Even being the second camel in a three-high stack is pretty good! But being at the bottom of a stack hurts a lot.

Here's the Python 3.x file I used to do all these calculations. Just uncomment what you want in the main method:

Fancy math equations by MathJax. Fancy graphs by Flot. Camel Up (or Camel Cup?) designed by Steffen Bogen.