Où l'ordinateur du Puissance 4 se trompe : ses 10 niveaux passés au solveur
L'ordinateur du site propose dix niveaux, du hasard pur au niveau 10 qui calcule 8 coups à l'avance. Mais « calculer 8 coups » ne dit pas où il se trompe, ni quel genre d'erreur il commet. Pour le savoir, nous avons fait jouer chaque niveau sur 562 positions de milieu et de fin de partie, puis vérifié chacun de ses coups avec un solveur exact, celui qui sert à l'outil « meilleur coup » du site. Le résultat est net : à partir du niveau 4, aucune de ses fautes ne donne une victoire en un coup, et au niveau 10 aucune ne peut être punie en moins de cinq jetons. Ses erreurs sont lointaines, elles se concentrent avant le 24e jeton, et les niveaux 4 à 7 se trompent souvent dès leur premier coup.
Ce que fait l'ordinateur, niveau par niveau
Le comportement de l'ordinateur est entièrement décrit dans le moteur du jeu, et il tient en quelques règles :
- Niveau 1 : il joue une colonne au hasard.
- Niveau 2 : il gagne s'il peut aligner quatre jetons tout de suite, sinon il tire une colonne au hasard, avec un poids plus fort au centre (4 pour la colonne centrale, 1 pour les colonnes du bord).
- Niveau 3 : il gagne s'il le peut, sinon il bloque ton alignement immédiat, sinon même tirage attiré par le centre.
- Niveaux 4 à 10 : il gagne ou bloque s'il le faut, sinon il cherche le meilleur coup par une recherche minimax avec élagage alpha-bêta. La profondeur va de 2 jetons posés (les siens et les tiens confondus) au niveau 4 à 8 jetons au niveau 10, soit un de plus par niveau. Au bout de la recherche, une évaluation compte les jetons de la colonne centrale et les lignes de quatre cases où un seul camp a déjà deux ou trois jetons.
Un détail compte beaucoup : la tolérance. Quand deux coups ont des évaluations proches, l'ordinateur tire au hasard entre eux. L'écart toléré vaut 60 points au niveau 4, puis 30, 20, 12, 8, 4 et enfin 2 points au niveau 10, et il tombe à zéro dès qu'une victoire forcée est en vue. Ce hasard dépend d'une graine tirée au début de chaque partie, ce qui explique que deux parties identiques au départ ne se poursuivent pas forcément de la même façon.
Le premier coup : les niveaux 4 à 7 ouvrent n'importe où
Le Puissance 4 est résolu depuis 1988 (James D. Allen puis Victor Allis, indépendamment) : le premier joueur gagne s'il commence au centre et joue parfaitement ensuite. S'il commence dans une colonne voisine du centre, la partie est nulle avec un jeu parfait des deux côtés ; s'il commence dans l'une des quatre colonnes extérieures (1, 2, 6 ou 7), c'est le second joueur qui peut forcer la victoire. L'histoire de cette preuve est racontée dans notre article sur le Puissance 4 résolu.
Nous avons demandé à chaque niveau son premier coup quand il ouvre la partie, avec 400 graines différentes (100 pour les niveaux 8 à 10, plus lents) :
| Niveau | Centre (col. 4) | Voisines (col. 3 et 5) | Extérieures (col. 1, 2, 6, 7) |
|---|---|---|---|
| 1 | 13,8 % | 29,0 % | 57,3 % |
| 2 et 3 | 24,3 % | 37,8 % | 38,0 % |
| 4 à 7 | 14,8 % | 28,8 % | 56,5 % |
| 8 | 38 % | 62 % | 0 % |
| 9 et 10 | 100 % | 0 % | 0 % |
Sur une grille vide, les sept colonnes reçoivent des évaluations trop proches pour dépasser la tolérance des niveaux 4 à 7 : ces niveaux tirent leur premier jeton pratiquement au hasard, et dans notre tirage, plus d'une fois sur deux, ils ouvrent dans une colonne extérieure, c'est-à-dire dans une ouverture que la théorie donne perdante pour eux. Le niveau 8 ne s'écarte jamais des trois colonnes centrales, mais il choisit une colonne voisine du centre, nulle en théorie, 62 fois sur 100. Les niveaux 9 et 10 ouvrent toujours au centre : quand ils commencent, ils ont la partie théoriquement gagnée, et c'est à toi d'attendre leur première faute.
La méthode : 562 positions résolues exactement
Le solveur de l'outil « meilleur coup » calcule la valeur exacte d'une position : gagnée, nulle ou perdue pour le joueur qui a le trait, en supposant un jeu parfait des deux côtés. Plus la grille est vide, plus ce calcul est long : pour garder un banc d'essai raisonnable, nous avons travaillé sur des positions d'au moins 12 jetons, et les chiffres ci-dessous ne disent rien des douze premiers coups (sauf le tout premier, traité à part plus haut) :
- 120 parties ont été jouées par l'ordinateur du site contre lui-même, avec un niveau tiré entre 3 et 10 pour chaque camp ;
- dans chacune, nous avons prélevé la position aux jetons 12, 15, 18, 21, 24, 27, 30, 33 et 36 (tant que la partie durait), soit 562 positions ;
- chaque coup légal de chaque position a été résolu exactement. 278 positions sont gagnées pour le joueur au trait, 65 sont nulles et 219 perdues ;
- chaque niveau a joué les 343 positions non perdues, avec 4 graines différentes, soit 1 372 coups par niveau. Une faute est un coup qui fait baisser la valeur : une position gagnée qui devient nulle ou perdue, une position nulle qui devient perdue.
Ces positions viennent de parties de l'ordinateur, pas de parties humaines : les pourcentages ci-dessous décrivent cette banque de positions et donnent des ordres de grandeur, pas le taux d'erreur exact que tu rencontreras dans tes parties.
Les fautes de chaque niveau
Le tableau donne la part des coups fautifs de chaque niveau, au total, selon que la position de départ était gagnée ou nulle, puis selon le nombre de jetons déjà posés (12 à 17, 24 à 29, 30 et plus) :
| Niveau | Total | Gagnée | Nulle | 12 à 17 | 24 à 29 | 30 et + |
|---|---|---|---|---|---|---|
| 1 | 45,1 % | 43,1 % | 53,8 % | 50,6 % | 42,5 % | 43,3 % |
| 2 | 40,8 % | 38,5 % | 50,8 % | 44,5 % | 42,5 % | 38,9 % |
| 3 | 30,5 % | 29,4 % | 35,4 % | 33,0 % | 29,0 % | 22,6 % |
| 4 | 21,7 % | 20,3 % | 27,7 % | 30,7 % | 13,1 % | 6,3 % |
| 5 | 16,9 % | 14,2 % | 28,5 % | 25,4 % | 6,3 % | 3,4 % |
| 6 | 14,3 % | 12,1 % | 23,5 % | 22,7 % | 4,0 % | 1,4 % |
| 7 | 13,4 % | 11,2 % | 23,1 % | 22,7 % | 4,0 % | 0 % |
| 8 | 10,9 % | 8,7 % | 20,0 % | 17,6 % | 4,4 % | 0 % |
| 9 | 8,5 % | 6,4 % | 17,7 % | 13,5 % | 3,6 % | 0 % |
| 10 | 9,1 % | 7,5 % | 16,2 % | 14,5 % | 1,6 % | 0 % |
Trois choses ressortent. D'abord, le gain est rapide jusqu'au niveau 6, puis beaucoup plus lent : du niveau 6 au niveau 10, le taux de fautes ne passe que de 14,3 % à 9,1 %. Dans cette banque, les niveaux 9 et 10 font à peu près autant de fautes, l'écart entre eux est trop faible pour être significatif sur 1 372 coups.
Ensuite, une position nulle est plus difficile à tenir qu'une position gagnée. Le niveau 10 lâche une nulle dans 16,2 % des cas, une victoire dans 7,5 %. Une explication se lit dans les positions elles-mêmes : entre 12 et 17 jetons, dans une position gagnée, un peu plus de la moitié des coups légaux gardent la victoire en moyenne (53,7 %) ; dans une position nulle, seulement un quart des coups gardent la nulle (25,4 %), et dans 8 des 16 positions nulles de cette phase il n'y en a qu'un seul.
Enfin, les fautes se concentrent avant le 24e jeton. Sur les 125 fautes du niveau 10, 121 tombent entre le 12e et le 23e jeton. Il ne se trompe plus que dans 1,6 % des cas entre 24 et 29 jetons, et à partir de 30 jetons nous n'avons mesuré aucune faute des niveaux 7 à 10, sur 208 coups chacun. Une explication probable : quand la grille se remplit, il reste moins de colonnes jouables et la fin de partie se rapproche, si bien que la recherche de l'ordinateur en voit une part de plus en plus grande.
Le niveau 10 ne tombe jamais dans un piège court
Pour chaque faute qui transforme une position en défaite, nous avons cherché en combien de jetons l'adversaire peut forcer la victoire, avec la fonction exacte du moteur qui sert à construire le défi du jour (« gagne en N coups »), jusqu'à 4 jetons :
| Niveau | Fautes qui perdent | Punies en 1 jeton | Punies en 2 à 4 jetons | Il faut plus de 4 jetons |
|---|---|---|---|---|
| 1 | 564 | 254 | 79 | 231 |
| 2 | 520 | 251 | 65 | 204 |
| 3 | 379 | 110 | 65 | 204 |
| 4 | 241 | 0 | 53 (dès 2 jetons) | 188 |
| 5 | 182 | 0 | 36 (dès 2 jetons) | 146 |
| 6 | 152 | 0 | 13 (dès 3 jetons) | 139 |
| 7 | 139 | 0 | 26 (dès 3 jetons) | 113 |
| 8 | 97 | 0 | 4 (à 4 jetons) | 93 |
| 9 | 87 | 0 | 0 | 87 |
| 10 | 80 | 0 | 0 | 80 |
Le tableau suit l'horizon de chaque niveau. Le niveau 3 bloque ton alignement immédiat, mais il lui arrive de jouer juste sous la case dont tu as besoin, et de te la donner : ce sont ses 110 fautes punies en un jeton. À partir du niveau 4, la recherche voit au moins ta réponse, et plus aucune faute ne se punit en un jeton. Ensuite, la punition la plus courte observée passe à 2 jetons aux niveaux 4 et 5, à 3 jetons aux niveaux 6 et 7, à 4 jetons au niveau 8 : elle s'allonge d'un jeton chaque fois que la recherche gagne deux jetons de profondeur. Au niveau 10, la recherche couvre ses 4 jetons et tes 4 réponses : une victoire forcée en 4 jetons ou moins lui est visible, et les 80 fautes perdantes mesurées demandent toutes plus de 4 jetons pour être punies. Le niveau 9 n'en a aucune non plus dans notre banque, mais sa profondeur de 7 ne lui garantit pas de voir ta quatrième réponse.
Concrètement : contre les niveaux 9 et 10, une menace double préparée sur deux ou trois coups ne passera pas, l'ordinateur l'a vue venir. Ce qui le bat, ce sont les plans dont l'effet arrive plus tard que son horizon, typiquement une menace placée sur une case que la gravité ne rendra jouable que bien plus tard, quand la colonne se sera remplie. C'est le terrain de la parité et du zugzwang, que décrit notre guide des stratégies gagnantes, et que l'article sur la parité des cases détaille.
Ce qu'il faut retenir
- Contre les niveaux 4 à 7, laisse l'ordinateur commencer de temps en temps. Le réglage « qui commence » propose « Moi », « Au hasard » ou « L'ordinateur ». Dans notre tirage, plus d'une fois sur deux ces niveaux ouvrent dans une colonne extérieure, ce qui te donne en théorie une partie gagnable en second.
- Contre les niveaux 9 et 10, oublie les pièges courts. Aucune de leurs fautes mesurées ne se punit en 4 jetons ou moins. Construis des menaces qui ne deviendront jouables que bien plus tard.
- Attaque entre le 12e et le 23e jeton. Parmi les positions testées, c'est là que le niveau 10 a commis 121 de ses 125 fautes. Après le 30e jeton, nous ne l'avons plus vu se tromper : si tu n'as pas pris l'avantage avant, n'attends pas de cadeau.
- Une position nulle est un piège pour lui aussi. Il y lâche la nulle environ deux fois plus souvent qu'il ne lâche une victoire. Une partie équilibrée et serrée te laisse plus de chances qu'une attaque brouillonne.
- Regarde où la partie a basculé. À la fin d'une partie contre l'ordinateur, le lien « Analyser la partie coup par coup » ouvre l'outil meilleur coup, qui calcule la valeur exacte de chaque position à partir de 8 jetons et montre le coup qui a tout changé. Chaque niveau a aussi son classement.
Comment ces chiffres ont été obtenus
Tous les coups de l'ordinateur ont été calculés par le moteur qui joue sur le site, appelé directement, niveau par niveau et graine par graine. Les valeurs des positions viennent du solveur de l'outil « meilleur coup », qui suit la méthode publiée par Pascal Pons (recherche alpha-bêta avec table de transposition) ; nous l'avons utilisé en mode « gagné, nul ou perdu », plus rapide que le calcul du nombre exact de coups, et contrôlé sur des positions de 16 jetons contre son calcul complet. Les valeurs théoriques du premier coup (centre gagnant, colonnes voisines nulles, colonnes extérieures perdantes pour celui qui commence) sont celles des résolutions publiées depuis 1988. Nous en avons recalculé une avec le solveur du site : après une ouverture en colonne 1 et une réponse au centre, le premier joueur est perdu, donc l'ouverture en colonne 1 (et en colonne 7, par symétrie) est bien perdante pour lui. Il a fallu environ 190 millions de positions examinées et un peu moins de trois minutes de calcul.