---
title: "IA : Pour les jeux"
date: 2023-10-10
tags: ["IA", "jeux"]
categories: ["Intelligence artificielle", "Cours"]
mathjax: true
---

Presque tous les humains jouent, que se soit des jeux de cartes, de sociétés ou
vidéo. L'IA pour les jeux est donc facile à vulgariser. Prenons le cas des
échecs, dans le cadre de l'IA on s'affranchit du monde physique : elle ne
s'occupe que de la **logique**, ici pas de robot qui bouge les pièces.

Les **jeux-vidéo** utilisent massivement l'IA mais les contraintes sont fortes
(temps-réel) et elle est biaisée sans quoi l'ordinateur gagnera à chaque fois.

## Article de Claude Shannon

C'est en 1950 que [Claude Shannon][l_cshannon] écrit un article fondateur sur
l'intelligence artificielle : un programme pour les jeux d'échec. En découlera
le *nombre de Shannon* qui estime la complexité d'un jeu d'echec.

[l_cshannon]: https://fr.wikipedia.org/wiki/Claude_Shannon

## Un jeu simple

Prenons une grille de 3x3, chaque joueur pose un jeton de 2 cases, l'un
verticalement et l'autre horizontalement.

![Jeux de grille](./images/grille_jeux.svg)

Afin de déterminer les situations favorables pour un joueur donné, il est
possible de construire un arbre. Celui-ci commence par la position initiale et 
explore toutes les possibilités. L'exemple ci-dessous en affiche juste une 
partie :

![Organisation des possibilités en arbres](./images/arbre_jeux.svg)

Nous pouvons introduire alors la notion de **facteur de branchement** qui
représente le nombre d'enfants pour un nœud donné. Bien entendu ce *facteur de
branchement* peut différer en fonction du nœud sur lequel on se situe. Dans
notre exemple ci-dessus, il est de 4 pour le premier tout en haut (joueur1) puis
de 2 pour celui du joueur 2 tout à gauche. Nous pourrons alors calculer le
**facteur de branchement moyen**.

Nous pouvons ainsi explorer toutes les possibilités, on parle alors de
**devellopement total**. Mais l'arbre peut devenir très vite complexe, dans le
cadre de notre grille en 3x3, il contient 75 nœuds, une grille de 4x4 en
compterai 65 081, et en 5x5 **plus de 2 milliards** avec un temps de traitement
de plus de **700 secondes**! On se retrouve face à une **explosion
combinatoire**.

### Simplifier notre arbre

Nous pourrions d'abord reconnaitre les états déjà atteints par d'autres chemins et
ne pas les explorer de nouveau. Nous pouvons aussi considérer les états
symétriques de notre plateau de jeu. Voici un exemple de portion d'arbre
symétiques :

![Exemple de portion d'arbre symétrique](./images/arbre_symetrique.svg)

nous pourrions "*elaguer*" notre arbre pour nous concentrer sur les branches qui
mèment à une stratégie gagnante. Si une branche amie mène à la victoire, ou si
une branche ennemie mène à la défaite, alors **nous ne devellopons pas les
branches voisines**.

Pour ces deux idées, nous sommes obligés de conserver un état de notre arbre en
memoire. De plus nous sommes toujours obligés d'aller jusqu'au feuilles. Aucun
jeu ne permet de mettre en place ces techniques efficacement **sauf à la toutes
fin de la partie**.

## Introduction d'heuristique


D'après [Wikipedia][heuristique_wikipedia] :

> En algorithmique, une heuristique est une méthode de calcul qui fournit 
> rapidement une solution réalisable, pas nécessairement optimale ou exacte, 
> pour un problème d'optimisation difficile.

[heuristique_wikipedia]:https://fr.wikipedia.org/wiki/Heuristique_(math%C3%A9matiques)

Le principe ici est de dévelloper l'arbre que jusqu'à une certaine profondeur
*p*. Les feuilles de l'arbre ne sont plus forcément les position finales du jeu.
Donc nous ne pouvons plus utiliser les information *gagné* ou *perdu*. Il faut
alors **évaluer les positions**.

### Définition intuitive

Ici, nous associons un réel au plateau de jeu (avec adversaire) dans une
*fonction statique*. Plus cet heuristique est élevé et positif, plus la victoire 
est proche, et plus on s'en éloigne lorsqu'elle est petite et négative.

### Mode opératoire

 1. On dévellope l'abre jusqu'à une certaine profondeur définie au préalable.
    Cette profondeur prend en compte le temps de jeu et le facteur de
    branchement estimé;
 2. On évalue la position aux feuilles, cette position dépends du plateau et du
    joueur;
 3. On fait remonter l'évaluation pour **trouver le meilleur coup**.

 Le but ici est de **maximiser la valeur heuristique** obtenue sur le plateau
 après les *p* prochains coups et cherchant la branche adaptée. Bien entendu
 nous supposons alors que les deux joueurs jouent au mieux. C'est même un
 prérequis pour optimiser les calculs.

Le tout est maintenant de savoir comment?

## Recherche avec horizon: MiniMax

Cet algorithme se compose de deux fonctions : 

 * `MaxMin` pour remonter le meilleur coup à jouer lorsque le joueur ami joue;
    ```
    Fonction MaxMin(etat)
        etat : Plateau de jeu courant
        Si EstFeuille(etat) Alors
            Retourner evalue(AMI, etat)
        Fin Si
        Meilleur ← −∞
        Pour Tout successeur s de etat Faire
            Meilleur ← max(Meilleur,MinMax(s))
        Fin Pour
        Retourner Meilleur
    Fin Fonction
    ```
 * `MinMax` pour remonyer le meilleur coup à jouer pour l'ennemi.
    ```
    Fonction MinMax(etat)
        etat : Plateau de jeu courant
        Si EstFeuille(etat) Alors
            Retourner evalue(ENNEMI, etat)
        Fin Si
        Pire ← +∞
        Pour Tout successeur s de etat Faire
            Pire ← min(Pire,MaxMin(s))
        Fin Pour
        Retourner Pire
    Fin Fonction
    ```

Mais cet algorithme a des limitation :

 * Que se passe-t-il si un joueur joue mal, ou ne suit pas les recommandations
   de l'heuristique?
 * Le dilème des prisonniers voir [Wikipedia][prisonnier_wikipedia];
 * L'amplification des valeurs heuristiques : une valeur faible mais isolée dans
   une zone dangereuse sera préférée à une valeur *presque* identiqque dans une
   zone amie;

L'espace des états atteignable dépends du facteur de branchement et du nombre de
coups. Il peut vite devenir **gigantesque** : de l'ordre de 35 puissance 30 pour
les échecs (35 en facteur debranchement et 30 coups environ).

## recherche avec horizon: AlphaBeta

C'est une technique permettant de réduire le nombre de nœuds évalués par
l'algorithme *MinMax*. En effet ce dernier effectue un parcours complet de
l'arbre jusqu'au niveau donné. *AlphaBeta* permet d'optimiser grandement 
*MinMax* en réalisant un élagage. en effet il n'est pas nécessaire de parcourir
les sous-arbres qui ne changerons pas la configuration du nœud courant, sans
conséquence sur l'évaluation.

Nous avons deux type des nœuds :

 * α : le meilleur choix à un moment donné pour *Max* sur le chemin dévellopé.
   Sa valeur est croissante;
 * β : le meilleur choix à un moment donné pour *Min* sur le chemin dévellopé.
   Sa valeur est décroissante;

Voici l'algorithme des deux fontions, comme pour *MaxMin*, cependant α sera 
initialisé avec -∞ et β avec +∞ :

```
Fonction MaxValue(etat, α, β)) # Évaluation niveau AMI
    etat : Plateau de jeu courant
    α : Meilleur évaluation courante pour AMI
    β : Meilleur évaluation courante pour ENNEMI
    Si EstFeuille(etat) Alors
        Retourner evalue(etat) # Évaluation heuristique
    Fin Si
    Pour Tout successeur s de etat Faire
        α ← max(α,MinValue(s, α, β))
        Si α ≥ β Alors # Coupe β
            Retourner β
        Fin Si
    Fin Pour
    Retourner α
Fin Fonction

Fonction MinValue(etat, α, β)) # Évaluation niveau ENNEMI
    etat : Plateau de jeu courant
    α : Meilleur évaluation courante pour AMI
    β : Meilleur évaluation courante pour ENNEMI
    Si EstFeuille(etat) Alors
        Retourner evalue(etat) # Évaluation heuristique
    Fin Si
    Pour Tout successeur s de etat Faire
        β ← min(β,MaxValue(s, α, β))
        Si α ≥ β Alors # Coupe α
            Retourner α
        Fin Si
    Fin Pour
    Retourner β
Fin Fonction
```

Comme pour *MinMax*, il est possible de combiner les deux fonctions en une seul,
il suffit alors de permuter α et β à chaque itération.

Les coupes seront faites dès que \\(\alpha \geqslant \beta\\)

### Catégories de nœuds et nœuds traités

Nous pouvons classer les nœuds en 4 catégories:

 * *Type 1* : -∞ +∞
 * *Type 2* : -∞ β
 * *Type 3* : α +∞
 * *Type 4* : α β

soit un arbre \\(A\\) de profondeur \\(p\\) et un facteur de branchement 
\\(b\\) :

 * \\(U_p\\) représente le nombre de feuilles de type 1;
 * \\(V_p\\) de feuilles de type 2;
 * \\(W_p\\) de feuilles de type 3;
 
Nous avons donc :
 
 * \\(U_p = 1\\)
 * \\(V_p = (b-1) + bW_{b-1}\\)
 * \\(W_p = V_{p-1}\\)

Ce qui permet de dire :

 * \\(V_p = (b-1) + b(V_{p-2})\\)
 * donc \\(V_{p+1} = b + bV_{p-2}\\)
 * donc \\(V_{p+1} = b(V{p-2} + 1)\\)
 * après simplification nous obtenons le nombre de nœuds traités : \\(b^{p/2}\\)
   au lieu de \\(b^p\\)

### Problématique du temps réel

Les questions sur le choix des profondeurs doivent être fixées avant de
commencer la recherche. On veut aller le plus profond possible dans l'arbre.

[prisonnier_wikipedia]:https://fr.wikipedia.org/wiki/Dilemme_du_prisonnier