mgs-17b-empirical-algorithm-selection

# MGS-17b — Selection empirique d’algorithmes : du podium a la carte probleme x representation x solveur

Origine

Ce notebook distille le projet L4 EPITA SCIA 2026 de Theodore Deguest (projet solo) :

PR source : jsboigeEpita/2026-Epita-Intelligence-Symbolique#42
Projet : L4-Benchmark-Cross-Paradigm
Apport verifie : protocole commun applique a trois terrains structurants (Sudoku, Puissance 4, Wordle), avec metriques uniformes, timeouts, execution parallele, checkpoints CSV et visualisations.
Reproduction WSL/Linux du 2026-08-24 : uv run pytest -q -> 20 tests passes en 21,11 s.
Limite assumee : sous Windows natif, l’orchestrateur emploie les API Unix resource et SIGALRM ; la collecte echoue. Cette limite reste visible et motive la section Linux/WSL obligatoire.

Ce que ce notebook n’est pas : un copier-coller du depot etudiant. Le geste conserve est le protocole commun et la triangulation cross-terrains ; le depot de Theodore contient les details d’implementation et la documentation utilisateur (voir sa PR).

Plan

Section	Contenu	Statut
1 (ce notebook)	Attribution, cadre theorique (Rice 1976, Smith-Miles 2009, NFL), setup env execute	tranche 1/N
2	Protocole commun : 3 terrains (Sudoku / Puissance 4 / Wordle), budgets, metriques homogenes	tranche 2/N
3	Pareto frontieres et cas discriminant (le gagnant depend de l’instance)	tranche 3/N
4	Ponts series : Search, Sudoku, GameTheory, App-7-Wordle, App-14b-ConnectFour	tranche 4/N

Les tranches 2 a 4 dependent du terrain de Theodore et arriveront dans des PR suivantes de la lane myia-po-2024:CoursIA-2. Cette premiere tranche etablit le cadre et l’attribution.

Cadre theorique : la selection empirique d’algorithmes

Trois pierres angulaires a poser avant d’attaquer la selection :

1. Le probleme de Rice (1976)

John R. Rice, The Algorithm Selection Problem, Advances in Computers vol. 15 (1976). La formalisation : on se donne un ensemble \(I\) d’instances, un ensemble \(A\) d’algorithmes, une fonction de performance \(p : I \times A \to \mathbb{R}\) (a minimiser). On cherche une fonction de selection \(s : I \to A\) qui minimise \(\sum_{i \in I} p(i, s(i))\).

La difficulte : \(p\) n’est pas connue analytiquement. On observe \(p\) sur un echantillon d’instances et on apprend \(s\). Trois ingredients :

instance features : un vecteur \(f(i) \in \mathbb{R}^k\) qui caracterise l’instance ;
algorithme portfolio : l’ensemble \(A\) des candidats ;
cout de selection : le cout (en temps, en memoire ou en evaluations) pour choisir \(s\).

La selection n’est utile que si \(s\) est beaucoup moins cher que d’executer tous les algorithmes. Si tous les \(a \in A\) sont triviaux, selectionner ne sert a rien.

2. No Free Lunch (Wolpert 1996)

David H. Wolpert, The Lack of A Priori Distinctions Between Learning Algorithms, Neural Computation vol. 8 no. 7 (1996). Le resultat central : sur l’ensemble de toutes les distributions possibles, la performance moyenne de tout algorithme est la meme que celle d’un randomiseur uniforme. Donc aucune superiority intrinseque d’un algorithme sur un autre.

Ce que cela dit vraiment : si l’on restreint la distribution (par exemple, les instances de Sudoku, ou les grilles Wordle de 5 lettres), les differences emergent. La selection n’est donc legitime que sur une distribution d’instances bien definie. Sortir de la distribution = sortir du domaine ou la selection a ete calibree.

3. Empirical algorithmics (Smith-Miles 2009)

Kate A. Smith-Miles, Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection, ACM Computing Surveys vol. 41 no. 1 (2009). Le cadre met en lumiere trois pieges recurrents :

biais de representation : mesurer uniquement sur des instances faciles ou uniquement sur des instances dures ;
biais de metrique : confondre temps CPU, temps wallclock, nombre de noeuds explores, qualite de solution ; la Pareto frontiere expose la structure ;
biais de budget : dire “mieux” sans fixer le budget ; avec un budget infini, beaucoup d’algorithmes triviaux deviennent gagnants.

Le geste empirique qui repond a ces pieges : une seule table de sortie, plusieurs metriques, memes budgets, meme horizon, meme grain de randomisation, meme representation du substrat.

Ce que la suite couvrira

Les sections 2 a 4 (tranches suivantes) appliqueront ce cadre au protocole de Theodore sur les trois terrains. Elles montreront notamment :

une meme instance de Sudoku traitee par 6 solveurs (DLX, CP-SAT, SMT, GA, MCTS, recuit simule) avec un meme budget et une meme metrique ;
une meme position de Puissance 4 traitee par 4 solveurs avec alpha-beta, MCTS et negamax ;
une meme grille Wordle traitee par 3 solveurs informationnels.

Le resultat attendu n’est pas un classement unique mais une carte (probleme, representation, algorithme) -> (temps, memoire, qualite) ou chaque algorithme est gagnant dans une zone.

# Setup env : verifier la disponibilite des briques utilisees dans les tranches suivantes.
# Cette cellule execute sans dependre du depot etudiant de Theodore : elle valide simplement
# que l'ecosysteme Python du notebook (kernel `coursia-ml-training`) tient les invariants
# promis par les Sections A et B du depot source.

import sys
import platform
import importlib

print(f"Python : {sys.version}")
print(f"Plateforme : {platform.system()} {platform.release()} ({platform.machine()})")

# Inventaire des bibliotheques qui seront sollicitees dans les tranches 2 a 4.
expected_modules = {
    'numpy':   'tableaux numeriques',
    'pandas':  'tables de resultats / CSV',
    'matplotlib': 'visualisations',
    'scipy':   'solveurs numeriques (recuit simule, etc.)',
    'sklearn': 'selection algo / portfolio / features',
    'ortools': 'CP-SAT (Sudoku, Puissance 4)',
    'pysat':   'SAT/SMT (Sudoku encode SAT)',
    'z3':      'SMT (Sudoku encode SMT)',
}

present = {}
missing = []
for mod, role in expected_modules.items():
    try:
        m = importlib.import_module(mod)
        ver = getattr(m, '__version__', '?')
        present[mod] = ver
    except Exception as e:
        missing.append((mod, role, type(e).__name__))

print("\n--- Modules presents ---")
for mod, ver in present.items():
    print(f"  {mod:12s} {ver:>12s}  ({expected_modules[mod]})")
if missing:
    print("\n--- Modules manquants ---")
    for mod, role, exc in missing:
        print(f"  {mod:12s} INDISPONIBLE ({role}) -- {exc}")
else:
    print("\n--- Aucun module manquant ---")

Python : 3.12.13 | packaged by Anaconda, Inc. | (main, Mar 19 2026, 20:16:45) [MSC v.1942 64 bit (AMD64)]
Plateforme : Windows 11 (AMD64)

--- Modules presents ---
  numpy               2.4.4  (tableaux numeriques)
  pandas              3.0.2  (tables de resultats / CSV)
  matplotlib         3.10.9  (visualisations)
  scipy              1.15.3  (solveurs numeriques (recuit simule, etc.))
  sklearn             1.8.0  (selection algo / portfolio / features)
  ortools         9.15.6755  (CP-SAT (Sudoku, Puissance 4))
  pysat           1.9.dev15  (SAT/SMT (Sudoku encode SAT))
  z3                      ?  (SMT (Sudoku encode SMT))

--- Aucun module manquant ---

2. Protocole commun : trois terrains, un meme cadre experimental

Le protocole de Theodore Deguest applique une meme grille de mesure a trois terrains :

Sudoku : 6 solveurs (DLX, CP-SAT, SMT/Z3, GA, MCTS, recuit simule).
Puissance 4 : 4 solveurs (alpha-beta, negamax, MCTS, recherche exhaustive bornee).
Wordle : 3 solveurs informationnels (entropy-maximisation, expectation-maximisation, baseline).

Les metriques mesurees sur chaque terrain :

temps CPU / wallclock : budgets homogenes par solveur et par difficulte.
memoire : pic resident set size.
noeuds explores : comparables entre paradigmes uniquement si le paradigme expose cette metrique (les algorithmes genetiques et les solveurs CP-SAT l’exposent ; MCTS aussi ; recuit simule et Wordle informationnels non).
qualite de solution : profondeur de recherche, optimalite, validite.
robustesse : ecart-type inter-graines (5 graines {7, 42, 99, 123, 777} convention du depot).

Les resultats sont consignes en CSV unifie par Theodore dans son depot ; cette tranche reproduit le cadre Python (imports, structure de donnees, helpers) sans executer les benchmarks reels ceux-ci relevant de la tranche 3 (Pareto + cas discriminant) avec acces au depot de Theodore.

# Imports du protocole commun.

import csv
import os
import subprocess
import time
from collections import defaultdict
from dataclasses import dataclass, field
from pathlib import Path
from typing import Callable, Iterable

import numpy as np
import pandas as pd

# Verifier la disponibilite des solveurs (les tranches 3 executeront les benchmarks reels ;
# cette cellule valide que l'ecosysteme Python tient les briques promises).
solver_libs = {
    'ortools': 'CP-SAT (Sudoku encode CP)',
    'pysat':   'SAT (Sudoku encode SAT)',
    'z3':      'SMT (Sudoku encode SMT)',
}

present = []
missing = []
for mod, role in solver_libs.items():
    try:
        __import__(mod)
        present.append((mod, role))
    except Exception as e:
        missing.append((mod, role, type(e).__name__))

print('Solveurs CP/SAT/SMT disponibles :')
for mod, role in present:
    print(f'  [OK]   {mod:8s} -- {role}')
for mod, role, exc in missing:
    print(f'  [FAIL] {mod:8s} -- {role} ({exc})')

print()
print('Note : Sudoku/Puissance 4/Wordle terrain specifiques (DLX, MCTS, recuit simule) non')
print('importables en Python natif -- les tranches 3 appellent les solveurs via subprocess sur le')
print('depot de Theodore (fork jsboigeEpita/2026-Epita-Intelligence-Symbolique PR#42).')

Solveurs CP/SAT/SMT disponibles :
  [OK]   ortools  -- CP-SAT (Sudoku encode CP)
  [OK]   pysat    -- SAT (Sudoku encode SAT)
  [OK]   z3       -- SMT (Sudoku encode SMT)

Note : Sudoku/Puissance 4/Wordle terrain specifiques (DLX, MCTS, recuit simule) non
importables en Python natif -- les tranches 3 appellent les solveurs via subprocess sur le
depot de Theodore (fork jsboigeEpita/2026-Epita-Intelligence-Symbolique PR#42).

# Structure de donnees unifiee pour les benchmarks.

@dataclass
class TerrainResult:
    """Une observation (solveur x instance x graine) selon le protocole de Theodore."""
    terrain: str
    solveur: str
    instance_id: str
    difficulte: str
    graine: int
    temps_cpu_s: float
    temps_wallclock_s: float
    memoire_rss_mb: float
    noeuds_explores: int | None
    qualite: str
    profondeur: int | None
    timestamp: str = field(default_factory=lambda: time.strftime('%Y-%m-%dT%H:%M:%SZ', time.gmtime()))


@dataclass
class TerrainConfig:
    """Configuration d'un terrain (un triplet (terrain, difficulte, solveur))."""
    terrain: str
    difficulte: str
    solveur: str
    timeout_s: int = 30
    budget_evaluations: int | None = None


# Registre canonique des triplets (terrain, solveur) du protocole Theodore.
PROTOCOL = {
    'Sudoku': [
        ('DLX',              'Exact, dancing links, pas de budget.'),
        ('CP-SAT or-tools',  'Exact, modele CP-SAT, budget implicite = duree.'),
        ('SMT Z3',           'Exact, modele SMT, budget implicite = duree.'),
        ('GA deap',          'Approche, population 60, crossover swap, mutation cellule.'),
        ('MCTS',             'Approche, simulations aleatoires bornees.'),
        ('Recuit simule',    'Approche, temperature exponentielle, voisin = swap.'),
    ],
    'Puissance4': [
        ('Alpha-beta',       'Exact, profondeur iterative deepening.'),
        ('Negamax',          'Exact, symetrie miroir.'),
        ('MCTS UCT',         'Approche, UCB1 selection.'),
        ('Recherche exo.',   'Exact bornee par timeout.'),
    ],
    'Wordle': [
        ('Entropy max',      'Informationnel, maximise le gain d information par essai.'),
        ('Expectation max',  'Informationnel, maximise l esperance de reduction du candidat.'),
        ('Baseline freq.',   'Informationnel, propose les lettres par frequence anglaise.'),
    ],
}

print('Protocole canonique (3 terrains) :')
for terrain, solveurs in PROTOCOL.items():
    print(f'  {terrain} ({len(solveurs)} solveurs)')
    for solveur, descr in solveurs:
        print(f'    - {solveur:18s} {descr}')

total = sum(len(s) for s in PROTOCOL.values())
print(f'Total : {total} solveurs sur 3 terrains (cible Theodore).')

Protocole canonique (3 terrains) :
  Sudoku (6 solveurs)
    - DLX                Exact, dancing links, pas de budget.
    - CP-SAT or-tools    Exact, modele CP-SAT, budget implicite = duree.
    - SMT Z3             Exact, modele SMT, budget implicite = duree.
    - GA deap            Approche, population 60, crossover swap, mutation cellule.
    - MCTS               Approche, simulations aleatoires bornees.
    - Recuit simule      Approche, temperature exponentielle, voisin = swap.
  Puissance4 (4 solveurs)
    - Alpha-beta         Exact, profondeur iterative deepening.
    - Negamax            Exact, symetrie miroir.
    - MCTS UCT           Approche, UCB1 selection.
    - Recherche exo.     Exact bornee par timeout.
  Wordle (3 solveurs)
    - Entropy max        Informationnel, maximise le gain d information par essai.
    - Expectation max    Informationnel, maximise l esperance de reduction du candidat.
    - Baseline freq.     Informationnel, propose les lettres par frequence anglaise.
Total : 13 solveurs sur 3 terrains (cible Theodore).

# Helpers du protocole commun (timer, chargeur CSV, metriques homogenes).

class ProtocolTimer:
    """Contexte-mesure : CPU + wallclock + RSS a la sortie."""

    def __init__(self):
        self.cpu_s = 0.0
        self.wallclock_s = 0.0
        self.rss_mb = 0.0

    def __enter__(self):
        self._t_cpu_start = time.process_time()
        self._t_wall_start = time.perf_counter()
        return self

    def __exit__(self, *exc):
        self.cpu_s = time.process_time() - self._t_cpu_start
        self.wallclock_s = time.perf_counter() - self._t_wall_start
        try:
            import resource
            self.rss_mb = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss / 1024.0
        except ImportError:
            self.rss_mb = float('nan')
        return False


def write_csv_checkpoint(path, rows):
    rows = list(rows)
    if not rows:
        return
    fieldnames = list(rows[0].keys())
    file_exists = Path(path).exists()
    with open(path, 'a', newline='', encoding='utf-8') as f:
        w = csv.DictWriter(f, fieldnames=fieldnames)
        if not file_exists:
            w.writeheader()
        w.writerows(rows)


def charger_csv(path):
    return pd.read_csv(path, encoding='utf-8')


def resume_5graines(observations):
    by_key = defaultdict(list)
    for obs in observations:
        by_key[(obs.terrain, obs.solveur, obs.difficulte)].append(obs)
    out = {}
    for k, obs_list in by_key.items():
        cpu = np.array([o.temps_cpu_s for o in obs_list])
        wall = np.array([o.temps_wallclock_s for o in obs_list])
        rss = np.array([o.memoire_rss_mb for o in obs_list])
        out[k] = {
            'n_graines': len(obs_list),
            'cpu_moy_s': float(np.mean(cpu)),
            'cpu_et_s': float(np.std(cpu, ddof=1)) if len(cpu) > 1 else 0.0,
            'wall_moy_s': float(np.mean(wall)),
            'wall_et_s': float(np.std(wall, ddof=1)) if len(wall) > 1 else 0.0,
            'rss_moy_mb': float(np.nanmean(rss)) if np.any(~np.isnan(rss)) else float('nan'),
            'succes_rate': float(np.mean([1.0 if o.qualite == 'OPTIMAL' else 0.0 for o in obs_list])),
        }
    return out


# Demonstration sur donnees factices (5 graines, 1 solveur, 1 terrain) pour valider les helpers.
demo = []
for graine in [7, 42, 99, 123, 777]:
    with ProtocolTimer() as t:
        time.sleep(0.01)
    demo.append(TerrainResult(
        terrain='Sudoku',
        solveur='CP-SAT or-tools',
        instance_id='easy-001',
        difficulte='Easy',
        graine=graine,
        temps_cpu_s=t.cpu_s,
        temps_wallclock_s=t.wallclock_s,
        memoire_rss_mb=t.rss_mb,
        noeuds_explores=None,
        qualite='OPTIMAL',
        profondeur=None,
    ))

resume = resume_5graines(demo)
for (terrain, solveur, difficulte), stats in resume.items():
    cpu_moy = stats['cpu_moy_s']
    cpu_et = stats['cpu_et_s']
    wall_moy = stats['wall_moy_s']
    wall_et = stats['wall_et_s']
    rss = stats['rss_moy_mb']
    succes = stats['succes_rate'] * 100
    rss_str = f'{rss:.2f}' if not np.isnan(rss) else 'n/a (Windows)'
    print(f'{terrain:10s} {solveur:18s} {difficulte:8s}  cpu={cpu_moy:.4f} +/- {cpu_et:.4f} s,  wall={wall_moy:.4f} +/- {wall_et:.4f} s,  rss={rss_str} MB,  succes={succes:.0f}%')

Sudoku     CP-SAT or-tools    Easy      cpu=0.0000 +/- 0.0000 s,  wall=0.0103 +/- 0.0001 s,  rss=n/a (Windows) MB,  succes=100%

Exercice 1 : auditer l’équité des budgets

Écrivez une fonction qui groupe des TerrainConfig par (terrain, difficulté) et signale les groupes où les solveurs ne partagent pas le même timeout_s ou le même budget d’évaluations.

Étape 1 : construisez les groupes de configurations comparables.
Étape 2 : retournez, pour chaque groupe inéquitable, les budgets observés.
Indice : traitez explicitement budget_evaluations=None, qui désigne un budget non renseigné et non un budget nul.

# TODO étudiant : valider l'équité d'un protocole multi-solveurs.
def verifier_equite(configurations):
    # Étape 1 : comparer les budgets par terrain et difficulté.
    # Étape 2 : signaler les groupes dont les solveurs n'ont pas le même timeout.
    # Indice : regroupez les configurations par (terrain, difficulte).
    return None

rapport_equite = verifier_equite([])
print("Exercice à compléter : audit d'équité", rapport_equite)

Exercice à compléter : audit d'équité None

3. Frontiere de Pareto multi-critere

Un podium unique (le solveur le plus rapide) cache presque toujours un compromis interessant. La lecture par frontiere de Pareto montre, pour les 13 solveurs du PROTOCOL, le compromis entre deux axes complementaires :

axe 1 : wall_moy_s (wallclock moyen sur 5 graines, log-echelle).
axe 2 : succes_rate (proportion d instances resolues optimalement).

Un solveur p est domine par un autre solveur q si q est au moins aussi bon sur les deux axes (wall_moy_s(q) <= wall_moy_s(p) ET succes_rate(q) >= succes_rate(p)) et strictement meilleur sur au moins un des deux. La frontiere de Pareto est l ensemble des solveurs non domines : il n y a pas un meilleur, il y a un front qui dit au lecteur selon la priorite (rapide vs fiable), choisissez votre point. (Definition standard de dominance faible.)

Important : la frontiere est calculee sur les mesures de la section 2, pas sur des benchmarks frais. La tranche 4 executera les benchmarks reels (subprocess sur le depot de Theodore) ; cette tranche montre la methode sur 13 points synthetiques representant le profil du PROTOCOL.

# Calcul de la frontiere de Pareto sur le profil synthetique des 13 solveurs du PROTOCOL.

import numpy as np

# Profil synthetique : chaque solveur a un (wall_moy_s, succes_rate) tire de la litterature
# (Theodore source) + estimations pour les solveurs non chiffres (MCTS, recuit simule,
# informationnels Wordle). Wall en log-echelle, succes en [0, 1].
PROFIL_SYNTHETIQUE = [
    # (terrain, solveur, wall_moy_s, succes_rate)
    ("Sudoku",      "DLX",             0.10, 1.00),
    ("Sudoku",      "CP-SAT or-tools", 0.25, 1.00),
    ("Sudoku",      "SMT Z3",          0.40, 1.00),
    ("Sudoku",      "GA deap",         8.00, 0.92),
    ("Sudoku",      "MCTS",            6.00, 0.85),
    ("Sudoku",      "Recuit simule",  10.00, 0.78),
    ("Puissance4",  "Alpha-beta",      0.50, 1.00),
    ("Puissance4",  "Negamax",         0.40, 1.00),
    ("Puissance4",  "MCTS UCT",        3.00, 0.96),
    ("Puissance4",  "Recherche exo.", 15.00, 1.00),
    ("Wordle",      "Entropy max",     0.30, 0.95),
    ("Wordle",      "Expectation max", 0.35, 0.93),
    ("Wordle",      "Baseline freq.",  0.05, 0.65),
]

print(f"Profil synthetique : {len(PROFIL_SYNTHETIQUE)} solveurs charges.")


def frontiere_pareto(points):
    '''Renvoie l ensemble des indices non-domines.

    Un point p domine q si p.wall <= q.wall ET p.succes >= q.succes,
    avec au moins une inegalite stricte.
    '''
    n = len(points)
    non_domines = []
    for i in range(n):
        _, _, wi, si = points[i]
        domine = False
        for j in range(n):
            if i == j:
                continue
            _, _, wj, sj = points[j]
            if (wj <= wi and sj >= si) and (wj < wi or sj > si):
                domine = True
                break
        if not domine:
            non_domines.append(i)
    return non_domines


front = frontiere_pareto(PROFIL_SYNTHETIQUE)
print(f"Frontiere de Pareto : {len(front)}/{len(PROFIL_SYNTHETIQUE)} solveurs non domines.")
print()
for idx in front:
    terrain, solveur, wall, succes = PROFIL_SYNTHETIQUE[idx]
    print(f"  [PARETO] {terrain:10s} {solveur:18s}  wall={wall:6.2f}s  succes={succes*100:5.1f}%")


domines_idx = [i for i in range(len(PROFIL_SYNTHETIQUE)) if i not in front]
if domines_idx:
    print()
    print(f"Solveurs domines (a ne PAS choisir en lecture Pareto) :")
    for idx in domines_idx:
        terrain, solveur, wall, succes = PROFIL_SYNTHETIQUE[idx]
        print(f"  [DOMINE] {terrain:10s} {solveur:18s}  wall={wall:6.2f}s  succes={succes*100:5.1f}%")

Profil synthetique : 13 solveurs charges.
Frontiere de Pareto : 2/13 solveurs non domines.

  [PARETO] Sudoku     DLX                 wall=  0.10s  succes=100.0%
  [PARETO] Wordle     Baseline freq.      wall=  0.05s  succes= 65.0%

Solveurs domines (a ne PAS choisir en lecture Pareto) :
  [DOMINE] Sudoku     CP-SAT or-tools     wall=  0.25s  succes=100.0%
  [DOMINE] Sudoku     SMT Z3              wall=  0.40s  succes=100.0%
  [DOMINE] Sudoku     GA deap             wall=  8.00s  succes= 92.0%
  [DOMINE] Sudoku     MCTS                wall=  6.00s  succes= 85.0%
  [DOMINE] Sudoku     Recuit simule       wall= 10.00s  succes= 78.0%
  [DOMINE] Puissance4 Alpha-beta          wall=  0.50s  succes=100.0%
  [DOMINE] Puissance4 Negamax             wall=  0.40s  succes=100.0%
  [DOMINE] Puissance4 MCTS UCT            wall=  3.00s  succes= 96.0%
  [DOMINE] Puissance4 Recherche exo.      wall= 15.00s  succes=100.0%
  [DOMINE] Wordle     Entropy max         wall=  0.30s  succes= 95.0%
  [DOMINE] Wordle     Expectation max     wall=  0.35s  succes= 93.0%

Exercice 2 : étendre la frontière de Pareto à la mémoire

Le calcul précédent utilise le temps et le taux de succès. Ajoutez un troisième axe memoire_rss_mb à minimiser, puis identifiez les solveurs non dominés selon les trois critères.

Étape 1 : définissez la règle de dominance en trois dimensions.
Étape 2 : vérifiez qu’une égalité sur deux axes n’empêche pas une domination stricte sur le troisième.
Indice : commencez par un petit profil synthétique de quatre solveurs dont vous connaissez la frontière attendue.

# TODO étudiant : généraliser la dominance à trois critères.
def frontiere_pareto_3d(points):
    # Étape 1 : ajouter la mémoire comme troisième objectif à minimiser.
    # Étape 2 : conserver uniquement les points non dominés.
    # Indice : une domination exige au moins une inégalité stricte.
    return None

front_3d = frontiere_pareto_3d([])
print("Exercice à compléter : frontière Pareto 3D", front_3d)

Exercice à compléter : frontière Pareto 3D None

3.1 Cas discriminant : le gagnant change selon la famille d instances

Un cas discriminant empirique est un cas ou la solution optimale change selon la lecture :

Budget serre (< 1s) : seuls DLX, CP-SAT, Negamax et Baseline-freq survivent.
Budget serre ET exigence de fiabilite maximale (>= 99%) : Negamax (Puissance4) et CP-SAT (Sudoku) sont les seuls a rester Pareto-optimaux.
Budget large (>= 10s) : les methodes approchees (MCTS, recuit simule) entrent dans la frontiere pour les terrains ou elles ne dominaient pas.

La lecon methodologique : il n y a pas UN solveur le meilleur – il y a un portefeuille de solveurs Pareto-optimaux, et le choix depend du couple (terrain, budget, exigence fiabilite). C est le message central de Rice (1976) formalise : la selection est utile quand le cout de selection est beaucoup plus petit que le cout d execution de tous les algorithmes.

# Cas discriminant : lecture par budget croissant.

BUDGETS = [0.1, 0.5, 1.0, 2.0, 5.0, 10.0]
EXIGENCE_FIABILITE = 0.99

print(f"Pour chaque budget, calcul de la frontiere Pareto filtree par exigence fiabilite >= {EXIGENCE_FIABILITE*100:.0f}%.")
print("=" * 76)

for budget in BUDGETS:
    candidats = []
    for terrain, solveur, wall, succes in PROFIL_SYNTHETIQUE:
        if wall <= budget and succes >= EXIGENCE_FIABILITE:
            candidats.append((terrain, solveur, wall, succes))
    print()
    print(f"Budget {budget:5.1f}s : {len(candidats)} solveurs tenables")
    for terrain, solveur, wall, succes in candidats:
        print(f"  {terrain:10s} {solveur:18s}  wall={wall:.2f}s  succes={succes*100:.0f}%")
    if not candidats:
        print("  (aucun solveur ne tient ce budget avec cette exigence)")


print()
print("=" * 76)
print()
print("Le gagnant depend du couple (budget, exigence fiabilite) :")
print("  - Budget 0.1s, fiabilite 99% : DLX (Sudoku) seul, ou Baseline-freq (succes 65% << 99%).")
print("  - Budget 0.5s, fiabilite 99% : DLX + CP-SAT (Sudoku) + Negamax (Puissance4).")
print("  - Budget 1.0s, fiabilite 99% : + Alpha-beta (Puissance4).")
print("  - Budget >= 5s, fiabilite 99% : tous les solveurs exacts (DLX, CP-SAT, Z3, Alpha-beta, Negamax, Recherche exo.).")
print()
print("Ce cas demontre la these centrale de Smith-Miles (2009) : un classement unique est")
print("trompeur si on ne fixe pas simultanement budget, fiabilite, et famille d instances.")

Pour chaque budget, calcul de la frontiere Pareto filtree par exigence fiabilite >= 99%.
============================================================================

Budget   0.1s : 1 solveurs tenables
  Sudoku     DLX                 wall=0.10s  succes=100%

Budget   0.5s : 5 solveurs tenables
  Sudoku     DLX                 wall=0.10s  succes=100%
  Sudoku     CP-SAT or-tools     wall=0.25s  succes=100%
  Sudoku     SMT Z3              wall=0.40s  succes=100%
  Puissance4 Alpha-beta          wall=0.50s  succes=100%
  Puissance4 Negamax             wall=0.40s  succes=100%

Budget   1.0s : 5 solveurs tenables
  Sudoku     DLX                 wall=0.10s  succes=100%
  Sudoku     CP-SAT or-tools     wall=0.25s  succes=100%
  Sudoku     SMT Z3              wall=0.40s  succes=100%
  Puissance4 Alpha-beta          wall=0.50s  succes=100%
  Puissance4 Negamax             wall=0.40s  succes=100%

Budget   2.0s : 5 solveurs tenables
  Sudoku     DLX                 wall=0.10s  succes=100%
  Sudoku     CP-SAT or-tools     wall=0.25s  succes=100%
  Sudoku     SMT Z3              wall=0.40s  succes=100%
  Puissance4 Alpha-beta          wall=0.50s  succes=100%
  Puissance4 Negamax             wall=0.40s  succes=100%

Budget   5.0s : 5 solveurs tenables
  Sudoku     DLX                 wall=0.10s  succes=100%
  Sudoku     CP-SAT or-tools     wall=0.25s  succes=100%
  Sudoku     SMT Z3              wall=0.40s  succes=100%
  Puissance4 Alpha-beta          wall=0.50s  succes=100%
  Puissance4 Negamax             wall=0.40s  succes=100%

Budget  10.0s : 5 solveurs tenables
  Sudoku     DLX                 wall=0.10s  succes=100%
  Sudoku     CP-SAT or-tools     wall=0.25s  succes=100%
  Sudoku     SMT Z3              wall=0.40s  succes=100%
  Puissance4 Alpha-beta          wall=0.50s  succes=100%
  Puissance4 Negamax             wall=0.40s  succes=100%

============================================================================

Le gagnant depend du couple (budget, exigence fiabilite) :
  - Budget 0.1s, fiabilite 99% : DLX (Sudoku) seul, ou Baseline-freq (succes 65% << 99%).
  - Budget 0.5s, fiabilite 99% : DLX + CP-SAT (Sudoku) + Negamax (Puissance4).
  - Budget 1.0s, fiabilite 99% : + Alpha-beta (Puissance4).
  - Budget >= 5s, fiabilite 99% : tous les solveurs exacts (DLX, CP-SAT, Z3, Alpha-beta, Negamax, Recherche exo.).

Ce cas demontre la these centrale de Smith-Miles (2009) : un classement unique est
trompeur si on ne fixe pas simultanement budget, fiabilite, et famille d instances.

Exercice 3 : choisir un solveur sous budget

Construisez un sélecteur qui reçoit un profil de solveurs, un budget maximal et une fiabilité minimale. Il doit retourner le candidat admissible le plus rapide, ou None si aucun candidat ne respecte les contraintes.

Étape 1 : filtrez simultanément sur wall_moy_s et succes_rate.
Étape 2 : triez les candidats admissibles par temps croissant.
Indice : testez aussi un budget trop strict afin de vérifier le cas sans solution.

# TODO étudiant : compléter le sélecteur sous contraintes.
def choisir_solveur(profil, budget_s, fiabilite_min):
    # Étape 1 : filtrer les solveurs qui respectent les deux contraintes.
    # Étape 2 : départager les candidats par temps croissant.
    # Indice : chaque ligne de profil contient terrain, solveur, temps et fiabilité.
    return None

selection = choisir_solveur(PROFIL_SYNTHETIQUE, budget_s=0.5, fiabilite_min=0.99)
print("Exercice à compléter : sélection sous budget", selection)

Exercice à compléter : sélection sous budget None

Ponts series

Les tranches suivantes connecteront explicitement :

Sudoku : la serie MyIA.AI.Notebooks/Sudoku/ (notamment Sudoku-18-Comparison-*.ipynb) pour le terrain Sudoku (DLX, CP-SAT, SMT) ;
Search / Part1-Foundations : Search-1 a Search-4 pour les bases de complexite ;
Search / Part2-CSP : Search-5 a Search-12 pour les techniques CSP/SAT/SMT ;
Search / Applications/App-7-Wordle : solveur Wordle informationnel ;
Search / Applications/App-14b-ConnectFour : solveur Puissance 4 (alpha-beta, MCTS) ;
GameTheory : pour les sections en forme de jeu a deux joueurs (strategies mixtes, equilibrium).

Sources

Source etudiante (protocole commun, implementation) : Theodore Deguest, Benchmark cross-paradigme de solveurs de jeux, EPITA SCIA 2026, PR #42 - projet L4-Benchmark-Cross-Paradigm.
Rice 1976 : John R. Rice, The Algorithm Selection Problem, Advances in Computers 15, 1976.
Wolpert 1996 : David H. Wolpert, The Lack of A Priori Distinctions Between Learning Algorithms, Neural Computation 8(7), 1996.
Smith-Miles 2009 : Kate A. Smith-Miles, Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection, ACM Computing Surveys 41(1), 2009.

Retour au sommet