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 derniers cas, cela n’a pas d’importance (la partie est gagnée ou perdue de toute façon) mais dans les deux premiers les règles pourraient être affinées si cela s’avère utile.

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. Vous pouvez la mettre en favoris avec ce permalien.

Laisser un commentaire

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

+ soixante = soixante-dix

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>