tout le monde sait ce que c'est la bataille, je vais rien apprendre à personne.
l'autre jour j'étais tombé sur un article de 1995, qui s'intéresse à la durée moyenne d'une partie ainsi qu'à la probabilité d'avoir une partie infinie. d'autres articles ou preprints (2010, 2011) ont également démontré quelques résultats intéressants, d'autant plus qu'ils proposaient chacun leur variante du jeu, des choix qui avaient évidemment leur répercussion sur les propriétés à long terme.
parmi les "variantes" susmentionnés, celles que j'ai implémentées sont de deux sortes :
- dans quel ordre on récupère les cartes à la fin d'un pli
- est-ce que lors d'une bataille (=une égalité), on place d'abord une carte face cachée avant la prochaine carte
avec tout cela, cette petite page permet deux choses : faire une partie de bataille, ou en simuler un tas d'un coup pour calculer quelques statistiques sur la durée des parties. bon jeu !
1 7
Nombre de cartes par couleur :
1 13
carte intermédiaire lors d'une bataille
_________________
Nombre de parties à simuler :
1000 100000
Observations
Résultats connus
les articles mentionnés plus haut ont démontré mathématiquement certains résultats concernant l'existence des parties infinies. en notant m le nombre de couleurs et n le nombre de valeurs :
- pour m=4 (carte la plus haute d'abord & sans carte intermédiaire), 1995 montre qu'il n'existe aucune partie infinie pour n=1 ou 2, mais qu'il en existe pour n=3,4,6,7,8 et tout multiple de 4.
- pour m=1 (carte la plus haute d'abord), 2010 montre qu'il existe une partie infinie pour tout les n qui ne sont pas de forme 2k ou 3·2k
- pour m=4 (carte du joueur 1 d'abord), 2011 montre qu'il existe une partie infinie pour n=13
- pour m=1 (carte du joueur 1 d'abord), 2011 montre qu'il existe une partie infinie pour n=6
- pour m=1 (ordre aléatoire), 2011 montre qu'il n'existe aucune partie infinie pour tout n
Mes simulations
de mon côté, l'outil ne vérifie pas (encore !) de façon mathématique et rigoureuse qu'une partie est bien infinie. dans les cas déterministes, càd les ordres "carte la plus haute d'abord" et "carte du joueur 1 d'abord", cela pourrait se vérifier en constatant la présence d'un cycle. à une règle du jeu fixée, par surjectivité de la fonction reliant les configurations initiales de paquets à leurs nombres de manches, il existe nécessairement un nombre de manches maximal pour les parties finies. de par l'absence totale observée de parties finissant après 15000 manches, je me suis contenté de considérer que le maximum était d'un ordre de grandeur similaire, et donc qu'à partir de 20000 manches la partie était "infinie".
en tapotant de ci de là, j'ai fait quelques simulations (que vous pouvez refaire vous-même !) sur 100000 parties dans le cas classique m=4 et n=13 d'un jeu de cinquante-deux cartes, afin d'estimer empiriquement dans quelles configurations l'on trouvait des parties infinies.
| Avec carte intermédiaire | Sans carte intermédiaire | |
|---|---|---|
| Aléatoire(1) | 0% de parties infinies moy: 430, max: 4000 | 0% de parties infinies moy: 580, max: 5000 |
| Plus haute d'abord(2) | 0% de parties infinies moy: 250, max: 1700 | 0% de parties infinies moy: 320, max: 2200 |
| Joueur 1 d'abord | 41.3% de parties infinies moy: 1800, max: 15000 | 99.8% de parties infinies(3) moy: 90, max: 100 |
(1) c'est le non-déterminisme de cette variante qui avait permis de démontrer mathématiquement l'absence de parties infinies pour m=1 couleur. par cette heuristique, on peut conjecturer qu'il en est de même pour d'autres m, en particulier notre m=4...
(2) toutes les parties semblent a priori finies dans cette variante... mais lorsque l'on simule 1 million de parties à m=4 n=7 un jeu de vingt-huit cartes, il apparaît, respectivement avec et sans carte intermédiaire, des parties infinies dans 0.015% et 0.1% des cas* ! pareil pour m=4 n=5, dans 0.0008% et 0.002% des cas* !! c'est dingue non !!
je n'ai trouvé aucune partie infinie pour les autres n. pour n=1,2,3 le nombre de configurations initiales de paquets étant inférieur à 20000 (cf. 1995), je peux présumer avec quasi-quasi-certitude qu'à 1 million de tests elles ont toutes été vérifiées. pour n=4, il y a environ 31 millions de parties possibles ; rien trouvé sur 200 millions de tests, où le problème du collectionneur de coupons (cf. 2023 non c'est le même auteur que 1995 ?? légende !) indique que j'aurais pourtant visité 1-e-200/31=99.8% des parties possibles. et pour n≥5 il y en a plus de 150 milliards, impossible de toutes les parcourir... mais même si je n'en ai trouvé aucune, les contre-exemples ci-dessus montrent qu'on est jamais à l'abri d'une infime probabilité !
(*je me dois d'être transparent... ces observations ne sont plus reproducibles depuis une légère màj des règles dans mon code. pour suivre l'article de 1995, à la fin d'une bataille on ramasse d'abord les cartes du haut puis vers le bas, alors qu'avant c'était toute la pile en une fois donc l'inverse. et voilà super, je ne trouve plus aucune partie infinie quelque soit le n. les mystères de la science.)
(3) les indicateurs de moyenne et de maximum montrent que dans l'infime fraction des parties qui se terminent, elles le font très rapidement. l'assomption faite "+ de 20000 manches ⇒ infini" est d'autant plus forte, car s'il n'y en a aucune de durée 200 à 20000, il paraît fort plausible qu'il n'y en ait aucune de durée >20000.
rien à voir mais je trouve assez comique que les articles 2010 et 2011 se citent mutuellement hahaha