Les trois comparaisons au cœur de l'étude DFS, menées jusqu'au bout : l'ordre de remplissage (le balayage par lignes gagne, un mauvais ordre est catastrophique), les heuristiques (MRV sauve le remplissage du bord d'abord mais coûte du débit ; davantage de propagation n'a rien apporté) et les ruptures (elles brisent le mur de profondeur ; le levier, c'est le calendrier de ruptures, pas le plafond par cellule).
par Raphaël Anjou
Trois comparaisons portent l'étude DFS. Chacune isole une décision en maintenant tout le reste fixe. Tous les scores sont le nombre moyen d'arêtes appariées sur les dix variantes à coins épinglés, mono-cœur, soixante secondes. Le débit se mesure en nœuds de recherche par seconde et n'est jamais comparé d'une famille à l'autre.
Les deux références exécutent le même algorithme strict de balayage par lignes : NAIVE-CLEAN
comme moteur généraliste lisible, NAIVE-CODEGEN comme boucle chaude 16×16 spécialisée à la
main, réservée au balayage par lignes. La spécialisation livre ce qu'elle promet sur l'axe
qu'elle vise. NAIVE-CODEGEN est sensiblement plus rapide par nœud, jusqu'à un tiers de plus sur
certaines instances. Sur le score, les deux se valent, à un point ou deux d'écart à soixante
secondes et bien à l'intérieur de la dispersion entre exécutions, ce qui est la lecture honnête
plutôt qu'une affirmation selon laquelle la spécialisation nuirait. À temps de calcul fixé, un
moteur plus rapide atteint un point différent du même arbre, et la meilleure solution partielle
d'un retour sur trace ne varie pas de façon monotone avec la vitesse à laquelle il y est parvenu.
Les références constituent donc une comparaison de vitesse propre et ne sont délibérément pas
présentées comme une comparaison de score. Les effets sur le score qui méritent d'être étudiés
se trouvent tous sur les axes ci-dessous, là où la recherche elle-même change.
Fixons le moteur (strict, sans heuristique) et changeons uniquement l'ordre dans lequel les cellules sont remplies. Les six ordres ne diffèrent que par l'endroit où la recherche envoie son front, montré ci-dessous.
Même moteur, mêmes soixante secondes, un écart de plus de 300 points dû au seul ordre de remplissage. C'est la forme mesurée d'un savoir de la communauté : le bord d'abord n'est bon qu'avec une heuristique pour choisir les cellules à l'intérieur de l'anneau. Seul, c'est l'un des pires ordres disponibles.
Éprouvez le levier vous-même : choisissez l'un des neuf ordres de parcours du moteur ci-dessous et regardez le même retour sur trace atteindre une profondeur différente sur le même puzzle.
Fixons maintenant le chemin près du cadre et ajoutons une chose à la fois. Le plus grand levier est MRV, qui remplit ensuite la cellule vide la plus contrainte, choisie dynamiquement. Il transforme le bord d'abord qui calait (moyenne 67) en une recherche dont la moyenne est de 324 (meilleur 341) à une profondeur d'environ 190. Il recalcule aussi la cellule la plus contrainte sur tout le front à chaque étape, si bien que le débit en nœuds chute de trois ordres de grandeur, de dizaines de millions de nœuds par seconde à quelques milliers. Chaque nœud vaut bien plus, et on en visite bien moins. Le débit en nœuds et le score sont des axes différents.
Ajouter une anticipation plus lourde par-dessus n'a pas rapporté davantage de score à ce budget.
La leçon n'est pas que la propagation est inutile. C'est qu'à petit budget fixe, sur cette instance, l'élagage utile le moins cher (la vérification en avant) capte déjà tout le bénéfice disponible, et qu'un raisonnement plus coûteux ne récupère pas son surcoût par nœud en soixante secondes.
Le retour sur trace strict, quel que soit son ordre ou son heuristique, frappe un mur bien avant un
plateau complet : le balayage par lignes plafonne autour de la profondeur 208 sur 256, et même la
variante stricte la plus rapide (NAIVE-CODEGEN) n'atteint que 216. Les moteurs recordmen le
franchissent en rompant : ils autorisent un nombre borné d'incompatibilités d'arêtes intérieures,
libérées selon un calendrier de profondeur, avec une règle interdisant qu'une cellule porte trop
d'arêtes rompues. Le score d'un plateau complet est alors 480 − #ruptures.
Ces chiffres de ruptures voisinent avec ceux des réimplémentations à la Blackwood et à la Verhaard, reparties de zéro, du benchmark frère, qui atteignent les 430 et quelques sur les mêmes cinq indices. L'accord d'un moteur indépendant valide de façon croisée la machinerie de ruptures ici.
Blackwood et McGavin sont le haut de gamme de cette même famille, et tous deux se compilent et s'exécutent sur cette machine, si bien que cette étude les a fait tourner sur une grille épinglée et une grille non épinglée, chaque score étant recalculé canoniquement à partir du plateau propre au moteur. Le résultat est un enseignement à part entière, et il a deux moitiés.
Sur la grille épinglée, ils s'effondrent. Le C de McGavin, compilé avec les propres options ARM de son auteur (réglage natif plus optimisation au moment de l'édition de liens), atteint la profondeur 211 sur le puzzle à indice central simple à environ 85 millions de tuiles par seconde, bien devant notre moteur strict le plus rapide, et pourtant épingler trois coins l'effondre à la profondeur 21, un score canonique de 13. Son chemin de balayage engendré ne visite jamais les coins tôt, si bien qu'un coin épinglé contraint aussitôt son voisinage et coince le chemin fixe presque immédiatement. Le C# de Blackwood code en dur son jeu de pièces et son balayage, si bien qu'il ne peut même pas exprimer un épinglage de coin arbitraire ; sur la contrainte à cinq indices correspondante, son heuristique de ruptures s'agite jusqu'à la profondeur 47, un score canonique de 75, parce qu'il est réglé pour l'instance à un indice, quasi non contrainte, où son record de 470 a été établi.
Cet effondrement est justement le propos. Un moteur recordman bâti autour d'une configuration d'indices ne se transfère pas à une autre, et un chemin de balayage fixe ne peut pas absorber un épinglage arbitraire. Nos moteurs repartis de zéro traitent un épinglage comme une cellule pré-placée que le balayage saute simplement, ce qui explique pourquoi ce sont eux, et non les binaires de la communauté, qui font office de doublures sur la grille épinglée.
Sur une grille non épinglée équitable, ils tournent comme prévu. Donnez à chaque moteur les pièces officielles avec le seul indice central obligatoire, et rien ne se coince sur un coin. En soixante secondes sur un cœur, McGavin atteint 392, notre moteur de ruptures le plus fort 344, la réimplémentation de Verhaard 286, et Blackwood 214. Lisez ces chiffres comme ce qu'un seul cœur achète en une minute à froid, non comme le plafond d'un moteur : le 470 de Blackwood et les exécutions profondes de McGavin sont venus de journées sur des centaines de cœurs, que ce budget ne peut pas montrer. Ce que la grille montre, en revanche, c'est que les quatre tournent correctement une fois disparus les épinglages qui brisent un chemin de balayage fixe, ce qui est exactement ce que la grille épinglée refusait aux deux moteurs étrangers. Les deux grilles figurent sur le classement de l'étude ci-dessus.
Un thème traverse les trois comparaisons : le nombre de nœuds n'est pas le score. Les variantes les plus rapides par nœud (la référence en codegen et le moteur strict de balayage par lignes) n'atteignent pas les meilleurs plateaux ; la plus lente par nœud (MRV avec propagation) en atteint de bien meilleurs ; et les ruptures qui l'emportent le font en changeant quelle branche est légale, non en visitant les branches plus vite. La vitesse brute est un facteur constant, tandis qu'où la recherche peut aller et si elle en a le droit est le facteur exponentiel.