Algorithmes par les Jeux

Résolution de jeux à un joueur

Le Sudoku

On a une manière brutale et naïve de résoudre un sudoku

Exemple

sudoku
C’est un algorithme de type “backtracking” (retour en arrière)
backtracking
On parcourt ainsi toutes les possibilités de remplir la grille \rightarrow c’est en fait un parcours en profondeur d’un arbre, dans lequel on cherche la branche qui mène à une solution

Light up

Light up est un puzzle consistant à illuminer une grille formée de carrés noirs et blancs en ajoutant des ampules selon les règles suivantes :

Exemple

lightup

Implémentation d’un algorithme de résolution par backtracking

typedef struct state {
   int nb_light;
   int light_pos;
}

Plus d’infos sur le TP ici et les fichiers ici.

\Rightarrow Sur un niveau difficile, la résolution par backtracking peut être couteuse

Comment améliorer cet algorithme ?

  1. Placer les lumières que lumières que l’on peut placer à coup sûr

    Exemple

    q1_exemple
    N_{b} = nombre de carrés noirs
    i \in \\\{1, ..., N_{b}\\\}, avec :

    • Need_{i} = nombre dans le carré (dont on a besoin)
    • Space_{i} = nombre de carrés blanc pouvant accueillir une ampoule autour de ?
    • Have_i = nombre d’ampoules que l’on a autour
      Spl_i = { carrés blanc admissibles autour }

    Si Space_i + Have_i = Need_i \rightarrow on met une ampoule dans tous les éléments de Spl_i

  2. Éliminer les cases qui ne pourront pas accueillir d’ampoule

Exemple

q2_exemple
Si Have_i = Need_i \rightarrow toutes les positions restantes de Spl_i peuvent être marquées d’une croix

Exemple : Si on applique ce pattern 1 - 2 deux foix :

q2_exemple2
Le jeu est presque résolu en 2 étapes !
3. S’il y a une case non allumée isolée, on peut y placer une ampoule
N_w = nombre de carrés blancs
J \in \\\{1, ..., N_w\\\}
Si Source_J = 1, on peut placer une ampoule dans la seule position valable; Source_J correspond au nombre de carrés non éclairés autour de J_i incluent J

Exemple

impl_ex
Il y a d’autres patterns possibles d’améliorations…

Chiu - Chou - Yang - Yen ont publié en 2010 un article “A simple and rapid Lights-Up solver” dans lequel ils présentent un algorithme efficace du puzzle. Ils utilisent notamment 1, 2 et 3 ainsi que d’autres patterns ; ainsi qu’une méthode de parcours arborescente pour résoudre les zones blanches non encore éclairées.

Le fichier lightup.c contient une implémentation de cet algorithme \rightarrow vous pouvez ainsi tester et comparer l’efficacité de votre algorithme de backtracking par rapport à celui-ci.

Remarque

En fait, la résolution rapide de gros puzzles de Light Up est un problème qui intéresse encore des chercheurs à l’heure actuelle.
\rightarrow jeu qui apparaît comme un problème aux “Computer Olympiads” en 2010

Jeux à deux joueurs et IA

On étudie un jeu à deux joueurs à somme nulle (somme des gains et pertes égale à 0) où :

Exemple TicTacToe, Dames, Jeu de Go, Échecs, Puissance 4…

Difficultés :

Idée (naïve) : Construire l’arborescence des coups réalisables

Exemple avec un TicTacToe

arborescence_tictactoe

Exemple : Pour les Échecs,

\begin{aligned}F(p) = &200(N_{k} - N_{k'}) + 9(N_{Q} - N_{Q'}) + S(N_{R} - N_{R'}) \\\ &+ 3(N_{B} + N_{N} - N_{B'} - N_{N'}) + N_{p}- N_{p'} \\\ &-(D-D'+S-S'+I-I')\end{aligned}
où N\cdot désigne le nombre de \cdot chez le joueur blanc (respectivement N\cdot' chez le joueur noir) et K King, Q Queen, R Rook (Tour), B Bishop (Fou), N kNight (Cavalier) et P Pawn (Pion).

D = nombre de pions doublés (cf. image)
echec_pion_double
S = nombre de pions bloqués
I = nombre de pions isolés
M = mobilité du joueur

Cette fonction renvoie un nombre flottant : plus il est grand (positif), plus le joueur blanc a l’avantage; plus il est petit (négatif); plus le joueur noir a l’avantage

Exemple

exemple_chess_board
\begin{aligned}f(p) = &200(1-1)+9(1-1)+5(0-1)+3(2+0-1-0) \\\ &+3-3-\frac{0-2+0-1+1-1}{2}+\frac{37-46}{10}\\\ &\simeq-1.4\end{aligned}
On peut donc supposer qu’à cette position, le joueur noir a légèrement l’avantage. Cependant, si blanc bouge son fou en H7 (pour mettre en échec le roi), il prend l’avantage en capturant la dame au coup suivant…
exemple_chess_board 1-echec
Ceci est appelé un effet d’horizon.

Problème majeur : Complexité spatiale beaucoup trop grande aka arbre de jeu immense

Exemples

Pour éviter cette explosion combinatoire, on peut se limiter à parcourir l’arbre jusqu’à une certaine profondeur

Exemple : TicTacToe avec profondeur 2

tictactoe profondeur
Principe de résolution :

Pour obtenir une telle fonction, on utilise une estimation h : \mathcal{P} \rightarrow \R fonction d’évaluation
Cette fonction devra être d’autant plus fiable que p est proche d’une position terminale
Mais h est seulement une heuristique, et on ne peut pas prévoir les effets d’horizon.
\Rightarrow Il faut donc trouver un bon compromis entre la profondeur de jeu choisie et la fonction d’évaluation

Plus la profondeur est élevée, plus la fonction d’évaluation a des chances d’être efficace en s’approchant des positions terminales; mais plus la taille en mémoire sera importante.

Algorithme Minimax

Hypothèses :

Joueur 1 = MAX
Joueur 2 = MIN

minimax (profondeur n, position p, joueur J)
    - si p est terminale
        return h*(p)
    - si n = 0 # On a atteint la profondeur maximale
        return h(p)
    - sinon, soit p1, ..., pm les m positions accessibles depuis p
        - si J = MAX
            return max minimax(n - 1, pi, MIN) # 1 <= i <= m
        - si J = MIN
            return min minimax(n - 1, pi, MAX) # 1 <= 1 <= m

Inconvénients

  1. Complexité élevée \RA \O(c^{n}) avec c coups légaux en moyenne par chaque position et profondeur n.
  2. Plus problématique : effets d’horizon; pour minimax(n, p, J) il se peut que p_{n+1} soit perdante alors que p_{n} est favorable

Amélioration

Première idée : on va éviter de parcourir les positions superflus de l’arbre de jeu \Rightarrow Élagage de l’arbre de recherche

Cet algorithme s’appelle alpha-beta (\alpha-\beta) puisque selon le joueur, on va réaliser deux types d’élagage dans l’arbre

Remarque

Cela n’enlève pas l’effet d’horizon, mais permet d’augmenter la profondeur en réduisant le nombre de positions à explorer.

On donne maintenant deux exemples d’élage de positions superflues : \begin{cases} \text{une coupure } \alpha \\\\ \text{une coupure } \beta \end{cases}
alphabeta

(1) MAX va choisir la valeur maximale renvoyée par l’évaluation de tous les coups possibles de MIN, donc 12
(2) MIN va choisir la valeur minimale renvoyée par l’évaluation de tous les coups possibles de MAX, donc 12

Exemple :
alphabeta2

coupe_alpha

Alpha-Beta (\alpha-\beta)

On considère comme précédemment une fonction d’évaluation h : \mathcal{P} \rightarrow \R et deux joueurs : MIN et MAX.
Pour évaluer p à une profondeur n, pour le joueur J, on conserve :

[Knuth ‘7s]: Lorsque l’algorithme minimax trouve un coup en parcourant n noeuds, alpha-beta trouve ce même coup en parcourant \approx 1+2\sqrt{n} coups si les coups sont bien ordonnées
\RA L’ordre des coups est important car en fonction de l’ordre, on ne réalise pas le même élagage.

Exemple:
alphabeta_ordre

alphabeta (profondeur n, position p, joueur J, alpha, beta)
    - si p est terminale, alpha = -INF ; beta = +INF
        return h*(p)
    - si n = 0
        return h(p)
    - sinon
        - soient p1, ..., pm les m positions accessibles depuis p
        - si J = MIN
            - e <- alphabeta(n-1, p1, MAX, alpha, beta)
            - si e <= alpha
                return alpha
            - sinon beta <- min(beta, e)
                recalculer e pour les autres positions p2, ..., pm
        - si J = MAX
            - e <- alphabeta(n-1, p1, MIN, alpha, beta)
            - si e >= beta
                return beta
            - sinon alpha <- max(alpha, e)
                recalculer e pour les autres positions p2, ..., pm

Schéma résumé :
alphabeta_resume

Remarque

Il existe une variante de l’algorithme minimax, appelée negamax, plus utilisée actuellement. Plutôt que de tester si on est à une profondeur paire ou impaire pour savoir si on cherche à maximiser ou minimiser, on peut inverser le signe des évaluations et toujours chercher à maximiser.
On peut donc toujours procéder à un élagage alpha-beta à partir d’un negamax

Améliorations de l’algorithme alpha-beta

  1. Autoriser des coupures plus longues : jusqu’à présent, on a réalisé des coupures alpha ou beta en comparant la valeur d’un noeud avec les valeurs des frères de son parent. On peut aussi regarder les parents des parents, exemple :
    amelioration_alphabeta_parent
    Le 20 entouré en rouge ne peut a priori pas donner lieu à un élagage classique.
    Mais on peut constater que le frère du parent de son parent a pour valeur 10, et que valeur \geq 20 ne sera jamais choisie :

    • soit le minimum sera obtenue par le frère du 20 à profondeur 2, auquel cas le 20 n’est pas selectionné.
    • soit le 20 remonte jusqu’à 1, mais dans ce cas c’est le 10 qui sera choisi
      \ra le 20 ne sera donc jamais choisi, et donc son frère non plus (soit il est \leq 20 et ne remonte pas, soit il est \geq 20 et il sera encore moins choisi pour la même raison) : on peut donc réaliser une coupure “grande-\betaeta / \beta+”

  2. Alpha-beta itératif incrémental
    L’idée est de commencer par réaliser une recherche à profondeur 1, puis recommencer avec une recherche complète à profondeur 2, puis profondeur 3, etc, jusqu’à ce qu’une solution soit trouvée
    Avantage : On trouve toujours la solution la plus courte, puisqu’un noeud n’est jamais engendré tant que tous les noeuds à profondeur inférieur n’ont pas été explorés.
    alphabeta_it_incr
    Complexité: \O(d) si l’algo se termine à profondeur d
    A priori, on perd beaucoup de temps dans les itérations précédent la solution. Mais ce travail supplémentaire est en général beaucoup plus petit que la dernière itération
    Exemple : Si n coups en moyenne par position, à profondeur d, on a n^{d} noeuds.
    Le nombre de noeuds à profondeur d-1 est de n^{d-1} mais chaque noeud est engendré 2 fois (une fois par le lancement à profondeur d-1 et une fois pour le lancement à profondeur d)
    Au final : nombre de noeuds engendrés : n^{d} + 2n^{d-1} + 3n^{d-2} + \dots + dn = \O(n^{d})
    Si n est grand, le premier terme est dominant, et c’est la dernière itération qui prend le plus de temps.
    De plus : alpha-beta incrémental permet de :

    • développer des heuristiques de parcours, en reprenant le parcours de l’arbre à partir de la position qui était jugée la meilleur au lancement à profondeur précédente
    • optimiser l’élagage en implémentant un tri rapide pour placer les meilleurs coups dans l’ordre

  3. Approfondissement sélectif quiescence

    • Pour pallier aux inconveniants des effets d’horizon, Deap Blue a utilisé une meta fonction d’évaluation qui n’évalue pas la position mais plutôt le type de la position
      \ra elle évalue si une position est stable (essentiellement, si il reste des pièces en prise) qui donneront grosso-modo la même évaluation à profondeur d ou d+1.
      Une position stable a donc une évaluation en laquelle on peut avoir confiance alors qu’une instable non.
      Deepblue utilise un mécanisme de quiescence pour continuer de développer les positions basses de l’ordre jusqu’à des positions stables. Aux échecs, la quiescence est couramment utilisée pour des coups de capture ou des coups de promotion (sauf quand le roi est en échec)
      Chaque étape de l’algorithme est constituée de 4 phases :
      1. Sélection : Depuis la racine de l’arbre, on sélectionne successivement des enfants jusqu’à atteindre une feuille.
      2. Expansion : Si cette feuille n’est pas une position terminante, créer un enfant (ou plusieurs) en appliquant un mouvement suivant les règles du jeu, puis ajouté cet enfant marqué (0/0)
      3. Simulation (“Playout” ou “Roll-out” en anglais) : Simuler une exécution d’une partie au hasard depuis cet enfant, jusqu’à atteindre une position de jeu terminale
      4. Back propagation : Utiliser le résultat de la partie au hasard et mettre à jour les informations sur la branche en partant de la feuille vers la racine
        Exemple : deepblue

  4. Approfondissement sélectif
    Si un coup semble intéressant, on continue à cherche à une profondeur plus grande que la profondeur habituelle.
    Si un coup semble mauvais, on arrête de chercher à une profondeur plus petite que la profondeur habituelle.
    Exemple : Chinook, IA pour les dames

    • S’il analyse un coup qui perd 3 pions, plutôt que d’analyser à profondeur 10, il va réduire à seulement 5 coups à l’avance, en considérant que le coup a de bonnes chances d’être mauvais
    • S’il analyse un coup qui paraît très bon, il augmentera la profondeur à 12 coups à l’avance

Monte-Carlo Tree Search (MCTS)

L’algorithme MCTS est un autre algorithme d’IA pour les jeux basé sur une recherche arborescente

MCTS conserve en mémoire un arbre qui correspond aux noeuds déjà explorés de l’arbre de jeu.
\ra une feuille de cet arbre est soit une position terminale du jeu, soit un noeud dont aucun enfant n’a encore été exploré.

Dans chaque noeud, on stocke deux nombres : le nombre de simulations gagnantes et le nombre totale de simuations.
mcts
Si la partie est perdante pour J1 : on incrémente le nombre de simulation total uniquement pour les noeuds J1 et on incrémente à la fois le nombre de simulations totales et gagnantes pour J2… et inversement si la partie est gagnante pour J1.

Avantages :

selection (pos p)
    Si p est terminale
        return p
    N = nombre de visites du père p (fonction getN)
    Si N == 0
        return p
    M <- { Mouvements possibles depuis p }
    { max, best } <- { -1, ∅ }
    pour chaque m ∈ M faire
        ni = nombre de fois où p à été visité
        Si ni == 0
            return p
        new_eval <- UCT(p, m)
        Si new_eval > max
            { max, best } <- { new_eval, m }
    p' <- apply_move(p, best)
    return selection(p')

expansion (pos p)
    Si p est terminale
        return p
    N <- getN(p)
    Si N == 0
        make_moves(s)
    M <- { Mouvements possibles depuis p }
    pour chaque m ∈ M
        Ni <- getNi(p, m)
        Si Ni == 0
            p' = apply_move(p, m)
            return p'

playout (pos p)
    while not(p position termionale)
        M <- next_moves(p)
        m <- random(M)
        p <- apply_move(p, m)
    return score(p)

back_propagate (pos p, score)
    if parent(p) == ∅
        return
    add_score(p, score)
    return back_propagate(parent(p), score)

Fonction d’évaluation Puissance 4 :

  1. Grille de jeu pondérée
    puissance4
    score(J1) = somme des poids des cases sur lesquelles J1 a un jeton

  2. Compter le nombre d’alignements
    Pour chaque joueur, on évalue son score de la façon suivante :

    • +1 par jeton
    • +5 par 2 jetons alignés
    • +50 par 3 jetons alignés
    • +1000 par 4 jetons alignés

    f(p) = score(J1) - score(J2)

    Inconvénient : Cette évaluation tient en compte des alignements “bloqués”, par exemple :
    exemple_puissance4 donnera un score positif pour J1 avec 2 alignements de 3, alors qu’un seul alignement de 4 n’est encore possible.
    Mieux : Ne compter dans ce calcul que les alignements encore envisageables