Quel algorithme pour un jeu de morpion puis-je utiliser pour déterminer le "meilleur coup" pour l'IA ?

Question

Dans une mise en œuvre du morpion, je suppose que le défi consiste à déterminer le meilleur coup à jouer par la machine.

Quels sont les algorithmes qui peuvent être poursuivis ? Je cherche des implémentations allant du plus simple au plus complexe. Comment pourrais-je m'attaquer à cette partie du problème ?

Answer 1

La stratégie proposée par Wikipedia pour jouer une partie parfaite (victoire ou égalité à chaque fois) semble être un pseudo-code simple :

Citation de Wikipédia (Tic Tac Toe#Stratégie)

Un joueur peut jouer une partie parfaite de morpion (pour gagner ou, au moins, faire match nul) s'il choisit à chaque tour le premier coup disponible de la liste suivante, telle qu'elle est utilisée dans le programme de morpion de Newell et Simon de 1972[6].

1. Gagner : si vous en avez deux d'affilée, jouez le troisième pour obtenir trois d'affilée.

2. Blocage : Si l'adversaire en a deux d'affilée, jouez le troisième pour les bloquer.

3. Fourchette : Créez une opportunité où vous pouvez gagner de deux façons.

4. Bloquer la fourchette de l'adversaire :

   Option 1 : En créer deux à la suite pour forcer l'adversaire à se défendre, tant que que cela n'aboutisse pas à la création une fourchette ou une victoire. Par exemple, si "X" a un coin, que "O" a le centre, et que "X" a également le coin opposé, "O" ne doit pas jouer un coin afin de gagner. (Jouer un coin dans ce scénario crée une fourchette pour que "X" gagne. gagner).

   Option 2 : S'il y a une configuration où l'adversaire peut bifurquer, bloquer cette bifurcation.

5. Centre : Jouez le centre.

6. Coin opposé : Si l'adversaire est dans le coin, jouez le coin opposé. opposé.

7. Coin vide : Jouez un coin vide.

8. Côté vide : Jouez un côté vide.

La reconnaissance de ce à quoi ressemble une situation de "bifurcation" pourrait être effectuée de manière brute comme suggéré.

Remarque : un adversaire "parfait" est un bon exercice, mais il ne vaut pas la peine de "jouer" contre lui. Vous pouvez cependant modifier les priorités ci-dessus pour donner des faiblesses caractéristiques aux personnalités des adversaires.

Answer 2

Ce dont vous avez besoin (pour le morpion ou un jeu beaucoup plus difficile comme les échecs), c'est de l'option algorithme minimax ou sa variante légèrement plus compliquée, élagage alpha-beta . Un minimax naïf ordinaire fera l'affaire pour un jeu dont l'espace de recherche est aussi petit que le morpion, cependant.

En bref, il ne s'agit pas de rechercher le déménagement qui a le meilleur résultat possible pour vous, mais plutôt le déménagement où le pire résultat possible est le meilleur possible. Si vous supposez que votre adversaire joue de manière optimale, vous devez supposer qu'il choisira le coup le plus défavorable pour vous, et vous devez donc choisir le coup qui minimise son gain maximal.

Answer 3

La méthode de force brute consistant à générer toutes les planches possibles et à les noter en fonction des planches qu'elles produisent ensuite plus bas dans l'arbre ne nécessite pas beaucoup de mémoire, surtout si l'on sait que les rotations de planches à 90 degrés sont redondantes, tout comme les retournements sur l'axe vertical, horizontal et diagonal.

Une fois que vous en êtes arrivé là, il y a quelque chose comme moins de 1 000 données dans un graphique en arbre pour décrire le résultat, et donc le meilleur mouvement pour l'ordinateur.

-Adam

Answer 4

Un algo typique pour le morpion devrait ressembler à ceci :

Board : Un vecteur à neuf éléments représentant la planche. Nous stockons 2 (indiquant blanc), 3 (indiquant X), ou 5 (indiquant O). Tour : Un nombre entier indiquant quel coup du jeu est sur le point d'être joué. Le 1er coup sera indiqué par 1, le dernier par 9.

L'algorithme

L'algorithme principal utilise trois fonctions.

Make2 : renvoie 5 si la case centrale de l'échiquier est vide c'est à dire si board[5]=2 . Sinon, cette fonction renvoie un carré quelconque qui n'est pas un coin. (2, 4, 6 or 8) .

Posswin(p) : Retourne 0 si le joueur p ne peut pas gagner à son prochain coup ; sinon, elle renvoie le numéro de la case qui constitue un coup gagnant. Cette fonction permettra au programme à la fois de gagner et de bloquer la victoire des adversaires. Cette fonction fonctionne en vérifiant chacune des lignes, des colonnes et des diagonales. En multipliant les valeurs de chaque case entre elles pour une ligne entière (ou une colonne ou une diagonale), on peut vérifier la possibilité d'un gain. Si le produit est 18 ( 3 x 3 x 2 ), alors X peut gagner. Si le produit est 50 ( 5 x 5 x 2 ), alors O peut gagner. Si une ligne (colonne ou diagonale) gagnante est trouvée, la case vide qui s'y trouve peut être déterminée et le numéro de cette case est renvoyé par cette fonction.

Go (n) : effectue un déplacement sur la case n. Cette procédure définit le conseil d'administration. [n] à 3 si Turn est impair, ou à 5 si Turn est pair. Il incrémente également Turn de 1.

L'algorithme a une stratégie intégrée pour chaque mouvement. Il effectue le coup impair s'il joue X le coup pair s'il joue O.

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

Je l'ai utilisé. Faites-moi savoir ce que vous en pensez.

Answer 5

Puisque vous n'avez affaire qu'à une matrice 3x3 d'emplacements possibles, il serait assez facile d'écrire une recherche dans toutes les possibilités sans taxer votre puissance de calcul. Pour chaque espace ouvert, calculez tous les résultats possibles après avoir marqué cet espace (de manière récursive, je dirais), puis utilisez le coup qui a le plus de chances de gagner.

Optimiser cela serait un gaspillage d'efforts, vraiment. Bien que certains faciles pourraient l'être :

• Vérifiez d'abord les victoires possibles pour l'autre équipe, bloquez la première premier que vous trouvez (s'il y en a 2, le jeu est de toute façon).
• Toujours prendre le centre s'il est ouvert (et la règle précédente n'a pas de candidats).
• Prendre les coins avant les côtés (à nouveau, si les règles précédentes sont vides)