L'idée est arrivée avant le casse-tête lui-même. En mai 2007, deux mois avant
la mise en vente d'Eternity II, la liste de diffusion évoquait un effort
communautaire à la manière de SETI@home, et la réponse de Brendan Owen fut le
premier énoncé clair de la thèse que les quinze années suivantes n'ont cessé
de confirmer : il existe des jeux de pièces qui « seront impossibles avec les
algorithmes de retour arrière actuels », quel que soit le nombre de machines
enrôlées
(groups.io message 222,
message 226). La communauté a
tout de même construit les projets répartis, plus d'une fois et sous deux
formes distinctes. Toutes deux méritent qu'on les comprenne, car l'une d'elles
s'est révélée réellement utile. L'histoire sociale (l'essor et le déclin
d'eternity2.net, les querelles de concours qui l'entouraient) se trouve dans
les pages d'histoire ; cette page est la vue
systèmes.
La première forme, c'est la foule : des inconnus téléchargent un client,
donnent des cycles, et se partagent tout prix par contrat.
eternity2.net était le fer de lance. Dave Clark, auteur d'un solveur
réparti pour Eternity I, l'a lancé sur l'infrastructure BOINC de Berkeley le
mois même où le casse-tête est sorti, en juillet 2007
(message 756). Les sceptiques
affirmaient dès le lancement que, sans avancée algorithmique, même
100 000 machines n'avaient pour ainsi dire aucune chance
(message 763) ; la foule est
venue quand même. En six semaines, le projet comptait plus de 1 300 membres
inscrits ; 160 d'entre eux se trouvaient aux États-Unis, où le casse-tête
n'était pas encore sorti
(message 2122,
message 2132). Le projet a
soumis à Tomy une partielle à 462 arêtes, puis une 463
(message 2663), le nombre qui a
servi de plafond public à la communauté pendant plus d'un an. Cinq mois après
le lancement, Clark l'a fermé et a publié le bilan : plus de 1,6 TFlops de
puissance de calcul cumulée, plus de 10¹⁹ opérations processeur, meilleurs
scores « dans le milieu des 460 environ », et son propre verdict qu'une
solution par force brute « allait toujours de toute évidence être impossible »
(message 3511). Il a ouvert le
code source de son solveur de recherche en partant
(message 3716), et ses formats
de fichiers sont devenus le standard d'échange de la communauté.
Le Eternity 2 Syndicate y a ajouté le juridique. Lancé en octobre 2007 à
eternity2syndicate.co.uk, ses membres faisaient tourner un backtracker rapide
sur un espace de recherche partitionné (la même architecture qu'eternity2.net)
mais avec un contrat explicite : l'argent du prix partagé proportionnellement
aux placements apportés. En une semaine, il annonçait ~20 machines à une
moyenne de 300 millions de placements par seconde ; bientôt 40 membres
faisaient tourner 50 instances de solveur, avec des statistiques de progression
réservées aux membres (message 3021,
message 3078,
message 3105). Un site français
de résolution répartie tournait en parallèle ; Clark a salué la
« concurrence »
(message 1254). En mai 2008 est
venue la version à micro-échelle : le « E2@home » d'e2dude, une seule personne
revendiquant des scores supérieurs à 460 par semaine et par PC et recrutant
des bénévoles pour une part du prix mineur de 10 000 $
(message 5474).
Aucun de ces essaims n'a battu de record. La seule campagne de bénévoles à
avoir gagné de l'argent a inversé la recette : au lieu d'un client faible sur
de nombreuses machines, Louis Verhaard a publié le solveur le plus puissant
qui existât, eii, pour que quiconque puisse le faire tourner, avec le prix
partagé 50-50 entre lui et l'utilisateur au meilleur score
(message 5940). Les machines de
la communauté ont trouvé son 467 plus de quarante fois
(message 6275), et il a remporté
le seul prix qu'Eternity II ait jamais versé.
La page eii raconte cette
histoire en entier ; la leçon pour cette page-ci est sans détour : l'algorithme
était l'actif, et la foule n'en était que le multiplicateur.
La seconde forme est plus discrète et a survécu à la première : un chercheur,
de nombreuses machines qu'il contrôle personnellement, visant une cible
finie.
La grappe de François Galea. En 2009, Galea a rapporté avoir résolu
exactement le banc d'essai 10×9 de Brendan Owen (93 jours sur une grappe de
7 nœuds de Pentium 4 doubles) et avoir le 10×10 en cours depuis ~110 jours sur
une grappe de trois PlayStation 3, toujours non résolu (istarinz avait
abandonné le même 10×10 après un mois sur un Xeon quadricœur)
(message 6918). C'est le plus
ancien exemple net du bon cas d'usage : le 10×9 possède un arbre connaissable
et fini, si bien que davantage de cœurs achètent une véritable date
d'achèvement plutôt qu'un billet de loterie.
La ferme récupérée de Peter McGavin.
McGavin a bâti son parc avec tout ce qui coûtait peu : ~20 cœurs à la maison,
trois ODROID XU4, vingt-cinq Orange Pi Lite à 12 $ (130+ cœurs), puis des
serveurs de travail empruntés pour 400+ au total. Ce pic était intermittent,
non soutenu : le travail était « étalé sur environ 4 ans en utilisant par
intermittence jusqu'à environ 400 cœurs à la fois »
(message 9804), les serveurs
empruntés seulement lors du dernier mois environ, et selon sa propre note les
cœurs de serveur « sont des hyperthreads, à proprement parler »
(message 9753) tandis que les
cartes ARM tournent à environ un tiers d'un cœur de PC. En 2017, cette ferme a
résolu le set_1 10×10 de Brendan, le banc d'essai communautaire vieux d'une
décennie : ~2×10¹⁷ nœuds, environ 180 cœurs-ans, moins de 0,5 % de l'arbre
complet, « aucune nouvelle méthode, juste de la persévérance systématique et
la loi des grands nombres »
(message 9686,
message 9688). Trois ans plus
tard, il a pointé « environ deux cents » cœurs sur le solveur fraîchement
publié de Joshua Blackwood pendant quelques jours et a décroché le 469, alors
record absolu sur le vrai casse-tête
(message 10045).
Le cloud a fait des apparitions éclair : Amazon EC2 a été suggéré dès 2010
(message 8106), et David Barr a
essayé son programme de recherche sur AWS Lambda en 2016
(message 9642). Mais les parcs
loués n'ont jamais supplanté ceux détenus en propre ; pour un casse-tête sans
échéance, l'économie favorise le matériel qu'on peut laisser tourner pendant
des années.
| Effort | Modèle | Échelle | Résultat | Source |
|---|
| eternity2.net (Dave Clark, 2007) | Essaim de bénévoles (BOINC) | 1 300+ membres, 1,6 TFlops | 462–463 soumis ; >10¹⁹ ops ; fermé après 5 mois | 756, 3511 |
| Site réparti français (royale_zerezo, 2007) | Essaim de bénévoles | inconnu | S'est éteint sans résultat | 1253 |
| Eternity 2 Syndicate (Amos, 2007) | Essaim de bénévoles + contrat de prix | ~40 membres, 50 instances, ~300M placements/s | Aucun record ; s'est éteint avec le site | 3021, 3078, 3105 |
| E2@home (e2dude, 2008) | Micro-syndicat | Quelques bénévoles | Revendique plus de 460 ; aucun record vérifié | 5474 |
| Publication d'eii (Verhaard, 2008–09) | Binaire publié, partage de prix 50-50 | PC de la communauté | 467 trouvé 40+ fois ; le seul prix jamais versé | 5940, 6275 |
| Grappe + PS3 de Galea (2009) | Parc en propre | 14 CPU + 3 PlayStation 3 | 10x9 résolu exactement en 93 jours ; 10x10 non résolu | 6918 |
| Réservations de rangées supérieures (2013) | Protocole de liste de diffusion | Une poignée de membres | 4 318 956 rangées listées ; solution connue vérifiée ; s'est essoufflé | 9164, 9177 |
| Ferme de rangées de McGavin (2016–17) | Parc en propre (récupéré) | 400+ cœurs au pic, intermittent sur ~4 ans (beaucoup sont des hyperthreads) | set_1 10×10 de Brendan résolu, ~180 cœurs-ans | 9688, 9804 |
| McGavin sur le solveur de Blackwood (2020) | Parc en propre | « environ deux cents » cœurs, quelques jours | 469/480, le record de son temps | 10045 |
| wrapper_blackwood (Bucas, 2021–) | Serveur de tâches + clients par cœur | Un travailleur par cœur | Cartes de paramètres, pas des records | dépôt |
Le retour arrière a l'air séquentiel, mais il se répartit à merveille : fixez
un préfixe de la recherche et chaque sous-arbre en dessous devient une tâche
indépendante, sans le moindre besoin de communication. La communauté a employé
trois recettes concrètes.
Bandes de préfixes. Découper l'espace des premiers placements en plages et
confier chaque plage à un travailleur. C'est ce qu'ont fait eternity2.net et le
Syndicate, l'« espace de recherche partitionné » du
message 3021, et c'est la forme
la plus faible, car sur le casse-tête complet chaque bande est également
désespérée.
Listes de premières rangées. Énumérer toutes les complétions légales de la
première rangée, puis traiter chaque rangée comme une tâche : un retour arrière
borné sur le reste du plateau. En 2013, sur la suggestion de McGavin, Martin
(capiman) a énuméré les 4 318 956 rangées supérieures légales du set 1 10×10 de
Brendan et a publié la liste
(message 9164). McGavin a
parcouru jusqu'au bout la rangée contenant la solution connue, la
rangée 1 407 888, en 15 310 secondes, trouvant exactement cette solution
(message 9167), et Michel
Gaillard a « réservé » les entrées 1000002–1000035 en postant sur la liste
(message 9177). Cet effort de
2013 s'est essoufflé ; celui de 2017 a ajouté l'ingrédient manquant : le
classement. McGavin a noté ~20 millions de permutations de première rangée
par leur probabilité, au sens de la
théorie du complexe, de solution par nœud
d'arbre de recherche et a mis en ferme les meilleures rangées d'abord. La
solution est arrivée au parcours de rangée ~92 907 contre une prédiction d'une
pour ~70 000
(message 9688). Le classement
faisait la différence entre une loterie et un calendrier. Les tâches ont une
valeur extrêmement inégale ; un bon modèle statique de savoir quelles tranches
sont prometteuses vaut plus que n'importe quelle quantité de matériel
supplémentaire.
Balayages de paramètres. La variante moderne répartit des
configurations au lieu de sous-arbres. Le
wrapper_blackwood de Jef Bucas
est un petit serveur Python qui distribue des tâches par HTTP, où chaque tâche
est une variation des paramètres du
solveur de Blackwood ; les
clients (un travailleur par cœur) génèrent le source C# à partir de gabarits
avec cette variation intégrée, le compilent, l'exécutent et rapportent. La
sortie n'est pas un record mais une carte : quels triplets de couleurs et
quels calendriers de quotas atteignent la profondeur, agrégés sur des
centaines d'exécutions.
La mécanique de coordination était d'une informalité frappante. Le protocole
de réservation de 2013 reposait sur l'honneur : on revendiquait une plage de
rangées en postant un message
(message 9177), et cela
fonctionnait parce que les participants se comptaient sur les doigts d'une main.
La vérification, en revanche, était prise au sérieux, et c'était toujours la
même méthode : le recalcul indépendant. Quand McGavin a vérifié la
rangée 1 407 888, apal1969 a réexécuté la même rangée sur un code distinct et
l'a confirmée avec 6,77×10¹¹ nœuds
(message 9168) ; quand le 10×10
est tombé en 2017, Martin a validé la solution de façon indépendante
(message 9725) ; les plateaux
records étaient publiés avec la liste complète des pièces et vérifiés dans le
visualiseur en ligne de Jef Bucas
(message 10045). Rien n'entrait
au registre de la communauté sur la seule parole de quelqu'un.
Le véritable problème de coordination de l'ère des essaims était économique, et
le concours l'aggravait : les inscriptions au prix pouvaient être disqualifiées
si elles étaient publiées, si bien qu'eternity2.net a cessé de publier les
scores supérieurs à 463 : un projet réparti incapable de dire à ses propres
bénévoles ce qu'ils avaient trouvé
(message 3511). Les contrats de
partage de prix (les parts proportionnelles aux placements du Syndicate, le
50-50 d'eii, la part du prix mineur d'E2@home) étaient des tentatives
d'empêcher les bénévoles d'empocher une trouvaille pour eux-mêmes, et de les
garder motivés, à l'intérieur de ce secret imposé. Quand le concours est mort,
le problème s'est évaporé : les efforts modernes publient tout, et la confiance
repose sur la reproductibilité plutôt que sur des contrats.
Rien, et la communauté en connaissait la raison avant même de commencer. Les
estimations d'arbre du groupe lui-même, convergeant à partir
d'implémentations indépendantes en 2008, situaient la recherche complète à
environ 2,2×10⁴³ nœuds par solution, de l'ordre de 10²⁷ cœurs-ans
(message 5193,
message 5197). Face à cela, le
total cumulé de 10¹⁹ opérations d'eternity2.net représente environ 10⁻²⁴ du
travail d'une seule solution : multiplier votre parc par mille, ou par un
million, ne déplace en rien un nombre pareil. Owen l'avait dit deux mois avant
la sortie du casse-tête
(message 226) ; la lettre de
fermeture de Clark le concédait presque dans les mêmes termes
(message 3511).
Le point plus profond est celui sur lequel ce wiki ne cesse de revenir : le
matériel multiplie une recherche, tandis que l'élagage la reconfigure.
Élagage contre vitesse développe l'argument
général, et la théorie du complexe fournit
l'arithmétique exacte de la raison pour laquelle l'arbre du casse-tête complet
écrase tout parc concevable. Chaque effort réparti sur le casse-tête complet a
confirmé l'argument de dénombrement ; aucun ne l'a entamé.
Les efforts qui ont fonctionné partagent une propriété : la cible était finie
et les mathématiques le disaient à l'avance.
- Résolution exhaustive à la frontière de faisabilité. Le 10×9 de Galea et
le 10×10 de McGavin sont des arbres de ~10¹⁵–10¹⁷ nœuds : monstrueux pour une
seule machine, traitables pour un parc. La répartition a converti « un jour »
en 93 jours et 180 cœurs-ans respectivement.
- Mesure. Le 10×10 de McGavin a fait double emploi comme la plus solide
validation que la théorie du complexe ait
jamais reçue : la solution est arrivée selon le calendrier prédit, et les
histogrammes de nœuds publiés correspondaient au modèle
(message 9688). Une ferme de
cœurs est un bel instrument pour mesurer une théorie.
- Études paramétriques. wrapper_blackwood est le gabarit moderne : quand la
question est « laquelle de ces mille configurations cherche le plus
profond ? », les tâches sont vérifiables, bornées et indépendantes, ce qui
est exactement ce que la répartition recherche.
- Des records, mais seulement en aval d'un algorithme. Le 469 est venu de
~200 cœurs faisant tourner un solveur qui était déjà, à lui seul, de classe
record (message 10045). Les
cœurs ont multiplié l'algorithme de Blackwood ; à aucun moment dans cette
archive ils ne s'y sont substitués.
Le résumé en une ligne
Quinze ans de calcul collectif, distillés : les foules sans algorithme n'ont
rien acheté ; les parcs pointés sur des cibles finies et bien modélisées ont
acheté exactement ce que le modèle promettait. Le multiplicateur est réel ;
il ne fait que multiplier ce que vous avez déjà.