bataille — Durée d’une partie de bataille

En ce moment, ma fille aime jouer à Bata-waf. C’est long et répétitif. Pour combler les temps morts pendant lesquels elle joue, compare, ramasse, ou mélange les cartes, je me suis demandé quel était la durée moyenne d’une partie. Le résultat est là.

Ce programme simule des parties de bataille (le jeu de carte) en mesurant la durée (en nombre de tours) de chaque partie. Il affiche le résultat sous la forme d’un tableau au format CSV (par exemple bataille/bataille-4-13-1000000.csv, où chaque ligne est de la forme durée, effectif), ou sous la forme d’un graphique, ou il calcule des statistiques sur les durées des parties.

Règles

Voici les règles utilisées dans cette simulation.

  • Les cartes (4 couleurs de 13 cartes) sont mélangées, et réparties équitablement entre les deux joueuses.
  • Chaque tour se déroule de la manière suivante.
    1. À chaque tour, chacune des joueuses pioche la carte située sur le dessus de son paquet.
    2. Elles comparent leur carte.
      • Si les cartes sont de valeur différente, la joueuse ayant la carte la plus grande remporte le tour.
      • Si les cartes sont de même valeur, il y a une bataille : les joueuses posent chacun sur la table, face cachée, une nouvelle carte, et piochent encore une carte dont ils comparent la valeur en revenant à l’étape 2 (il peut y avoir à nouveau une bataille).
    3. Quand les batailles sont résoluées, la joueuse remportant le tour ramasse les cartes des deux joueuses, et les place dans un ordre aléatoire en bas de son tas de carte.
    4. Retour à l’étape 1.
  • La partie se termine lorsqu’à n’importe quelle phase du jeu, une joueuse doit piocher, mais n’a plus de cartes.

Remarquons un cas particulier : si les deux joueuses ont le même nombre de carte, et enchaînent bataille après bataille, il peut arriver un cas où les deux joueuses, en même temps, sont à cours de cartes à piocher. Dans ce cas là, la partie s’arrête et il y a match nul (même si cela est sans importance pour cette simulation, où seul le nombre de tours compte).

État de l’art

En 1995, Jean-Paul Delahay et Philippe Mathieu ont publié une analyse de la partie de bataille [Delahay1995]. Leurs règles diffèrent des miennes de deux manières :

  • en cas de bataille, ils ne placent pas de cartes face cachées sur la carte précédente ;
  • en fin de plis, les cartes sont remises sous le tas de la joueuse gagnante dans un ordre bien précis (alors que dans ma version, l’ordre est aléatoire).

Ils s’intéressent surtout aux parties nulles et infinies, cas que j’ignore ici :

  • Je ne m’intéresse pas aux parties nulles : si une partie est nulle, elle est terminée, et c’est tout ce qui m’importe.
  • Ma règle mettant en jeu le hasard, les parties infinies sont impossibles.

Selon leurs calculs (ou simulations), les parties nulles ou infinies sont très rares : environ 2% de chaque pour 3 cartes de 4 couleurs différentes, ou 0,18% de parties nulles et 0,027% de parties infinies pour un jeu de 4 cartes de 4 couleurs. Nous devrions donc trouver des résultats similaires, même si j’ignore ces cas-là.

Voir dans l’analyse une comparaison de nos résultats.

Analyse des résultats

Indicateurs

Voici les indicateurs pour les jeux les plus courants. Toutes les configurations ont été testées, pour un nombre de couleurs inférieur à 10, et un nombre de cartes par couleur inférieur à 10 : voir les données et graphiques, les statistiques.

Jeu de 32 cartes

Sur un million de parties (avec un jeu de 8 cartes de 4 couleur) :

(png, hires.png, pdf)

../_images/bataille-1.png
  • Plus courte partie : 3 plis ; plus longue partie : 1625 plis.
  • Moyenne : 126.5, Médiane : 96.0, Mode : 44.
  • Intervalle de confiance : [20 ; 404].
  • Données brutes.

Interprétation : Une partie dure en moyenne 126,5 plis ; la moitié des parties dure 96 plis ou moins, la moitié dure 96 plis ou plus ; la durée la plus fréquente est 44 plis. Dans 95% des cas, la durée de la partie est comprise entre 20 et 404 plis.

Jeu de 52 cartes

Sur un million de parties (avec un jeu de 13 cartes de 4 couleur) :

(png, hires.png, pdf)

../_images/bataille-2.png
  • Plus courte partie : 15 plis ; plus longue partie : 6680 plis.
  • Moyenne : 441.4, Médiane : 334.0, Mode : 140.
  • Intervalle de confiance : [70 ; 1414].
  • Données brutes.

Jeu de Bata-waf

Sur un million de parties (avec un jeu de 6 cartes de 6 couleur) :

(png, hires.png, pdf)

../_images/bataille-3.png
  • Plus courte partie : 2 ; plus longue partie : 1260.
  • Moyenne : 118.9, Médiane : 90.0, Mode : 40.
  • Intervalle de confiance : [20 ; 374].
  • Données brutes.

Parité

Une chose qui m’a surpris est que selon mes simulations, la probabilité d’obtenir une durée de partie (en nombre de plis) paire ou impaire n’est absolument pas la même. Dans le graphique suivant, la courbe bleue correspond aux durées de parties paires, alors que la orange aux parties impaires (avec un jeu de 52 cartes).

(png, hires.png, pdf)

../_images/bataille-4.png

Je ne comprends ni pourquoi, pour un jeu de 52 cartes, les deux parités ne sont pas équiprobables, ni pourquoi cela dépend du nombre de couleurs et de cartes.

J’ai calculé la parité la plus courante en fonction du nombre de cartes et de couleurs. En ignorant les parties avec peu de cartes ou de couleurs, la règle semble être :

  • Si le nombre de couleurs et le nombre de valeurs sont tous les deux pairs, les parties de durée paire sont les plus probables.
  • Si le nombre de couleurs ou le nombre de valeurs est un multiple de 4, les parties de durée paire sont les plus probables.
  • Si le nombre de couleurs et le nombre de valeurs sont tous les deux impairs, les parties de durée paire et impaire sont à peu près équiprobables.
  • Sinon, si le nombre de couleurs est pair, et le nombre de valeurs est impair, ou l’inverse, les parties de durée paire sont les plus probables.

Je ne sais absolument pas quoi faire de ces affirmations…

Comparaison

Comme dit plus haut, dans leur article, Delahay te Mathieu n’utilisent pas exactement les mêmes règles que moi. Pour voir la différence, j’ai simulé 1000000 de parties avec mes règles, et avec celles de Delahay et Mathieu. Voici les statistiques obtenues.

  Moi Delahay & Mathieu
Plus courte partie 15 23
Plus longue partie 6680 6955
Moyenne 441,4 582,3
Médiane 334 438
Mode 140 197
Intervalle de confiance [70 ; 1414] [92 ; 1872]
Données brutes Télécharger Télécharger

Remarquons également que ces statistiques diffèrent grandement de celles annoncées dans leur article : ils obtiennent une durée moyenne de 287 plis (la plus grande partie trouvée ayant 4571 plis), quand je trouve en moyenne 582 plis (la plus grande partie trouvée ayant 6955).

Plusieurs hypothèses peuvent expliquer cela :

  • la description de des règles utilisées comporte une ambigüité : l’ordre dans lequel sont ramassées les cartes en cas de bataille : peut-être que mon interprétation n’est pas la bonne ;
  • ils ont fait une erreur dans leurs simulations ;
  • j’ai fait une erreur dans ma simulation.

À ma connaissance, ils n’ont pas publié le programme utilisé pour les simulations. Malhreusement, je serais tenté de dire que l’erreur vient de mon côté.

Usage

Calcule la durée de parties de bataille, et manipule les résultats (affichage au format CSV, calcul de statistiques, tracé de graphiques…).

Par défaut, simule une seule partie et affiche sa durée (en nombre de plis).

usage: bataille [-h] [-V] [-c COULEURS] [-v VALEURS]
                {brut,lscache,plot,stat,multistat} ...

Named Arguments

-V, --version show program’s version number and exit
-c, --couleurs

Nombre de couleurs du jeu de cartes.

Default: 4

-v, --valeurs

Nombre de cartes dans chaque couleurs.

Default: 13

Sub-commands:

brut

Calcule les durées de plusieurs parties, et affiche les données brutes au format CSV.

bataille brut [-h]

lscache

Affiche la liste des simulations disponibles dans le cache.

bataille lscache [-h]

plot

Affiche un graphique des durées des parties.

bataille plot [-h]

stat

Calcule les statistiques des durées des parties (une seule configuration).

bataille stat [-h]

multistat

Calcule les statistiques des durées des parties (plusieurs configurations).

bataille multistat [-h]

# Simulations sauvegardées

Si ces commandes sont appelées depuis le dépôt git, le résultat de certaines simulation (longues) est recherché dans des fichiers enregistré dans le dépôt plutôt que simulées à nouveau. Cela permet de gagner du temps.

Utilisez bataille cache pour voir la liste des simulations disponibles.

# Nombre de processeurs utilisés

Les simulations sont faites en parallèle. Par défaut, autant de processus que de processeurs sont lancés. Pour modifier cette valeur, définir la variable d’environnement WORKERS au nombre de processeurs utilisés.

Notes et Références

[Delahay1995]Jean-Paul Delahay et Philippe Mathieu, La bataille, enfin analysée. http://www.lifl.fr/%7Ejdelahay/pls/1995/030.pdf