2 Jeux

Nous considérons ici les jeux

déterministes : sans hasard (sauf ici) ;
à information parfaite : tous les éléments sont connus de tous les joueurs ;
à deux joueurs : un contre l’autre (le mode coopératif peut se formuler comme une résolution de problème).

Exemples de jeux qui entrent dans ce cadre :

2.1 Formalisation d’un jeu

Un jeu comprend les éléments suivants :

une définition de l’état du jeu (la concaténation des variables susceptibles d’évoluer au cours d’une partie, par exemple : la position des pièces, tour du joueur… ) ;
un état initial dans lequel la partie commence ;
une liste de coups ou actions possibles pour chaque état (ou une fonction de l’état qui retourne cette liste) ;
un fonction de transition d’un état à l’autre en fonction du coup joué ;
un test de terminaison pour détecter si l’état correspond à une fin de partie ;
une fonction de récompense qui retourne le score en fonction de l’état atteint en fin de partie (par ex. \{+1,0,-1\} pour gagné, match nul ou perdu).

2.2 Arbre de jeu

Un arbre de jeu se définit comme un arbre de recherche où

chaque nœud contient un état du problème ;
chaque branche correspond à une action (un coup) possible à partir de cet état ;
la racine contient l’état initial de la réflexion ;

mais avec un élément supplémentaire :

chaque niveau/profondeur de l’arbre est associé à un joueur (celui qui doit jouer).

Cette différence est essentielle car l’adversaire agit sur le résultat : il ne suffit pas de prendre un chemin qui mène à la meilleure récompense, mais il s’agit de prendre un chemin qui mène à une bonne récompense quelles que soient les actions de l’adversaire.

Note

À chaque tour de jeu de l’ordinateur, celui-ci construit un arbre de jeu dans le but de trouver un tel chemin. Ainsi, l’état initial stocké dans la racine de l’arbre n’est pas l’état initial de la partie, mais l’état courant de la partie lorsque c’est à l’ordinateur de jouer.

2.3 Minimax et ses variantes

L’algorithme Minimax permet de calculer le coup à jouer pour l’ordinateur à partir d’un arbre de jeu.

Le problème ici est que l’algorithme ne contrôle pas les décisions de l’adversaire. En fait, l’algorithme ne peut même pas savoir comment va jouer l’adversaire, et il est donc difficile de prédire ce qu’il va se passer si l’on joue tel ou tel coup.

Pour pouvoir s’en sortir, il est donc nécessaire de faire des hypothèses sur la manière de jouer de l’adversaire.

2.3.1 Algorithme minimax

L’algorithme minimax adopte une stratégie au pire cas, c’est-à-dire qu’il travaille sous l’hypothèse que l’adversaire joue toujours le mieux possible, et donc de manière optimale.

Faire cette hypothèse permet deux choses :

l’algorithme peut calculer les coups de l’adversaire à l’avance ;
si l’adversaire ne joue pas comme prévu, alors il ne peut que jouer moins bien, et donc de manière plus avantageuse pour l’ordinateur que ce que l’algorithme avait prévu.

Cette stratégie permet donc de calculer le coup optimal avec des garanties sur le score obtenu en fin de partie.

Pour cela, l’algorithme calcule, récursivmenet à partir des feuilles, une valeur numérique (la valeur minimax) pour chaque nœud de l’arbre et détermine le coup à jouer comme celui qui maximise la valeur parmi l’ensemble des fils de la racine.

La valeur d’un nœud se calcule de trois manières différentes, en fonction du type de nœud:

pour un nœud Max (c’est à l’ordinateur de jouer) : le maximum des valeurs des fils ;
pour un nœud Min (c’est à l’adversaire de jouer) : le minimum des valeurs des fils ;
pour une feuille (fin de partie) : la récompense (score de fin).

2.3.1.1 Complexité du minimax

Puisque l’algorithme effectue un calcul dans chaque nœud, les deux facteurs principaux qui influencent la complexité du minimax sont :

le facteur de branchement moyen b
environ 10 au reversi, 35 aux échecs, 360 au Go
la profondeur de l’arbre n
60 au reversi, environ 40 aux échecs et 400 au Go

La complexité est donc :

le nombre de nœuds en O(b^n) pour la complexité en temps ;
la taille d’une branche en O(bn) pour la complexité en espace (car l’algorithme travaille récursivement branche par branche).

La complexité en temps est ici bien trop grande pour être raisonnable pour la plupart des jeux connus et les variantes ci-dessous permettent de réduire les facteurs b et n.

2.3.2 Algorithme alpha-beta (réduire b)

L’idée de l’algorithme alpha-beta est d’élaguer l’arbre pour éviter d’explorer des branches inutiles. Ces branches inutiles sont celles qui ne seraient jamais jouées par des joueurs qui adoptent une stratégie optimale.

Il peut sembler difficile de les détecter avant d’avoir calculé la stratégie optimale, mais en réalité, on peut utiliser le fait que l’algorithme minimax parcourt l’arbre récursivmeent, et donc en profondeur d’abord. Ainsi, certaines informations sur une branche peuvent être obtenues avant de descendre dans une autre et utilisées pour couper des branches alternatives inutiles.

L’algorithme Alpha-beta peut s’écrire avec deux fonctions presque identiques à celles utilisées par minimax et simplement deux variables supplémentaires : \alpha et \beta qui enregistrent les informations utiles des branches précédentes.

Initialiser alpha = -inf, beta = inf

Fonction valeurMax ( noeud, alpha, beta ) 
    v = -inf
    Pour chaque fils de noeud:
        calculer sa valeur et le max courant :
          v = max ( v, valeurMin(fils, alpha, beta) )
        Si v >= beta, retourner v
        alpha = max( alpha, v )
    Retourner v
    
Fonction valeurMin ( noeud, alpha, beta ) 
    v = inf
    Pour chaque fils de noeud
        calculer sa valeur et le min courant :
          v= min ( v, valeurMax(fils, alpha, beta))
        Si v <= alpha, retourner v
        beta = min( beta, v )
    Retourner v

Note

L’algorithme alpha-beta permet de gagner du temps pour un coût presque nul (deux variables et quelques tests) sans perdre aucune garantie sur la qualité de la solution.

En effet, seules les branches dont les valeurs ne peuvent pas influencer la décision finale sont supprimées.

2.3.3 Limitation de profondeur (réduire n)

La limitation de profondeur est une technique très simple pour gagner énormément de temps : il suffit de ne pas explorer l’arbre jusqu’aux feuilles (fins de parties), mais uniquement jusqu’à une certaine profondeur prédéterminée (10 par exemple).

Le problème ici est que les valeurs des récompenses obtenues pour les feuilles ne sont plus accessibles et aucun calcul n’est possible. Pour contourner ce problème, on utilise une fonction d’évaluation qui se charge d’estimer la valeur des nœuds non terminaux au niveau de la profondeur maximale autorisée.

Pour être utile, cette fonction d’évaluation doit avoir les propriétés suivantes :

être rapidement calculable ;
être représentative des chances de gagner pour l’ordinateur à partir de l’état considéré.

Dans les jeux à somme nulle (où les joueurs ont des positions symétriques et jouent avec le même type de pièces et d’actions possibles), on découpe généralement cette fonction ainsi : evaluation(etat) = evalJoueur(Max) - evalJoueur(Min) à l’aide d’une fonction intermédiaire chargée d’évaluer la position d’un joueur en particulier. Celle-ci peut par exemple simplement compter le nombre de pièces d’un joueur dans les cas les plus simples.

Avertissement

Contrairement à alpha-beta, utiliser la limitation de profondeur ne permet plus de garantir le score de fin de partie et l’optimalité de la décision.

En effet, tous les calculs sont basés sur la fonction d’évaluation qui n’est qu’une heuristique particulière.

2.3.4 Expectimax (pour les jeux avec du hasard)

Le hasard peut prendre différentes formes :

un coup ne donne le résultat prévu qu’avec une certaine probabilité ;
un tirage aléatoire pré-conditionne chaque coup ;

mais cela revient dans tous les cas à insérer un coup joué par le hasard entre les coups des adversaires.

Ainsi, on peut développer un arbre de jeu probabiliste contenant des nœuds chance sur des couches intermédiaires associées au hasard entre chaque couche d’un arbre de jeu classique. Dans cet arbre, les branches qui descendent d’un nœud chance sont étiquetées avec les probabilités d’être tirées au hasard.

Par exemple, si chaque joueur doit lancer un dé avant de jouer, 6 branches sont crées avec les probabilités 1/6.

L’algorithme Expectimax fonctionne ensuite comme l’algorithme minimax avec une nouvelle règle pour ces nœuds chance : la valeur du nœud est la moyenne pondérée des valeurs sur l’ensemble des fils, où la pondération est donnée par les probabilités de chacune des actions tirées au sort.

2.4 Algorithme MCTS

À venir…