Comprendre MCTS - 3 L'approche heuristique (2024)

Hello ! Aujourd'hui, je continue ce que j'ai commencé fin 2018, à savoir le chemin vers l'explication de MCTS. Aujourd'hui, 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. Cette approche 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, on génère les états correspondants à chaque coup possible. Pour chacun de ces états, on génère tous les coups possibles à partir de cet état, ce qui génère un certain nombre de nouveaux états. On reproduit cela n fois, et on obtient donc un certain nombre d'états possibles du jeu. Vous avez sans doute déjà entendu que les joueurs d'échec raisonnent "à n coups" (avec un certain n). Cela correspond exactement à ce raisonnement.

Nous avons donc maintenant un certain nombre 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 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ératlement 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 retirées celles qui sont protégées. Voire, pour chaque pièce, 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 doné 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, Monte Carlo Tree Search, que je vous présenterai la prochaine fois.

Comprendre MCTS - 3 L'approche heuristique (2024)
Top Articles
Latest Posts
Article information

Author: Rev. Porsche Oberbrunner

Last Updated:

Views: 6411

Rating: 4.2 / 5 (73 voted)

Reviews: 80% of readers found this page helpful

Author information

Name: Rev. Porsche Oberbrunner

Birthday: 1994-06-25

Address: Suite 153 582 Lubowitz Walks, Port Alfredoborough, IN 72879-2838

Phone: +128413562823324

Job: IT Strategist

Hobby: Video gaming, Basketball, Web surfing, Book restoration, Jogging, Shooting, Fishing

Introduction: My name is Rev. Porsche Oberbrunner, I am a zany, graceful, talented, witty, determined, shiny, enchanting person who loves writing and wants to share my knowledge and understanding with you.