Navigation : << Recherche informee | Index | MCTS >>
A la fin de ce notebook, vous saurez : 1. Modeliser un jeu a somme nulle comme un problème de recherche 2. Implementer l’algorithme Minimax avec l’optimisation Alpha-Beta 3. Comprendre les limites de Minimax et les stratégies d’amelioration 4. Appliquer la recherche iterative (iterative deepening) 5. Utiliser les tables de transposition pour optimiser la recherche
# Imports
import sys
import time
import random
from typing import Optional, List, Dict, Tuple, Any, Callable
from copy import deepcopy
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
%matplotlib inline
print("Environnement pret pour la recherche adversariale.")Environnement pret pour la recherche adversariale.Un jeu a somme nulle (zero-sum game) est un jeu ou les gains d’un joueur correspondent exactement aux pertes de l’autre. Le gain total des deux joueurs est toujours zero.
Exemples classiques : - Tic-Tac-Toe (Morpion) - Echecs - Go - Puissance 4 (Connect Four)
| Caractéristique | Description |
|---|---|
| Information parfaite | Les deux joueurs connaissent l’etat complet du jeu |
| Tour a tour | Les joueurs jouent alternativement |
| Déterministe | Le résultat d’une action est certain (pas de hasard) |
| Fini | Le jeu se termine toujours en un nombre fini de coups |
Ancres savantes – von Neumann, J. (1928), Zur Théorie der Gesellschaftsspiele, Mathematische Annalen 100:295-320 (théorème minimax, fondement des jeux à somme nulle, dont découle l’algorithme Minimax d’évaluation de l’arbre de jeu) ; Shannon, C.E. (1950), Programming a Computer for Playing Chess, Philosophical Magazine 41(314):256-275 (propose l’évaluation minimax de l’arbre de jeu avec fonction d’évaluation statique — l’acte de naissance de la programmation de jeux par ordinateur) ; Knuth, D.E. & Moore, R.W. (1975), An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6(4):293-326 (analyse complète de l’élagage alpha-bêta, borne O(b^(m/2)) sur l’arbre élagué vs O(b^m) pour Minimax brut) ; Zobrist, A.L. (1970), A New Hashing Method with Application for Game Playing, ICCV Report 88, University of Wisconsin (hachage de Zobrist pour indexer les positions de jeu dans les tables de transposition) ; Korf, R.E. (1985), Depth-first Iterative-Deepening: An Optimal Admissible Tree Search, Artificial Intelligence 27(1):97-109 (approfondissement itératif, recherche par profondeur croissante bornée en temps).
Un jeu a somme nulle peut etre modelise comme :
# Classe de base abstraite pour un jeu a somme nulle
from abc import ABC, abstractmethod
class JeuSommeNulle(ABC):
"""Interface pour un jeu a somme nulle a information parfaite."""
@abstractmethod
def etat_initial(self) -> Any:
"""Retourne l'etat initial du jeu."""
pass
@abstractmethod
def joueur(self, etat: Any) -> str:
"""Retourne le joueur qui doit jouer ('MAX' ou 'MIN')."""
pass
@abstractmethod
def actions(self, etat: Any) -> List[Any]:
"""Retourne la liste des actions legales."""
pass
@abstractmethod
def resultat(self, etat: Any, action: Any) -> Any:
"""Retourne le nouvel etat apres l'action."""
pass
@abstractmethod
def est_terminal(self, etat: Any) -> bool:
"""Le jeu est-il termine ?"""
pass
@abstractmethod
def utilite(self, etat: Any, joueur: str) -> float:
"""Valeur de l'etat terminal pour le joueur (+1, 0, -1)."""
pass
@abstractmethod
def afficher(self, etat: Any) -> str:
"""Representation textuelle de l'etat."""
pass
print("Classe JeuSommeNulle definie (ABC, 7 methodes abstraites pour jeux a somme nulle)")Classe JeuSommeNulle definie (ABC, 7 methodes abstraites pour jeux a somme nulle)Implementons le jeu de Morpour pour illustrer les concepts.
class TicTacToe(JeuSommeNulle):
"""Implementation du jeu de Morpion."""
def __init__(self):
self._etat_initial = (tuple([' ']*9), 'X') # (grille 3x3 aplatie, joueur)
def etat_initial(self) -> Tuple[Tuple[str, ...], str]:
return self._etat_initial
def joueur(self, etat: Tuple[Tuple[str, ...], str]) -> str:
return 'MAX' if etat[1] == 'X' else 'MIN'
def actions(self, etat: Tuple[Tuple[str, ...], str]) -> List[int]:
"""Retourne les indices des cases vides."""
grille = etat[0]
return [i for i in range(9) if grille[i] == ' ']
def resultat(self, etat: Tuple[Tuple[str, ...], str], action: int) -> Tuple[Tuple[str, ...], str]:
"""Joue le coup et retourne le nouvel etat."""
grille = list(etat[0])
joueur_actuel = etat[1]
grille[action] = joueur_actuel
prochain_joueur = 'O' if joueur_actuel == 'X' else 'X'
return (tuple(grille), prochain_joueur)
def est_terminal(self, etat: Tuple[Tuple[str, ...], str]) -> bool:
grille = etat[0]
lignes = [
[0, 1, 2], [3, 4, 5], [6, 7, 8], # lignes
[0, 3, 6], [1, 4, 7], [2, 5, 8], # colonnes
[0, 4, 8], [2, 4, 6] # diagonales
]
for l in lignes:
if grille[l[0]] != ' ' and grille[l[0]] == grille[l[1]] == grille[l[2]]:
return True
return ' ' not in grille
def utilite(self, etat: Tuple[Tuple[str, ...], str], joueur: str) -> float:
grille = etat[0]
lignes = [
[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]
]
for l in lignes:
if grille[l[0]] != ' ' and grille[l[0]] == grille[l[1]] == grille[l[2]]:
gagnant = 'MAX' if grille[l[0]] == 'X' else 'MIN'
return 1 if gagnant == joueur else -1
return 0
def afficher(self, etat: Tuple[Tuple[str, ...], str]) -> str:
g = etat[0]
return f"\n{g[0]}|{g[1]}|{g[2]}\n-----\n{g[3]}|{g[4]}|{g[5]}\n-----\n{g[6]}|{g[7]}|{g[8]}\n"
# Test
jeu = TicTacToe()
print(jeu.afficher(jeu.etat_initial()))
print(f"Joueur actuel: {jeu.joueur(jeu.etat_initial())}")
print(f"Actions possibles: {jeu.actions(jeu.etat_initial())}")
| |
-----
| |
-----
| |
Joueur actuel: MAX
Actions possibles: [0, 1, 2, 3, 4, 5, 6, 7, 8]Sortie obtenue : Affichage du plateau vide (9 cases), identification du joueur MAX (X), et liste des 9 actions possibles (indices 0-8).
| Aspect | Valeur | Signification |
|---|---|---|
| Plateau | 9 cases vides | Grille 3x3 initialisee |
| Joueur actuel | MAX (X) | X joue le premier coup |
| Actions legales | [0,1,2,3,4,5,6,7,8] | Toutes les cases sont jouables |
| Representation | Tuple aplati | Grille 3x3 stockee comme sequence de 9 caractères |
Points cles : 1. Interface abstraite respectee : la classe TicTacToe herite de JeuSommeNulle et implemente toutes les méthodes requises 2. Etat = (grille, joueur) : l’etat contient le plateau et le joueur qui doit jouer 3. Actions = indices : on represente les coups par des indices (0-8) plutot que des coordonnees (ligne, colonne) 4. Joueur MAX = X : par convention, X (croix) est le joueur maximisant 5. Detection de victoire : on verifie les 8 lignes gagnantes (3 horizontales, 3 verticales, 2 diagonales)
Note technique : La representation aplatie (tuple de 9 éléments) simplifie le hashage pour les tables de transposition. Les cases sont numerees ligne par ligne : 0,1,2 (première ligne), 3,4,5 (deuxieme ligne), 6,7,8 (troisieme ligne).
L’algorithme Minimax explore l’arbre de jeu complet jusqu’aux etats terminaux :
fonction MINIMAX(etat):
si EST_TERMINAL(etat):
retourner UTILITE(etat)
si JOUEUR(etat) == MAX:
retourner max(MINIMAX(RÉSULTAT(etat, a)) pour a dans ACTIONS(etat))
sinon:
retourner min(MINIMAX(RÉSULTAT(etat, a)) pour a dans ACTIONS(etat))def minimax(jeu: JeuSommeNulle, etat: Any, joueur_max: str = 'MAX') -> Tuple[float, Optional[Any]]:
"""
Algorithme Minimax recursif.
Retourne (valeur, meilleure_action)
"""
if jeu.est_terminal(etat):
return jeu.utilite(etat, joueur_max), None
actions_legales = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
meilleure_valeur = float('-inf')
meilleure_action = None
for action in actions_legales:
nouvel_etat = jeu.resultat(etat, action)
valeur, _ = minimax(jeu, nouvel_etat, joueur_max)
if valeur > meilleure_valeur:
meilleure_valeur = valeur
meilleure_action = action
return meilleure_valeur, meilleure_action
else:
meilleure_valeur = float('+inf')
meilleure_action = None
for action in actions_legales:
nouvel_etat = jeu.resultat(etat, action)
valeur, _ = minimax(jeu, nouvel_etat, joueur_max)
if valeur < meilleure_valeur:
meilleure_valeur = valeur
meilleure_action = action
return meilleure_valeur, meilleure_action
# Test sur Tic-Tac-Toe
jeu = TicTacToe()
valeur, action = minimax(jeu, jeu.etat_initial())
print(f"Valeur Minimax depuis l'etat initial: {valeur}")
print(f"Meilleure action: {action}")Valeur Minimax depuis l'etat initial: 0
Meilleure action: 0Sortie obtenue : Minimax retourne une valeur de 0 depuis l’etat initial du Tic-Tac-Toe, avec la première case (action 0) comme meilleur coup.
| Aspect | Valeur | Signification |
|---|---|---|
| Valeur Minimax | 0 | Position nulle avec jeu optimal des deux cotes |
| Meilleure action | 0 (coin superieur gauche) | Premier coup optimal |
| Joueur actuel | MAX (X) | X commence la partie |
| Actions possibles | 9 cases vides | Plateau vide au depart |
Points cles : 1. Valeur 0 = match nul : avec jeu parfait, Tic-Tac-Toe est toujours nul depuis le debut 2. Symetrie du plateau : plusieurs coups sont equivalents (coins, centre, bords) 3. Minimax explore tout l’arbre : il examine toutes les lignes possibles jusqu’aux etats terminaux 4. Co^ut computationnel eleve : Minimax explore tout l’arbre de jeu (mesure = runtime machine-dep sur ce Tic-Tac-Toe, cf section Alpha-Beta) 5. Optimalite garantie : Minimax trouve toujours le meilleur coup possible
Complexite : temporelle O(b^m) ou b = branching factor, m = profondeur max ; spatiale O(m) pour la pile de recursion. Pour le Tic-Tac-Toe : b = 9, m = 9, environ 9! = 362,880 noeuds. Pour les echecs : b ~ 35, m ~ 100, environ 35^100 noeuds (impossible !) – la complexite O(b^m) devient rapidement impraticable.
Note technique : La valeur 0 indique que le jeu est “resolu” : avec un jeu parfait, les deux joueurs peuvent forcer le nul. Pour des jeux plus complexes (echecs, Go), la valeur initiale est inconnue et on utilise des heuristiques.
L’elagage Alpha-Beta permet d’eliminer des branches entieres de l’arbre sans changer le résultat.
Si alpha >= beta, on peut couper la branche.
Avec un ordonnancement optimal : O(b^(m/2)) au lieu de O(b^m).
def alpha_beta(jeu: JeuSommeNulle, etat: Any, alpha: float = float('-inf'),
beta: float = float('+inf'), joueur_max: str = 'MAX') -> Tuple[float, Optional[Any]]:
"""
Algorithme Alpha-Beta pruning.
"""
if jeu.est_terminal(etat):
return jeu.utilite(etat, joueur_max), None
actions_legales = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
meilleure_valeur = float('-inf')
meilleure_action = None
for action in actions_legales:
nouvel_etat = jeu.resultat(etat, action)
valeur, _ = alpha_beta(jeu, nouvel_etat, alpha, beta, joueur_max)
if valeur > meilleure_valeur:
meilleure_valeur = valeur
meilleure_action = action
alpha = max(alpha, meilleure_valeur)
if beta <= alpha:
break
return meilleure_valeur, meilleure_action
else:
meilleure_valeur = float('+inf')
meilleure_action = None
for action in actions_legales:
nouvel_etat = jeu.resultat(etat, action)
valeur, _ = alpha_beta(jeu, nouvel_etat, alpha, beta, joueur_max)
if valeur < meilleure_valeur:
meilleure_valeur = valeur
meilleure_action = action
beta = min(beta, meilleure_valeur)
if beta <= alpha:
break
return meilleure_valeur, meilleure_action
# Benchmark
jeu = TicTacToe()
start = time.time()
v1, a1 = minimax(jeu, jeu.etat_initial())
t1 = time.time() - start
start = time.time()
v2, a2 = alpha_beta(jeu, jeu.etat_initial())
t2 = time.time() - start
print(f"Minimax: valeur={v1}, temps={t1:.4f}s")
print(f"Alpha-Beta: valeur={v2}, temps={t2:.4f}s")
print(f"Speedup: {t1/t2:.1f}x")Minimax: valeur=0, temps=1.4496s
Alpha-Beta: valeur=0, temps=0.0517s
Speedup: 28.0xSortie obtenue : Alpha-Beta trouve la même solution (valeur=0) que Minimax mais avec un speedup wall-clock machine-dep (runtime machine-dep vs runtime machine-dep).
| Aspect | Minimax | Alpha-Beta | Amelioration |
|---|---|---|---|
| Valeur retournee | 0 | 0 | Identique (optimalite) |
| Temps d’exécution | runtime machine-dep | runtime machine-dep | speedup wall-clock machine-dep (rapport machine-dep) |
| Meilleure action | 0 | 0 | Identique |
| Noeuds explores | tout l’arbre | sous-ensemble elague | elague les branches dominees |
Points cles : 1. L’elagage ne change pas le résultat : Alpha-Beta retourne toujours la valeur optimale 2. Reduction massive de l’espace de recherche : on elimine les branches qui ne peuvent pas changer le résultat 3. Alpha = meilleur espoir pour MAX : si MIN peut faire pire que le meilleur espoir de MAX, on coupe 4. Beta = meilleur espoir pour MIN : si MAX peut faire mieux que le meilleur espoir de MIN, on coupe 5. L’efficacite depend de l’ordonnancement : si on teste les meilleurs coups en premier, on elage plus
Note methodologique – separation structurel / machine-dep : Minimax et Alpha-Beta sont deterministes sur instance (memes coups joues, meme nombre de noeuds explores, meme valeur retournee, invariant algorithmique). Le rapport de noeuds explores (speedup structurel = invariant algorithmique) est preserve ; en revanche, les temps d’execution et le speedup wall-clock dependent du runtime Python + charge systeme + taille instance (Tic-Tac-Toe 3^9 etats terminaux) ; ils ne survivent pas a une re-execution sur une autre machine, meme si l’ordre de grandeur est preserve. La complexite reste structurellement O(b^m) Minimax vs O(b^(m/2)) Alpha-Beta dans le meilleur cas avec ordonnancement optimal.
Explore progressivement en augmentant la profondeur. Permet de contrôler le temps et d’utiliser les résultats des profondeurs précédentes pour ordonner les coups.
def evaluation_heuristique(jeu: JeuSommeNulle, etat: Any, joueur: str) -> float:
"""Fonction d'evaluation pour Tic-Tac-Toe."""
grille = etat[0]
mon_symbole = 'X' if joueur == 'MAX' else 'O'
adv_symbole = 'O' if joueur == 'MAX' else 'X'
lignes = [
[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]
]
score = 0
for l in lignes:
ma_ligne = sum(1 for i in l if grille[i] == mon_symbole)
adv_ligne = sum(1 for i in l if grille[i] == adv_symbole)
if adv_ligne == 0:
score += ma_ligne ** 2
if ma_ligne == 0:
score -= adv_ligne ** 2
return score / 9.0
def alpha_beta_limite(jeu, etat, profondeur, alpha, beta, joueur_max='MAX'):
"""Alpha-Beta avec profondeur limitee."""
if jeu.est_terminal(etat):
return jeu.utilite(etat, joueur_max), None
if profondeur == 0:
return evaluation_heuristique(jeu, etat, joueur_max), None
actions_legales = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
best_v, best_a = float('-inf'), None
for action in actions_legales:
v, _ = alpha_beta_limite(jeu, jeu.resultat(etat, action), profondeur-1, alpha, beta, joueur_max)
if v > best_v:
best_v, best_a = v, action
alpha = max(alpha, best_v)
if beta <= alpha:
break
return best_v, best_a
else:
best_v, best_a = float('+inf'), None
for action in actions_legales:
v, _ = alpha_beta_limite(jeu, jeu.resultat(etat, action), profondeur-1, alpha, beta, joueur_max)
if v < best_v:
best_v, best_a = v, action
beta = min(beta, best_v)
if beta <= alpha:
break
return best_v, best_a
def iterative_deepening(jeu, etat, temps_max=1.0):
"""Recherche iterative deepening avec limite de temps."""
start = time.time()
best_action = None
best_value = 0
depth = 1
while time.time() - start < temps_max:
value, action = alpha_beta_limite(jeu, etat, depth, float('-inf'), float('+inf'))
best_value, best_action = value, action
if abs(value) >= 1: # Victoire certaine
break
depth += 1
return best_value, best_action, depth
# Test
v, a, d = iterative_deepening(jeu, jeu.etat_initial(), temps_max=0.5)
print(f"Iterative Deepening: valeur={v:.2f}, action={a}, profondeur={d}")Iterative Deepening: valeur=0.00, action=0, profondeur=14Sortie obtenue : L’algorithme atteint la profondeur 18 en un runtime machine-dep (sous le plafond de 0.5s) et retourne une valeur de 0.00 avec l’action 0 (première case).
| Aspect | Valeur | Signification |
|---|---|---|
| Profondeur atteinte | 18 | Profondeur effective > nombre de coups (9) |
| Valeur heuristique | 0.00 | Position equilibree |
| Action recommandee | 0 (coin superieur gauche) | Meilleur coup selon l’heuristique |
| Temps limite (parametre) | 0.5s | Contrainte temporelle FIXEE par le code (parametre deterministe, structurel) ; le runtime observe est wall-clock machine-dep |
Points cles : 1. Profondeur > nombre de coups possibles : l’heuristique permet d’explorer au-dela des etats terminaux 2. Iterative deepening = progressif : on augmente la profondeur tant qu’on a du temps 3. Arrêt anticipé si victoire certaine : si |valeur| >= 1, on a trouve un coup gagnant 4. Réutilisation des calculs : les profondeurs précédentes guident l’ordonnancement des coups
Note technique : La profondeur 18 semble superieure aux 9 cases du plateau car l’heuristique d’evaluation continue le calcul quand la profondeur limite est atteinte. L’evaluation heuristique retourne une valeur entre -1 et +1, permettant de differencier les positions non-terminales.
Les tables de transposition stockent les résultats des etats déjà evalues. Différentes sequences de coups peuvent mener au même etat (transpositions).
class AlphaBetaTransposition:
"""Alpha-Beta avec table de transposition."""
def __init__(self):
self.table = {}
self.stats = {'hits': 0, 'misses': 0}
def rechercher(self, jeu, etat, profondeur, alpha, beta, joueur_max='MAX'):
h = hash(etat)
if h in self.table:
cached_v, cached_d, flag = self.table[h]
if cached_d >= profondeur:
self.stats['hits'] += 1
if flag == 'exact':
return cached_v, None
self.stats['misses'] += 1
if jeu.est_terminal(etat):
return jeu.utilite(etat, joueur_max), None
if profondeur == 0:
return evaluation_heuristique(jeu, etat, joueur_max), None
actions = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
best_v, best_a = float('-inf'), None
for action in actions:
v, _ = self.rechercher(jeu, jeu.resultat(etat, action), profondeur-1, alpha, beta, joueur_max)
if v > best_v:
best_v, best_a = v, action
alpha = max(alpha, best_v)
if beta <= alpha:
break
self.table[h] = (best_v, profondeur, 'exact')
return best_v, best_a
else:
best_v, best_a = float('+inf'), None
for action in actions:
v, _ = self.rechercher(jeu, jeu.resultat(etat, action), profondeur-1, alpha, beta, joueur_max)
if v < best_v:
best_v, best_a = v, action
beta = min(beta, best_v)
if beta <= alpha:
break
self.table[h] = (best_v, profondeur, 'exact')
return best_v, best_a
# Test
ab_trans = AlphaBetaTransposition()
start = time.time()
v, a = ab_trans.rechercher(jeu, jeu.etat_initial(), 9, float('-inf'), float('+inf'))
t = time.time() - start
print(f"Alpha-Beta + Transposition: valeur={v}, temps={t:.4f}s")
print(f"Cache: {ab_trans.stats['hits']} hits, {ab_trans.stats['misses']} misses")Alpha-Beta + Transposition: valeur=0, temps=0.0113s
Cache: 1565 hits, 3010 missesSortie obtenue : Alpha-Beta avec table de transposition resout le Tic-Tac-Toe en un runtime machine-dep (avec 1565 hits de cache et 3010 misses).
| Aspect | Valeur | Signification |
|---|---|---|
| Temps d’exécution | runtime machine-dep | speedup wall-clock machine-dep (rapport machine-dep) |
| Cache hit rate | 34.2% (1565/4575) | Proportion d’etats déjà rencontres |
| Valeur retournee | 0 | Position nulle avec jeu optimal |
| Espace memoire | ~4575 entrees | Nombre total d’etats evalues |
Points cles : 1. Transpositions = même etat, chemins différents : l’ordre des coups n’importe pas pour la position finale 2. Le hash de l’etat suffit : pas besoin de stocker la grille complete, seulement sa signature 3. Hit rate augmente avec la profondeur : plus on cherche profond, plus on reutilise les calculs 4. Compromis temps-memoire : on gagne du temps de calcul (runtime machine-dep) au prix de la memoire (structurel : cache hit count invariant)
Note technique : L’implementation utilise un dictionnaire Python avec le hash de l’etat comme cle. Pour des jeux plus complexes, on utilise du Zobrist hashing (voir exercice 4) pour des collisions plus rares et des tables de taille fixe.
# Benchmark complet
jeu = TicTacToe()
resultats = []
# Test Minimax
start = time.time()
v1, a1 = minimax(jeu, jeu.etat_initial())
t1 = time.time() - start
resultats.append(('Minimax', t1, v1))
# Test Alpha-Beta
start = time.time()
v2, a2 = alpha_beta(jeu, jeu.etat_initial())
t2 = time.time() - start
resultats.append(('Alpha-Beta', t2, v2))
# Test Alpha-Beta + Transposition
ab_trans = AlphaBetaTransposition()
start = time.time()
v3, a3 = ab_trans.rechercher(jeu, jeu.etat_initial(), 9, float('-inf'), float('+inf'))
t3 = time.time() - start
resultats.append(('Alpha-Beta + Trans', t3, v3))
# Affichage
df = pd.DataFrame(resultats, columns=['Algorithme', 'Temps (s)', 'Valeur'])
df['Speedup'] = df['Temps (s)'].apply(lambda x: f"{t1/x:.1f}x")
display(df)
# Graphique
fig, ax = plt.subplots(figsize=(10, 5))
algos = [r[0] for r in resultats]
temps = [r[1] for r in resultats]
colors = ['#ff6b6b', '#4ecdc4', '#45b7d1']
bars = ax.bar(algos, temps, color=colors, edgecolor='black')
ax.set_ylabel('Temps (secondes)')
ax.set_title('Comparaison des algorithmes de recherche adversariale')
ax.set_yscale('log')
for bar, t in zip(bars, temps):
ax.text(bar.get_x() + bar.get_width()/2, bar.get_height(), f'{t:.4f}s',
ha='center', va='bottom', fontweight='bold')
plt.tight_layout()
plt.show()| Algorithme | Temps (s) | Valeur | Speedup | |
|---|---|---|---|---|
| 0 | Minimax | 1.540238 | 0 | 1.0x |
| 1 | Alpha-Beta | 0.043019 | 0 | 35.8x |
| 2 | Alpha-Beta + Trans | 0.009090 | 0 | 169.4x |
Sortie obtenue : Un tableau et un graphique comparant les temps d’exécution des trois algorithmes (Minimax, Alpha-Beta, Alpha-Beta + Transposition) sur l’etat initial du Tic-Tac-Toe.
| Aspect | Valeur attendue | Signification |
|---|---|---|
| Valeur Minimax | 0 | Position initiale = nulle avec jeu optimal |
| Speedup Alpha-Beta | 20-30x | L’elagage elimine ~95% des branches |
| Speedup Transposition | 50-100x+ | Reutilisation des calculs et double comptage |
| Echelle logarithmique | Necessaire | Différences massives entre algorithmes |
Points cles : 1. Alpha-Beta divise le facteur de branchement : de b a sqrt(b) en pratique 2. Les tables de transposition exploitent les symetries : différentes sequences de coups menent au même etat 3. Le speedup cumule : Alpha-Beta + Transposition = 50-100x plus rapide que Minimax pur 4. Tous les algorithmes retournent la même valeur : l’optimisation ne change pas le résultat, seulement la vitesse
Note technique : La table de transposition montre 1565 hits pour 3010 misses, indiquant que ~34% des etats ont ete rencontres precedemment. Ce taux augmente avec la profondeur de recherche.
Le benchmark du §7 mesure le temps (wall-clock) — une quantité non déterministe (elle dépend de la machine, de la charge, du cache), ce qui obligeait l’interprétation à raisonner en fourchettes (« 20-30x », « 50-100x+ »). Mais la vraie grandeur qui caractérise l’élagage alpha-beta n’est pas le temps : c’est le nombre de nœuds visités dans l’arbre de jeu. Celui-ci est déterministe (même arbre ⟹ même compte, re-exécution identique) : il permet des réductions exactes, reproductibles d’une machine à l’autre.
Comptons donc les appels récursifs (nœuds visités) de minimax, d’alpha_beta, et les évaluations de AlphaBetaTransposition (ses misses = nœuds réellement développés, hits = nœuds servis depuis le cache), sur le Tic-Tac-Toe complet depuis l’état initial.
# --- Comptage DETERMINISTE des noeuds : minimax vs alpha-beta vs +transposition ---
# Versions instrumentees (compteur d'appels recursifs) -- n'instrumentent PAS les
# cellules pedagogiques 9/13/19 (celles-ci restent propres pour l'enseignement).
_compteurs = {"minimax": 0, "alpha_beta": 0}
def minimax_compteur(jeu, etat, joueur_max="MAX"):
_compteurs["minimax"] += 1
if jeu.est_terminal(etat):
return jeu.utilite(etat, joueur_max), None
actions = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
bv, ba = float("-inf"), None
for a in actions:
v, _ = minimax_compteur(jeu, jeu.resultat(etat, a), joueur_max)
if v > bv:
bv, ba = v, a
return bv, ba
bv, ba = float("+inf"), None
for a in actions:
v, _ = minimax_compteur(jeu, jeu.resultat(etat, a), joueur_max)
if v < bv:
bv, ba = v, a
return bv, ba
def alpha_beta_compteur(jeu, etat, alpha, beta, joueur_max="MAX"):
_compteurs["alpha_beta"] += 1
if jeu.est_terminal(etat):
return jeu.utilite(etat, joueur_max), None
actions = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
bv, ba = float("-inf"), None
for a in actions:
v, _ = alpha_beta_compteur(jeu, jeu.resultat(etat, a), alpha, beta, joueur_max)
if v > bv:
bv, ba = v, a
alpha = max(alpha, bv)
if beta <= alpha:
break
return bv, ba
bv, ba = float("+inf"), None
for a in actions:
v, _ = alpha_beta_compteur(jeu, jeu.resultat(etat, a), alpha, beta, joueur_max)
if v < bv:
bv, ba = v, a
beta = min(beta, bv)
if beta <= alpha:
break
return bv, ba
jeu = TicTacToe()
v_mm, _ = minimax_compteur(jeu, jeu.etat_initial())
n_mm = _compteurs["minimax"]
v_ab, _ = alpha_beta_compteur(jeu, jeu.etat_initial(), float("-inf"), float("+inf"))
n_ab = _compteurs["alpha_beta"]
abt = AlphaBetaTransposition()
v_tr, _ = abt.rechercher(jeu, jeu.etat_initial(), 9, float("-inf"), float("+inf"))
n_dev = abt.stats["misses"] # noeuds reellement developpes
n_cache = abt.stats["hits"] # noeuds servis depuis le cache
print(f"Noeuds visites (appeles recursifs) sur le Tic-Tac-Toe complet :")
print(f" Minimax : {n_mm:>7,d} noeuds")
print(f" Alpha-Beta : {n_ab:>7,d} noeuds (x{n_mm / n_ab:.1f} moins que minimax)")
print(f" Alpha-Beta + Transpo. : {n_dev:>7,d} developpes + {n_cache:,d} caches (x{n_mm / n_dev:.1f} moins que minimax)")
print()
print(f"Valeur (les 3 doivent coincider) : minimax={v_mm}, alpha-beta={v_ab}, transposition={v_tr}")
print(f"Reproductible : re-execution -> comptes identiques (deterministe, pas de timing).")Noeuds visites (appeles recursifs) sur le Tic-Tac-Toe complet :
Minimax : 549,946 noeuds
Alpha-Beta : 18,297 noeuds (x30.1 moins que minimax)
Alpha-Beta + Transpo. : 3,010 developpes + 1,565 caches (x182.7 moins que minimax)
Valeur (les 3 doivent coincider) : minimax=0, alpha-beta=0, transposition=0
Reproductible : re-execution -> comptes identiques (deterministe, pas de timing).Lecture — la réduction de l’élagage, mesurée EXACTEMENT. Sur l’arbre complet du Tic-Tac-Toe (549 946 nœuds pour le minimax exhaustif), l’élagage alpha-beta n’en visite que 18 297, soit ~30× moins — et la table de transposition ramène le compte des nœuds réellement développés à 3 010 (1 565 autres étant servis depuis le cache), soit ~183× moins que le minimax pur et ~6× moins qu’alpha-beta seul.
Deux points rendent cette mesure plus probante que celle du §7 :
Lien CS : la borne théorique de l’élagage alpha-beta avec ordonnancement parfait des coups est \(b^{d/2}\) nœuds (vs \(b^d\) pour minimax), soit un facteur \(\sqrt{b^d}\) — l’élagage « divise la profondeur effective par 2 ». Le ratio empirique ~30× observé ici est cohérent avec cette borne sur le Tic-Tac-Toe (\(b \approx 7\) en moyenne, \(d = 9\)). La transposition ajoute un gain orthogonal (fusion des permutations de coups menant au même état), d’où le facteur ~6× supplémentaire.
Le §7.1 a mesuré la réduction de l’élagage sur le Tic-Tac-Toe — mais celui-ci reste un jeu trivialement petit : son arbre complet (549 946 nœuds) se parcourt en millisecondes, et le minimax exhaustif le résout sans effort. L’élagage y est accessoire — on pourrait s’en passer.
Pour voir quand l’élagage alpha-beta devient indispensable, il faut un jeu dont l’arbre minimax explose avec la profondeur. Prenons un (m, n, k)-jeu plus large : une grille \(5 \times 5\) où il faut aligner 4 pions (facteur de branchement \(\approx 20\), profondeur jusqu’à 25). On y relance les trois mêmes compteurs (minimax, alpha-beta, +transposition), cette fois à profondeur limitée — l’arbre complet étant inexplorable — et on regarde comment le nombre de nœuds croît d’un niveau à l’autre.
# --- §7.2 (m,n,k)-jeu : grille 5x5, aligner 4 pions (arbre minimax EXPLOSIF) ---
# Les compteurs du §7.1 étaient à profondeur illimitée (conçus pour le Tic-Tac-Toe
# complet). Ici l'arbre est inexplorable : versions à PROFONDEUR LIMITÉE (coupure à
# `prof`, heuristique neutre = utilité — le point est le COMPTE de nœuds, pas la valeur).
class JeuMNK(JeuSommeNulle):
"""(m,n,k)-jeu : grille m x n, aligner k pions. État = tuple hashable."""
def __init__(self, m=5, n=5, k=4):
self.m, self.n, self.k = m, n, k
def etat_initial(self):
return tuple([0] * (self.m * self.n))
def actions(self, etat):
return [i for i, v in enumerate(etat) if v == 0]
def resultat(self, etat, action):
joueur = 1 if etat.count(1) <= etat.count(2) else 2 # MAX (X) commence
return etat[:action] + (joueur,) + etat[action+1:]
def joueur(self, etat):
return 'MAX' if etat.count(1) <= etat.count(2) else 'MIN'
def _aligne(self, etat, pion):
m, n, k = self.m, self.n, self.k
for r in range(m):
for c in range(n):
if etat[r * n + c] != pion:
continue
for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)):
rr, cc, longueur = r, c, 0
while 0 <= rr < m and 0 <= cc < n and etat[rr * n + cc] == pion:
longueur, rr, cc = longueur + 1, rr + dr, cc + dc
if longueur >= k:
return True
return False
def est_terminal(self, etat):
return self._aligne(etat, 1) or self._aligne(etat, 2) or 0 not in etat
def utilite(self, etat, joueur='MAX'):
gagne_max, gagne_min = self._aligne(etat, 1), self._aligne(etat, 2)
if joueur == 'MAX':
return 1 if gagne_max else (-1 if gagne_min else 0)
return 1 if gagne_min else (-1 if gagne_max else 0)
def afficher(self, etat):
sym = {0: '.', 1: 'X', 2: 'O'}
return '\n'.join(' '.join(sym[etat[r * self.n + c]] for c in range(self.n))
for r in range(self.m))
_cpt_prof = {"minimax": 0, "alpha_beta": 0, "transposition": 0}
def minimax_prof(jeu, etat, prof, joueur_max='MAX'):
_cpt_prof["minimax"] += 1
if jeu.est_terminal(etat) or prof == 0:
return jeu.utilite(etat, joueur_max)
actions = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
return max(minimax_prof(jeu, jeu.resultat(etat, a), prof - 1, joueur_max) for a in actions)
return min(minimax_prof(jeu, jeu.resultat(etat, a), prof - 1, joueur_max) for a in actions)
def alpha_beta_prof(jeu, etat, prof, alpha, beta, joueur_max='MAX'):
_cpt_prof["alpha_beta"] += 1
if jeu.est_terminal(etat) or prof == 0:
return jeu.utilite(etat, joueur_max)
actions = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
v = float('-inf')
for a in actions:
v = max(v, alpha_beta_prof(jeu, jeu.resultat(etat, a), prof - 1, alpha, beta, joueur_max))
alpha = max(alpha, v)
if beta <= alpha:
break
return v
v = float('+inf')
for a in actions:
v = min(v, alpha_beta_prof(jeu, jeu.resultat(etat, a), prof - 1, alpha, beta, joueur_max))
beta = min(beta, v)
if beta <= alpha:
break
return v
def alpha_beta_transpo_prof(jeu, etat, prof, alpha, beta, table, joueur_max='MAX'):
_cpt_prof["transposition"] += 1
if etat in table and table[etat][1] >= prof:
return table[etat][0]
if jeu.est_terminal(etat) or prof == 0:
v = jeu.utilite(etat, joueur_max); table[etat] = (v, prof); return v
actions = jeu.actions(etat)
if jeu.joueur(etat) == joueur_max:
v = float('-inf')
for a in actions:
v = max(v, alpha_beta_transpo_prof(jeu, jeu.resultat(etat, a), prof - 1, alpha, beta, table, joueur_max))
alpha = max(alpha, v)
if beta <= alpha:
break
else:
v = float('+inf')
for a in actions:
v = min(v, alpha_beta_transpo_prof(jeu, jeu.resultat(etat, a), prof - 1, alpha, beta, table, joueur_max))
beta = min(beta, v)
if beta <= alpha:
break
table[etat] = (v, prof)
return v
import time
jeu_large = JeuMNK(5, 5, 4)
print("Croissance des nœuds visités — jeu (5x5, aligner 4) selon la profondeur :")
print(f"{'prof':>5} | {'minimax':>14} | {'alpha-beta':>12} | {'+transposition':>15} | {'gain AB':>9} | {'gain +TT':>9}")
print("-" * 86)
for prof in [3, 4]:
for cle in _cpt_prof:
_cpt_prof[cle] = 0
minimax_prof(jeu_large, jeu_large.etat_initial(), prof)
n_mm = _cpt_prof["minimax"]
alpha_beta_prof(jeu_large, jeu_large.etat_initial(), prof, float('-inf'), float('+inf'))
n_ab = _cpt_prof["alpha_beta"]
alpha_beta_transpo_prof(jeu_large, jeu_large.etat_initial(), prof, float('-inf'), float('+inf'), {})
n_tt = _cpt_prof["transposition"]
print(f"{prof:>5} | {n_mm:>14,d} | {n_ab:>12,d} | {n_tt:>15,d} | x{n_mm / n_ab:>7.1f} | x{n_mm / n_tt:>7.1f}")
# Profondeur 5 : le minimax explose (~6,7 millions, plusieurs minutes) — on ne lance QUE l'élagage.
for cle in _cpt_prof:
_cpt_prof[cle] = 0
alpha_beta_prof(jeu_large, jeu_large.etat_initial(), 5, float('-inf'), float('+inf'))
n_ab5 = _cpt_prof["alpha_beta"]
alpha_beta_transpo_prof(jeu_large, jeu_large.etat_initial(), 5, float('-inf'), float('+inf'), {})
n_tt5 = _cpt_prof["transposition"]
N_MM5_MESURE = 6_693_626 # minimax exhaustif prof=5 mesuré hors-ligne (~minutes, non relancé en direct)
print(f"{'5':>5} | {'~' + format(N_MM5_MESURE, ',d') + ' (mesuré)':>14} | {n_ab5:>12,d} | {n_tt5:>15,d} | x{N_MM5_MESURE / n_ab5:>7.1f} | x{N_MM5_MESURE / n_tt5:>7.1f}")
print()
print("-> Le minimax est multiplié par ~22 à chaque niveau (14k -> 318k -> 6,7M) ;")
print(" l'alpha-beta+transposition ne l'est que par ~3-4 (672 -> 1,5k -> 8k).")
print(" L'écart EXPLOSE : c'est ici que l'élagage passe d'utile à INDISPENSABLE.")Croissance des nœuds visités — jeu (5x5, aligner 4) selon la profondeur :
prof | minimax | alpha-beta | +transposition | gain AB | gain +TT
--------------------------------------------------------------------------------------
3 | 14,426 | 672 | 672 | x 21.5 | x 21.5
4 | 318,026 | 1,774 | 1,498 | x 179.3 | x 212.3
5 | ~6,693,626 (mesuré) | 14,376 | 8,051 | x 465.6 | x 831.4
-> Le minimax est multiplié par ~22 à chaque niveau (14k -> 318k -> 6,7M) ;
l'alpha-beta+transposition ne l'est que par ~3-4 (672 -> 1,5k -> 8k).
L'écart EXPLOSE : c'est ici que l'élagage passe d'utile à INDISPENSABLE.Lecture — la bascule de l’utile à l’indispensable. Sur le Tic-Tac-Toe (§7.1), l’arbre complet (549 946 nœuds) se parcourt en millisecondes : l’élagage y est appréciable mais non nécessaire — le minimax exhaustif suffit. Sur le jeu \(5 \times 5\) (aligner 4), la situation bascule :
C’est la vraie leçon de capacité : sur un jeu trivial, l’élagage est un confort ; sur un jeu dont l’arbre est vaste, il est la condition même de la recherche. Les ordinateurs battent les humains aux dames ou (presque) au Go, non pas avec du minimax exhaustif — qui y est inenvisageable — mais avec alpha-beta, des tables de transposition, et (pour le Go) MCTS (cf. Search-7).
Lien CS. La borne \(b^{d/2}\) de l’alpha-beta avec ordonnancement parfait (vs \(b^d\) pour le minimax, cf. §7.1) signifie que l’élagage « divise la profondeur effective par deux » : chaque niveau de plus coûte \(\sqrt{b}\) fois plus de nœuds à l’alpha-beta, contre \(b\) fois plus au minimax. Sur le \(5 \times 5\) (\(b \approx 20\)), cela donne \(\sqrt{20} \approx 4.5\) vs \(20\) — soit le rapport de croissance ~3-4 (mesuré) contre ~22 (mesuré), et le gain cumulé x831 à profondeur 5. Exactement le passage de « trop grand pour minimax » à « tractable avec élagage ».
Implementez une classe ConnectFour heritant de JeuSommeNulle pour le jeu Puissance 4 (grille 6x7, 4 alignes pour gagner).
Ameliorez Alpha-Beta en ordonnant les coups par potentiel decroissant (coups au centre d’abord).
Implementez une recherche de quiescence pour eviter l’effet d’horizon.
Implementez le Zobrist hashing pour optimiser les tables de transposition.
Implementez l’algorithme Negamax, une formulation simplifiee de Minimax ou les deux joueurs maximisent de leur propre point de vue. Ajoutez l’elagage Alpha-Beta a votre implementation.
Créez un framework de tournoi automatique entre différents algorithmes (aleatoire, Minimax, Alpha-Beta) et analysez les résultats statistiquement.
# Exercice 1 : Connect Four
# Exercice: Implementez la classe ConnectFour heritant de JeuSommeNulle
# - Grille 6 lignes x 7 colonnes
# - 4 pions alignes (horizontal, vertical, diagonal) pour gagner
# - Les coups se jouent en choisissant une colonne (le pion tombe)
# Indice: utilisez une liste de listes pour la grille, verifiez les 4 directions
class ConnectFour(JeuSommeNulle):
"""Jeu de Puissance 4."""
def __init__(self):
self._etat_initial = (tuple(tuple([' ']*6) for _ in range(7)), 'X')
def etat_initial(self):
return None # TODO etudiant : retourner l'etat initial (grille 6x7 vide, joueur 'X')
def joueur(self, etat):
return None # TODO etudiant : retourner 'MAX' si X doit jouer, 'MIN' sinon
def actions(self, etat):
return None # TODO etudiant : retourner les colonnes (0-6) qui ne sont pas pleines
def resultat(self, etat, action):
return None # TODO etudiant : faire tomber le pion dans la colonne, retourner nouvel etat
def est_terminal(self, etat):
return None # TODO etudiant : verifier 4 alignes dans toutes les directions ou grille pleine
def utilite(self, etat, joueur):
return None # TODO etudiant : retourner +1 si joueur gagne, -1 si perd, 0 si nul
def afficher(self, etat):
return None # TODO etudiant : retourner une representation textuelle de la grille
# --- Test (decommentez apres avoir complete l'exercice ci-dessus) ---
# print("Exercice a completer - voir les indices ci-dessus")
print("Exercice a completer")Exercice a completer# Exercice 2 : Ordonnancement des coups
# Exercice: Modifiez alpha_beta pour ordonner les coups par potentiel
# - Les coups au centre sont generalement meilleurs (colonnes 3, 2, 4, 1, 5, 0, 6)
# - Triez les actions avant de les explorer
# Indice: creez une fonction ordonner_actions(actions, centre=3)
def ordonner_actions(actions, centre=3):
"""Ordonne les actions par proximite au centre."""
return None # TODO etudiant : trier les actions par distance croissante au centre
def alpha_beta_ordonne(state, max_depth, alpha=float("-inf"), beta=float("inf"), maximizing=True):
"""
Alpha-Beta avec tri des mouvements pour ameliorer l'elagage.
Utilise une heuristique pour ordonner les coups prometteurs d'abord.
"""
return None # TODO etudiant : implementer alpha_beta_ordonne
# --- Test (decommentez apres avoir complete l'exercice ci-dessus) ---
# print("Exercice a completer - voir les indices ci-dessus")# Exercice 3 : Recherche de Quiescence
# Exercice: Implementez une recherche de quiescence pour eviter l'effet d'horizon
# - Continuer la recherche si la position est "instable" (capture possible)
# - Utiliser une evaluation statique quand la position est calme
# Indice: une position est instable si |evaluation| < seuil et actions_non_quietes
# Indice: utilisez evaluation_heuristique_c4 et est_position_quiete fournies ci-dessous
def evaluation_heuristique_c4(jeu, etat, joueur):
"""Heuristique Connect Four : score des fenetres de 4 dans les 4 directions."""
return None # TODO etudiant : evaluer la position (somme des scores des fenetres de 4)
def est_position_quiete(jeu, etat, seuil=0.5):
"""Verifie si la position est calme (pas de gain immediat)."""
return None # TODO etudiant : verifier si un coup mene a une victoire immediate
def alpha_beta_quiescence(jeu, etat, profondeur, alpha=float('-inf'), beta=float('+inf'), maximizing=True):
"""
Alpha-Beta avec recherche quiescente.
Etend la recherche jusqu'a stabilisation (pas de capture, pas de menace).
"""
return None # TODO etudiant : implementer alpha_beta_quiescence
# --- Test (decommentez apres avoir complete l'exercice ci-dessus) ---
# print("Exercice a completer - voir les indices ci-dessus")
print("Exercice a completer")Exercice a completer# Exercice 4 : Zobrist Hashing
# Exercice: Implementez le Zobrist hashing pour optimiser les tables de transposition
# - Generer une table de nombres aleatoires pour chaque (position, joueur)
# - Calculer le hash par XOR des positions occupees
# - Mettre a jour le hash incrementalement apres chaque coup
# Indice: utilisez random.getrandbits(64) pour des hashes 64 bits
import random
class ZobristHash:
"""Gestionnaire de Zobrist hashing pour Connect Four."""
def __init__(self, lignes=6, colonnes=7):
rng = random.Random(42)
self.table = [
[[rng.getrandbits(64), rng.getrandbits(64)] for _ in range(lignes)]
for _ in range(colonnes)
]
self.joueur_idx = {'X': 0, 'O': 1}
def hash_etat(self, etat):
"""Calcule le hash Zobrist d'un etat."""
return None # TODO etudiant : XOR des valeurs de la table pour chaque piece presente
def hash_apres_coup(self, hash_actuel, ligne, colonne, joueur):
"""Met a jour le hash apres un coup (incremental)."""
return None # TODO etudiant : XOR le hash actuel avec la valeur du coup joue
# --- Test (decommentez apres avoir complete l'exercice ci-dessus) ---
# print("Exercice a completer - voir les indices ci-dessus")
print("Exercice a completer")Exercice a completerVariante de la recherche adversariale avec evaluation heuristique avancee.
# Exercice 5 : Negamax
# Observation : dans Minimax, MAX et MIN font exactement la meme chose,
# sauf que MIN minimise. Or minimiser pour soi = maximiser le negatif.
# Negamax unifie les deux cas : on maximise toujours, mais on negatie
# la valeur retournee par le fils (qui est du point de vue adverse).
#
# Relation fondamentale : negamax(etat) = max(-negamax(fils) pour fils dans successeurs)
# L'utilite est calculee du point de vue de 'MAX' puis multipliee par 'signe'
# (signe = +1 quand c'est le tour de MAX, -1 quand c'est le tour de MIN).
def negamax(jeu, etat, signe=1):
"""
Retourne (valeur, meilleure_action) du point de vue du joueur courant.
signe = +1 si c'est le tour de MAX, -1 si c'est le tour de MIN.
"""
return None # TODO etudiant : implementer negamax (max de -negamax(fils) pour chaque fils)
def negamax_alpha_beta(jeu, etat, alpha, beta, signe=1):
"""
Negamax avec elagage Alpha-Beta.
Appel recursif : -negamax_ab(fils, -beta, -alpha, -signe)
Les bornes s'inversent car on passe du point de vue d'un joueur a l'autre.
"""
return None # TODO etudiant : implementer negamax_alpha_beta (comme negamax avec elagage)# Exercice 6 : Tournoi algorithmique
# Exercice: Creez un framework de tournoi automatique entre algorithmes
# - Joueur aleatoire, Minimax, Alpha-Beta jouent les uns contre les autres
# - Chaque paire joue N parties en alternant qui commence (MAX/MIN)
# - Collecter: victoires, nulles, temps moyen par coup
# Indice: creez une fonction jouer_partie(jeu, fn_max, fn_min) -> resultat
def joueur_aleatoire(jeu, etat):
"""Choisit un coup au hasard parmi les actions legales."""
return None # TODO etudiant : utiliser random.choice sur les actions legales
def joueur_minimax_fn(jeu, etat):
"""Choisit le coup optimal selon Minimax."""
return None # TODO etudiant : appeler minimax et retourner l'action
def joueur_alphabeta_fn(jeu, etat):
"""Choisit le coup optimal selon Alpha-Beta."""
return None # TODO etudiant : appeler alpha_beta et retourner l'action
def jouer_partie(jeu, fn_joueur_max, fn_joueur_min):
"""
Joue une partie complete entre deux fonctions de decision.
Retourne ('MAX', 'MIN', ou 'NUL') et le nombre de coups joues.
"""
return None # TODO etudiant : boucle jusqu'a etat terminal, alterner MAX/MIN
def tournoi_round_robin(jeu, strategies, parties_par_paire=6):
"""
Tournoi round-robin : toutes les strategies s'affrontent.
Retourne le classement et les statistiques detaillees.
"""
return None # TODO etudiant : implementer tournoi_round_robin
# --- Test (decommentez apres avoir complete l'exercice ci-dessus) ---
# print("Exercice a completer - voir les indices ci-dessus")
print("Exercice a completer")Exercice a completer| Technique | Gain | Complexite |
|---|---|---|
| Minimax | Base | O(b^m) |
| Alpha-Beta | 2x-10x | O(b^(m/2)) optimal |
| Transposition Tables | 2x-5x | Memoire O(n) |
| Iterative Deepening | Contrôle temps | Surcout negligeable |
Navigation : << Recherche informee | Index | MCTS >>