La frontière ouverte d'Eternity II réunie au même endroit : chaque angle qui vaut encore une tentative, le mur qu'il attaque, ce qui a déjà été essayé et où cela s'est arrêté, et s'il s'agit d'une cible abordable pour un débutant ou d'un objectif difficile et bien cartographié.
Voici le tableau des angles ouverts : une ligne par direction qui mérite encore une tentative. Chaque entrée pose la question en une ligne, nomme le mur qu'elle attaque (issu de pourquoi c'est difficile), renvoie à ce qui a déjà été essayé et à l'endroit où cela s'est arrêté (dans la carte murs-méthodes et les impasses), et indique son abordabilité. Les étiquettes disent ce qu'elles disent : abordable pour un débutant désigne une cible qu'on peut prendre sans dix ans de contexte ; difficile, bien cartographié désigne une cible que beaucoup de tentatives solides ont balisée sans qu'aucune ne l'ait franchie ; sans prise en charge désigne un angle sur lequel personne ne travaille activement, ce qui est distinct d'un angle qui a été attaqué puis a tenu.
Pour l'état de l'art, le score vit sur la page records ; cette page ne montre que ce qui reste ouvert.
La piste canonique. Le meilleur plateau ne respectant que l'indice de départ obligatoire est à 470/480 depuis que la communauté l'a atteint, et un 480 conçu est acquis : l'éditeur a construit le puzzle à partir d'une solution, donc un plateau parfait existe et seul son emplacement reste ouvert.
Mur. Rigidité : les plateaux records sont des îles localement figées, et les dix arêtes manquantes se trouvent de l'autre côté de tous les murs structurels à la fois.
Essayé, et où cela s'est arrêté. Toute méthode de la carte murs-méthodes finit contre la rigidité ; les constructions depuis zéro et depuis le corpus plafonnent entre 458 et 463, et aucune ne franchit le plafond. La force de calcul brute ne le comble pas non plus, ce qui est consigné sous jeter plus de calcul contre le mur.
Étiquette. Difficile, bien cartographié. C'est le sommet du puzzle entier : on sait beaucoup de choses sur pourquoi il résiste, ce qui est précisément la raison pour laquelle un franchissement inédit ferait la une.
La ligne stricte à cinq indices est suivie séparément de la ligne ouverte à 470, car l'essentiel des progrès sur le record ouvert s'est fait sans les indices. Le meilleur plateau respectant les cinq placements est à 464.
Mur. Rigidité de nouveau, plus les placements d'indices qui rétrécissent la région atteignable : moins de plateaux satisfont les cinq, donc la botte de foin est plus petite, mais l'aiguille aussi.
Essayé, et où cela s'est arrêté. Le 464 est la marque courante de la ligne stricte sur la page puzzles à indices ; les constructions strictes et re-compressions du projet atteignent la classe des 460 sans la dépasser, comme le montre la carte murs-méthodes.
Étiquette. Difficile, bien cartographié, mais un pas plus court que l'écart de 470 à 480 : 464 à 465, c'est une seule arête, sur une ligne où la région atteignable est plus resserrée et donc plus facile à raisonner que le record ouvert.
Brendan Owen a publié une paire de 10x10 générés sans indice avec leurs statistiques. L'un (set_1) est tombé ; l'autre (set_2) n'a jamais été résolu et reste le prochain échelon convenu par la communauté sous le 16x16 complet.
Mur. La même difficulté d'appariement d'arêtes que le puzzle complet, à une taille qu'une seule machine peut réellement terminer. Set_1 a demandé une recherche vaste mais bornée, donc set_2 est une cible d'ingénierie de recherche, pas une cible structurelle.
Essayé, et où cela s'est arrêté. L'histoire complète est sur la page benchmarks : set_1 a été résolu, les statistiques de set_2 sont connues, et il tient toujours.
Étiquette. Abordable pour un débutant. C'est la seule cible ouverte dimensionnée pour une machine personnelle et un backtracker bien réglé plutôt qu'une grappe de calcul, donc la première vraie tentative recommandée.
Chaque plateau record se trouve dans un bassin que des preuves MIP montrent localement optimal jusqu'à un halo de plusieurs cellules. La question ouverte est de savoir si une suite de petits coups légaux atteint un autre bassin.
Mur. Rigidité sous sa forme la plus tranchée, et pourquoi le saut de bassin paraît impossible : le pas d'un grand plateau vers un meilleur est un unique échange géant et indivisible, sans gradient à suivre.
Essayé, et où cela s'est arrêté. Le théorème de rigidité consigne des preuves MIP d'optimalité de halo sur plusieurs bassins, et la recherche d'une courte chaîne d'évasion entre bassins a échoué pour une raison structurelle exposée sur pourquoi le saut de bassin paraît impossible. L'entrée recombiner deux bons plateaux est le même mur vu du côté du croisement.
Étiquette. Difficile, bien cartographié. Un seul coup de franchissement, ou une preuve qu'aucun n'existe, changerait la façon dont on juge toute méthode de recherche locale.
Faire se rejoindre deux recherches partielles au milieu est complet en principe, mais le nombre de plateaux partiels à stocker croît d'environ un facteur vingt par erreur d'appariement supplémentaire tolérée, si bien que les moitiés cessent de se rejoindre bien avant le 16x16 complet.
Mur. Le coût de l'exactitude mesuré directement : l'approche meet-in-the-middle est exacte, mais sa mémoire dépasse ce que toute machine peut contenir.
Essayé, et où cela s'est arrêté. BANDSAW a résolu une bande de fin de partie à l'optimalité prouvée et, ce faisant, a mesuré la croissance d'environ un facteur vingt par erreur des deux côtés, donc se rejoindre au milieu cesse de payer à taille réelle ; ce résultat est la ligne BANDSAW de la carte. Une meilleure représentation, ou une rencontre avec perte qui reste saine, est le levier ouvert.
Étiquette. Difficile, bien cartographié. Le mur est ici quantifié, donc le progrès est mesurable : tout encodage qui abaisse le facteur de croissance par erreur est un gain réel, même sans résolution complète.
Presque toute méthode redécouvre la même poignée de bassins. Dans un balayage complet des méthodes, seul le parallel tempering a produit de façon fiable de nouveaux bassins, et même lui plafonne vite.
Mur. Rigidité vue comme un goulot de diversité : la contrainte n'est pas le score qu'une méthode atteint mais le nombre de bassins distincts qu'elle sait trouver, et l'arsenal standard en trouve trop peu.
Essayé, et où cela s'est arrêté. L'étude de diversité est écrite sur la carte murs-méthodes : la recherche locale adaptative, le placement en serpent et le haut de la distribution d'un générateur entraîné retombent tous dans les bassins connus, et seul le parallel tempering s'en échappe de façon fiable. Générer des plateaux avec un transformeur est l'une des tentatives de diversité qui n'ont pas tenu.
Étiquette. Sans prise en charge, et ouvert. Contrairement aux cibles cartographiées ci-dessus, celle-ci n'a pas de liste d'attaques balisée à battre : un mécanisme de diversité vraiment neuf est une idée que personne n'a encore plantée, ce qui en fait l'entrée la plus spéculative et la moins contrainte par les travaux antérieurs.
Les plus petits mouvements qui séparent les meilleurs plateaux connus et l'échelle à laquelle les plateaux partiels réellement distincts s'effondrent sont tous deux un patch de quelques centaines de cases. La question ouverte est de savoir si c'est un lien causal, la rigidité découlant de la loi d'aire, ou deux faits indépendants partageant par hasard une échelle de longueur.
Mur. Rigidité et la loi d'aire. La rigidité est établie de manière indépendante, par des preuves MIP d'optimalité de halo et un halo SAT versé ; la loi d'aire est une estimation de distinction. Réduire l'une à l'autre les relierait, mais rien sur le site ne le dérive.
Essayé, et où cela s'est arrêté. La page de la loi d'aire observe l'échelle partagée et renvoie à pourquoi le saut de bassin semble impossible ; elle ne prétend pas que la rigidité est causée par l'effondrement. Le résultat de rigidité est exact et région par région, et tient seul sans invoquer la loi d'aire. Aucune page n'affirme le pont causal, ce qui est justement pourquoi il figure ici comme question.
Étiquette. Difficile, bien cartographié. Les deux extrémités sont parmi les murs les plus étudiés de la section ; la part ouverte est l'arête entre eux, et la trancher dans un sens ou l'autre reformulerait la lecture des deux murs.
Chaque case intérieure conserve 73 à 137 pièces légales, et le puzzle se situe à la transition de phase d'environ une solution attendue. Les deux sont regroupés sous « rien de local à élaguer », mais aucune dérivation ne lie le décompte de branchement à la position à environ 17 couleurs intérieures.
Mur. Aucun coup forcé et le pic de difficulté. Le décompte de branchement est un compte de candidats par case sur le jeu de pièces ; le pic est un énoncé sur le nombre de solutions à 17 couleurs. Un puzzle pourrait en principe avoir l'un sans l'autre.
Essayé, et où cela s'est arrêté. Élagage contre vitesse et la carte mur-méthode regroupent les deux murs sous le même thème, qu'il n'y a rien de local à élaguer, ce qui est une union thématique et non une affirmation causale. Aucune page ne dérive le profil de branchement du décompte de couleurs.
Étiquette. Difficile, bien cartographié. Les deux murs sont chacun mesurés exactement ; la pièce manquante est la dérivation qui les relie, laquelle transformerait un thème partagé en mécanisme.
Le mouvement entre deux plateaux records est un cycle indivisible de nombreuses cases, et chaque préfixe propre score moins ; cela montre pourquoi la réparation locale ne peut franchir entre bassins. La question ouverte est de savoir si la même géométrie plafonne les producteurs DFS et beam constructifs, qui saturent entre 458 et 463 pour des raisons calculées seulement entre plateaux finis, pas dans l'arbre de recherche.
Mur. Sigma-cycles et rigidité, vus sur l'axe de diversité. Le résultat des sigma-cycles est un énoncé exact sur chaque paire de planches embarquées, mais il est calculé entre plateaux records finis, pas sur l'arbre de recherche constructif qui les produit.
Essayé, et où cela s'est arrêté. La carte mur-méthode documente que les producteurs à partir de zéro et beam saturent comme les autres, et l'enquête de diversité a trouvé que l'arsenal standard redécouvre sans cesse les mêmes bassins. Étendre le mécanisme des sigma-cycles pour expliquer ce plafond constructif, plutôt que seulement celui de la réparation locale, n'est pas prouvé et n'est affirmé nulle part sur le site.
Étiquette. Difficile, bien cartographié, et proche de la question de diversité ci-dessus : une preuve que la même géométrie de cycle régit la saturation constructive unifierait deux plafonds observés indépendamment.
Chaque affirmation ci-dessus s'appuie sur une page déjà présente sur ce wiki : les murs dans pourquoi c'est difficile, les tentatives arrêtées dans la carte murs-méthodes et les impasses, les cibles de référence sur la page benchmarks. Si vous en prenez une et qu'elle bouge, le carnet est ouvert et il y a une place pour le compte rendu.