Ce soir, les enfants voulaient lancer une partie de bataille dix minutes avant de souper. Devant mon peu d’enthousiasme (on ne sait jamais trop quand ce genre de parties finissent), ma belle-mère a suggéré qu’au lieu de jouer à deux (comme le voulaient les deux grands), on devrait jouer à quatre, et comme ça, ça irait plus vite.
Et si ma belle-mère avait raison ? et si elle avait tort ? Car je veux bien croire que le temps moyen d’une partie (une partie se finissant quand il y a un vainqueur, c’est à dire quelqu’un qui a collecté toutes les cartes du jeu), voire le temps médian d’une partie, soit fonction du nombre de joueurs. A priori j’aurais toutefois tendance à croire qu’au contraire, ça va rallonger. En effet, intuitivement, si on joue à trois, au bout d’un moment, un joueur aura perdu toutes ses cartes, et – en moyenne – le paquet est alors partagé entre les deux joueurs qui restent. Et on revient alors à une partie avec deux joueurs. Donc plus y a de joueurs, plus ça devrait durer. Maintenant, on peut aussi noter qu’avec 30 cartes, et 10 joueurs, il est possible que le même joueur gagne 3 fois de suites (de l’ordre d’une chance sur 1000 avec un jeu simplifié, certes), au tout début, et donc en 3 coups, la partie est finie. Ce qui ne peut pas arriver avec 5 joueurs par exemple. Donc avec beaucoup de joueurs, il serait possible de finir une partie beaucoup plus vite. Damned… c’est pénible les belles-mères !
N’ayant pas le courage de faire des maths (il restait dix minutes avant le souper), je me suis contenter de faire un petit programme pour faire des simulations. Bon, j’avoue, je considère une version très simplifiée de la bataille. On a joueurs, et
cartes, avec
multiple de
. On distribue toutes les cartes, soit
cartes par joueur, au premier tour. Je vais alors supposer qu’il n’y a pas de bataille. C’est un peu nul, j’en conviens (puisque c’est le nom du jeu). Autrement dit, on tire au hasard un vainqueur parmi les joueurs. Et de manière équiprobable, c’est à dire qu’un joueur avec beaucoup de cartes n’a pas – a priori – de meilleures cartes que les autres. Le vainqueur prend alors les
cartes, et
-1 joueurs (les perdants) perdent une carte.
Une partie se simule alors de la manière suivante,
Time=function(np=2,nc=36){
t=0
N=rep(nc/np,np)
VN=N
P=1:np
while(sum(N==0)<(np-1)){
i=sample(P,1)
N=pmax(N-1,0)
N[i]=N[i]+length(P)
P=which(N!=0)
t=t+1
VN=rbind(VN,N)
}
return(list(time=t,traj=VN))
}
Par exemple, avec deux joueurs, on a l’évolution suivante du nombre de cartes par joueur (sur un jeu contenant =60 cartes),
set.seed(1)
T=Time()
barplot(t(T$traj),col=c("blue","red"),border=NA)
et avec trois joueurs (et toujours nos 60 cartes)
T=Time(np=3,nc=36)
barplot(t(T$traj),col=c("blue","red","green"),border=NA)
Ici, il semble que la partie avec trois joueurs ait duré beaucoup plus longtemps que celle avec deux. Et que lorsque le troisième joueur a perdu toutes ses cartes, les deux joueurs avaient autant de cartes l’un que l’autre (et on était alors revenu à la position initiale). Mais est-ce toujours le cas ? Faisons quelques simulations pour se faire une idée plus précise… On peut utiliser
game=function(npsim=2,ns=5000,ncsim=60){
T=rep(NA,ns)
for(i in 1:ns){T[i]=Time(np=npsim,nc=ncsim)$time}
return(T)
}
Et on peut regarder des simulations avec 2, 3, 4, 5, etc joueurs,
G1=game(np=2,nc=60) G2=game(np=3,nc=60) G3=game(np=4,nc=60) G4=game(np=5,nc=60) G5=game(np=6,nc=60) G6=game(np=10,nc=60) G7=game(np=12,nc=60) G8=game(np=15,nc=60) G9=game(np=20,nc=60) G10=game(mp=30,nc=60) G=data.frame(G1,G2,G3,G4,G5,G6,G7,G8,G9,G10) boxplot(G,names=c(2,3,4,5,6,10,12,15,20,30))
Si on regarde le dessin brut, on a
autrement dit, il semble que la distribution du temps d’une partie soit indépendante du nombre de joueurs (ici en abscisse). On peut regarder les temps moyens
> trunc(apply(G,2,mean)) G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 896 925 929 922 919 918 913 908 909 873
avec éventuellement un intervalle de confiance à 95% sur le temps moyen d’une partie, avec 60 cartes
> rbind(trunc(apply(G,2,mean)-2/sqrt(5000)*apply(G,2,sd)),
+ trunc(apply(G,2,mean)),
+ trunc(apply(G,2,mean)+2/sqrt(5000)*apply(G,2,sd)))
G1 G2 G3 G4 G5 G6 G7 G8 G9 G10
[1,] 875 904 908 901 898 897 893 887 888 852
[2,] 896 925 929 922 919 918 913 908 909 873
[3,] 917 946 950 943 940 939 934 929 930 894
ou encore les quartiles
> trunc(apply(G,2,quantile))
G1 G2 G3 G4 G5 G6 G7 G8 G9 G10
0% 46 48 50 42 38 33 36 4 3 2
25% 379 403 410 409 407 402 393 391 388 358
50% 681 706 720 710 701 701 706 692 709 660
75% 1192 1233 1249 1209 1203 1221 1229 1194 1195 1178
100% 6746 6927 5656 8135 7392 6377 7926 8542 7528 7062
Histoire de se conforter, on notera que les dernières valeurs minimales ont du sens, compte tenu de notre remarque initiale. Visuellement on obtient
avec en rouge la valeur moyenne (et l’intervalle de confiance autour), toujours en fonction du nombre de joueurs (et toujours le même nombre de cartes). Avec 5 fois plus de simulations, on a la même histoire, avec le temps moyen suivant
> rbind(trunc(apply(G,2,mean)-2/sqrt(25000)*apply(G,2,sd)),
+ trunc(apply(G,2,mean)),
+ trunc(apply(G,2,mean)+2/sqrt(25000)*apply(G,2,sd)))
G1 G2 G3 G4 G5 G6 G7 G8 G9 G10
[1,] 893 909 917 912 911 912 902 899 895 860
[2,] 902 919 926 922 920 922 911 908 904 869
[3,] 912 928 936 931 930 931 920 918 913 878
Personnellement, malgré la très légère concavité que l’on peut observer sur le graphique ci-dessus (à peine significatif) j’ai l’impression que l’on a toujours la même distribution, quel que soit le nombre de joueurs. Étonnant, non ? J’attends que quelqu’un m’explique que ce résultat est intuitif, et pourrait se trouver simplement, en faisant des maths (je ne dis pas que le temps moyen est le même, je dis que la distribution de la durée d’une partie est indépendante du nombre de joueurs, ce qui me semble plus compliqué à établir). En attendant, je vais essayer d’améliorer mon modèle pour modéliser les batailles. Ou expliquer à mes enfants que leur père est un nerd, car il préfère taper des codes sur son ordinateur plutôt que de jouer à la bataille… Honte à moi !
(histoire de formaliser un peu). Le but du jeu est dedeviner sur quelle face la pièce va tomber: si on devine bien, on gagne, sinon on perd. Et le but de mon billet est de comprendre quelle est la stratégie qu’il convient de mettre en œuvrer si on connaît, ou si on estime 
.
, on prédit pile, sinon on prédit face (à chaque lancer si on fait plusieurs lancers consécutifs).
la variable correspondant à la valeur prise au lancer, disons 1 si on tomber sur pile et 0 sur face. Et notons 
la valeur prédite. On gagne si 
, et la probabilité de gagner est alors
. Considérons le polynôme 
, dont les racines sont 
et 
, i.e sur 
,
lancers, on a un échantillon 
et on estime la probabilité de tomber sur pile par
(qui tire une loi uniforme sur le segment unité), pour la prochaine valeur, on prédit
, et la probabilité de gagner est alors
(comme auparavant). En revanche, dans le second cas, le calcul de la probabilité de gagner est
… En fait, généralement, les calculs de probabilités sont assez troublants et paradoxaux. On va considérer ici des gens devant prendre des situations en présence d’incertitude, et plus particulièrement deux situations: la difficulté de prendre en compte de l’information (et donc de calculer des probabilités conditionnelles) et le cas où les gens doivent agir en prenant des décisions de manière aléatoire (et donc fixent en même les probabilités).
Avant hier, j’avais mis en ligne (
Mais il existe des cas encore plus vicieux, où les probabilités ne peuvent pas être considérées comme exogènes, ou objectives, car elles sont déterminées par les joueurs. Considérons une jeu simple, un peu dans l’esprit du pierre-feuille-ciseau (que j’avais déjà évoqué 
, et 2 avec probabilité 
(avec 
). Ma fille sort 1 doigt avec probabilité 
, et 2 avec probabilité
(avec 
). La valeur espérée du jeu (de mon point de vue) est
qui va minimiser cette valeur, alors que moi, je cherche 
qui la maximise. Bref, un problème classique de problème minmax de théorie des jeu. L’équilibre (s’il existe) sera 
où 
et 
solution de
. Autrement dit, si 
, ma fille a toujours intérêt à sortir un doigt (car 
) et ce n’est pas un équilibre… pareillement, si 
, ma fille a toujours intérêt à sortir deux doigts, et là encore ce n’est pas un équilibre. Autrement dit, le seul équilibre possible est obtenu lorsque 
, i.e l’équilibre correspond à 
. De manière dual, pour ma part, je cherchais à trouver
. Autrement dit, afin que le jeu soit à l’équilibre, il faut que nous jouions la stratégie suivante: sortir un doigt avec probabilité 
(et pas 
) et deux avec probabilité 
. Et la valeur espérée du jeu est alors
Ce week end, en sortant de l’exposition sur les mammouths à Rennes avec mon fils, on est passé à la fête de la science, voir si on pouvait faire quelques casses têtes à un stand tenu par des collègues de Beaulieu. Et là, un petit problème de théorie des jeux m’a été soumis, et je ne pouvais pas passer à côté de l’occasion (surtout quand on connaît la morale) d’en parler ici.
