Un grand merci à Karim pour sa relecture.
Salut les internautes. Aujourd’hui, je continue ce que j’ai commencé fin 2018, à savoir le chemin vers l’explication de MCTS. Dans ce billet, je vais vous parler de la manière classique de traiter les jeux trop grands pour être résolus en Intelligence Artificielle, alpha-beta. Et du coup, je vais vous parler d’heuristiques pour les jeux et de Deep Blue, et aussi pourquoi le ‘Deep’ de Deep Blue n’a rien à voir avec le ‘Deep’ de Deep Mind. L’approche utilisée par Deep Blue a été très majoritairement utilisée jusque dans les années 2000. Comme nous l’avions vu, un jeu extensif peut être représenté comme un arbre dont chaque noeud correspond à un état et chaque arête correspond à un mouvement. Nous nous étions arrêtés en disant qu’il était impossible d’explorer tout l’arbre des échecs.
Salut les internautes. Aujourd’hui, je continue ce que j’ai commencé fin 2018, à savoir le chemin vers l’explication de MCTS. Dans ce billet, je vais vous parler de la manière classique de traiter les jeux trop grands pour être résolus en Intelligence Artificielle, alpha-beta. Et du coup, je vais vous parler d’heuristiques pour les jeux et de Deep Blue, et aussi pourquoi le ‘Deep’ de Deep Blue n’a rien à voir avec le ‘Deep’ de Deep Mind. L’approche utilisée par Deep Blue a été très majoritairement utilisée jusque dans les années 2000. Comme nous l’avions vu, un jeu extensif peut être représenté comme un arbre dont chaque noeud correspond à un état et chaque arête correspond à un mouvement. Nous nous étions arrêtés en disant qu’il était impossible d’explorer tout l’arbre des échecs.
Le but de la méthode par fonction heuristique est de faire une exploration limitée. On explore l’arbre à une certaine profondeur – appelons-la n – et on obtient un certain nombre de nœuds, représentants les états du jeu à n coups. Exprimé autrement, on part de l’état actuel du jeu et on génère les états correspondants à chaque coup possible. Pour chacun de ces états, on calcule tous les coups possibles à partir de cet état, ce qui produit un certain nombre de nouveaux états. On reproduit cela n fois, et on obtient donc un ensemble d’états possibles du jeu. Vous avez sans doute déjà entendu que les joueurs d’échec raisonnent « à n coups » (avec n un nombre). Cela correspond exactement à ce raisonnement.
Nous avons donc maintenant un nombre précis d’états du jeu disponible. L’arbre obtenu par le processus ressemble beaucoup à l’arbre minimax dont nous avons parlé précédemment, sauf que les feuilles ne sont plus des états finaux (en général). Il est donc impossible de calculer un score selon les règles du jeu, en particulier pour les jeux combinatoires où le score est 1 pour une victoire et -1 pour une défaite. C’est pour évaluer ces feuilles que la fonction heuristique entre en jeu. Cette fonction est d’ailleurs aussi appelée fonction d’évaluation. Cette fonction est définie par des experts du jeu et est censée définir à quel point le joueur est en train de gagner ou de perdre. On l’appelle heuristique parce qu’elle donne une bonne idée de la valeur d’un état du jeu sans que cela ne soit une information précise sur qui va gagner ou perdre. Reprenons l’exemple des échecs. Si vous avez toutes vos pièces et que votre adversaire a perdu sa reine, ses tours et ses fous, il semble que vous soyez en avantage par rapport à ellui. Le nombre (et la valeur) des pièces sont donc des éléments de la fonction. Mais ce ne sont pas les seuls. On va généralement aussi s’appuyer sur ce que peuvent faire ces pièces (combien de cases sont disponibles pour elles, quelles pièces elles menacent etc.) et sur la sécurité de la position du roi.
Et c’est là qu’une question se pose : quel type de fonction privilégier ? Par exemple, on pourrait calculer les pièces menacées, mais retirer celles qui sont protégées. Voire définir un « niveau de menace » pour chaque pièce. Il y a un compromis à faire entre la complexité de cette fonction et le nombre d’états qu’il est possible de traiter en un temps donné. On peut faire une fonction complexe, fiable, et explorer moins l’arbre pour ne pas avoir trop d’états à évaluer. Ou alors on fait une fonction plus simple, moins « intelligente » et on explore l’arbre plus en profondeur. L’expérience a montré que cette seconde option était plus efficace. C’est cette profondeur d’exploration qui est à l’origine du « deep » de Deep Blue. Rien à voir donc avec la profondeur d’un réseau de neurones, qui a donné son nom à Deep Mind.
Après avoir défini la profondeur de l’arbre et la fonction d’évaluation, on se retrouve avec l’équivalent d’un arbre minimax, sauf que les scores sont compris entre -1 et 1, et ne sont pas nécessairement l’une de ces deux valeurs. L’exploration est identique. Cela signifie en particulier qu’il est possible d’utiliser l’élagage. L’algorithme implémentant ces deux parties est appelé alpha-beta pruning et c’est sur celui-ci que se base Deep Blue qui a détrôné l’humain aux échecs !
Reste deux cas où cet algorithme est inefficace: quand y a beaucoup de mouvement possibles à chaque état, par exemple au go où il y a initialement 361 coups possibles, il est impossible d’aller « profond » dans l’arbre car le nombre d’évaluations explose. Enfin, la création d’une fonction heuristique est parfois complexe, voire impossible. Là encore, c’est le cas du go où il n’y a pas de fonctions heuristiques simples et fiables, l’état d’un plateau étant difficile à déterminer. Pour ces cas, on va devoir trouver une autre méthode nommée Monte Carlo Tree Search, que je vous présenterai la prochaine fois. D’ici-là renseignez-vous, réfléchissez et surtout n’oubliez pas de rêver.
