Dans ce nouvel article, je vous propose d’apprendre à construire un programme capable de jouer au morpion en utilisant des techniques de machine learning. Bien que très simple, le jeu de morpion constitue dans les faits un très bon exemple pour apprendre à mettre en place des techniques de machine learning. Nous verrons donc brièvement en quoi le machine learning peut s’avérer plus pertinent que les algorithmes traditionnels sur un tel problème, et ensuite nous passerons à la pratique en développant notre programme. Nous apprendrons alors dans cette dernière partie à coder un programme capable de jouer contre lui-même au jeu du morpion.
Table des matières :
Pourquoi le machine learning ?
Pour développer un jeu comme le morpion, on pourrait être tenté d’adopter une approche itérative. En effet, on peut partir du principe que les règles sont assez simples à coder à première vue, dans la mesure où l’espace est limité en taille, et parce que la seule règle est d’aligner trois croix ou ronds soit en diagonale, soit à la verticale ou horizontale. Par ailleurs, il s’agit d’un jeu “fini” où les combinaisons pour gagner sont déjà connues. Pourtant et en dépit de sa relative simplicité, ce jeu peut offrir plusieurs dizaines voire centaines de configurations différentes. Le fait de coder ce jeu de façon assez traditionnelle (soit avec des règles explicites) va imposer d’énumérer les nombreux cas de figure possibles. On va devoir par exemple signaler les cas où deux éléments sont alignés, si deux éléments sont séparés uniquement par un espace vide à combler, prévoir des stratégies pour obtenir un match nul ou pour gagner etc… Cela peut être extrêmement fastidieux à coder. L’approche qui consiste à utiliser le machine learning va nous permettre au contraire de développer un programme beaucoup plus simple en fournissant à notre programme une certaine autonomie. L’objectif ici n’est donc plus de lui indiquer l’ensemble des règles et des exceptions à suivre, mais de disposer d’exemples (ou d’un semblant de logique) à partir desquels notre programme va pouvoir prendre des décisions avec une relative autonomie.
En nous basant sur ce que nous savons du machine learning, nous pourrions alors opter dans un premier temps pour une approche basée sur l’apprentissage (ou sur l’analyse) d’exemples et de contre-exemples. On pourrait décider ainsi de fournir de nombreux exemples de situation à notre programme pour lui permettre de savoir quand jouer tel ou tel coup. On pourrait également combiner avec cette approche des méthodes issues de l’apprentissage par renforcement. Cette méthode présente pourtant un inconvénient : c’est qu’il va falloir fournir un très grand nombre d’exemples à notre programme pour qu’il apprenne à reconnaître les meilleurs coups à jouer. Cette méthode n’est donc pas très économique. Par ailleurs, elle ne garantit pas une prise de décision optimale. Notre algorithme va simplement chercher des similitudes sans pour autant comprendre ce qu’il fait, si l’on peut s’exprimer ainsi.
Nous pouvons alors nous tourner vers d’autres méthodes qui consistent non pas à fournir des dizaines ou des centaines d’exemples à un programme, mais à lui permettre au contraire de se projeter dans les états futurs d’une configuration donnée pour prendre la meilleure décision possible. C’est notamment ce que permet l’algorithme Minimax qui est très largement appliqué dans l’univers des jeux comme le morpion.
Introduction à Minimax
Si on reprend l’exemple du morpion, l’algorithme va en quelque sorte déplier l’ensemble des coups possibles à la suite d’un mouvement jusqu’à atteindre un stade dit “terminal” (victoire, défaite ou match nul). Ces différents états sont évalués de façon négative ou positive par l’algorithme, un peu comme sous la forme d’une récompense, d’une punition ou encore d’une action neutre. L’algorithme sera alors amené à chaque fois à prendre la décision qui implique la plus forte récompense. Prenons un exemple simple avec cette première position au morpion :
X - -
X - O
O O X
Imaginons maintenant que ce soit à l’ordinateur de jouer pour les croix. La première étape de l’algorithme va alors consister à simuler les différents coups possibles. Ce qui nous donne l’ensemble des possibilités suivantes :
X X - X - X X - -
X - O X - O X X O
O O X O O X O O X
Les deux premières situations à gauche sont neutres, mais la troisième situation est par contre positive. On va alors stocker en mémoire le score des différentes situations. Notre algorithme va alors jouer à coup sûr le troisième coup. Le but de l’algorithme n’est pas seulement d’observer ce qui va se passer après un coup, mais de penser l’ensemble des coups possibles qui peuvent alors l’amener à une victoire ou une défaite par exemple. Ce travail va de pair avec ce que l’on appelle d’une part la maximisation et minimisation. Ce principe veut tout simplement dire qu’un joueur cherche à maximiser ses gains (donc jouer les coups qui lui permettent de se rapprocher d’une victoire), tandis que l’autre va chercher à minorer au maximum les gains possibles pour l’autre joueur (donc jouer des coups qui amèneront vers un match nul ou une victoire). Si vous avez par exemple un joueur A et joueur B, A cherchera à maximiser ses gains tandis que B sera à la recherche des coups pouvant limiter les gains du joueur A. Maintenant que nous savons comment fonctionne l’algorithme du Minimax, nous allons pouvoir passer à l’étape de programmation.
Implémenter l’algorithme Minimax
Nous allons donc maintenant mettre en place l’algorithme du Minimax pour développer un jeu de morpion doté d’une certaine capacité à prendre des décisions. Pour commencer, nous allons tout d’abord déclarer une variable “Grid” qui sera un tableau représentant notre grille de morpion :
var Grid = [
0, 1, 2,
3, 4, 5,
6, 7, 8
]
On déclare ensuite une variable “AIMove” dans laquelle nous allons stocker les mouvements de l’ordinateur :
var AIMove
Le jeu de morpion possède l’avantage d’être assez simple pour qu’on considère qu’il s’agit d’une victoire : il faut simplement que trois croix ou ronds soit alignés à la verticale, horizontale ou en diagonale. On va donc commencer par coder cette fonction qui a pour but de vérifier si nous avons à faire ou non à cette configuration. Commençons par déclarer une fonction “Win” :
function Win (Grid) {
On peut alors créer à l’intérieur de cette fonction une variable qui va contenir l’ensemble des alignements possibles. Nous allons déclarer une variable “WinSituation” qui va alors contenir le tableau suivant :
var WinSituation = [
[0,1,2],
[3,4,5],
[6,7,8],
[0,3,6],
[1,4,7],
[2,5,8],
[0,4,8],
[6,4,2]
]
Il suffit ensuite de créer une boucle pour itérer à travers l’ensemble de ces propositions pour vérifier le contenu de ces cases. Si ces cases contiennent à chaque fois une croix ou un rond, on sait qu’il s’agit d’une victoire. On commence donc d’abord par créer une boucle pour itérer à travers l’ensemble des situations possibles :
for (var i = 0; i < WinSituation.length; i++) {
On récupère ensuite un ensemble à tester que l’on va conserver dans une variable “TestRow”. Il faut également stocker les valeurs contenues dans cet ensemble. On va alors créer une valeur “RowValues” :
var TestRow = WinSituation[i]
var RowValues = []
On met alors en place une deuxième boucle pour itérer à travers cet ensemble. On va alors pousser l’ensemble de ces éléments dans la variable “RowValues”. Une fois que cela est fait, nous allons mettre en place les deux fonctions pour savoir si toutes les cases sont occupées par des croix ou par des ronds. En fonction du résultat nous pouvons alors retourner la valeur correspondante (“1” si les croix gagnent, “-1” pour les ronds) :
for (var j = 0; j < TestRow.length; j++) {
RowValues.push(Grid[TestRow[j]])
}
var CrossesWin = function (Value) {
return Value === 'X'
}
var NoughtsWin = function (Value) {
return Value === 'O'
}
if ( RowValues.every(CrossesWin) ) {
return 1
} else if ( RowValues.every(NoughtsWin) ) {
return -1
}
}
Maintenant que nous disposons de notre fonction pour vérifier qu’il y a une victoire ou non, nous allons pouvoir commencer à coder notre fonction qui va nous servir à mettre en place l’algorithme Minimax. Pour ce faire, commençons par déclarer la fonction “Minimax” :
function Minimax (NewGrid, Player) {
La première chose à faire est de vérifier que des cases sont encore libres pour jouer. On déclare donc une variable “Available” qui nous retourner toutes les valeurs du jeu qui sont égales à des nombres :
var Available = NewGrid.filter( function(a) {
return typeof a === 'number'
})
Nous allons ensuite avoir besoin de savoir quelle est la situation du jeu. Pour ce faire nous allons vouloir faire appel à notre fonction “Win” sous la forme de conditions, et nous retournons la valeur correspondante. Si toutes les cases sont occupées (soit si la variable “Available” ne contient aucun élément) nous retournons une valeur de 0 :
if ( Win(NewGrid) === 1 ) {
return 1
} else if ( Win(NewGrid) === -1 ) {
return -1
} else if (Available.length === 0) {
return 0
}
Une fois que cela est fait, nous allons pouvoir passer à l’étape qui consiste à simuler les mouvements possibles. Nous allons devoir consigner ces mouvements ainsi que les scores correspondants. Nous déclarons les variables “Moves” et “Scores” :
var Moves = []
var Scores = []
Nous allons ensuite pouvoir itérer à travers les cases disponibles. Nous mettons donc en place une boucle pour itérer à travers la variable “Available” :
for (var i = 0; i < Available.length; i++) {
Nous déclarons à la suite une variable “Move” dans laquelle nous allons stocker le coup correspondant car nous aurons besoin plus tard :
var Move
On va donc ensuite passer dans cette variable “Move” la position du coup disponible de cette façon :
Move = NewGrid[Available[i]]
Il faut ensuite modifier le contenu de la grille en y inscrivant ensuite soit une croix ou un rond de la façon suivante :
NewGrid[Available[i]] = Player
On fait alors appel à la fonction “Minimax” avec le joueur adverse. Si ce sont les croix qui sont en train de jouer, nous faisons appel aux ronds. Et vice versa. Nous poussons ensuite les résultats obtenus dans la variable “Scores” :
if (Player === 'X') {
Scores.push(Minimax(NewGrid, 'O'))
} else {
Scores.push(Minimax(NewGrid, 'X'))
}
Il faut ensuite rétablir l’état de la grille. On remet donc en état la grille en remplaçant le contenu par la variable “Move” (qui contient le numéro du coup). Puis on passe ensuite ce coup dans la variable “Moves”, puis on ferme la boucle :
NewGrid[Available[i]] = Move
Moves.push(Move)
}
Nous avons ensuite besoin de faire remonter le meilleur coup (ou le coup qui permet de minimiser les gains de l’adversaire). Nous allons donc ici partir du principe que ce sont les croix qui souhaitent maximiser leur score. Nous allons donc faire remonter le meilleur score en recherchant le maximum dans la variable “Scores” et en le stockant dans la variable “HighScore”. Nous recherchons ensuite la position de ce meilleur score et nous la stockons dans la variable “HighScoreIndex”. Nous assignons à la variable “AIMove” le numéro du mouvement qui correspond au scorele plus élevé. Et enfin nous retournons le score le plus élevé :
if (Player === 'X') {
var HighScore = Math.max(…Scores)
var HighScoreIndex = Scores.indexOf(HighScore)
AIMove = Moves[HighScoreIndex]
return Scores[HighScoreIndex]
Puis on fait la même chose si c’est l’autre joueur qui joue. Il s’agit ici au contraire de réaliser une minimisation. Nous récupérons le score le plus bas que nous stockons dans la variable “LowScore”. Nous récupérons la position de ce score et nous la stockons dans une variable “LowScoreIndex”. Puis nous assignons à la variable “AIMove” le mouvement correspondant à la position du score le plus bas. Et enfin nous retournons ce score :
} else {
var LowScore = Math.min(…Scores)
var LowScoreIndex = Scores.indexOf(LowScore)
AIMove = Moves[LowScoreIndex]
return Scores[LowScoreIndex]
}
}
Maintenant que notre fonction “Minimax” et “Win” sont programmées, nous allons pouvoir faire appel à ce programme. L’ordinateur va jouer contre lui-même. L’initiative appartiendra aux croix. Nous ajoutons alors le code suivant :
var Play = 1
var Turn = 1
var AI
while (Play !== 0) {
var Available = Grid.filter(function (a) {
return typeof a === 'number'
})
if ( (Win(Grid) === 1) || (Win(Grid) === -1) || (Available.length === 0) ) {
Play = 0
} else {
if (Turn === 1) {
AI = 'X'
Turn = 0
} else {
AI = 'O'
Turn = 1
}
var Choice = Minimax(Grid, AI)
Grid[AIMove] = AI
console.log('\n')
console.log(Grid[0],Grid[1],Grid[2])
console.log(Grid[3],Grid[4],Grid[5])
console.log(Grid[6],Grid[7],Grid[8])
}
}
Si vous lancez ensuite le programme, vous pourrez alors obtenir la partie suivante. Les mouvements de l’ordinateur sont mis en valeur en rouge :
X 1 2
3 4 5 Tour des croix
6 7 8
X 1 2
3 O 5 Tour des ronds
6 7 8
X X 2
3 O 5 Tour des croix
6 7 8
X X O
3 O 5 Tour des ronds
6 7 8
X X O
3 O 5 Tour des croix
X 7 8
X X O
O O 5 Tour des ronds
X 7 8
X X O
O O X Tour des croix
X 7 8
X X O
O O X Tour des ronds
X O 8
X X O
O O X Tour des croix | Match nul
X O X
Vous venez donc d’apprendre à créer un programme capable de jouer au morpion en utilisant une technique d’optimisation par maximisation et minimisation qui consiste à rechercher de façon exhaustive l’ensemble des positions possibles pour prendre la meilleure décision. Vous noterez que quelque soit la configuration, les matchs machine contre machine aboutissent continuellement à un match nul. Vous pouvez également faire des tests avec quelques coups jouées d’avance pour voir comment travaille l’algorithme dans d’autres situations.
Conclusions
Nous avons donc vu ici le fonctionnement de l’algorithme Minimax en l’appliquant sur un problème concret comme le jeu du morpion et nous avions appris à le mettre en œuvre avec un programme développé en Javascript. Il s’agit donc d’un algorithme relativement simple à mettre en œuvre. Cet algorithme présente toutefois des limites importantes. Il se borne en effet à des jeux alternés, où il est possible de prédire l’ensemble des états, où l’environnement du jeu est totalement observable et à sommes nulles (ce qui veut dire que les situations sont soient favorables ou défavorables). Par ailleurs, il existe également des jeux où observer l’ensemble des états possibles peut être très coûteux (comme par exemple le Go et les échecs) ce qui implique de limiter l’exploration des possibilités.
Simon CHABROL 
Laisser un commentaire