← Retour au blog

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 :

DirectionCalculAlignements
Horizontale4 positions par rangée × 6 rangées24
Verticale3 positions par colonne × 7 colonnes21
Diagonale montante4 × 3 points de départ12
Diagonale descendante4 × 3 points de départ12
Total69

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. 1Col. 2Col. 3Col. 4Col. 5Col. 6Col. 7
Rangée 63457543
Rangée 546810864
Rangée 45811131185
Rangée 35811131185
Rangée 246810864
Rangée 13457543

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ésPositions distinctesDont positions déjà gagnées
010
170
2490
32380
41 1200
54 2630
616 4220
754 859728
8184 2751 892
9558 18619 412
101 662 62344 225
114 568 683273 261
1212 236 101573 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 :

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ésSuites de coups encore en coursParties qui se terminent à ce coupPositions distinctes
7810 50413 03254 859
85 628 80444 430184 275
938 307 6901 086 882558 186
10263 770 5884 261 0581 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) :

1234567
6JRJJRRJ
5RJRRRJJ
4RRRJRRR
3JJJRJJJ
2RJJJRRJ
1RRJJRJR

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 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 :

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.

À lire aussi

← Retour au blog Jouer au Puissance 4
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →