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.
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.