(Ce texte est connexe à deux de mes productions de magistère, voir le bas de cette page.)
Nous parlons ici du jeu de carte de la bataille (« war » en anglais), plus précisément, de la bataille à une couleur. Initialement, le paquet est un mélange de l’ensemble {1,…,n} (une permutation) et chaque joueur (J1 et J2) en reçoit la moitié. Chaque joueur joue la première carte de son paquet ; le joueur qui possède la carte la plus grande remporte les deux cartes et les place sous son paquet, selon la règle suivante : d’abord la carte du J1 puis la carte du J2. Donnons deux exemples :
avec les tas (2,1),(4,3) (haut des tas à gauche, J1 à gauche) cela donne (1),(3,2,4) puis (),(2,4,1,3) ;
avec les tas (3,1),(2,4) cela donne (1,3,2),(4) puis (3,2),(1,4) puis (2,3,1),(4) puis (3,1),(2,4) donc la partie est infinie (à noter que pour d’autres règles de remise de cartes, les parties infinies n’arrivent pas forcément aux mêmes valeurs de n).
Plusieurs questions se posent alors.
Existe-t-il des parties infinies ? Si oui, en quelle proportion ?
Quelle est la longueur maximale d’une partie finie ?
Les gains sont-ils répartis équitablement entre les deux joueurs ?
La situation peut facilement se modéliser grâce par exemple à ce code, publié par Philippe Mathieu et Jean-Paul Delahaye (Université de Lille) à l’occasion d’articles pour la revue Pour la Science. On trouve alors les résultats suivants (pour chaque valeur de n, on teste les n! parties possibles ; seule les valeurs paires de n sont testées). Les données sont obtenues en jouant toutes les parties possibles.
Proportion de parties infinies et répartition des gains (en %)
| n | proportion de parties infinies | gains J1 | gains J2 |
|---|---|---|---|
| 2 | 0 | 50 | 50 |
| 4 | 33 | 33 | 33 |
| 6 | 53 | 23.33 | 23.75 |
| 8 | 67 | 16.94 | 17.10 |
| 10 | 75 | 12.28 | 12.48 |
Une différence frappante avec la règle de remise selon la carte la plus haute est qu’ici il y a beaucoup de parties infinies (contre une faible proportion pour la règle du max). Pour ces valeurs de n, on voit que la proportion de parties infinies augmente (jusqu’où ?), et que le J2 gagne plus de parties que J1 (la différence tend-elle vers 0 ?).
Longueur maximale des parties finies
| n | longueur max | nombre de parties de longueur max | dont victoire J2 |
|---|---|---|---|
| 2 | 1 | 2 | 1 |
| 4 | 4 | 2 | 1 |
| 6 | 9 | 5 | 2 |
| 8 | 20 | 9 | 0 |
| 10 | 29 | 48 | 0 |
| 12 | 44 | (1090) | (0) |
Les valeurs entre parenthèses n’ont été obtenues que pour un sous-ensemble des n! parties possibles (cf. ci-après). À noter que la suite obtenue pour les longueurs maximales correspond à la suite A073360 de l’OEIS… mais nous y reviendrons plus tard.
On peut remarquer qu’à partir de n=10, les parties finies les plus longues voient systématiquement la victoire du J1, ce qui est peut-être étonnant au vu du tableau ci-avant où l’on voyait que le J2 gagne plus de parties que le J1. Voici un exemple de tas initiaux qui donne une partie infinie : (2, 9, 6, 5, 7, 12),(1, 10, 3, 4, 8, 11) Comme beaucoup d’autres (aussi pour des n plus petits), le n est à la fin du tas du J1 et le n-1 à la fin du tas du J2 (plus précisément, n ou n-1 est à la fin du J1 et n-1 ou n-2 est à la fin du J2, la dernière du J2 étant le maximum de sa main). La valeur pour le tableau précédent du nombre de parties réalisant le maximum a été trouvé en recherchant uniquement des parties de ce type. En recherchant les parties finies de cette forme pour n = 14, on trouve un maximum de 59… contre le 69 du terme suivant de la suite de l’OEIS mentionné plus haut.
Autres questions
On pourrait aussi regarder les parties les plus longues où J2 gagne (toujours avec la règle de remise « cartes de J1 en premier »).
Finalement, on peut également regarder ce qui se passe pour la règle « min », où l’on remet d’abord la carte la plus basse. La situation semble similaire au cas de la règle « max », en particulier en ce qui concerne la proportion de parties infinies.