Le prix d'une solution complète
Une recherche exacte du 16x16 avec cinq indices coûte environ 2^134,4 nœuds, et aucune piste examinée ne comble l'écart de 56 à 73 bits face à des budgets de 2^78 et 2^61,5 nœuds. Le travail est mis en pause, avec les conditions de reprise énoncées. Cette page porte les chiffres fixes et indexe les dix pages qui les appuient.
par Raphaël Anjou
Épuiser une recherche simple, rangée par rangée, sur les vraies pièces d'Eternity II avec cinq indices demande environ 10^40,457 nœuds (2^134,4), mesuré, et la prédiction du modèle aléatoire tombe à moins de 0,04 chiffre. Sur cette statistique, le jeu de pièces officiel est un membre ordinaire des plateaux peints avec les mêmes effectifs de couleurs. Cela chiffre la recherche complète ; cela ne trouve aucun moyen de la raccourcir.
Réfuter un mauvais cadre complet des vraies pièces coûte cher : la ligne d'échec préenregistrée est atteinte, et réfuter des cadres partiels coûte 2,2 à 2,5 bits de plus que ce qu'on économise. L'information bon marché sur le cadre, environ 17,4 bits, se trouve aux quatre coins d'indices. Savoir si les cadres éloignés des coins se réfutent à bas prix reste indécidé.
Sous un balayage par lignes, une tuile connue retire de 1 à 10 bits de l'arbre de recherche complet selon la seule position de sa case dans le balayage (médiane 5,8 bits, sur des plateaux 16x16 peints), et plusieurs tuiles valent ensemble moins que leur somme. Sur ces plateaux, 10 tuiles bien réparties laissent l'arbre au-dessus de 10^15 nœuds et 16 à 24 le ramènent en dessous, un chiffre vérifié de bout en bout seulement. Rien ici ne mesure le vrai puzzle, hormis deux contrôles de transfert.
Un filtre ajouté au balayage par lignes ne peut économiser que ce que sa profondeur permet, et les contrôles qui réfutent presque tous les mauvais plateaux ne mordent qu'aux profondeurs 144 à 192, après le niveau le plus large de l'arbre (158). Une coupe gratuite parfaite à la profondeur 144 économiserait 2,4 bits sur les 134,4 que coûte le balayage : aucun filtre tardif ne comble l'écart. Le tableau des plafonds est de l'arithmétique dérivée d'un profil mesuré, pas une expérience.
Aucune des sept familles d'approches (recherche qui apprend, représentations avec perte, forme de l'arbre, ordres adaptatifs, structure du jeu de tuiles, reformulation algébrique ou de l'espace de recherche), ni les idées lointaines, les nogoods de cadre ou les autres ordres de remplissage, n'est chiffrée à 10 bits ou plus avec un mécanisme à l'appui. Le plus grand gain qui survit est d'environ 5,5 bits, pour un écart de 56 à 73 bits ; quelques fermetures reposent sur un seul lecteur ou une seule famille de solveurs et sont signalées comme telles.
Dix petites expériences de moteur préenregistrées, sur plateaux générés de 6x6 à 9x9, en ont retenu cinq et écarté cinq. Le seul gain mesuré est un nœud qui coûte 5.3 à 6.1 fois moins cher pour une recherche identique ; aucune des trois méthodes qui modifient l'arbre (retour sur le bloqueur, ordre des valeurs par impact, appariement de Hall) ne l'a réduit face à sa référence. Rien ici ne fait avancer Eternity II.
Cinq expériences préenregistrées sur la mémorisation et l'indexation des impasses n'ont trouvé aucun gain qui compte pour une résolution complète. Trois ont été tuées (bandes de la carte de différence, rejeu indexé sur la coupe, indexation à cinq indices) et deux conservées comme mesures (indexation par quota, et courbe de quota à cinq indices). Le résultat conservé sur le quota est un effet de débit de 53 fois, soit environ 5.7 bits de débit, ce qui n'est pas un arbre plus petit.
Notre portage d'un backtracker de type record différait du moteur publié sur sept points ; les sept ont été corrigés et testés, et les suites de nœuds coïncident avec l'ancien portage partout où les interrupteurs hérités sont activés. Avec les cinq indices, les réglages fidèles font moins bien que les anciens (profondeur maximale 18 à 54 contre 33 à 215 sur huit graines) : la correction n'est donc pas un progrès dans ce cadre.
Sur des plateaux jouets générés, une relaxation semi-définie de l'appariement des arêtes est certifiée propre sur trois plateaux 5x5, indécidée sur un et inexacte sur un autre ; elle ne tient pas en 16x16 et n'a donné aucune lecture en 6x6. Sa forme de rang faible trouve bien des solutions, mais comme une recherche aléatoire que le recuit simple bat en coût. Rien ici n'est un progrès sur Eternity II.
L'apprentissage de clauses n'offre aucune avance croissante sur la simple propagation par cohérence d'arc, sur des préfixes erronés des vraies pièces : la ligne d'arrêt fixée d'avance s'est déclenchée sur le travail cumulé, et en comptes l'apprentissage vaut 0 bit de plus que la cohérence d'arc. Les plateaux jouets (5x5 à 7x7) penchent dans le même sens sans l'établir. Rien ici ne fait progresser Eternity II.
déterministe : se reproduit à l'octet près
just experiments approach-pricingRéimprime en quelques secondes le tableau du plafond d'une coupe gratuite parfaite à partir du profil de niveaux versionné. Ne rejoue ni le profil du balayage ligne par ligne, ni les essais sur petits plateaux, ni les contre-vérifications, qui se trouvent dans les dossiers d'expériences cités dans les sources.
Continuer l'exploration
Cité par
- Une carte de toutes les approches connues
- Les expériences de Raphaël Anjou
- Le prix d'une recherche complète
- Cadre et coins : un mauvais cadre ne se réfute pas à bas prix
- Ce que vaut une tuile connue sous balayage par lignes
- Filtres tardifs : tout contrôle qui marche marche trop tard
- Sept familles d'approches chiffrées face à l'arbre du balayage par lignes
- Dix expériences de moteur sur petits plateaux : des nœuds plus rapides, pas d'arbres plus petits