Maintenir en vie les K plaquettes partielles les plus prometteuses à la fois et les faire croître case par case. La recherche en faisceau est le moteur des constructeurs ex nihilo de ce projet, et une illustration limpide des raisons pour lesquelles la largeur seule s'enlise dans les profondeurs de l'intérieur.
Reproduire ce résultat: prose — aucun calcul derrière cette page
Un retour arrière en profondeur d'abord s'engage sur une seule plaquette partielle et creuse. La recherche en faisceau, elle, prend ses précautions : elle maintient en vie les meilleures plaquettes partielles à la fois, étend chacune d'elles d'une seule case, évalue tous les enfants, puis conserve à nouveau les meilleurs. L'idée remonte au système de reconnaissance vocale HARPY de Bruce Lowerre, dans les années 1970 ; l' article sur la beam-stack search de Zhou et Hansen offre un bon traitement moderne de cette famille de méthodes et de ses compromis.
Fixons un ordre de balayage sur les 256 cases. Un état du faisceau est un placement partiel, l'ensemble des pièces déjà dépensées et un score de bords appariés. Étendre un état à la profondeur revient à essayer chaque couple (pièce, rotation) légal pour la case (légal au regard des voisins déjà posés et de l'inventaire restant) et à ajouter au score le nombre de bords nouvellement appariés. On réunit tous les enfants issus des survivants, on trie, on tronque à , on répète 256 fois, et chaque survivant est alors une plaquette complète.
C'est l'inventaire qui distingue ce cas de la recherche en faisceau sur un problème de contraintes générique : chaque pièce n'existe qu'en un seul exemplaire, si bien qu'un placement n'est pas un simple choix local mais un prélèvement sur un budget global. Ce détail décide de tout ce qui suit.
Le laboratoire ci-dessous fait descendre un faisceau dans un arbre synthétique : facteur de branchement , profondeur , scores déterministes fondés sur un hachage, sans plaquette, parce que les pathologies sont plus faciles à voir quand l'instance est assez petite pour être dessinée. Deux traits y sont plantés délibérément : les scores des nœuds sont en partie héritables (un bon préfixe tend à avoir de bons enfants, ce qui fait précisément qu'un faisceau s'effondre sur un seul préfixe), et quelques nœuds pièges rapportent un gros score immédiat tout en empoisonnant discrètement chaque descendant : un modèle synthétique en deux lignes du vol de pièces, où un placement qui marque maintenant dépense une pièce dont l'intérieur profond aura besoin plus tard.
La recherche en faisceau est une recherche exponentielle dont on a supprimé l'exponentielle par décret :
pour une largeur , un facteur de branchement et une profondeur (plus un tri en par niveau). Les deux sont linéaires en , et c'est là tout l'attrait. Le prix, c'est l'incomplétude : un faisceau n'offre aucune garantie d'optimalité, aucun certificat en cas d'échec, et aucun moyen de revenir à un préfixe élagué. Son unique mode de défaillance systématique est l'effondrement que montre le laboratoire : quand les survivants deviennent copies d'un même préfixe, la largeur effective vaut 1, quel que soit le prix payé.
À l'échelle d'Eternity II l'arithmétique est clémente, et c'est exactement pour cela que les faisceaux sont ici le moteur ex nihilo : cases, = le nombre de candidats (pièce, rotation) légaux par case, quelques centaines au début, décroissant à mesure que l'inventaire se vide, si bien que même coûte de l'ordre de – évaluations d'enfants par plaquette complète : des minutes sur un ordinateur portable, incomparablement moins cher que tout chiffre exhaustif de la page sur les impasses. Ce que dit vraiment , ce n'est pas « bon marché » mais « aussi bon que sa seule fonction d'évaluation » : le faisceau évalue une fraction infime de l'arbre, et aucun score connu ne prédit quels préfixes de profondeur 100 se complètent encore bien. La largeur s'achète en monnaie linéaire ; la clairvoyance n'est pas à vendre.
À le faisceau est une construction gloutonne pure, et le glouton à redémarrages aléatoires a une queue de distribution brutalement lourde : sur le moteur de ce projet, des dizaines de milliers d'essais gloutons aléatoires ont plafonné autour de 408 sur 480, et l'extrapolation de la queue plaçait un 440 à des milliards de redémarrages. Élargir le faisceau vaut bien mieux, mais les rendements sont à peu près logarithmiques. Un faisceau de quelques centaines d'états construit des plaquettes autour de 450 ; pousser au-delà de dix mille a atteint le milieu des 450 puis a plafonné. (Mesuré sur le moteur de ce projet ; non reproduit de façon indépendante.)
Il y a une raison structurelle pour laquelle un faisceau pur ne peut guère être plus que « glouton, en plus large ». Un état de faisceau à la profondeur fait face exactement aux mêmes contraintes d'appariement de bords et d'inventaire qu'un nœud de DFS à la profondeur ; maintenir de nombreux états en vie ne relâche rien. Sans une fonction d'évaluation qui prédise de façon fiable quels préfixes de profondeur 100 se complètent encore bien (et aucune heuristique de ce genre n'est connue pour Eternity II), la largeur supplémentaire du faisceau ne fait pour l'essentiel que reproduire ce que les redémarrages aléatoires d'un retour arrière fournissent déjà.
Livré à lui-même, un faisceau s'effondre : en quelques dizaines de cases, la plupart des survivants partagent un même préfixe à haut score, et le faisceau dégénère vers un glouton doté d'un surcroît de comptabilité. Les correctifs classiques sont la déduplication de préfixes et l'échantillonnage dans les meilleurs plutôt que la prise des meilleurs, et les constructeurs de ce projet emploient les deux. Mais le levier de diversité le plus puissant trouvé ici ne se situait pas du tout dans le faisceau : c'était l'ordre de balayage. Faire tourner le même faisceau sous neuf ordres de visite différents (GAUNTLET) a produit dix-huit familles de plaquettes distinctes là où seize graines d'un seul ordre en avaient produit une.
L'autre bouton fécond est le départage. PRIOR tranche les égalités de score en faveur des pièces fréquentes à cette position dans un corpus de plaquettes fortes, relevant le plafond ex nihilo de quelques bords et atteignant 460 après raffinement. LODESTONE tranche les égalités en faveur des pièces qui servent des demandes rares, gagnant une petite amélioration médiane et une bien meilleure régularité, puis s'effondrant gravement dès que la loi a priori passe du rôle de départage à celui d'objectif.
Toutes les variantes de faisceau essayées ici s'enlisent de la même manière. La bordure et le premier intérieur se remplissent presque parfaitement ; les non-appariements se concentrent dans les dernières rangées, là où les pièces dont une case a besoin ont été dépensées bien plus tôt au service de cases plus faciles : le problème du vol de pièces. Un objectif local glouton ne peut pas voir ce budget global, et doubler ne recule le mur que d'un ou deux bords. Sur ce moteur, les faisceaux ex nihilo plafonnent au milieu des 450 ; la distance restante s'achète par le polissage par destruction-réparation, et non par plus de largeur. Sur ce puzzle, la recherche en faisceau est un bon moyen d'atteindre vite le plateau, et aucunement un moyen de le quitter.