# Camel Calculator

Algorithmic probability solver for the board game Camel Up

Camel Up is a board game that boils down to pure probability but at the beginning of each leg of the race there are 29,160 possible outcomes!

Let’s ruin the fun and solve it by brute forcing the permutations.

## The Game

The premise of the game is that you and your friends are gambling on a camel race. A *leg* is over when all five colored dice (white, green, blue, orange, and yellow) have been rolled, moving the corresponding colored camels. When a camel lands on an already occupied space, it forms a “camel stack” by hopping on top of the camel(s) already on the space. A camel in a stack can get carried along if one of the camel beneath it moves. When all of the dice have been rolled, the camel on top of the leading camel stack is the winner and the camel beneath/behind it is the runner-up.

On your turn you can do one of the following moves:

- Roll a die, moving a random camel 1, 2, or 3 spaces, and take one complementary coin.
- Bet on which camel will win the leg.
- If the camel you bet on gets 3
^{rd}-5^{th}place, you lose one coin. - If the camel gets 2
^{nd}place, you gain one coin. - The first person to bet on the camel that gets 1
^{st}place gets 5 coins. The second person gets 3 coins; third gets 2 coins. So betting early when things are uncertain could pay off!

- If the camel you bet on gets 3
- Place a desert / oasis tile.
- Bet on which camel will win the entire race.

Each die is six sided but it has two sets of 1, 2, and 3 printed on it.

Check out this review of the game if you want to learn more about the board game.

## The Simple Scenarios

Imagine the following: it’s your turn, four camels are in a stack, and yellow is one space ahead.

If yellow is the only die left to be rolled we can be sure the yellow camel is going to win the leg and green will get 2^{nd} place.

However, if just orange is left, every possible outcome leaves green in 1^{st} and orange in 2^{nd}.

If both orange and blue still need to move things start to get tricky. Out of the 18 possible roll scenarios, green ends in 1^{st} place 12/18 times and white wins the remaining 6/18 scenarios. In addition, orange will get 2^{nd} place 12/18 times and blue gets silver 6/18 scenarios.

## The Intuition

The odds for the orange and blue example are fairly easy to intuit: whenever blue moves first, green wins and orange gets 2^{nd}. When orange moves first, white and blue still take it when blue’s roll is greater or equal to orange’s roll (1/3 of blue’s rolls).

- When blue rolls first (carrying white, orange, and green along), it’ll land on top of yellow (with a 1) or ahead of yellow (with a 2 or 3). Then any number orange rolls keeps green in the lead.
- When orange rolls first it’ll just carry green along with it. Then they can only win if blue’s roll is less than orange’s roll: (2, 1) or (3, 1) or (3, 2).

The precise probability might not be automatically obvious but green clearly has the best chance of winning. You might be able to work this out in your head given a simple configuration and a couple dice but the complexities increase significantly with more dice.

## The Math

How do the complexities and possibilities grow as dice are added?

As shorthand, I’ll specify color and number of a given roll like so: G1 (green rolls a 1).

With one green die, there are just three leg-ending scenarios: G1, G2, or G3.

Camels only move once per leg so the number of possibilities decrease with each roll. The first of five dice has five possibilities; the second dice to be rolled has four possibilities; the third has three, etc. Therefore, permutations of color can be express as `5*4*3*2*1`

or `N!`

.

This tree illustrates all of the 5 dice order permutations where white is rolled first.

Since the numbers that the dice roll can repeat, each roll permutation has three possibilities (Camel Up dice have 1-3 printed on them twice). For five dice that equals `3*3*3*3*3`

or `3^5`

roll permutations.

*That means we’re able to calculate the total number of leg-ending scenarios like so: 3^N * N!*

## The Complex Scenarios

With three dice (green, white, & blue) we now know that there are `3^3 * 3! = 162`

scenarios possible. I’m not going to enumerate them all here because that’d be boring and nobody wants to scroll that much but here’s just a snapshot:

- (G1, B1, W1)
- (G1, B1, W2)
- (G1, B1, W3)
- ...
- (W3, G3, B2)
- (W3, G3, B3)
- (B1, W1, G1)
- ...
- (B3, W3, G2)
- (B3, W3, G3)
- (W1, B1, G1)
- ...
- (W3, B3, G1)
- (W3, B3, G2)
- (W3, B3, G3)

Four dice contains `3^4 * 4! = 1944`

different outcomes and five dices contains `3^5 * 5! = 29,160`

.

If the game had six camels we’d have `524,880`

possible scenarios.

Here are each camel’s chances of winning 1^{st} or 2^{nd} place given all five camels still have to move and the camels are in the configuration pictured above:

### Probability with 5 dice

orange | green | blue | white | yellow | |
---|---|---|---|---|---|

1^{st} |
25.7% | 34.4% | 10.3% | 20.7% | 8.9% |

2^{nd} |
28% | 23.9% | 11.6% | 19.5% | 17% |

## The Code

I wanted to get to know some of the more modern Javascript features so I used ES2017 syntax and Babel for the app and unit tests. I experimented with different ESLint & pug-lint configurations too.

The code is on Github and live on Heroku (I spent absolutely no time making it look nice).

### problems with recursion

I used Heap’s algorithm to generate the permutations of color. My first attempt worked fine as an executable Node script but when I tried to migrate it to an Express app I ran into `RangeError: Maximum call stack size exceeded`

errors due to the recursive nature of the algorithm.

So I rewrote the algorithm without recursion and it worked fine. Phew!

```
/**
* The colorPermuter takes a list of dice colors which need to be rolled. It then generates every
* possible order in which they could be rolled using
* [Heap's algorithm]{https://en.wikipedia.org/wiki/Heap%27s_algorithm}. The number of
* permutations: `N!` where `N` is the number of dice to be rolled.
*
* @function
* @name colorPermuter
*
* @param {Array.<string>} camels - An array of unrolled camel colors
*
* @returns {Array.<string[]>} result - A 2D array containing every possible order in which the
* colored dice could be rolled.
*/
const colorPermuter = (camels) => {
const { length } = camels;
const result = [camels.slice()];
const c = new Array(length).fill(0);
let i = 1;
let swappy;
let temp;
while (i < length) {
if (c[i] < i) {
swappy = i % 2 && c[i];
temp = camels[i];
camels[i] = camels[swappy];
camels[swappy] = temp;
c[i] += 1;
i = 1;
result.push(camels.slice());
} else {
c[i] = 0;
i += 1;
}
}
return result;
};
export default colorPermuter;
```

### figuring out who ends up on top

This exercise would have been pretty dry had it not been for the camels and their zany movement.

Once every possible roll scenario has been generated, each scenario gets passed to this function which moves the camels according to the rolls.

```
import _ from 'lodash';
/**
* Given a particular set of dice rolls, where would each camel end up?
*
* @function
* @name legRunner
*
* @requires lodash
*
* @param {Array.<Object>} scenario - An array of roll objects needed to complete the leg.
* @param {Array.<Object>} camels - The original camel configuration containing each camel's
* position on the board and stack.
*
* @returns {Array.<Object>} camels - The resulting camel configuration after applying the given rolls.
*/
const legRunner = (scenario, camels) => {
while (scenario.length) {
const roll = scenario.shift();
const luckyCamel = _.cloneDeep(_.find(camels, { color: roll.color }));
const luckyStack = _.filter(camels, (camel) => {
const sameSpace = camel.space === luckyCamel.space;
const onTopOf = camel.stack >= luckyCamel.stack;
return sameSpace && onTopOf;
});
const receivingSpace = luckyCamel.space + roll.number;
const receivingStackHeight = _.filter(camels, { space: receivingSpace }).length;
_.forEach(luckyStack, (camel) => {
camel.space += roll.number;
camel.stack += receivingStackHeight - luckyCamel.stack;
});
}
return _.orderBy(camels, ['space', 'stack'], ['desc', 'desc']);
};
export default legRunner;
```

## The Future

There are several game mechanics in Camel Up that I’d love to take into account in the future.

- Deserts and oases add a fun twist to camel movement.
- It would be nice to offer move recommendations instead of just odds.
- Better UI interaction — at least a visual representation of the board!