Hier soir
, j’évoquais l’utilisation des chaînes de Markov au jeu Serpents et Échelles. Comme me le faisait remarquer Jean-Philippe, de manière assez étrange, les enfants sont toujours beaucoup plus content après avoir fait un 6 qu’après avoir fait un 1. Mais est-ce réellement la valeur optimale que le dé doit prendre ? Ça dépend bien sûr de la position. Par exemple, au premier lancer, on peut se demander ce que deviendrait le nombre de tours moyen nécessaires pour finir le jeu, conditionnellement aux 6 lancers possibles. On peut calculer, toujours conditionnellement aux 6 valeurs possibles de dés (et des positions où on va se retrouver), l’espérance du nombre de tours pour finir la partie,
esperance=function(h0){ INITIAL = as.numeric(which(M[h0+1,]>0))-1 ESPERANCE=rep(NA,length(INITIAL)) names(ESPERANCE)=INITIAL for(k in 1:length(INITIAL)){ initial=rep(0,n+1); initial[INITIAL[k]]=1 distrib=initial%*%M game=rep(NA,1000) for(h in 1:length(game)){ game[h]=distrib[n+1] distrib=distrib%*%M} ESPERANCE[k]=sum(1-game)} return(ESPERANCE)}
(à partir du code mis en ligne hier), e.g. pour le premier lancer,
> esperance(0) 1 2 3 5 6 14 32.16499 31.99947 31.82348 31.47954 31.36441 29.83020
où la valeur indiquée est la position où l’on pourrait se retrouver (la dernière correspond à un 4). On note que le meilleur premier lancer possible est celui qui nous amène sur la première échelle, i.e. la 4ème case,
Si on regarde case par case, on a les valeurs des “meilleurs” lancers de dés suivant (sans forcément l’unicité) en fonction de sa position sur le plateau
(avec en rouge les serpents et en bleu les échelles). Amusant non ?
