Combien de positions possibles au Puissance 4 ? Le plateau en chiffres
Sept colonnes, six rangées, deux couleurs : le Puissance 4 a l'air d'un petit jeu. Pourtant, quand on demande combien de grilles différentes on peut obtenir en jouant, la réponse dépasse les 4 500 milliards. Entre les deux, il y a une suite de calculs simples, que nous avons refaits pas à pas avec un programme : les cases, les alignements, les bornes grossières, puis le compte exact, rangée par rangée de jetons. Chaque étape apprend quelque chose sur le jeu lui-même, et pas seulement sur les mathématiques.
Toutes les règles utilisées ici sont celles du Puissance 4 classique, que tu joues sur ce site : une grille verticale de 7 colonnes sur 6 rangées, les jetons tombent au plus bas de la colonne choisie, les joueurs jouent chacun leur tour, le premier qui aligne quatre jetons (horizontalement, verticalement ou en diagonale) gagne, et la partie est nulle quand la grille est pleine. Si tu veux revoir le détail, tout est dans notre guide complet des règles du Puissance 4.
Le plateau : 42 cases et 21 jetons chacun
Commençons par le plus facile. La grille compte 7 × 6 = 42 cases. Comme les joueurs posent un jeton à tour de rôle et qu'on ne retire jamais rien, une partie dure au plus 42 coups, soit 21 jetons par joueur. Le premier joueur pose ses jetons aux coups impairs (1, 3, 5…), le second aux coups pairs. Dans toute la suite, pour simplifier, le premier joueur a les rouges et le second les jaunes.
Cette simple alternance a une conséquence que l'on retrouvera dans tous les comptes : dans une position réelle, il y a toujours autant de jetons rouges que de jaunes, ou un rouge de plus. Une grille avec trois jetons jaunes et un seul rouge ne peut pas exister.
69 façons d'aligner quatre jetons
Combien y a-t-il de lignes de quatre cases sur lesquelles on peut gagner ? On les compte direction par direction :
| Direction | Calcul | Alignements |
|---|---|---|
| Horizontale | 4 positions par rangée × 6 rangées | 24 |
| Verticale | 3 positions par colonne × 7 colonnes | 21 |
| Diagonale montante | 4 × 3 points de départ | 12 |
| Diagonale descendante | 4 × 3 points de départ | 12 |
| Total | 69 |
Ces 69 alignements ne se répartissent pas également. Si l'on compte, pour chaque case, le nombre d'alignements qui passent par elle, on obtient cette carte :
| Col. 1 | Col. 2 | Col. 3 | Col. 4 | Col. 5 | Col. 6 | Col. 7 | |
|---|---|---|---|---|---|---|---|
| Rangée 6 | 3 | 4 | 5 | 7 | 5 | 4 | 3 |
| Rangée 5 | 4 | 6 | 8 | 10 | 8 | 6 | 4 |
| Rangée 4 | 5 | 8 | 11 | 13 | 11 | 8 | 5 |
| Rangée 3 | 5 | 8 | 11 | 13 | 11 | 8 | 5 |
| Rangée 2 | 4 | 6 | 8 | 10 | 8 | 6 | 4 |
| Rangée 1 | 3 | 4 | 5 | 7 | 5 | 4 | 3 |
Les deux cases centrales de la colonne 4 participent à 13 alignements, les coins à 3 seulement. C'est la raison géométrique de la force du centre, que nous détaillons dans l'article sur la colonne centrale, case la plus puissante du plateau. Retiens surtout l'ordre de grandeur : un jeton bien placé au centre travaille pour quatre fois plus de lignes qu'un jeton dans un coin.
Première estimation : 3 puissance 42, beaucoup trop
Chaque case peut être vide, rouge ou jaune. Une première borne, très grossière, consiste donc à multiplier 3 par lui-même 42 fois : 342 = 109 418 989 131 512 359 209, soit environ 1,1 × 1020, cent milliards de milliards.
Ce nombre est absurde pour le Puissance 4, parce qu'il compte des grilles impossibles : des jetons qui flottent au-dessus de cases vides, ou dix jetons jaunes pour deux rouges. L'immense majorité de ces 1020 combinaisons ne peut jamais apparaître sur une vraie grille.
La gravité élimine presque tout
Au Puissance 4, une colonne se remplit toujours par le bas. Elle est donc entièrement décrite par sa hauteur (de 0 à 6 jetons) et par la couleur de chacun de ses jetons. Pour une seule colonne, cela fait 1 possibilité vide, 2 avec un jeton, 4 avec deux jetons, et ainsi de suite jusqu'à 64 avec six jetons : 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 colonnes possibles.
Les sept colonnes étant indépendantes à ce stade, on obtient 1277 = 532 875 860 165 503 grilles, environ 5,3 × 1014. La gravité seule a divisé la première borne par plus de 200 000. Et si l'on ne regarde que la forme des piles, sans les couleurs, il n'existe que 77 = 823 543 profils de hauteurs différents.
On peut ensuite imposer l'équilibre des couleurs (autant de rouges que de jaunes, ou un rouge de plus). Le calcul se fait colonne par colonne en suivant l'écart entre rouges et jaunes, et donne exactement 70 728 639 995 483 grilles, environ 7,1 × 1013. C'est une borne honnête : toutes ces grilles respectent la gravité et l'alternance des couleurs. Mais elles ne sont pas toutes atteignables en jouant.
Le compte exact : 4 531 985 219 092 positions
Que manque-t-il ? La fin de partie. Dès qu'un joueur aligne quatre jetons, la partie s'arrête. Une grille où les deux camps ont chacun un alignement, ou bien où le joueur gagnant aurait dû s'arrêter plusieurs coups plus tôt, ne peut pas être obtenue. Ce sont précisément ces grilles que la borne précédente compte en trop.
Le nombre exact de positions qu'on peut rencontrer en jouant une partie de Puissance 4, grille vide et positions gagnantes comprises, a été calculé en 2008 par les informaticiens Stefan Edelkamp et Peter Kissmann : 4 531 985 219 092, soit environ 4,5 × 1012, un peu plus de 4 500 milliards. C'est environ seize fois moins que la borne de 7,1 × 1013, et plus de vingt millions de fois moins que 342.
Nous n'avons pas refait le calcul total, qui demande des techniques de comptage spécialisées. En revanche, nous avons énuméré une à une toutes les positions jusqu'à 12 jetons, en jouant tous les coups légaux et en éliminant les doublons. Le résultat :
| Jetons posés | Positions distinctes | Dont positions déjà gagnées |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 7 | 0 |
| 2 | 49 | 0 |
| 3 | 238 | 0 |
| 4 | 1 120 | 0 |
| 5 | 4 263 | 0 |
| 6 | 16 422 | 0 |
| 7 | 54 859 | 728 |
| 8 | 184 275 | 1 892 |
| 9 | 558 186 | 19 412 |
| 10 | 1 662 623 | 44 225 |
| 11 | 4 568 683 | 273 261 |
| 12 | 12 236 101 | 573 323 |
Ces valeurs sont celles de la suite de référence (OEIS A212693, reprise aussi sur le site de l'informaticien John Tromp), ce qui confirme les deux calculs l'un par l'autre. Quelques lectures utiles :
- Après 2 jetons, 49 positions, toutes différentes : 7 premiers coups possibles, 7 réponses chacun. Rien ne se confond encore.
- Après 3 jetons, 238 positions au lieu de 343 (7 × 7 × 7). Les deux rouges peuvent avoir été posés dans un ordre ou dans l'autre : jouer en colonne 3 puis en 5, ou en 5 puis en 3, donne la même grille. C'est la première apparition des transpositions.
- Les premières victoires arrivent avec 7 jetons : 728 positions où les rouges ont déjà aligné quatre jetons. Avec 8 jetons apparaissent les premières victoires jaunes.
- Le nombre est multiplié par 2,7 à 3 à chaque jeton entre 9 et 12 jetons, bien moins que les 7 coups théoriquement possibles, à cause des transpositions et des parties déjà terminées.
Cumulées, les positions de 0 à 12 jetons ne sont que 19 286 827. Elles représentent moins d'un millième de pour cent du total : l'essentiel des 4 500 milliards de positions se trouve en milieu et en fin de partie, quand la grille est à moitié pleine.
Positions et parties : deux choses différentes
Une position est une grille ; une partie est une suite de coups. Plusieurs suites mènent à la même grille, et l'écart grandit très vite. Nous avons compté les suites de coups légales, en arrêtant chaque suite dès qu'un joueur gagne :
| Coups joués | Suites de coups encore en cours | Parties qui se terminent à ce coup | Positions distinctes |
|---|---|---|---|
| 7 | 810 504 | 13 032 | 54 859 |
| 8 | 5 628 804 | 44 430 | 184 275 |
| 9 | 38 307 690 | 1 086 882 | 558 186 |
| 10 | 263 770 588 | 4 261 058 | 1 662 623 |
Au dixième coup, il existe 268 031 646 suites de coups (en cours ou juste terminées) pour seulement 1 662 623 grilles : chaque position est atteinte en moyenne par environ 160 chemins différents. Le nombre total de parties possibles est donc bien plus grand que le nombre de positions, et c'est le second qui compte pour l'analyse : peu importe le chemin, deux grilles identiques ont la même valeur.
C'est exactement ce qu'exploitent les programmes qui jouent au Puissance 4 : ils gardent en mémoire les positions déjà évaluées (une « table de transposition ») et ne refont pas le calcul quand ils retombent dessus par un autre chemin. L'article sur l'intelligence artificielle au Puissance 4 explique comment fonctionnent ces recherches.
Parties courtes, parties longues
La partie la plus courte dure 7 coups : 4 jetons rouges, 3 jaunes. Par exemple, si les rouges jouent colonnes 4, 3 et 2 et que les jaunes répondent chaque fois par-dessus (4, 3, 2), le quatrième jeton rouge en colonne 1 aligne la rangée du bas. Il existe 13 032 suites de 7 coups qui se terminent ainsi. Le second joueur, lui, ne peut pas gagner avant le 8e coup, son quatrième jeton : 44 430 suites de 8 coups se terminent par une victoire jaune.
La partie la plus longue dure 42 coups, et une partie nulle dure forcément 42 coups, puisque la nulle n'est déclarée que sur grille pleine. Voici une grille nulle réelle, obtenue en jouant les colonnes 7, 6, 6, 3, 2, 4, 1, 3, 1, 7, 5, 1, 1, 4, 5, 7, 7, 3, 4, 5, 5, 2, 3, 2, 3, 7, 5, 7, 5, 6, 2, 4, 6, 3, 4, 2, 1, 1, 2, 6, 6, 4 (R pour rouge, J pour jaune, rangée du haut en premier) :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 6 | J | R | J | J | R | R | J |
| 5 | R | J | R | R | R | J | J |
| 4 | R | R | R | J | R | R | R |
| 3 | J | J | J | R | J | J | J |
| 2 | R | J | J | J | R | R | J |
| 1 | R | R | J | J | R | J | R |
Aucune des 69 lignes n'y contient quatre jetons de la même couleur : la suite a été rejouée par le moteur de règles du site, qui l'a acceptée coup par coup et a déclaré la partie nulle sur grille pleine.
Ces nulles sont rares quand on joue n'importe comment. Sur 2 millions de parties simulées où chaque coup est tiré au hasard parmi les colonnes libres, le premier joueur gagne 55,5 % des parties, le second 44,2 %, et seulement 0,25 % se terminent par une nulle, soit une partie sur 400. Ces parties au hasard durent en moyenne 21,3 coups, la moitié de la grille. Entre deux joueurs attentifs, les parties s'allongent, parce que chacun bloque les alignements de l'autre au lieu de les laisser se former : sur 100 parties où l'ordinateur du site, à son niveau le plus fort, joue contre lui-même, la durée moyenne monte à 38,2 coups et 16 parties finissent nulles.
Le Puissance 4 parmi les autres jeux
Pour situer ces 4,5 × 1012 positions, deux repères :
- Le morpion (3 × 3) ne compte que 5 478 positions atteignables, grille vide comprise : nous l'avons vérifié par la même méthode d'énumération. On peut toutes les examiner à la main avec de la patience, et le jeu est nul quand les deux joueurs jouent bien.
- Les dames anglaises (damier 8 × 8) comptent environ 5 × 1020 positions, selon l'équipe de Jonathan Schaeffer qui a résolu ce jeu en 2007 : à peu près cent millions de fois plus que le Puissance 4.
Le Puissance 4 se trouve donc dans une zone intermédiaire : beaucoup trop vaste pour être appris par cœur ou parcouru par un humain, mais assez petit pour qu'un ordinateur en vienne à bout.
Pourquoi le jeu a pu être résolu sans tout énumérer
En 1988, James D. Allen et Victor Allis ont démontré, indépendamment l'un de l'autre, que le premier joueur gagne au Puissance 4 s'il joue parfaitement. Ils n'ont pas examiné les 4 500 milliards de positions : une preuve n'a besoin de considérer que les positions qui découlent de la stratégie gagnante, face à toutes les défenses adverses. Allis s'est appuyé sur des règles stratégiques (notamment le contrôle de la parité des rangées, paires ou impaires) pour couper d'énormes branches de l'arbre. L'histoire de cette résolution est racontée dans le Puissance 4 résolu par les mathématiciens.
Les programmes actuels procèdent autrement mais avec la même idée : ils explorent l'arbre des coups en abandonnant les branches qui ne peuvent pas changer le résultat (l'élagage alpha-bêta), essayent d'abord les colonnes centrales, et mémorisent les positions déjà vues. L'outil d'analyse « meilleur coup », accessible depuis l'accueil du jeu, repose sur ce principe : à partir de 8 jetons posés, il calcule dans ton navigateur la valeur exacte de chaque colonne.
Ce que ces chiffres changent pour ton jeu
Aucun joueur ne mémorisera 4 500 milliards de positions, ni même les 12 millions qui existent après 12 jetons. Mais les chiffres disent où concentrer ses efforts :
- L'ouverture est petite. Il n'y a que 49 positions après deux jetons et 238 après trois. C'est la seule partie du jeu qu'on peut vraiment étudier de façon systématique, en commençant par les premiers coups au centre.
- Pense en positions, pas en suites de coups. Avec environ 160 chemins par position dès le dixième coup, l'ordre dans lequel les jetons sont arrivés importe peu : seule compte la grille devant toi. Cela libère de la mémoire pour regarder les menaces.
- Le centre vaut plus que les bords, et la carte des 69 alignements le chiffre : 13 lignes pour les cases centrales, 3 pour les coins.
- Le milieu de partie est l'endroit où tout se joue. C'est là que se trouve la masse des positions, et donc là où l'on ne peut plus réciter : il faut calculer. Les principes du guide des stratégies gagnantes (menaces doubles, parité, zugzwang) servent précisément à se repérer dans cette zone.
Comment ces chiffres ont été obtenus
Les alignements, les bornes 342, 1277 et 70 728 639 995 483, le nombre de positions jusqu'à 12 jetons, les suites de coups jusqu'à 10 coups et les 5 478 positions du morpion ont été calculés par des programmes écrits pour cet article. Les positions ont été générées en jouant tous les coups légaux depuis la grille vide, sans jamais poursuivre une partie déjà gagnée, et les doublons éliminés en comparant le contenu des colonnes. La partie nulle et la partie la plus courte ont été rejouées par le moteur de règles qui arbitre les parties du site. La simulation de parties au hasard porte sur 2 millions de parties. Le total de 4 531 985 219 092 positions est celui calculé par Stefan Edelkamp et Peter Kissmann en 2008 ; nos valeurs de 0 à 12 jetons coïncident avec la suite de référence OEIS A212693.