La théorie complexe : compter l'arbre de recherche avant de le parcourir
La théorie complexe de Brendan Owen estime la largeur de l'arbre de recherche à chaque profondeur, et jusqu'au nombre total de solutions. Beaucoup, dans la communauté, la tiennent pour la chose la plus importante à comprendre sur Eternity II.
La théorie complexe est due à Brendan Owen, l'un des vérificateurs du puzzle ;
Peter McGavin l'a implémentée en C
en arithmétique à précision arbitraire et a publié les chiffres. Nous la
reprenons ici parce qu'un membre de la communauté (Dan Karlsson) a justement
fait remarquer qu'elle manquait, et parce qu'elle sous-tend presque toutes les
bonnes décisions qu'on peut prendre pour un solveur, à commencer par le choix
de l'ordre de recherche.
Prenez un ordre de balayage et parcourez-le case par case. À chaque nouvelle
case, une pièce inutilisée tirée au hasard s'accorde à ses voisines déjà posées
avec une certaine probabilité : un produit de chances d'accord de couleur par
arête. Multipliez cela par le nombre de pièces restantes et vous obtenez le
nombre attendu de façons d'étendre le plateau d'une case de plus. Enchaînez ce
calcul sur les 256 cases et vous disposez d'une estimation en forme close de la
largeur de l'arbre de recherche à chaque profondeur et, à la dernière case, du
nombre de solutions complètes du puzzle.
C'est une moyenne, non un décompte exact : le modèle suppose que les 22
couleurs d'arête sont tirées indépendamment, ce qui est faux (quatre arêtes
sont soudées à une même pièce rigide). Mais calibré sur de petits puzzles dont
le nombre réel est connu, il tombe à un facteur deux près. C'est amplement
suffisant pour en discerner la forme.
Avec la seule pièce centrale imposée, le puzzle compte de l'ordre de quinze
mille solutions ; ajoutez les quatre autres indices et le nombre attendu chute
à environ 4×10−8 : de manière écrasante, exactement une. C'est la
raison formelle pour laquelle le puzzle à 5 indices possède une unique solution
conçue.
Brendan a tabulé l'estimation non seulement pour E2 mais aussi pour les quatre
puzzles à indices plus petits, et c'est là qu'elle gagne sa crédibilité. Ces
puzzles à indices sont assez petits pour que leurs arbres aient été explorés
exhaustivement, si bien que l'estimation se place juste à côté du nombre réel.
Elle tombe à un facteur deux près, la calibration que cette page ne cesse de
promettre. La table consigne aussi le meilleur ordre de remplissage connu pour
chaque puzzle, et ils ne sont pas tous identiques : l'ordre est un choix que la
forme de l'espace de recherche récompense ou pénalise, non une propriété du
puzzle.
quantité
Clue #1
Clue #2
Clue #3
Clue #4
E2 · 1 hint
E2 · 5 hints
Solutions estimées
2.6e11
7.6e36
8.2e8
4.9e34
14,702
1
Solutions, comptées réellementcompté
115,071,633,408
·
2,195,647,488
·
·
·
Nœuds estimés de l'arbre
1.3e13
2.0e40
1.1e11
8.4e37
1.4e47
3.1e40
Nœuds de l'arbre, comptés réellementcompté
1.0e13
·
2.2e11
·
·
·
Meilleur ordre de remplissage connu
spiral-in
border first, then vertical scans
spiral-in
border first, then vertical scans
horizontal scans from bottom-left
horizontal scans from bottom-left
Les chiffres de théorie complexe de Brendan Owen pour les quatre puzzles à indices et le vrai plateau E2. Sur les petits puzzles à indices, l'arbre entier a été parcouru : l'estimation se vérifie donc contre le compte exact, et tombe à un facteur deux près. Le meilleur ordre de remplissage change d'un puzzle à l'autre, c'est un choix, pas une donnée.
Transcrit tel quel depuis la table communautaire « Backtracker estimates » sur groups.io. Les cellules vides le sont dans la source (puzzles à indices trop grands pour un comptage exhaustif, et colonnes E2 non parcourues).
Les puzzles à indices fournissent quatre points de mesure ; Brendan a vérifié
le modèle bien plus largement. Son étude « NxM puzzles using Eternity II
subset pieces » trace les nœuds-par-solution estimés contre le nombre réel
pour de l'ordre d'une centaine de plateaux plus petits construits à partir des
pièces mêmes d'E2, et sur un axe log-log le nuage épouse la diagonale sur onze
ordres de grandeur, de dix nœuds à 1011. Voilà le vrai fondement de la
confiance qu'on peut accorder à l'estimation sur un plateau trop grand pour
jamais être exploré : elle a eu raison partout où elle pouvait être vérifiée.
Une étude compagnon montre même qu'un score statique tout bête (la somme, au
carré, des comptes d'accords d'arête par case) prédit le nombre total de nœuds
d'un rectangle avec un R2 d'environ 0,84, preuve de plus que le coût de la
recherche est inscrit dans la structure du plateau avant même qu'on ait posé
une pièce.
Tracez la largeur attendue à chaque profondeur et trois régimes apparaissent.
Leur forme est ce que la communauté appelle l'entonnoir d'E2. Lancez le
balayage ci-dessous et observez le compteur : il grimpe jusqu'aux milliards,
puis bouge à peine pendant une centaine de cases à travers le plateau - cette
reptation plate au sein d'une bande astronomiquement large, c'est le mur -avant que les soixante dernières pièces ne le fassent redescendre en entonnoir.
profondeur
1/256
façons de prolonger
1
régime
Croissance
Croissance. Chaque placement a encore des dizaines de successeurs légaux. L'arbre s'élargit vite.
Une tête de recherche balayant la profondeur 1 → 256 le long de la courbe des branches attendues. Le nombre au-dessus du plateau indique combien il existe de façons légales d'étendre un plateau partiel à cet endroit, et combien chaque placement élague peu.
La même estimation, exécutée en direct pour différents ordres de balayage. Le
pic du plateau (le point le plus large que la recherche doit franchir) est
décidé par le seul ordre, avant qu'un seul nœud ne soit posé.
▶Interactif : l'entonnoir de l'espace de rechercheExplorer →
Croissance (profondeur 1–50). Les solutions se multiplient
géométriquement, de un à environ 1027. Chaque placement est pour ainsi
dire gratuit ; rien ne vous contraint encore.
Plateau (profondeur 50–200). L'arbre est à sa largeur maximale, environ
1045 façons d'étendre, tandis que le nombre de solutions ne bouge
presque pas. C'est là que les backtrackers passent environ 99 % de leur
temps, ce qui rejoint le constat empirique de Joe selon lequel l'essentiel du
temps se passe sous la profondeur 150.
Effondrement (profondeur 200–256). La largeur retombe de 1045 à
environ 104. Les ~60 dernières pièces sont fortement contraintes :
chacune posée élimine des ordres de grandeur de branches. La fin de partie
est localement facile ; le difficile, c'est d'y parvenir.
Si l'essentiel du travail se situe dans le plateau, l'objectif n'est pas la
vitesse brute. C'est de traverser le plateau jusqu'à l'entrée de l'entonnoir
(vers la profondeur 200), après quoi la recherche s'enchaîne de manière
déterministe. Et comme la théorie complexe note un ordre de balayage avant de
l'exécuter, on peut comparer des ordres par la hauteur du pic de leur plateau
plutôt que par tâtonnement. C'est la version rigoureuse d'une règle que ce site
énonce partout : l'ordre de remplissage est un choix de premier plan, et le
balayage de McGavin, du coin inférieur gauche et de gauche à droite, a été
retenu parce que la théorie complexe le disait bon.
La même idée fonctionne si l'on place des tuiles 2×2 ou 3×3 au lieu de pièces
isolées : un bloc entier de cases est engagé d'un coup, ses arêtes internes
étant déjà accordées. Le terrain de jeu des chemins de recherche
vous permet de le faire pour de vrai : choisissez une forme de bloc (1×1, 2×1,
2×2, 3×3, …) et estampez des blocs sur la grille pour construire un chemin par
blocs. Lancez la course et un solveur de macro-pièces dédié engage un
sous-assemblage valide entier par bloc au lieu d'une pièce à la fois, si bien
que la recherche progresse région par région. L'estimation du pic de plateau,
en regard, note toujours l'ordre de cases qu'impliquent vos blocs, prédisant le
coût avant que vous n'exécutiez le moindre nœud.
La théorie complexe est une estimation au premier moment ; elle est donc
aveugle à une chose : la question de savoir si les nombreux plateaux partiels
comptés sont réellement distincts. Les résultats d'entropie et de loi d'aire
montrent que la distinction s'effondre au-delà de ~80 cases, un effet du second
ordre que le modèle à arêtes indépendantes ne peut capter. Servez-vous donc de
la théorie complexe pour choisir des ordres et lire la forme de l'arbre, jamais
comme un décompte exact ni comme une borne.
La trace écrite de la théorie court à travers la liste de diffusion. Brendan
Owen a publié le modèle achevé en avril 2008
(msg 5197,
5209), et a plus tard démontré
une élégante forme close : pour un ordre de balayage, le pic du nombre de nœuds
se situe à la profondeur
256(1−1/e)≈161.8
(msg 8125) ; l'entonnoir
ci-dessus y culmine empiriquement. Peter McGavin a mis la théorie en forme
(msg 9188), a publié le chiffre
de 14 702 solutions attendues dès 2011
(msg 8924), et a livré en 2017 sa
validation la plus forte : la résolution du benchmark 10×10 sans indice de
Brendan en explorant les premières rangées classées par théorie complexe,
soit environ 180 années-cœur, tombant dans les prédictions de la théorie
(msg 9686,
9688). Son implémentation C de
référence de 2024 (msg 11197)
est ce que l'estimateur en direct de cette page porte, ligne pour ligne.