Ce que veut dire qu'un jeu est résolu
Un jeu est résolu quand on connaît le résultat obtenu si les deux joueurs jouent de façon parfaite depuis la position initiale. Il y a trois degrés habituels. Dans la solution « ultra faible », on sait seulement qui gagne ou s'il y a match nul, sans connaître la stratégie. Dans la « faible », on connaît en plus une stratégie qui garantit ce résultat dès le début. Dans la « forte », on connaît le meilleur résultat depuis n'importe quelle position possible.
Pour Puissance 4 sur la grille classique de 7 colonnes sur 6 rangées, le résultat est clair : avec un jeu parfait, c'est le joueur qui commence qui gagne. Cela ne veut pas dire qu'il gagne toujours en pratique, car pour y arriver il doit trouver le bon coup à chaque tour, et les parties entre personnes sont pleines d'erreurs.
Qui l'a résolu et quand
L'histoire a deux protagonistes qui sont arrivés à la même conclusion de façon indépendante en octobre 1988. Le premier fut James Dow Allen, qui a annoncé sa solution le 1er octobre 1988 dans un message au groupe de discussion rec.games.programmer. Quinze jours plus tard, le 16 octobre, le chercheur néerlandais Victor Allis a présenté sa propre solution, décrite dans son travail « A Knowledge-based Approach of Connect-Four », de la Vrije Universiteit.
La méthode d'Allis était « basée sur la connaissance » : au lieu de passer en revue toutes les positions, il a formulé des règles stratégiques, comme les cases qu'il convient de contrôler et les menaces qui comptent, et les a combinées avec une recherche pour démontrer que le premier joueur peut forcer la victoire. Plus tard, on est arrivé au même résultat par force brute, avec des bases de données de positions et des ordinateurs puissants ; le programmeur John Tromp, par exemple, a monté une base avec toutes les positions de 8 pions qui a servi de point de départ. Les deux voies concordent.
La clé de l'ouverture : la colonne centrale
N'importe quel premier coup ne suffit pas. Le résultat dépend de la colonne dans laquelle le premier joueur commence :
| Premier coup | Résultat avec un jeu parfait |
|---|---|
| Colonne centrale (la 4) | Celui qui commence gagne |
| Colonnes voisines du centre (la 3 et la 5) | Match nul |
| Colonnes extérieures (1, 2, 6 et 7) | Le deuxième joueur gagne |
Ce que signifie « celui qui commence gagne » en pratique
Que la théorie dise que le premier gagne ne t'assure rien si l'adversaire joue bien : l'avantage est réel, mais il exige de la précision. Malgré tout, commencer t'apporte deux choses concrètes. La première est l'initiative : tu joues en premier et l'adversaire doit souvent répondre à tes menaces. La seconde est la parité, une règle pratique très répandue chez les joueurs : comme la grille a 6 rangées, un nombre pair, et qu'on joue à tour de rôle, les cases des rangées impaires (la 1, la 3 et la 5, en comptant depuis le bas) tendent à revenir à celui qui a commencé, et celles des rangées paires au second. C'est pourquoi une menace sur une rangée impaire a souvent plus de valeur pour le premier joueur.
Pourquoi le centre vaut autant
Les pions de la colonne centrale participent à plus de lignes possibles que ceux de n'importe quelle autre colonne. Depuis le centre, on peut former quatre alignés à l'horizontale, à la verticale et sur les deux diagonales avec de nombreuses combinaisons différentes ; un pion sur le bord ne sert presque que dans une ou deux directions. C'est pourquoi les programmes forts ordonnent leurs coups du centre vers l'extérieur, et c'est pourquoi les livres d'ouverture commencent par la colonne 4.
Pour toi, la règle pratique est simple : quand tu n'as pas de coup clairement meilleur, choisis une colonne proche du centre. Et si l'adversaire occupe le centre en premier, ne te décourage pas : les colonnes voisines restent très bonnes.
Conseils pour gagner plus de parties contre des personnes
- Si tu commences, ouvre dans la colonne centrale. C'est la seule ouverture qui, avec un jeu parfait, gagne.
- Cherche les doubles menaces : deux lignes de trois avec la case de fermeture disponible en même temps. L'adversaire ne peut en bloquer qu'une. C'est la façon la plus courante de gagner contre des humains.
- Pense aux menaces « en l'air » : une ligne de trois dont la case finale n'est pas encore accessible parce qu'il manque un pion en dessous. Si cette case est sur une rangée qui t'arrange par parité, l'adversaire finit tôt ou tard par devoir jouer en dessous et te la donner.
- Avant de lâcher un pion, regarde quelle case se libère juste au-dessus. Si tu offres à l'adversaire une case qui lui permet de fermer une ligne, tu as perdu.
- Bloque les lignes de trois ouvertes des deux côtés avant qu'elles se forment : c'est une défaite certaine. Anticipe d'un tour.
- En fin de partie, ce qui compte, c'est qui se retrouve sans coups sûrs : surveille les colonnes que tu peux encore jouer sans danger.
- Si tu es le second, vise les cases des rangées paires et bloque sans te presser chaque menace des rangées impaires : c'est ton meilleur chemin vers le match nul ou vers une erreur de l'adversaire.
Alors, l'ordinateur ne peut pas perdre ?
Un programme qui jouerait parfaitement dès le début et commencerait en premier ne perdrait jamais, mais c'est une affirmation sur la solution théorique du jeu, pas sur n'importe quel programme. Résoudre toute la partie depuis la position initiale demande énormément de calcul, et dans un navigateur, avec à peine une seconde et demie par coup, ce n'est pas possible.
C'est pourquoi le niveau « Imbattable » de notre Puissance 4 se présente pour ce qu'il est : le niveau le plus fort. Il utilise une recherche alpha-bêta avec approfondissement itératif, une table qui retient les positions déjà vues, un ordre de colonnes qui commence par le centre et un très court livre d'ouvertures. Il analyse de nombreux coups à l'avance et laisse presque passer aucune erreur, mais nous ne promettons pas qu'il soit impossible à battre. Si tu le bats, tu as vraiment gagné.
Comment s'entraîner
Une bonne façon de progresser est de jouer contre l'ordinateur au niveau Difficile puis contre l'Imbattable, en alternant celui qui commence. Quand tu perds, revois la partie et repère à quel tour la double menace est apparue : on peut presque toujours la faire remonter à un coup tranquille antérieur. Il est aussi utile d'essayer les variantes, comme la grande grille ou le mode PopOut, qui obligent à penser autrement et entraînent la vision de la grille.
Questions fréquentes
Qui a démontré que Puissance 4 est résolu ?
James Dow Allen l'a annoncé le 1er octobre 1988 et, de façon indépendante, Victor Allis a présenté sa solution le 16 octobre 1988. Il y a eu ensuite des confirmations par force brute.
Qui gagne à Puissance 4 avec un jeu parfait ?
Le joueur qui commence, à condition que son premier pion aille dans la colonne centrale de la grille classique de 7×6. S'il commence dans une colonne voisine du centre, la partie est un match nul théorique, et s'il commence dans l'une des quatre colonnes des bords, le second joueur gagne.
Cela veut-il dire que celui qui commence gagne toujours ?
Non. C'est le résultat si personne ne commet d'erreur. En pratique, il faut continuer à trouver le bon coup à chaque tour, et les gens se trompent. Commencer est un avantage, pas une garantie.
Les autres tailles de grille sont-elles aussi résolues ?
Beaucoup le sont, mais le résultat change avec la taille. Par exemple, John Tromp a indiqué que la grille de 8×8 est une victoire du second joueur. Ce guide ne concerne que la grille classique de 7 colonnes sur 6 rangées.
Le niveau Imbattable ne perd-il jamais ?
Nous ne le promettons pas. C'est le niveau le plus fort que nous proposons, avec une recherche profonde et beaucoup de calcul par coup, mais il ne résout pas toute la partie dans le temps disponible. Il n'existe que sur la grille classique de 7×6.
Combien de positions compte Puissance 4 ?
On a dénombré 4 531 985 219 092 positions légales sur la grille de 7×6, un chiffre confirmé de façon indépendante en 2008 par Stefan Edelkamp et Peter Kissmann.