Résumé Technique : MCTS Sensible à la Géométrie pour les Problèmes Extremaux en Géométrie Combinatoire

Énoncé du Problème

L'article traite d'une classe de problèmes extremaux en géométrie combinatoire définis sur des grilles discrètes de $n \times n$. Ces problèmes cherchent à trouver des configurations de points qui satisfont des contraintes géométriques globales strictes tout en maximisant ou minimisant le nombre de points. Exemples représentatifs :

• Max-No-Three-in-Line (Max-N3IL) : Trouver le nombre maximum de points tels qu'aucun groupe de trois ne soit colinéaire.
• Min-Complete : Trouver l'ensemble « complet » le plus petit (où aucun point supplémentaire ne peut être ajouté sans violer la contrainte de non-colinéarité de trois points).
• Min-Dominating Set : Trouver le plus petit ensemble de points tel que chaque point de la grille repose sur une droite définie par deux points de l'ensemble.
• Autres Variantes : Problèmes impliquant des contraintes sur quatre points colinéaires (Max-N4IL), quatre points concycliques (Max-No-4-on-Circle) et des triangles isocèles (Max-No-Isosceles).

Défis :
Les solveurs exacts classiques (par exemple, la programmation linéaire en nombres entiers) souffrent d'une explosion combinatoire et de barrières de scalabilité (échouant souvent pour $n \approx 19$) en raison de la densité des contraintes en $O(n^3)$. Les modèles standards d'apprentissage par renforcement (RL) et basés sur les Transformers peinent face à :

1. La « Falaise de Validité » (Validity Cliff) : Un seul mouvement invalide (par exemple, créer trois points colinéaires) rend l'ensemble de la configuration invalide, créant un signal de récompense creux qui entrave l'optimisation par gradient.
2. Surcharge de Tokens/Calcul : Représenter des grilles nécessite $O(n^2)$ tokens, ce qui entraîne une faible scalabilité pour les mécanismes d'attention, tandis que la génération autoregressive hallucine souvent des placements invalides.
3. Généralisation : Les méthodes d'IA existantes échouent souvent à passer au-delà de petites grilles ($n < 15$) ou dépendent de données d'entraînement qui ne peuvent pas généraliser aux structures irrégulières et non algébriques des grandes configurations optimales.

Méthodologie : MCTS Sensible à la Géométrie

Les auteurs proposent un cadre de Recherche Arborescente de Monte Carlo sensible à la géométrie (Geometry-Aware MCTS) qui formule ces problèmes comme des processus de décision markoviens (MDP) déterministes. Le cadre introduit des innovations algorithmiques spécifiques pour gérer les contraintes strictes et les espaces de recherche étendus :

1. Espace d'Actions Réalisables Incrémentiel ($A_{feas}$)

Au lieu de traiter l'ensemble de la grille comme l'espace d'actions, le cadre maintient strictement un ensemble d'actions réalisables où le placement d'un point ne viole pas l'invariant géométrique $\Phi$.

• Mécanisme : Pour des problèmes comme Max-N3IL, le système utilise le Lancer de Rayons (Ray Casting). Lorsqu'un nouveau point est placé, il « lance des rayons » vers tous les points existants, marquant toutes les cellules de la grille sur ces lignes comme invalides.
• Amélioration de la Complexité : Cette mise à jour incrémentielle réduit la complexité de la vérification des contraintes de $O(n^3)$ (re-parcours de toute la grille) à $O(n^2)$ par nœud. Cela garantit que la recherche n'entre jamais dans des états invalides, contournant ainsi la falaise de la récompense creuse.

2. Exploitation de la Symétrie de la Grille ($D_4$)

Le cadre exploite le groupe diédral $D_4$ (rotations et réflexions) pour réduire l'espace de recherche et accélérer la découverte.

• Élagage Canonique : Lors de la phase d'expansion de l'arbre, l'algorithme calcule le sous-groupe stabilisateur $Stab(s)$ de l'état actuel. Il élague l'espace d'actions pour n'inclure qu'un seul représentant (action canonique) par orbite de mouvements équivalents, réduisant ainsi considérablement le facteur de branchement.
• Transitions par Lots Symmetriques : La fonction de transition du MDP est modifiée pour tenter de placer un lot entier d'orbites de points simultanément. Si le placement par lot est valide, l'agent valide l'ensemble du lot symétrique en une seule étape ; sinon, il revient au placement d'un point unique. Cela accélère la découverte de configurations symétriques et maintient l'arbre de recherche plus profond dans les sous-espaces symétriques.

3. Stratégie de Recherche Améliorée

Pour maximiser l'efficacité sous un budget de calcul fini, le cadre emploie :

• Réutilisation de Sous-Arbres : Puisque les transitions sont déterministes, l'arbre de recherche n'est pas jeté après chaque étape. Le nœud enfant devient la nouvelle racine pour la phase suivante, préservant les comptes de visites accumulés et permettant des « démarrages à chaud » (warm starts).
• Décroissance de l'Exploration Temporelle : La constante d'exploration dans la formule UCB1 est décrue au fil du temps, mais crucialement, le calcul de la décroissance tient compte des comptes de visites hérités des phases précédentes de l'arbre pour maintenir une confiance continue.
• Suivi Optimal « Anytime » : Pendant les simulations, tout état terminal trouvé est évalué par rapport au meilleur global. Cela garantit que les solutions « aberrantes » découvertes profondément dans les rollouts aléatoires sont enregistrées de façon permanente, même si la politique finale du MCTS converge vers un chemin différent.

Principales Contributions

1. Innovation Algorithmique : L'introduction d'un mécanisme de maintien d'un espace d'actions réalisables incrémentiel qui réduit la complexité de la vérification des contraintes de $O(n^3)$ à $O(n^2)$ pour les contraintes de colinéarité.
2. Exploitation de la Symétrie : Le développement de l'Élagage Canonique (via les stabilisateurs d'état) et des Transitions par Lots Symétriques, qui réduisent efficacement les facteurs de branchement et accélèrent la profondeur de recherche dans les sous-espaces symétriques.
3. Nouvelles Bornes Computationnelles : Le cadre établit de nouveaux résultats computationnels optimaux pour cinq des six problèmes étudiés.
   • Max-N3IL : A trouvé des configurations de taille $\approx 1.8n$ pour des grilles $82 \le n \le 119$, améliorant significativement la borne inférieure asymptotique de $\approx 1.5n$.
   • Min-Complete & Min-Dom : A trouvé des configurations de taille $\approx 0.95n$ pour $37 \le n \le 96$, fournissant de nouvelles bornes supérieures.
   • Autres Problèmes : Amélioration des bornes inférieures pour Max-N4IL (trouvant $3n$ points), Max-No-Isosceles ($\approx 1.4n$), et Max-No-4-on-Circle ($\approx 1.8n$).

Résultats et Signification

L'article démontre que le MCTS sensible à la géométrie peut naviguer efficacement dans la « falaise de validité » et l'explosion combinatoire qui frappent les autres méthodes.

• Scalabilité : Le cadre a exploré avec succès des tailles de grille allant jusqu'à $n=119$ pour Max-N3IL en utilisant un seul cœur de CPU et une limite stricte de 6 Go de mémoire, un exploit auparavant inatteignable pour ces échelles spécifiques.
• Efficacité : Les études d'ablation confirment que la combinaison des mises à jour incrémentielles, de l'élagage canonique et des transitions par lots est essentielle. Si l'élagage canonique seul offrait des gains marginaux, sa synergie avec les transitions par lots a débloqué des améliorations de performance significatives.
• Signification : Ce travail établit le MCTS sensible à la géométrie comme un cadre hautement adaptable pour la découverte de nouvelles configurations en géométrie combinatoire. Il fournit des constructions empiriques qui comblent l'écart entre les bornes théoriques inférieures et les bornes supérieures triviales, offrant des points de données précieux pour les futurs travaux théoriques. Les auteurs notent que bien que leur méthode ne fournisse pas de preuves sous forme close, elle offre un paradigme de recherche scalable capable de gérer des contraintes globales difficiles là où les méthodes algébriques ou probabilistes peinent.

L'article conclut que cette approche sert d'outil polyvalent pour les constructions en géométrie discrète, avec un potentiel futur d'intégration avec des réseaux neuronaux pour le guidage de la valeur/politique et une extension de la scalabilité via la parallélisation.