🔢 mathematics

Generation of maximal snake polyominoes using a deep neural network

Cet article présente l'utilisation d'un modèle de diffusion appelé SPS Diffusion pour générer des serpents polyominos maximaux sur de grandes grilles en apprenant les contraintes de connectivité et de maximalité à partir de données, bien que le modèle soit encore sujet à certaines erreurs structurelles.

Auteurs originaux : Benjamin Gauthier, Alain Goupil, Fadel Toure

Publié 2026-03-16

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Benjamin Gauthier, Alain Goupil, Fadel Toure

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous devez remplir un grand plateau de jeu (comme un échiquier géant) avec un seul et unique serpent de Lego, sans jamais le couper, sans qu'il ne se croise lui-même, et en essayant de le faire aussi long que possible pour couvrir le maximum de cases. C'est le défi des "polyominos serpents" (ou snake polyominoes).

Le problème ? Pour trouver le serpent le plus long possible sur un grand plateau, les ordinateurs traditionnels doivent essayer toutes les combinaisons possibles, un par un. C'est comme essayer de trouver une aiguille dans une botte de foin en construisant chaque brin de foin individuellement. Plus le plateau est grand, plus cela prend des années, voire des siècles. C'est ce qu'on appelle une "complexité exponentielle".

Voici comment les auteurs de ce papier, Benjamin, Alain et Fadel, ont décidé de contourner ce problème en utilisant une Intelligence Artificielle (IA) moderne.

1. L'Analogie du Sculpteur de Nuages

Au lieu de construire le serpent brique par brique (la méthode brute), les chercheurs ont entraîné un modèle d'IA qu'ils appellent SPS Diffusion.

Imaginez un sculpteur qui commence avec un énorme bloc de neige floue et bruyante (du "bruit").

L'entraînement : Le sculpteur regarde des milliers de photos de serpents Lego parfaits. Il apprend à reconnaître les formes : les virages serrés, les coins, et surtout, ce qu'il ne faut pas faire (comme faire un nœud, couper le serpent en deux, ou créer une fourche).
La création : Pour créer un nouveau serpent, le sculpteur prend un bloc de neige totalement flou. Il commence à enlever doucement la neige, couche par couche, en se basant sur ce qu'il a appris.
- Au début, on ne voit rien.
- Puis, des formes apparaissent.
- À la fin, après plusieurs étapes de "dénudage", il reste un serpent Lego bien formé sur le plateau.

Ce processus s'appelle la diffusion. Au lieu d'ajouter du bruit pour détruire l'image (comme dans la réalité), l'IA fait l'inverse : elle retire le bruit pour révéler la structure cachée.

2. Pourquoi c'est révolutionnaire ?

Les chercheurs ont découvert quelque chose de fascinant : l'IA n'a pas besoin qu'on lui explique les règles mathématiques complexes (comme "ne fais pas de boucle" ou "le serpent doit avoir une tête et une queue").

Apprentissage par l'exemple : L'IA a juste regardé des milliers de serpents existants. Elle a "intuitivement" compris la logique du serpent. C'est comme si un enfant apprenait à faire des nœuds en regardant ses parents, sans qu'on lui donne un manuel de physique.
La généralisation : Le plus impressionnant, c'est que l'IA a été entraînée sur de petits plateaux (par exemple 14x14 cases), mais elle a réussi à créer des serpents sur des plateaux beaucoup plus grands (jusqu'à 28x28, et même 50x50 !). C'est comme si un enfant qui a appris à faire des petits dessins dans un cahier d'écolier réussissait soudainement à peindre une fresque géante dans une cathédrale, en gardant le même style.

3. Les imperfections (Le serpent qui trébuche)

Bien sûr, l'IA n'est pas parfaite. Parfois, quand elle essaie de faire un serpent sur un très grand plateau, elle se trompe :

Elle crée parfois un nœud (le serpent se croise sur lui-même).
Elle crée une fourche (le serpent se divise en deux).
Parfois, elle crée plusieurs petits serpents qui ne se touchent pas (une "forêt" de serpents au lieu d'un seul).

C'est un peu comme un apprenti sculpteur qui, fatigué par la taille de la statue, laisse tomber un morceau de pierre ou fait une erreur de taille. Cependant, le fait qu'elle arrive à produire des serpents valides sur des tailles que les ordinateurs classiques ne peuvent même pas calculer est déjà une victoire énorme.

4. Pourquoi est-ce important ?

Jusqu'à présent, pour étudier les serpents les plus longs possibles, les mathématiciens étaient bloqués par la puissance de calcul. Ils ne pouvaient pas voir les grands plateaux.

Grâce à cette IA, ils peuvent maintenant :

Voir l'invisible : Observer des structures sur de très grands plateaux pour essayer de deviner des règles mathématiques (des conjectures) sur la longueur maximale possible.
Trouver des records : L'IA a déjà réussi à créer des serpents légèrement plus longs que ce qu'on pensait possible sur certains plateaux, suggérant qu'il y a encore des secrets à découvrir.

En résumé

Ce papier raconte l'histoire d'une équipe qui a remplacé le marteau et le burin (les algorithmes classiques lents) par un pinceau magique (l'IA). Même si le pinceau fait parfois des taches, il permet de peindre des paysages (des serpents géants) que personne n'aurait jamais pu dessiner seul. C'est une nouvelle façon de faire des mathématiques : au lieu de tout calculer, on apprend à la machine à "sentir" la forme du problème.

1. Problématique et Contexte

Le problème central de cette recherche est la génération et l'étude des polyominoes serpents maximaux (maximal snake polyominoes) dans des grilles rectangulaires de grande taille.

Définition : Un serpent est un polyomino où toutes les cellules ont un degré de 2 (connectées à deux voisins), sauf deux cellules extrémités (tête et queue) qui ont un degré de 1.
Limites des méthodes actuelles : La méthode standard consiste à énumérer exhaustivement tous les serpents possibles pour trouver le plus long. Cette approche par force brute a une complexité exponentielle. Bien que des travaux antérieurs aient permis d'atteindre certaines limites (par exemple, des grilles de taille 56x56 pour les polyominoes généraux), l'énumération complète devient impossible pour les grands rectangles, empêchant l'étude des motifs à grande échelle et la formulation de conjectures sur la longueur maximale.
Objectif : Développer une approche alternative basée sur l'apprentissage automatique pour générer des candidats de serpents maximaux dans des grilles trop grandes pour l'énumération exhaustive, sans coder explicitement les contraintes combinatoires (comme l'absence de cycles ou de branches).

2. Méthodologie : Le modèle SPS Diffusion

Les auteurs proposent l'utilisation d'un modèle de diffusion probabiliste débruiteur (Denoising Diffusion Probabilistic Model - DDPM), qu'ils nomment SPS Diffusion (Structured Pixel Space Diffusion).

Principe de fonctionnement :
- Le processus suit un schéma de diffusion inverse : le modèle part d'une image de bruit pur (distribution normale) et apprend à retirer le bruit étape par étape pour reconstruire une structure de serpent valide.
- Contrairement aux modèles de génération d'images naturels (comme Stable Diffusion), le modèle opère directement dans l'espace des pixels (Pixel Space) car les grilles de serpents sont petites (généralement < 64x64) et binaires (0 pour vide, 1 pour occupé).
Architecture du modèle :
- Le cœur du modèle est un mini U-Net (sans encodeur VAE ni module CLIP, car les données sont binaires et non conditionnées par du texte).
- L'architecture comprend des blocs résiduels et des blocs d'attention.
- Attention spatiale : Pour capturer les dépendances à longue distance dans la grille, le modèle utilise des embeddings de position rotative 2D (RoPE-2D) dans les couches d'auto-attention.
- Réduction de la résolution : Le modèle utilise uniquement 3 niveaux de sous-échantillonnage (downsampling) au lieu de 5 ou 6 pour les modèles d'images standards, afin de préserver l'intégrité structurelle des petits serpents.
Entraînement :
- Données : Le modèle est entraîné sur des serpents maximaux connus pour des grilles allant jusqu'à 50x14.
- Processus : Lors de l'entraînement, du bruit est ajouté aux serpents connus (diffusion avant) pour créer l'entrée ( $x_t$ ). La cible ($tgt$) est le bruit réel ajouté.
- Fonction de perte : L'erreur quadratique moyenne (MSE) a été sélectionnée car elle produit les meilleurs résultats structurels, évitant les déformations fréquentes observées avec d'autres fonctions de perte.

3. Contributions Clés

Apprentissage des contraintes implicites : Le modèle apprend les règles combinatoires complexes des serpents (connectivité, absence de cycles, unicité des composants) uniquement à partir des données, sans programmation explicite de ces règles.
Généralisation à des tailles non vues : Le modèle démontre une capacité à généraliser sa compréhension des serpents depuis les petites grilles d'entraînement vers des grilles beaucoup plus grandes lors de l'inférence.
Nouvelle approche pour la combinatoire : L'article établit que les réseaux de neurones profonds peuvent comprendre et générer des objets combinatoires discrets complexes, offrant un nouvel outil pour explorer des espaces de recherche inaccessibles par l'énumération exhaustive.

4. Résultats Expérimentaux

Performance sur les grilles vues : Le modèle génère facilement des serpents maximaux valides sur les tailles de grilles présentes dans l'ensemble d'entraînement.
Généralisation (Inference) :
- Le modèle réussit à générer des serpents valides sur des grilles carrées jusqu'à 28x28, dépassant la taille maximale carrée utilisée pour l'entraînement (14x14).
- Il génère également des serpents sur des rectangles allongés (ex: 10x60).
- Pour les grilles jusqu'à 17x17, le modèle produit des serpents dont la longueur dépasse parfois les bornes inférieures connues (calculées par énumération exhaustive), prouvant sa capacité à trouver de nouvelles configurations.
Limites et erreurs :
- Au-delà de 28x28, la qualité diminue : le modèle produit souvent des "forêts" de serpents (composantes déconnectées), des cycles, des branches (degré 3) ou des têtes/queues ouvertes.
- Le taux d'erreur augmente avec la taille de la grille.
- Pour une grille de 29x29, sur plus de 25 000 tentatives, aucun serpent valide n'a été généré, seulement des structures invalides.
Impact sur les bornes : Bien que le modèle ne garantisse pas la maximalité absolue (car il peut générer des erreurs), il permet d'approcher ou de dépasser légèrement les bornes inférieures connues pour certaines configurations, servant d'outil d'exploration pour la théorie.

5. Signification et Perspectives

Signification : Ce travail démontre que les modèles de diffusion peuvent capturer des structures combinatoires non triviales. Il offre une alternative prometteuse aux algorithmes de force brute pour étudier des problèmes d'optimisation combinatoire dans des espaces trop vastes pour l'énumération.
Défis restants :
- Réduire le taux d'erreur (branches, cycles) pour obtenir des serpents valides plus fréquemment.
- Améliorer l'évolutivité (scalability) vers des grilles encore plus grandes, potentiellement en modifiant l'architecture du U-Net ou les encodages de position.
- Utiliser une approche itérative où les serpents générés (même non maximaux) pourraient être réintégrés dans l'ensemble d'entraînement pour affiner le modèle.
Conclusion : Bien que le modèle SPS Diffusion ne remplace pas les méthodes exactes pour la vérification de preuves, il constitue un outil numérique puissant pour guider les conjectures et explorer la structure des serpents maximaux au-delà des limites computationnelles actuelles.