Exercice d’Application : Résolution des Tours de
Hanoi avec le Q-learning
Dr. Yoro DIA
Énoncé du Problème
Le problème des Tours de Hanoi est constitué de trois poteaux (Source, Auxili-
aire et Destination) et de 3 disques de tailles différentes empilés sur le poteau
Source. L’objectif est de déplacer tous les disques du poteau Source vers le
poteau Destination, en respectant les règles suivantes :
• Un seul disque peut être déplacé à la fois.
• Un disque plus grand ne peut jamais être placé sur un disque plus petit.
• Les disques peuvent être placés sur l’un des trois poteaux.
L’objectif de cet exercice est de définir un agent qui utilise le Q-learning
pour apprendre la meilleure séquence de déplacements afin de transférer tous
les disques vers le poteau Destination en utilisant le nombre minimal de mou-
vements.
1
Objectifs Pédagogiques
• Comprendre comment formuler un problème séquentiel comme une tâche
d’apprentissage par renforcement.
• Appliquer le Q-learning pour apprendre une politique optimale pour un
problème de puzzle.
• Analyser les résultats et comprendre les limites de la méthode pour des
problèmes combinatoires.
Détails de la Résolution
1. États : Un état est défini par la position de chaque disque sur les trois
poteaux.
2. Actions : Les actions sont les déplacements de disques d’un poteau à un
autre.
3. Récompense : Une récompense est attribuée uniquement lorsque l’état
final est atteint.
4. Facteur d’actualisation (γ) : Ce facteur détermine l’importance ac-
cordée aux récompenses futures.
5. Politique d’exploration (ϵ-greedy) : Utiliser une politique ϵ-greedy
pour encourager l’exploration.
Instructions
1. Initialisation : Créez une représentation des états, des actions et des
valeurs Q pour chaque état-action possible.
2. Mise en œuvre du Q-learning : Utilisez la mise à jour de la valeur Q :
Q(s, a) ← Q(s, a) + α r + γ max Q(s′ , a) − Q(s, a)
a
où α est le taux d’apprentissage, r est la récompense reçue, γ est le facteur
d’actualisation, et s′ est l’état suivant après l’action a.
3. Entraı̂nement de l’Agent : Faites en sorte que l’agent explore différentes
actions et enregistre la meilleure séquence de déplacements pour résoudre
le problème.
2
Code Python
import numpy as np
import random
# Parametres du Q-learning
alpha = 0.1 # Taux d’apprentissage
gamma = 0.9 # Facteur d’actualisation
epsilon = 0.1 # Probabilit3 d’exploration
episodes = 5000 # Nombre d’episodes d’apprentissage
# Initialisation des valeurs Q
Q = {}
def get_state_key(state):
return tuple([tuple(pole) for pole in state])
# Fonction pour initialiser l’etat du jeu (tous les disques sur
le poteau source)
def init_state():
return [[3, 2, 1], [], []] # Disques 3, 2, 1 empil3s sur le
poteau source
# Fonction pour g3n3rer toutes les actions valides
def valid_actions(state):
actions = []
for i in range(3):
if state[i]: # Si le poteau n’est pas vide
for j in range(3):
if i != j and (not state[j] or state[j][-1] >
state[i][-1]):
[Link]((i, j))
return actions
# Q-learning
for episode in range(episodes):
state = init_state()
done = False
while not done:
state_key = get_state_key(state)
if state_key not in Q:
Q[state_key] = {a: 0 for a in valid_actions(state)}
# Choisir une action (exploration vs exploitation)
if [Link](0, 1) < epsilon:
3
action = [Link](valid_actions(state))
else:
action = max(Q[state_key], key=Q[state_key].get)
# Appliquer l’action
src, dest = action
disk = state[src].pop()
state[dest].append(disk)
# Verifier si l’etat final est atteint
done = len(state[2]) == 3
# Recompense
reward = 1 if done else 0
# Calcul de la mise a jour Q
new_state_key = get_state_key(state)
if new_state_key not in Q:
Q[new_state_key] = {a: 0 for a in
valid_actions(state)}
max_future_q = max(Q[new_state_key].values()) if not done
else 0
Q[state_key][action] += alpha * (reward + gamma *
max_future_q - Q[state_key][action])
print("Entrainement␣termin3.")
Questions
1. Que représente la fonction de valeur Q dans ce contexte ?
2. Quelle est la politique optimale apprise par l’agent pour résoudre les Tours
de Hanoi avec trois disques ?
3. Expérimentez avec différentes valeurs de α, γ, et ϵ. Comment ces valeurs
affectent-elles la rapidité et l’efficacité de l’apprentissage ?