L’IA qui raisonne : recherche, contraintes, logique, planification.

• Écrire un joueur de puissance 4 imbattable en profondeur raisonnable.
• Résoudre sudoku, coloration, emploi du temps par CSP avec propagation.
• Encoder un problème en SAT et le résoudre avec votre propre DPLL.
• Planifier une séquence d’actions pour un robot à partir d’un but.

Références : Artificial Intelligence: A Modern Approach (Russell & Norvig) chapitres 3-11, Handbook of Satisfiability, cours CS221 (Stanford).

Chaque nœud est une position, chaque arête un coup ; MAX (nous) choisit le maximum des valeurs des enfants, MIN (l’adversaire) le minimum. La valeur remonte des feuilles (positions finales). Le morpion a ~550 000 nœuds : on explore tout. Les échecs en ont 10¹²⁰ : on coupe à une profondeur d et on estime les feuilles avec une fonction d’évaluation (matériel, mobilité…). Deep Blue (1997) explorait 200 millions de positions par seconde à profondeur 12-14 ; Stockfish aujourd’hui fait mieux avec une évaluation apprise (NNUE) — le mariage recherche + apprentissage.

α = la meilleure valeur que MAX est déjà sûr d’obtenir ; β = la meilleure que MIN est sûr d’obtenir. Si dans une branche MIN trouve un coup qui donne ≤ α, MAX n’y viendra jamais : inutile d’explorer le reste. Avec un bon ordre des coups (les meilleurs d’abord), alpha-bêta explore ≈ √(nœuds de minimax) : profondeur doublée à coût égal. Améliorations standard : approfondissement itératif, table de transposition (mémoïser les positions, module L04), recherche de quiescence, coups tueurs. Le puissance 4 a été résolu en 1988 (le premier joueur gagne en jouant au centre).

1) Backtracking (module L04) : affecter, vérifier, revenir. 2) Propagation : après chaque affectation, réduire les domaines des voisins (forward checking) ; plus loin, l’arc-consistance (AC-3) propage jusqu’au point fixe : chaque valeur d’une variable doit être compatible avec au moins une valeur de chaque voisine. 3) Heuristiques : MRV (variable au plus petit domaine), degré (variable la plus connectée), LCV (valeur qui contraint le moins). Les solveurs de contraintes (OR-Tools, MiniZinc) résolvent emplois du temps, ordonnancement d’usines, allocation de fréquences — des problèmes à des millions de variables.

Tout problème NP se réduit à SAT (Cook-Levin, module L23) : sudoku, coloration, planification, vérification de circuits, cryptanalyse. Les solveurs modernes (MiniSat, CaDiCaL, Kissat) ajoutent à DPLL l’apprentissage de clauses (CDCL : à chaque conflit, déduire une clause qui l’explique et l’ajouter), des heuristiques de choix de variables (VSIDS), des redémarrages, et résolvent des instances à des millions de variables — Intel et AMD vérifient leurs processeurs ainsi. La transition de phase vers 4,26 clauses/variable, où les instances aléatoires deviennent brutalement difficiles, est un lien remarquable avec la physique statistique.

La recherche aveugle explose avec le nombre d’objets (10 blocs : millions d’états). Les planificateurs (Fast Downward, LAMA) utilisent A* avec des heuristiques relaxées : résoudre le problème en ignorant les retraits (« delete relaxation ») donne une borne inférieure calculable en temps polynomial. Le langage standard est PDDL. En robotique, la planification de tâches (« prendre la tasse, ouvrir la porte… ») s’articule avec la planification de mouvement (module L21) : c’est le « task and motion planning », un domaine de recherche où les LLM commencent à servir de générateurs de plans candidats vérifiés par un planificateur symbolique.

L’unification (Robinson, 1965) est l’algorithme qui fait correspondre deux motifs avec variables — c’est aussi le cœur de l’inférence de types d’OCaml (module L07) ! La résolution enchaîne les règles en arrière depuis le but. Un programme Prolog est une base de faits et de règles ; « exécuter » = prouver. La dernière requête montre la réversibilité : app écrit pour concaténer sert à découper. Les systèmes experts des années 1980, Datalog (bases de données déductives), les vérificateurs de types et les assistants de preuve descendent de là. Limites : la recherche en profondeur peut boucler, et le raisonnement sous incertitude a exigé les réseaux bayésiens (module L11) puis l’apprentissage.

def negamax(p, joueur, alpha=-2, beta=2):
    global noeuds_nm; noeuds_nm += 1
    g = gagnant(p)
    if g: return 1 if g == joueur else -1
    if not coups(p): return 0
    autre = "O" if joueur == "X" else "X"; v = -2
    for i in coups(p):
        v = max(v, -negamax(jouer(p, i, joueur), autre, -beta, -alpha)); alpha = max(alpha, v)
        if alpha >= beta: break
    return v

def meilleur_coup_temps(p, joueur, budget_s):
    t0 = time.perf_counter(); meilleur, prof_ok = coups(p)[0], 0
    def nm(p, j, d, alpha, beta):
        g = gagnant(p)
        if g: return 1 if g == j else -1
        if not coups(p) or d == 0: return 0
        autre = "O" if j == "X" else "X"; v = -2
        for i in coups(p):
            v = max(v, -nm(jouer(p, i, j), autre, d - 1, -beta, -alpha)); alpha = max(alpha, v)
            if alpha >= beta: break
        return v
    for d in range(1, 10):
        autre = "O" if joueur == "X" else "X"
        c = max(coups(p), key=lambda i: -nm(jouer(p, i, joueur), autre, d - 1, -2, 2))
        if time.perf_counter() - t0 > budget_s: break
        meilleur, prof_ok = c, d
    return meilleur, max(prof_ok, 1) if prof_ok else (meilleur, 1)

def resoudre_csp(variables, domaines, contraintes):
    C = dict(contraintes); C.update({(v, u): (lambda f: (lambda x, y: f(y, x)))(f) for (u, v), f in contraintes.items()})
    dom = {v: set(d) for v, d in domaines.items()}; aff = {}
    def rec(dom):
        if len(aff) == len(variables): return dict(aff)
        v = min((x for x in variables if x not in aff), key=lambda x: len(dom[x]))
        for val in sorted(dom[v]):
            aff[v] = val; d2 = {u: set(d) for u, d in dom.items()}; ok = True
            for (a, b), f in C.items():
                if a == v and b not in aff:
                    d2[b] = {y for y in d2[b] if f(val, y)}
                    if not d2[b]: ok = False; break
            if ok:
                r = rec(d2)
                if r: return r
            del aff[v]
        return None
    return rec(dom)
def toutes(variables, domaines, contraintes, acc):
    C = dict(contraintes); C.update({(v, u): (lambda f: (lambda x, y: f(y, x)))(f) for (u, v), f in contraintes.items()})
    aff = {}
    def rec(dom):
        if len(aff) == len(variables): acc.append(dict(aff)); return
        v = min((x for x in variables if x not in aff), key=lambda x: len(dom[x]))
        for val in sorted(dom[v]):
            aff[v] = val; d2 = {u: set(d) for u, d in dom.items()}; ok = True
            for (a, b), f in C.items():
                if a == v and b not in aff:
                    d2[b] = {y for y in d2[b] if f(val, y)}
                    if not d2[b]: ok = False; break
            if ok: rec(d2)
            del aff[v]
    rec({v: set(d) for v, d in domaines.items()})

Énumérer toutes les affectations « toutes différentes » (10·9·8·…·3 = 1 814 400 avec S, M ≠ 0 : ≈ 1,45 million) prend quelques secondes ; la vraie résolution encode l’addition comme contrainte (non binaire) et propage : c’est ce que fait CP-SAT en millisecondes.

Clé de transposition : tuple("".join(col) for col in p). Ne stocker que si la recherche n’a pas été coupée (valeur exacte), ou stocker avec un drapeau (borne inférieure / supérieure / exacte) comme les vrais moteurs. Pour la question 3, la profondeur 6 doit gagner presque toutes les parties — sauf si l’évaluation est mauvaise : c’est l’occasion de l’améliorer.

def ac3(domaines, contraintes):
    """contraintes : {(u, v): fonction(x, y) → bool}. Réduit les domaines jusqu'au point fixe."""
    from collections import deque
    file = deque(contraintes)
    while file:
        u, v = file.popleft(); ok = contraintes[(u, v)]
        avant = len(domaines[u])
        domaines[u] = {x for x in domaines[u] if any(ok(x, y) for y in domaines[v])}
        if not domaines[u]: return False
        if len(domaines[u]) < avant:
            file.extend((w, u) for (w, z) in contraintes if z == u and w != v)
    return True

Pour 1) : représentez l’état du solveur par une pile d’affectations (variable, valeur, niveau, raison) ; lors d’un conflit sur la clause C, remplacez itérativement dans C le littéral affecté le plus récemment au niveau courant par sa clause raison (résolution), jusqu’à ce qu’un seul littéral du niveau courant reste : c’est la clause 1-UIP. Pour 3) : tout plan du problème original est un plan du problème relaxé (les retraits ne peuvent qu’empêcher des actions) ; donc le coût optimal relaxé minore le coût optimal réel — admissible. Le calculer exactement est NP-difficile, mais h^max et h^add s’obtiennent en temps polynomial.