IA tic-tac-toe

tictactoeUn jeu simple

Le tic-tac-toe, (souvent appelé morpion mais d’après wikipedia ce serait une erreur) fait partie des jeux les plus simples qui soient. D’une part du point de vue des règles qui sont extrêmement simples, mais aussi par l’aspect combinatoire. Il y a peu de jeux où le nombre de parties possibles est aussi restreint. C’est donc un très bon candidat pour s’initier à l’écriture d’une intelligence artificielle.

Nombre de positions possibles

Le nombre de positions possibles est un indicateur intéressant pour savoir la taille que prendrait une base de données recensant, par exemple, le meilleur coup à jouer pour chaque position.

Le plateau est composé de 9 cases, chacune pouvant être soit vide, soit remplie par un X ou un O. Il y a donc au maximum 39 = 19 683 positions possibles. Mais en réalité, ce nombre est largement surestimé. En effet, à supposer que le joueur qui commence est X, une position valide contient soit autant de X que de O, soit un X de plus.

Le véritable nombre de positions possibles peut se calculer relativement facilement en calculant d’abord le nombre de positions différentes après 0, 1, … 9 coups puis en sommant ces 10 termes. Le résultat est le onzième terme de la suite https://oeis.org/A005773 et vaut 6046.

A noter que ce chiffre peut encore être réduit si l’on supprime les positions qui sont symétriques. Par exemple, le premier coup peut placer un X dans 9 cases, produisant 9 positions différentes. Mais en réalité, seules 3 possibilités sont réellement distinctes: un coin, un bord ou le centre. Les 4 coins et les 4 bords sont symétriques par une rotation du plateau.

En tenant compte de ces symétries, le nombre de positions distinctes tombe à 1303, un nombre qui s’obtient facilement en écrivant un programme les générant toutes. Cela signifie qu’un dictionnaire de toutes les positions possibles et du meilleur coup associé ne prendrait que peu de place.

Nombre de parties possibles

Le nombre de parties possibles permet de se faire une idée du coût d’une recherche exhaustive des meilleurs coups. En parcourant toutes les parties possibles, on va nécessairement passer par toutes les positions possibles, mais on peut arriver de plusieurs manières à la même position. Le nombre de parties possibles pourrait donc a priori être plus grand ou plus petit que le nombre de positions possibles.

Pour le premier coup, le joueur X a 9 cases qu’il peut jouer. Pour le suivant, le joueur O a 8 cases qu’il peut jouer. Et ainsi de suite jusqu’au dernier coup. Il y’a donc au maximum 9! = 362880 parties possibles et leur recherche exhaustive nécessite de passer par 9!/9! + 9!/8! + 9!/7! + 9!/6! + 9!/5! + +9!/4! + +9!/3! + 9!/2! + 9!/1 = 623530 grilles intermédiaires à ajouter aux grilles finales pour obtenir un total de 986409 grilles examinées.

Mais en réalité, certaines parties s’interrompent avec un vainqueur avant que la grille soit remplie (après au moins 5 coups, nombre minimal pour placer 3 pions identiques), réduisant drastiquement les nombres de parties et de grilles à examiner. Une recherche exhaustive montre qu’il y a 255168 parties possibles pour un total de 549945 grilles examinées.

Cependant, en tenant compte des symétries:

    • Au premier coup, il y a seulement 3 choix possibles (coin, bord ou centre)
    • Au deuxième coup
        • Si le premier coup était au centre, il n’y a que 2 choix possibles (coin ou bord)
      • Si le second coup était au bord ou dans un coin, il y a 5 choix possibles (coin adjacent, coin opposé, bord adjacent, bord opposé, centre)
  • Etc…

La symétrie continue de réduire le nombre de possibilités significativement. Ainsi après le deuxième coup, sur les 12 positions, 6 présentent un axe de symétrie ne laissant que 4 possibilités à tester au lieu de 7. Soit 66 parties à considérer au lieu de 504.

Au final, on arrive à un total de 26950 parties possibles pour un total de 58747 grilles examinées. Un jeu d’enfant pour un ordinateur !

Faire jouer l’ordinateur

Afin de faire jouer l’ordinateur à un jeu, il y a plusieurs approches possibles.

Fournir des instructions

On peut par exemple écrire un certain nombre de règles permettant de décider du coup à jouer. Pour le tic-tac-toe, ces règles pourraient être (à appliquer dans l’ordre):

  • Si la prise d’une case permet de réaliser un alignement (et donc de gagner), choisir cette case
  • Si le joueur peut compléter un alignement en prenant une case au prochain coup, choisir cette case
  • Si le centre est libre, prendre le centre
  • Si un coin est libre prendre ce coin
  • Sinon prendre une des cases restantes (un bord)

Ces règles ne précisent pas quel coin ou quel bord prendre, ni quelle case prendre si plusieurs permettent de gagner ou permettent à l’adversaire de gagner. L’ordinateur peut simplement parcourir les cases dans un ordre donné et prendre la première qui correspond. Dans les deux premiers cas, cela n’a pas d’importance (la partie est gagnée où le joueur n’a pas le choix) mais dans les deux premiers les règles pourraient être affinées si cela s’avère utile. De plus, prendre le centre plutôt qu’un coin n’est pas nécessairement la meilleure stratégie.

En pratique, ces règles marchent relativement bien (un programme qui les utilise ne semble pas trop mal jouer) mais il lui arrive quand même de perdre ! Et une fois la faille trouvée par l’adversaire, il est facile de rejouer sans cesse la même partie et de gagner systématiquement.

Dans l’exemple ci-dessus, les règles ont été définies de manière intuitive. C’est pour cela qu’elle peuvent être (et sont) faillibles. Il est possible dans certain cas (le puissance 4 étant un exemple) d’établir des règles en prouvant qu’elles garantissent de gagner si on les applique. Cette approche s’avère alors non seulement très efficace mais aussi plus enrichissante que celles qui suivent car on a extrait un savoir concret sur le jeu (dans les autres approches, l’ordinateur sait jouer mais le développeur, lui, ne sait pas mieux jouer après avoir écrit son programme). Elle est par contre moins générique (les règles ne sont a priori valables que pour ce jeu) et à mon goût, moins fascinante.

Apprendre à apprendre

On peut aussi imaginer écrire un programme qui apprenne au fur et à mesure des parties. Il commence par jouer des coups au hasard, mais lorsqu’il retombe sur une situation qu’il connait, il rejoue les coups qu’il a observés comme étant gagnants ou évite les coups qui l’ont amené à perdre.

Ce type d’approche englobe en réalité un grand nombre d’algorithmes d’efficacité et de complexité variées. L’idéal est de réussir à écrire un programme qui parvienne à apprendre rapidement et dont l’apprentissage ne puisse pas être faussé.

Faire explorer tous les coups

L’intérêt d’un ordinateur, c’est sa capacité à réaliser en quelques secondes et sans erreur des millions d’opérations répétitives qu’un humain mettrait plusieurs années à réaliser et dans lequel se glisseraient bon nombre d’étourderies.

Il est donc naturel, pour le faire gagner à un jeu, de vouloir lui faire essayer tous les coups possibles et pour chacun, d’essayer tous les coups que peut jouer l’adversaire et ainsi de suite jusqu’à aboutir à une victoire, une défaite ou un nul.

Il suffit ensuite de considérer que l’adversaire va toujours jouer au mieux et donc, lorsque c’est son tour, appliquer la même logique pour choisir son coup. Cette approche est l’algorithme minimax dont le nom vient du fait que l’adversaire choisit toujours le coup ayant le score minimal alors que l’on choisira toujours le coup ayant le score maximal.

C’est cette approche que nous allons mettre en pratique par la suite.

Mélanger les approches

Pour des jeux complexes, il est intéressant de mélanger les approches. Explorer systématiquement tous les coups sur des jeux comme les échecs ou le go est hors de portée des ordinateurs actuels (et le restera probablement pendant très longtemps). On peut cependant explorer en s’arrêtant aux N coups suivants et estimer si la situation atteinte est meilleure ou moins bonne que les autres.

Cette estimation du « score » d’une position peut être basée sur des règles ou peut être construite par un apprentissage à l’aide d’une base de donnée de positions et évoluer au fil des parties afin de s’améliorer.

Pour certains jeux, comme les échecs, une base de donnée de moments critiques de la partie, comme les ouvertures, peut aussi se révéler utile.

Minimax pour tic-tac-toe

Voici le tic-tac-toe en python implémentant minimax en tenant compte des symétries et permettant de jouer entre humains, contre l’ordinateur ou de faire jouer l’ordinateur contre lui même. Cette dernière possibilité n’est pas aussi amusante qu’il y parait, l’ordinateur rejouant en boucle la même partie !

Le joueur humain peut placer ses pions à l’aide de la souris.

Les fonctions suivantes sont disponibles:

  • F1: change le mode de jeu pour le joueur 1 (alterne entre ordinateur et humain)
  • F2: change le mode de jeu pour le joueur 2
  • R: recommencer une nouvelle partie
  • Shift+R: activer/désactiver le redémarrage automatique de partie
  • Echap: quitter
  • U: diminuer la profondeur de recherche de l’IA pour le joueur 1
  • Shift+U: augmenter la profondeur de recherche de l’IA pour le joueur 1
  • D: diminuer la profondeur de recherche de l’IA pour le joueur 2
  • Shift+D: augmenter la profondeur de recherche de l’IA pour le joueur 2

L’intelligence artificielle est réactive mis à part sur les deux premiers coups où l’on observe une certaine latence. Une option simple pour améliorer cette réactivité est de cacher les résultats, soit à chaque exécution du programme dans un dictionnaire en mémoire, soit une fois pour toutes en les stockant dans un fichier et en les rechargeant au démarrage.

Pour aller plus loin …

Une manière de voir le cache des meilleurs coups à jouer:

Rendre le tic-tac-toe intéressant ?

Cette entrée a été publiée dans Divertissements, Informatique, Intelligence artificielle. Vous pouvez la mettre en favoris avec ce permalien.

4 réponses à IA tic-tac-toe

  1. Matt dit :

    Bonjour.
    Vous paraissez le plus compétent sur la question, les autres forums ne considérant pas la symétrie et les parties finies au 5 ème coup. J ‘ai un doute sur le chiffre de 576 parties nulles ou sans gagnants que j’ ai calculé. Pourriez vous confirmer. Merci
    Autrement je ne comprend pas pq sur le nb total en choix aléatoire qui intègre aussi les parties qui devraient s’arrêter vous faites : 9! = 362880 parties possibles et leur recherche exhaustive nécessite de passer par 9!/9! + 9!/8! + 9!/7! + 9!/6! + 9!/5! + +9!/4! + +9!/3! + 9!/2! + 9!/1 = 623530 gr. N est ce pas l’un ou l’autre ? Cad recherche exhaustive par rapport au nb de combi aleatoire

    • Colin Pitrat dit :

      Bonjour,

      vous parlez bien de parties et non juste de positions? Je ne trouve pas exactement la même valeur que vous.

      En ce qui concerne les positions, en supposant que X commence, une partie nulle est forcément une grille pleine qui contiendra donc 5 X et 4 O. L’idée est donc de compter le nombre de grilles contenant cette répartition qui n’ait ni ligne, ni colonne, ni diagonale d’une seule couleur.

      Cela ne laisse que 6 possibilités pour la première ligne: XXO, XOX, OXX, XOO, OXO, OOX. De même pour la deuxième ligne. Mais certaines combinaisons des 2 lignes ne laissent aucune possibilité pour la 3è ligne. Au total, sauf erreur de ma part, il n’y a que 16 grilles possibles en fin de partie, sans exclure les symétries.
      En excluant les symétries, il n’en reste plus que 3:

      X|X|O
      O|X|X
      X|O|O

      X|X|O
      O|O|X
      X|X|O

      X|X|O
      O|O|X
      X|O|X

      Maintenant, combien de parties permettent de les atteindre? Pour chacune, X à 5 choix pour le premier coup, puis 4, puis 3, etc … De même pour O en commençant à 4. Cela donne donc 144 possibilités de parties pour chaque grille.

      Soit un total de 3*144 = 432.

      Lorsque je parle de 9! parties possibles, c’est une première borne supérieure. Comme je le dis just après: « Mais en réalité, certaines parties s’interrompent avec un vainqueur avant que la grille soit remplie (après au moins 5 coups, nombre minimal pour placer 3 pions identiques), réduisant drastiquement les nombres de parties et de grilles à examiner. Une recherche exhaustive montre qu’il y a 255168 parties possibles pour un total de 549945 grilles examinées. »

      C’est une façon détournée de dire que j’ai arrêté l’approche mathématique à la borne supérieure donnée par 9! et que je me suis tournée vers la force brute pour une valeur exacte 🙂

  2. rich dit :

    Colin;
    i saw a comment of yours about Loop-quantum gravity as cellular automaton. I was soooo happy to hear that someone else was considering this. Have you had any luck on this?

    Abundant Thanks;
    rich e

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

+ thirty eight = forty seven