I wrote something to enumerate the relevant states and then print out the probabilities it found that way. Somehow a simulation felt like a cop-out to me :)
I believe this game is for more than one player? And it ends when ANY player gets 10 cherries, right? The code and results below assume that.
For the two-player case, I got a mean end turn of around 9.56. Since I was counting turns as every player spinning once, that's two spins per turn, so let's say that in the mean case, it takes between 19 and 20 spins for the game to end when two people are playing. It looks like the median is lower: about 15 spins, so half of the two-player games should end on or before the 15th spin.
The original question makes it sound like the one-player case is what was being considered so here is the info for that one.
For one player: the mean game length is 15.8 spins and the median game length is between 11 and 12 turns (half end on or before 11, half on or after 12 spins).
Here is the code to generate the data used above. Warning: It gets really slow as you add players (exponential runtime in number of players, but only quadratic in terms of the number of turns). You can change the values of turn_cap and num_players at the top of the file to match what you want to find out. It only enumerates up to turn_cap, because you probably don't care beyond that. Games that end later ARE still taken into account, it just doesn't spit out data for them.
(Python 2.5):
from copy import deepcopy
from sys import stdout
num_players = 2
turn_cap = 50 # I assume everybody is sick of it by this point
print_merges = False
print_num_states = False
print_turn_progress = True
ignore_score_of_finished_games = True
def flatten(list_of_lists):
r"""helper for flattening a list of lists into a single list"""
return [item for sub_list in list_of_lists for item in sub_list]
def count(iterable,p=bool):
r"""return for how many items in iterable the predicate p evaluates to true"""
n = 0
for item in iterable:
if p(item):
n += 1
return n
def lists_the_same(l0,l1):
return len(l0)==len(l1) and \
all(l0[i]==l1[i] for i in range(len(l0)))
def split_list(items,p):
r"""split the list "items" into two lists based on a predicate "p"
returns a tuple. (items where the predicate is true, items where the predicate is false) """
good, bad = [], []
for i in items:
if p(i):
good.append(i)
else:
bad.append(i)
return good, bad
class World:
def __init__(self, num_players=2, probability=1.0):
self.player_scores = [0 for x in range(num_players)]
self.probability = probability
self.turn_number = 0
self.ended_on_turn = None
self.num_players = num_players
def check_win(self):
if any(( (score>=10) for score in self.player_scores)):
self.ended_on_turn = self.turn_number
def gain_cherries(self, player_index, num_cherries):
self.player_scores[player_index] += num_cherries
self.check_win()
def lose_cherries(self, player_index, num_cherries):
self.player_scores[player_index] = max(0, self.player_scores[player_index] - num_cherries)
def lose_all_cherries(self, player_index):
self.player_scores[player_index] = 0
def run_turn(self):
r"""if not ended, it splits the world into 7 new worlds based on each player's spin"""
if None==self.ended_on_turn:
self.turn_number += 1
worlds = [self]
for i in range(self.num_players):
worlds = flatten([w.run_player_turn(i) for w in worlds])
return worlds
else:
return [self]
def run_player_turn(self, player_index):
new_worlds = [deepcopy(self) for i in range(7)]
for w in new_worlds:
w.probability = self.probability / 7.0
new_worlds[0].gain_cherries(player_index,1)
new_worlds[1].gain_cherries(player_index,2)
new_worlds[2].gain_cherries(player_index,3)
new_worlds[3].gain_cherries(player_index,4)
new_worlds[4].lose_cherries(player_index,2)
new_worlds[5].lose_cherries(player_index,2)
new_worlds[6].lose_all_cherries(player_index)
return new_worlds
def mergable(self, other):
if world_ended(self) and ignore_score_of_finished_games:
return ( (self.ended_on_turn == other.ended_on_turn) and
(self.num_players == other.num_players) )
else:
return ( lists_the_same(self.player_scores, other.player_scores) and
(self.turn_number == other.turn_number) and
(self.ended_on_turn == other.ended_on_turn) and
(self.num_players == other.num_players) )
def merge(self, other):
w = deepcopy(self)
w.probability += other.probability
return w
def __str__(self):
return ( str(self.player_scores) + ", " +
"p:" + str(self.probability) + ", " +
"ended on:" + str(self.ended_on_turn) + ", " )
def collapse_duplicate_worlds(world_list):
r"""look through the list of worlds, find ones that can be merged
and merge them, modifying the list in place"""
i0 = 0
while i0 < len(world_list):
i1 = len(world_list) - 1
while i1 > i0+1:
w0 = world_list[i0]
w1 = world_list[i1]
if w0.mergable(w1):
world_list[i0] = w0.merge(w1)
if print_merges:
print "merging",w0
print "with",w1
del world_list[i1]
i1 -=1
i0 += 1
def dump_stats(worlds):
print 'turn\tON\tBY'
p_on = [0.0 for i in range(turn_cap+1)]
p_by = [0.0 for i in range(turn_cap+1)]
for w in worlds:
if world_ended(w):
turn = w.ended_on_turn
p_on[turn] += w.probability
for i in range(turn, turn_cap+1):
p_by[i] += w.probability
for i in range(1,turn_cap+1):
print str(i)+'\t'+str(p_on[i])+'\t'+str(p_by[i])
def world_ended(w):
return None!=w.ended_on_turn
def main():
worlds = [World(num_players)]
finished_worlds = []
for i in range(turn_cap):
if print_turn_progress:
print "turn#:",i+1
worlds = flatten([w.run_turn() for w in worlds])
collapse_duplicate_worlds(worlds)
done, worlds = split_list(worlds,world_ended)
finished_worlds.extend(done)
if print_num_states:
print len(worlds),"unfinished world states"
print len(finished_worlds),"finished world states"
finished_worlds.extend(worlds)
dump_stats(finished_worlds)
if "__main__"==__name__:
main()
