Quelle est la stratégie gagnante pour le premier joueur des jeux Connect Four?

Meilleure réponse

La « stratégie » réelle est en fait assez complexe et implique une recherche exhaustive des points à traiter avec des tactiques, donc ce n’est pas pratique à utiliser à la main.

D’un autre côté, les informations stratégiques et certaines règles générales sont faciles à utiliser pour un être humain et feront probablement de vous un bon joueur.

Contexte

Commençons par passer rapidement en revue connect-4. Le jeu se joue sur un plateau 6 × 7; nous pouvons étiqueter chaque ligne avec un nombre et chaque colonne avec une lettre:

Chaque joueur choisit à tour de rôle une colonne; leur pierre est placée dans la cellule ouverte la plus basse de la colonne. Nous pouvons écrire un jeu en utilisant uniquement les colonnes; par exemple, si les deux joueurs jouent la colonne centrale, nous pouvons écrire dd. Cela conduirait au tableau suivant:

(Par convention, le joueur 1 sera bleu et le joueur 2 rouge.)

Un jeu peut être gagné en connectant quatre pièces de votre couleur horizontalement, verticalement ou en diagonale:

Une dernière notion utile est une menace , qui est juste trois morceaux daffilée avec le quatrième carré ouvert (mais pas nécessairement accessible). Ici, le bleu a une menace en diagonale:

Stratégie

Le jeu est résolu: le premier joueur (bleu) peut toujours forcer une victoire. Les idées fondamentales de la stratégie gagnante sont assez simples: contrôler zugzwang et contrôler impair / pair lignes.

Zugzwang

« Zugzwang » en tant que terme signifie perdre parce que vous doivent faire un mouvement. Une illustration simple serait davoir deux menaces lune sur lautre. Voici un exemple de bleu forçant une victoire sur la colonne c avec du rouge pour se déplacer:

Cependant, doublez les menaces comme celle-ci sont raisonnablement faciles à reconnaître à lavance et à contrer. En pratique, une forme beaucoup plus utile de Zugzwang consiste simplement à attendre que tout le tableau soit rempli et quil ne reste quun seul coup possible. Prenons lexemple simple où le rouge gagne à gauche, avec la force réelle ne se produisant quaprès une série de mouvements:

Menaces paires / impaires

Quiconque a une menace qui sera inexorablement comblée gagnera à la fin. Comme nous lavons vu dans lexemple précédent, le rouge peut gagner avec une menace dans un paire . En revanche, le bleu a besoin dune menace impair pour gagner: cest là que lasymétrie dans le jeu émerge.

Une menace étrange « plafonne » une colonne et retourne essentiellement qui peut obtenir quelle ligne en remplissant tout le boa rd. En particulier, cela signifie quune menace impaire valide est «plus forte» quune menace paire valide: si le bleu a une menace impaire dans une colonne et le rouge une menace paire dans une autre, le bleu lemportera toujours. Voici un exemple (en bleu pour jouer):

À partir de cette position, nous pouvons remplir à plusieurs reprises jusquà ce que nous arrivions à un position où le rouge doit jouer c car g (qui contient un nombre impair de pièces) entraînerait un gain bleu. Cela permet la colonne c se remplit jusquà ce que le rouge soit obligé de perdre:

Le Une menace impaire « fonctionne » car elle limite une seule colonne pour avoir un nombre impair de positions – ce qui fait que le tableau na plus un nombre pair de carrés (42) à un nombre impair, ce qui inverse la dynamique du jeu. Cela signifie également que si les deux rouge et bleu ont des menaces impaires indépendantes, ils sannulent: avoir deux colonnes impaires ramènent le total à pair.

Plus généralement, la distinction impair / pair nous donne une notion de contrôle : le rouge contrôle normalement le jeu, mais le bleu peut prendre le contrôle en établissant une menace étrange. En pratique, contrôler signifie pouvoir jouer nimporte quelle case paire ou, en option, jouer une case impaire mais laisser votre adversaire jouer une case paire en retour.

Tactiques

La distinction impair / pair nous permet de jouer « stratégiquement » – un tas de coups à venir, en tout cas. Pour gagner de manière cohérente, nous devons combiner nos connaissances sur la stratégie à long terme avec de solides mouvements tactiques à court terme. Nous devons garder à lesprit de petits pièges comme celui-ci:

Règles

La stratégie gagnante réelle du jeu se résume à un ensemble de neuf règles basées sur les principes stratégiques abordés précédemment et sur la tactique.Les règles ont été développées par Victor Allis en 1988 – je pense quil a été la première personne à résoudre le jeu.

Les règles peuvent « t toujours trouver la solution optimale: parfois, il faudrait faire une véritable recherche parmi les possibilités, en grande partie pour traiter des problèmes tactiques.

Voici ce que je pense être les règles les plus importantes, avec les noms quAllis leur a donnés . Il existe quelques règles supplémentaires, mais elles concernent soit des cas particuliers, soit simplement des combinaisons de règles précédentes. Vous pouvez en savoir plus sur toutes les règles de la thèse: Une approche basée sur les connaissances de Connect Four .

• baseinverse : vous pouvez toujours réclamer lune des deux cases accessibles lorsque votre adversaire revendique lautre, vous pouvez donc toujours bloquer une case à quatre en ligne qui a besoin de deux cases comme ça. Par exemple, le rouge peut toujours jouer un des carrés verts après que le bleu joue le o ther:

• vertical : vous pouvez toujours bloquer un quadruple vertical en jouant lun des deux carrés directement lun au-dessus de lautre. Le rouge peut toujours bloquer le quadruple vertical sur d en jouant lun des carrés en surbrillance:

• claimeven : celui qui contrôle le jeu (cest-à-dire rouge sauf si le bleu a une menace étrange ) peut jouer un carré sur une ligne paire (tant que ce carré nest pas immédiatement jouable). Cette règle incarne la stratégie de base pair / impair.
• aftereven : si vous avez le contrôle et que vous avez une menace dans une rangée paire, vous pourrez jouer cette ligne via claimeven. Cela signifie que toutes les menaces de la même colonne au-dessus de celle-ci sont bloquées. Par exemple, ici bleu ne pourra pas jouer b3 car le rouge a une menace sur b2:

• lowinverse : sil y a deux colonnes avec un nombre impair douvertures carrés, le résultat est pair. Sil y a deux carrés impairs es dans de telles colonnes qui ne sont pas directement jouables, quiconque contrôle le jeu pourra jouer au moins à lune dentre elles. Cela peut également sappliquer aux cases qui sont loin dêtre jouables et non côte à côte. Dans ces deux exemples simples, le rouge peut obtenir au moins lun des deux carrés surlignés:

Gagner

Le jeu a en fait été résolu grâce à une combinaison de ces règles et une recherche exhaustive – les règles en elles-mêmes ne sont malheureusement pas suffisantes.

De nombreuses règles dépendent du contrôle du jeu. Puisque le rouge a le contrôle au départ, le bleu ne peut pas utiliser la plupart des règles jusquà ce quils parviennent à établir une menace étrange. Bleu peut établir une menace étrange en utilisant certaines des règles qui ne dépendent pas du contrôle ou simplement dune pensée tactique comme la combinaison de groupes de deux pièces pour garantir une menace étrange à lavenir.

Il savère que le premier le joueur peut le faire contre un jeu optimal tant que le premier coup est d1. Cela signifie que le premier joueur peut toujours gagner. La recherche qui a établi cela est également détaillée dans la thèse.

Pour les joueurs humains, ce type de logique est difficile à travailler. Heureusement, quelquun dautre a trouvé un ensemble de bonnes ouvertures que vous pouvez généralement utiliser: Expert Play dans Connect-Four .

De plus, jai réalisé toutes les illustrations en utilisant le merveilleux paquetage de diagrams de Haskell. En fait, toute cette réponse était en fait un exercice juste pour apprendre à utiliser la bibliothèque, ce que je voulais faire depuis un moment! Vous pouvez jeter un oeil au code sur lessentiel. Le code est compliqué, mais cest une excellente démonstration que, contrairement à la croyance populaire, Haskell est en fait génial pour le prototypage interactif et lécriture de code jetable.

De plus, je pense que cest cool de voir comment Emacs peut prévisualiser les SVG et les PNG dans un tampon, me donnant essentiellement un environnement sur mesure pour développer des images comme celle-ci: