Réalisation d'une IA jouant au jeu Acrobot avec MCTS
Présentation du jeu Acrobot
Le jeu Acrobot est un environnement de type contrôle classique disponible dans Gymnasium. Le but du jeu est simple :
Un système à deux segments articulés (un pendule double) doit amener l’extrémité du second segment au dessus d’une certaine hauteur. L’agent peut appliquer un couple moteur limité sur l’articulation centrale, ce qui influence le mouvement des deux segments. L’agent reçoit des récompenses négatives à chaque étape, ce qui a pour but d'encourager l'agent à trouver la solution le plus rapidement possible. La réussite est atteinte lorsque l’extrémité du pendule dépasse la hauteur cible (la ligne noire).
Cet environnement est idéal pour expérimenter avec des algorithmes de planification comme le MCTS, car il combine une dynamique continue avec des actions discrètes simples, tout en offrant un défi non trivial de contrôle et de planification à court et long terme.
Monte Carlo Tree Search (MCTS)
Le Monte Carlo Tree Search (MCTS) est un algorithme de planification et d’apprentissage par simulation qui permet à un agent de choisir des actions en explorant un arbre de décisions. L’idée est d’estimer la valeur des actions en simulant des parties complètes depuis l’état courant et en utilisant ces simulations pour guider le choix :
- Chaque nœud de l’arbre représente un état de l’environnement, et chaque branche correspond à une action possible.
- L’agent sélectionne les actions à explorer en équilibrant exploitation (choisir les actions avec de bonnes valeurs estimées) et exploration (essayer des actions moins connues) via une formule comme UCB1 :
où :
- (Vi) : valeur cumulée du nœud (i)
- (Ni) : nombre de visites du nœud (i)
- (Np) : nombre de visites du parent
- (c) : coefficient d’exploration
(Algorithme UCB1, réalisé en python, permettant de choisir le meilleur noeud parmis plusieurs)
def ucb1(children, c=1.0):
parent_visits = sum(child.visits for child in children.values()) + 1e-5
best_score = -float('inf')
best_child = None
for action, child in children.items():
if child.visits == 0:
score = float('inf')
else:
exploit = child.value / child.visits
explore = math.sqrt(math.log(parent_visits) / child.visits)
score = exploit + c * explore
if score > best_score:
best_score = score
best_child = child
return best_child
- Après chaque simulation, la récompense finale est propagée vers le haut de l’arbre (backpropagation) pour mettre à jour les valeurs des nœuds traversés.
- À la fin des itérations, l’action choisie est celle qui maximise la valeur moyenne estimée au nœud racine.
Ainsi, MCTS permet à l’agent de planifier plusieurs coups à l’avance sans connaître explicitement la dynamique de l’environnement, en s’appuyant sur des simulations pour guider ses décisions.
Étapes pour réaliser l’IA
Réalisation des fonctions nécessaires :
Importation des bibliothèques nécessaires et création de l'objet "Node" (noeud)
L'objet Node (noeud) possède :
- Un état
- un parent
- un enfant
- le nombre de visites
- une valeur
import gymnasium as gym
import math
import random
import copy
env = gym.make("Acrobot-v1")
obs, info = env.reset()
# Crtion d'un objet représentant le noeud d'un arbre
class Node:
def __init__(self, state, parent):
self.parent = parent
self.state = state
self.visits = 0
self.value = 0.0
self.children = {}
La fonction de simulation
Cette fonction permet, à partir d'un noeud, de faire X simulations à partir du noeud de la fin du jeu.
def simulate(Inode: Node, max_steps):
total_reward = 0
env_simu = copy.deepcopy(env.unwrapped)
env_simu.state = Inode.state
steps = 0
done = False
#Tant que le programme n'a pas réussi, ou que le max_steps n'a pas été atteint, on réalise des simulations
while not done and steps < max_steps:
steps += 1
action = env_simu.action_space.sample()
obs, reward, terminated, truncated, _ = env_simu.step(action)
total_reward += reward
if terminated:
done = True
return env_simu.state, done, total_reward
La fonction "Backpropagate"
La méthode backpropagate joue un rôle central dans le MCTS en permettant de remonter la récompense obtenue après une simulation à travers l’arbre de décision
def backpropagate(node: Node, reward):
while node is not None:
node.visits += 1
node.value += reward
node = node.parent
La fonction de réalisation de cycle
La fonction cycle représente une itération complète de MCTS à partir d’un nœud donné. Elle commence par créer les enfants du nœud si nécessaire, puis sélectionne un noeud au hasard parmi les enfants nouvellement créés. À partir de ce nœud, plusieurs simulations sont effectuées, chaque simulation produisant une récompense cumulée qui est ensuite propagée vers le haut de l’arbre grâce à backpropagate
def cycle(noeud, env):
simulate_node = noeud
all_actions = list(range(env.action_space.n))
if noeud.children == {}:
for action in all_actions:
noeud.children[action] = Node(state=copy.deepcopy(noeud.state), parent=noeud)
simulate_node = random.choice(list(noeud.children.values()))
for _ in range(random.randint(50, 100)):
final_state, done, epdone, total_reward = simulate(simulate_node, max_steps=300)
simulate_node.state = final_state
backpropagate(simulate_node, reward=total_reward)
return final_state, done, epdone, total_reward
La fonction "MCTS"
Dans cette fonction, on rassemble tout ce que l'on a codé auparavant. On commence par initialisé le noeud racine ainsi que certaines variables. Ensuite, dans la boucle "while", tant que le jeu n'est pas terminé, ou que les episodes ne se sont pas écoulés et que le compteur est inférieur aux nombres d'itérations choisis, on effectue des cycles.
def mcts(env, iterations=100):
racine = Node(state=copy.deepcopy(env.unwrapped.state), parent=None)
done = False
compteur = 0
while not done and compteur < iterations:
final_state, done, epdone, total_reward = cycle(noeud=racine, env=env)
compteur += 1
print('episode :', compteur)
print('recompense actuel :', total_reward)
if done:
print('Agent a reussi')
else:
print('Agent a pas réussi')
print("Nb d'itérations :", compteur)
print("Nombre de visites racine :", racine.visits)
print("Nombre d’enfants :", len(racine.children))
return racine
Observations
- Après réflexion, la réalisation d’un MCTS sur un jeu tel que Acrobot n’est pas très idéale car l’environnement possède un espace d’état continu et infini avec une dynamique physique complexe, or, le MCTS est efficace pour des espaces discret et limitées, comme le jeu de plateau Taxi. Pour ce type d’environnement, le Q-Learning est plus adapté pour apprendre une politique optimale.