J'ai écrit quelque chose pour énumérer les états pertinents et ensuite imprimer les probabilités trouvées de cette manière. De toute façon, une simulation semblait être une solution de facilité pour moi :)
Je crois que ce jeu est pour plus d'un joueur? Et cela se termine quand N'IMPORTE QUEL joueur obtient 10 cerises, n'est-ce pas? Le code et les résultats ci-dessous supposent cela.
![Probabilité de la fin de Hi-Ho Cherry-O (2 joueurs)]()
Pour le cas à deux joueurs, j'ai obtenu un nombre de tours de fin moyen d'environ 9,56. Comme je comptais les tours à chaque fois que chaque joueur tournait une fois, cela fait deux tours par tour, donc disons que dans le cas moyen, il faut entre 19 et 20 tours pour que le jeu se termine lorsque deux personnes jouent. Il semble que la médiane soit plus basse: environ 15 tours, donc la moitié des jeux à deux joueurs devraient se terminer au 15ème tour ou avant.
La question originale donne l'impression que le cas à un joueur était envisagé, donc voici les informations pour ce cas.
![Probabilité de la fin de Hi-Ho Cherry-O (1 joueur)]()
Pour un joueur: la longueur moyenne du jeu est de 15,8 tours et la longueur médiane du jeu est entre 11 et 12 tours (la moitié se termine avant le 11ème, la moitié après le 12ème tour).
Voici le code pour générer les données utilisées ci-dessus. Attention : cela devient vraiment lent lorsque vous ajoutez des joueurs (une durée d'exécution exponentielle en fonction du nombre de joueurs, mais seulement quadratique en termes de nombre de tours). Vous pouvez modifier les valeurs de turn_cap et num_players en haut du fichier pour ce que vous voulez découvrir. Il n'énumère que jusqu'à turn_cap, car vous ne vous souciez probablement pas au-delà. Les jeux qui se terminent plus tard sont toujours pris en compte, il n'affiche simplement pas de données pour eux.
(Python 2.5):
from copy import deepcopy
from sys import stdout
num_players = 2
turn_cap = 50 # Je suppose que tout le monde en a marre à ce stade
print_merges = False
print_num_states = False
print_turn_progress = True
ignore_score_of_finished_games = True
def flatten(list_of_lists):
r"""aide pour aplatir une liste de listes en une seule liste"""
return [item for sub_list in list_of_lists for item in sub_list]
def count(iterable,p=bool):
r"""retourne pour combien d'éléments dans l'itérable le prédicat p évalue à vrai"""
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"""divise la liste "items" en deux listes en fonction d'un prédicat "p"
retourne un tuple. (éléments pour lesquels le prédicat est vrai, éléments pour lesquels le prédicat est faux) """
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"""si ce n'est pas terminé, cela divise le monde en 7 nouveaux mondes basés sur le lancer de chaque joueur"""
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) + ", " +
"terminé le tour:" + str(self.ended_on_turn) + ", " )
def collapse_duplicate_worlds(world_list):
r"""parcourt la liste des mondes, trouve ceux qui peuvent être fusionnés
et les fusionne, modifiant la liste sur 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 "fusion de",w0
print "avec",w1
del world_list[i1]
i1 -=1
i0 += 1
def dump_stats(worlds):
print 'tour\tFINI\tPAR'
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 "tour#:",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),"états de monde inachevés"
print len(finished_worlds),"états de monde terminés"
finished_worlds.extend(worlds)
dump_stats(finished_worlds)
if "__main__"==__name__:
main()
