IA02 - Résolution de morpion n×n par MCTS

Projet réalisé dans le cadre du cours IA02 : Logique et Résolution de problèmes par la recherche.

Objectif : implémenter un Monte Carlo Tree Search ainsi que diverses méthodes d'optimisations pour résoudre un problème de morption n×n

Le jeu : morpion "k-alignés" (façon Gomoku)

Le morpion 3×3 classique généralisé naïvement en taille n×n, en gardant la règle "aligner une ligne entière", devient absurde dès que n dépasse 4 ou 5 : il faudrait aligner 15 pions sur une grille 15×15, ce qui n'arrive jamais en pratique. La partie se termine presque toujours nulle.

Ce projet généralise donc la condition de victoire à k pions alignés, k étant fixé indépendamment de n (par exemple k=4 ou 5). Une grille 15×15 avec k=5 reste un jeu réellement gagnable, tout en ayant un espace d'états bien trop grand pour une recherche exhaustive -> c'est précisément le régime où MCTS est pertinent.

Architecture

src/ia02/
├── types.py              Types de base (Cell, Player, Action, Score, Strategy)
├── rules.py              Détection "k pions alignés", vectorisée numpy
├── board.py              Plateau immuable (numpy), coups, victoire, plateau->str
├── symmetry.py           Groupe D4 (8 symétries) et forme canonique
├── cache.py              Décorateurs @memoize et @memoize_canonical
├── players/
│   ├── baseline.py       Stratégies aléatoire / premier coup légal
│   ├── minimax.py        Minimax + alpha-bêta + heuristique (référence)
│   └── mcts.py           MCTS/UCT avec statistiques partagées par symétrie
├── game.py               Boucle de jeu (fait s'affronter deux stratégies)
└── cli.py                Interface en ligne de commande
tests/                    Suite pytest (63 tests)
benchmarks/benchmark.py   Bancs de mesure illustratifs (temps, table de transposition)

Le plateau : numpy, immuable, hashable

La classe Board encapsule un tableau numpy n×n rendu en lecture seule (cells.setflags(write=False)).

Chaque coup (Board.play) renvoie un nouveau Board plutôt que de modifier l'existant :

board.legal_actions()         # np.where(cells == EMPTY)  -> liste de (r, c)
board.is_full()               # np.all(cells != EMPTY)
board.play(Cell.X, (2, 3))    # copie + écriture + re-verrouillage en lecture seule

L'avantage de ce Board immuable est qu'il est alors hashable (hash calculé une fois sur les octets bruts du tableau) et donc utilisable directement comme clé de cache ou de table de transposition

La détection de victoire (rules.has_k_in_a_row) est entièrement vectorisée avec numpy.lib.stride_tricks.sliding_window_view : on calcule en une seule expression toutes les fenêtres de k cases consécutives sur les lignes et les colonnes, et on boucle uniquement sur les diagonales (il y en a O(n), donc négligeable) plutôt que sur chacune des n² cases individuellement.

Symétrie : le groupe D4

Un plateau carré admet 8 orientations stratégiquement identiques : 4 rotations (0°, 90°, 180°, 270°) et leurs 4 réflexions (le professeur appelait ça "groupe diédral D4"). Deux positions qui ne diffèrent que par une de ces transformations ont exactement les mêmes coups gagnants et la même valeur de jeu - les traiter comme des états distincts dans un cache ou un arbre de recherche gaspille du travail jusqu'à un facteur 8.

symmetry.py définit chaque élément du groupe comme une paire de fonctions gardées synchronisées :

• array_fn transforme le plateau (np.rot90, np.fliplr, .T, ...) ;
• coord_fn transforme une coordonnée (r, c) de la même façon.

canonical_form(cells) renvoie la représentation minimale (au sens lexicographique des octets) parmi les 8 - une convention arbitraire mais déterministe, qui garantit que deux plateaux symétriques retombent exactement sur le même tableau canonique, donc sur la même clé de cache.

Ce mécanisme est vérifié directement dans tests/test_symmetry.py : pour chaque symétrie, coord_fn et array_fn sont testés comme cohérents entre eux, chaque symétrie est vérifiée inversible, et canonical_form est vérifiée invariante par les 8 transformations.

Mémoïsation : @memoize et @memoize_canonical

On définit dans cache.py un décorateur générique et typé pour garder ne mémoire les différentes situations sur lesquelles on a déjà compute et leur résultat :

@memoize
def square(x: int) -> int:
    return x * x

Et sa variante consciente de la symétrie, utilisée par l'heuristique du minimax :

@memoize_canonical
def heuristic(board: Board, player: Player) -> Score:
    ...

Ainsi, avant d'effectuer tout calcul sur une position, on regarde avec memoize si on n'a pas déjà été confronté à cette action et quelle décision a été prise, ou plus largement avec memoize_canonical si on n'a pas déjà été confronté à une sysmétrie de notre situation.

Algorithme principal : MCTS / UCT

MCTS explore l'arbre de jeu par échantillonnage plutôt qu'exhaustivement, ce qui le rend utilisable même quand l'arbre complet est intraitable (n grand).

Pour cela, on utilise quatre phases répétées jusqu'à épuisement d'un budget (nombre d'itérations ou temps) :

1. Sélection : Depuis la racine, on descend l'arbre en choisissant à chaque noeud entièrement développé l'action de plus haut score UCT :

   UCT(a) = valeur_moyenne(a) ± C · sqrt(ln(N_parent) / N(a))
   

   (+ pour X qui maximise, − pour O qui minimise ; C = √2 par défaut). Le premier terme privilégie les coups qui se sont avérés bons (exploitation), le second les coups peu explorés (exploration).

2. Expansion : Au premier noeud rencontré avec un coup jamais essayé, on crée l'enfant correspondant.

3. Simulation : Depuis ce nouvel enfant, une partie aléatoire jusqu'à un état terminal donne un échantillon de résultat (+1, 0 ou −1).

4. Rétropropagation : Ce résultat remonte jusqu'à la racine, mettant à jour les statistiques de chaque ancêtre traversé.

Le coup final choisi est celui de la racine le plus visité ("robust child"), un critère moins sensible au bruit qu'une simple comparaison de valeurs moyennes sur peu d'échantillons.

Optimisation par symétrie dans MCTS

Chaque noeud calcule la forme canonique de son plateau et va chercher ses statistiques (visites, valeur moyenne par action) dans une table de transposition indexée par cette forme canonique plutôt que par le plateau brut. Deux noeuds représentant des plateaux symétriques (même joueur au trait) partagent alors le même objet de statistiques : l'expérience de recherche accumulée sur l'un profite immédiatement à l'autre, sans jamais avoir à explorer les deux séparément.

Seules les statistiques sont partagées ainsi la structure de l'arbre (quels enfants ont déjà été créés localement, quels coups restent à essayer) reste propre à chaque noeud. Garder la structure de l'arbre locale et ne partager que les statistiques évite ce piège (exemple : qu'un noeud se fasse vider la liste de tout ses coups possibles à cause de ses syémtries) tout en conservant le bénéfice principal de l'optimisation. benchmarks/benchmark.py mesure directement l'effet sur la taille de la table de transposition (moins d'entrées à nombre d'itérations égal, cf. "Résultats de benchmark" ci-dessous).

Référence de performance : MCTS vs Alpha-Beta/Heuristique

players/minimax.py fournit un minimax à profondeur limitée avec élagage alpha-bêta et une heuristique d'évaluation vectorisée. Cela sert de point de comparaison dans le README et les benchmarks : la complexité du alpha-beta explose avec n (facteur de branchement en n²), là où MCTS garde un temps de décision borné par son budget configuré, quel que soit n

Résultats de benchmark

Mesures obtenues en lançant make bench sur la machine de développement (les valeurs absolues varient selon le matériel, la tendance est ce qui compte) :

--- Effet de la symétrie sur MCTS (n=4, k=3, 300 itérations) ---
  sans    symétrie : table de transposition =   301 entrées
  avec    symétrie : table de transposition =    86 entrées

--- Passage à l'échelle : minimax profondeur 2 vs MCTS (budget fixe 0.3s) ---
  n=3 : minimax     27 ms   |   MCTS   302 ms
  n=4 : minimax    194 ms   |   MCTS   301 ms
  n=5 : minimax    513 ms   |   MCTS   308 ms
  n=6 : minimax   1125 ms   |   MCTS   304 ms
  n=7 : minimax   1989 ms   |   MCTS   318 ms

Le temps de minimax croît fortement avec n même à profondeur fixe (plus de coups légaux à chaque noeud), tandis que le temps de MCTS reste constant : il est piloté par un budget, pas par la taille du plateau.

Utilisation

Avec un environnement virtuel (Makefile)

make install      # crée .venv/ et installe le projet + outils de dev
make test         # pytest
make typecheck    # mypy --strict
make play         # partie humain vs MCTS (n=5, k=4)
make selfplay     # MCTS vs MCTS
make bench        # pour réaliser un benchmark (voir ci-dessous)

Avec Docker

make docker-build
make docker-run    # équivalent à `make play`, sans installer Python localement

En ligne de commande directement

python -m ia02.cli play --n 7 --k 4 --opponent mcts --time-budget 2.0
python -m ia02.cli selfplay --n 9 --k 5 --x mcts --o minimax --depth 2
python -m ia02.cli selfplay --n 6 --k 4 --x mcts --o mcts --no-symmetry --quiet

Options principales :

• --n (taille de grille),
• --k (pions à aligner),
• --opponent/--x/--o (human, random, first_legal, minimax, mcts),
• --depth (minimax), --time-budget/--n-iterations (MCTS),
• --no-symmetry (désactive le partage par symétrie, pour comparaison),
• --seed (seed pour reproduire les parties)

Tests

make test         # 63 tests : plateau, symétries, cache, minimax, MCTS, jeu complet
make typecheck    # mypy --strict, aucune erreur

Les tests de symétrie vérifient concrètement les propriétés mathématiques du groupe D4 (cohérence array_fn/coord_fn, inversibilité, invariance de la forme canonique) plutôt que de se contenter d'exemples isolés. Les tests de MCTS et minimax vérifient que chaque algorithme prend bien un coup gagnant immédiat ou bloque une menace immédiate - des propriétés tactiques simples mais qui auraient révélé la plupart des bugs rencontrés pendant le développement (signe UCT inversé pour O, incohérence entre statistiques partagées et structure de l'arbre, etc.).