My kids enjoy playing a co-operative game called Erster Obstergarten (‘My first orchard’).
The game is very simple, there are four trees, each with four pieces of fruit (red apples, green apples, blue plums and yellow pears). A crow is at the start of a path that is five steps long. Players take turns rolling a 6-sided die, four of the sides are coloured, corresponding to one of the trees, the fifth side is a basket, which allows the player to pick any coloured fruit they want. The sixth side is the crow, and if that turns up the crow moves one step along the path. So there’s a 1 in 6 chance the crow moves forward each roll. Here’s a video (in German)showing the rules.
The players win if all the fruit are picked before the crow reaches the end of the path. My question is what is the probability that the players win?
Essentially it comes down to whether 5 sixes are rolled before 4 ones, twos, threes and fours but I can’t figure out how the basket changes the odds. My observation is that the players tend to win more often that not, maybe two-thirds to three-quarters of the time? But I can’t quite figure out the actual probabilities and it bugs me.
It isn’t all that hard…but it involves multiplying out a whole ton-load of possibilities. It’s something you could give a computer to solve by brute force.
Also, you have to sum up some infinite series. It’s possible you could roll “red apples” over and over and over, to the exclusion of anything else. Obviously, this isn’t likely, but for a full analysis of the game, that has to be calculated.
And, yeah, the basket complicates things too, as a full analysis has to take into account all four of the possible decisions you might make when it comes up.
I’m not sure this is something you can fully analyze with pencil and paper…at least not before a month or two of figurin’.
Looking at the video (crow starts and finishes OFF his track), is it possible six 6’s are needed for failure?
Even without the basket complication, writing down and solving the mathematical expressions would be extremely tedious I think. But solving via Monte Carlo simulation is trivial. If I’ve made no mistake, you have 63.1% chance of success if the rule is that the 5th crow move kills you, 76.8% if it’s the 6th crow move.
We may well have the rules wrong, they are in German and we lost them anyway. So the crow may have to move six spaces to win.
I’m relieved to see there wasn’t a simple arithmetic method to work the probabilities out. Thanks for doing the simulations. What did you use to run them?
I ran 20,000,000 simulations for each value of Crow’s path-length from 1 to 6, and noted that the derived precision was better than the three sig-figs I reported here. The batch of 20 million simulations for length-6 took about 11 seconds on my slow laptop.
I did some simulations as well though not 20 million. For 5 steps required by crow to lose, I found that winning games lasted on average 34 die rolls, losing games lasted on average 19 rolls and about 5% of the time, the kids got tired of playing and quit the game after 100 rolls without winning or losing.
How did you deal with the basket rolls? Did you just take one off the tree with the most fruit left? I wonder if my kids tendency to take one of their favourite colour, even if there are more fruit on different trees, has any effect on the outcome.
The 5% extra long games seems off. I’ve never seen the kids give up in disgust and they’re not especially patient children. The variance in length between winning and losing games surprises me a bit as well.
The game must end after a maximum of 20 eventful rolls (rolls where a fruit is picked or the crow advances). Until one tree is stripped bare all rolls have to be eventful. So at least the first 4 rolls will be eventful leaving a maximum of 16 eventful rolls to reach a conclusion.
Even if only one tree is left the probability for a roll being non-eventful is only 0.5 (1 in 6 crow rolls 1 in 6 baskets 1 in 6 the right colour leaving 1 in 2 non eventful). The probability of getting 80 non eventful rolls before 16 eventful ones has to be a lot less than 1 in 20.
I suspect oldguy’s code is counting rolls of 7 to 10 as valid but non eventful roles.
I wrote up a little sim as well and my results match yours: 63.135% if the crow has 5 moves, and 76.852% for 6 moves. I assumed that the kids would pick the tree with the most fruit left.
This is why I tend to write stuff in JavaScript and then post the code (in a spoiler box) so people can run it themselves and check. Anyone can press Ctrl-Shift-I and paste into their browser’s console.
And it’s C-like. It’s actually harder to go the other direction, from JavaScript to C, since C has such lousy String handling.
I don’t code so lets see if I understand how you did this.
You set up 5 sets of tokens, with the last set being the crow.
In line 13 you check whether any tokens are left in any of sets 0-3 (the fruit) and a token is left in set 4.
If there isn’t that game is over and you check whether there are any tokens left in set 4, if there are the crow is still on the path and the players won that round. If there aren’t the crow won that round.
If there are tokens left line 15 is the roll and lines 16-29 deal with basket rolls, and set the roll to the set out of sets 0-3 with the highest number of tokens left (how does it deal with situations where there are more than 1 set with the same highest value)?
Lines 33 to 35 decrease the tokens left in the set that was rolled by one? Is that what line 35 does?
Then you go back to line 13, check the sets and continue.
Line 42 is a mystery to me.
Line 44 sets the random number generator to some sort of time value.
Lines 46 to 50 keep track of how many games have been played, up to the limit set in line 47.
Line 42 is just standard C/C++ boilerplate. It defines the “entry point” of the program, which is always called “main” and has some particular parameters. I don’t need the parameters but C++ requires that I specify them anyway. I’ve probably typed that line a thousand times in my life.
The rest of it you’ve got. For basket rolls, if more than one tree have the same number, I end up picking the last one. It doesn’t matter which one it is as long as it’s the largest. I could have picked another algorithm, like picking a random tree, but that would affect the results.
As you note, line 44 “seeds” the random number generator to the time. It’s just a way of ensuring that I get different random numbers on each run. As you know, computers are deterministic, so I need to use some sort of outside non-deterministic influence to get different numbers each time.
It kind of helped knowing what you were simulating! I doubt I could understand much of it at all if I didn’t.
I can see how the basket roll bit works now, you set max-value at set 0’s value then step through each set up to 3, changing the max value if a set has a higher value than the current one.
But line 22 makes me think you take the first of multiple max values. If set 1 has 3 left, and set 2 also has 3 left (and sets 0 and 3 have less) line 22 won’t pick set 2 as it’s not greater than set 1. Wouldn’t you need it to be “if current set is greater than or equal to the running max value then make the current set the max value” to pick the last of multiple max values? Not that it should make any difference to the outcome, as you say.
Anyway, thanks again for such a comprehensive answer.
You state what happens when the player rolls a basket or the crow, but forgot to mention what happens when one of the colors (colours?) comes up. From the other comments, it appears that everyone assumes that when a player rolls, for example, red, they pick one of the red fruits, but that is not outlined in the OP.
I didn’t watch the video, because I know very little German.