Eternity II a une histoire officielle (un communiqué de presse, un prix, une
échéance) et il en a une véritable, qui s'est déroulée sur une liste de
diffusion. Le groupe eternity2 (à l'origine un
groupe Yahoo) est l'endroit où le casse-tête a été analysé avant d'exister,
numérisé le jour de son lancement, déclaré insoluble en moins de quinze jours,
et où la seule somme de prix jamais versée a discrètement été rattachée à l'un
des habitués de la liste. Cette page raconte cette histoire à partir de
l'archive elle-même : chaque événement renvoie au message où il s'est produit.
La partie I couvre de la fondation du groupe jusqu'à la première date d'examen,
de 2000 à février 2009.
Le fait le plus étrange à propos de la communauté Eternity II est sa date de
naissance. Brendan Owen a créé le groupe eternity_two en octobre 2000, six ans
et demi avant l'annonce du casse-tête, « because we anticipated a follow up
puzzle » à Eternity I
(msg 404). Les plus anciens
messages conservés spéculent sur ce que pourraient être les pièces de la suite,
et misent à tort sur des tétraèdres 3D
(msg 8).
Dès 2001, le groupe répétait déjà le problème du concepteur plutôt que celui du
solveur : Günter Stertenbrink demandait comment on construirait un casse-tête
doté d'un prix colossal et d'une chance d'à peine 1 % d'être résolu en dix ans
(msg 15), presque exactement le
cahier des charges que l'équipe de Christopher Monckton allait plus tard
exécuter. Les vétérans d'Eternity I dérivaient là et attendaient : Dave Clark,
auteur du solveur distribué ESolve pour E1, a rejoint le groupe en avril 2001
(msg 21). Lorsque les premiers
comptes rendus de presse sont arrivés en décembre 2005, avec Monckton promettant
que la suite exigerait « the lifetime of the Universe » tandis que le co-concepteur
Oliver Riordan parlait de « several years », Stertenbrink en a tiré la
conclusion qui s'imposait : « So we can conclude, the end of the universe is in
several years. »
(msg 34)
L'annonce est tombée le 22 janvier 2007 : 256 pièces, 2 000 000 $ US pour la
première solution correcte, lancement le 28 juillet, et un coup médiatique au
London Toy Fair où un homme fort détruisait « the computer containing a solution »
(msg 36). Cet ordinateur, comme un
initié chez le distributeur l'a plus tard admis, ne contenait absolument rien
(msg 148).
Le groupe n'a pas attendu les pièces. En deux jours, il comptait les types de
bords sur des photos promotionnelles, et Owen avait dérivé la formule du nombre
attendu de solutions qui faisait de la difficulté un paramètre de conception
ajustable (msg 38,
msg 44). Il a publié un générateur
de casse-têtes de type Eternity II
(msg 41) ; Alan O'Donnell avait le
premier solveur fonctionnel une semaine plus tard
(msg 64). Au 8 juillet, trois
semaines avant que quiconque ait touché une vraie pièce, anr_56 avait estimé les
comptes de types de bords à partir des photos de lancement et Owen avait fait
tourner les chiffres sur cette configuration : environ 10^30 fois plus difficile
que les jeux d'essai que le groupe résolvait en quelques minutes. « No one will
solve this puzzle », a-t-il conclu
(msg 665).
Puis vinrent les fameuses 48 heures. L'Australie a reçu le casse-tête en
premier, et Owen était chez Kmart la veille du lancement, « first one to grab it
off their stack » (msg 1051). Il a
fait passer les panneaux de pièces dans un programme de vision par ordinateur
qu'il avait écrit à l'avance
(msg 789), a rapporté une
distribution des bords « as flat as could be »
(msg 1054), et a confirmé les
paramètres réels : 5 couleurs de bordure, 17 couleurs intérieures, le pire des
scénarios pour le groupe (msg 977).
Ensuite, après la « nice chat to Mr Monckton » de Dave Clark, il a publié la
première estimation du nombre de solutions pour le jeu de pièces réel : environ
5 930 solutions avec l'indice obligatoire, contre le chiffre de Monckton
lui-même d'environ 5 millions
(msg 987). Le casse-tête avait deux
jours et sa difficulté était déjà mesurée.
La même semaine a fixé les usages de la communauté. Pour vérifier les
transcriptions de pièces sans partager de données protégées, les membres ont
convergé vers des sommes de contrôle CRC publiées
(msg 1063) ; et le nouveau venu
Sergio Demian Lerner a mis en garde contre les « jeux fantômes » : le jeu
d'essai d'un inconnu pouvait être le vrai casse-tête réencodé, vous incitant à
livrer une solution à 2 M$
(msg 1210).
Une semaine après le début d'août, l'inventeur du casse-tête est arrivé en
personne ; il venait disqualifier quelqu'un. Postant depuis une adresse Yahoo
invérifiable, Christopher Monckton a déclaré détenir le copyright sur les motifs
des pièces et que son « web-trawling software » avait signalé le site web de
Brendan Owen : Owen, qui visait le prix moindre, était éliminé
(msg 1342,
msg 1352,
msg 1358). Il est apparu par la
suite que le fichier incriminé ne correspondait même pas aux vraies pièces
(msg 1358). Des membres ont
protesté qu'un compte de forum anonyme ne pouvait guère avoir de poids officiel ;
Monckton a persisté (msg 1374,
msg 1377). Le refroidissement a été
réel et durable : un an plus tard, Owen, en tant que modérateur, supprimait
encore des tables de données dérivées « to be safe »
(msg 5651). C'est dans ce climat
qu'Owen, montrant que les statistiques plates des pièces d'E2 tuaient la
stratégie qui avait percé Eternity I, a tracé sa ligne rouge : « If we cannot
talk about something as fundamental as piece frequencies, then I will give up on
this puzzle now » (msg 1667,
msg 1694).
La théorie est venue vite après cela. kubzpa a prouvé par un
argument de parité qu'un score
d'exactement 479 (un seul bord non concordant) est impossible
(msg 1640) ; gardez cela en tête,
car dix-sept mois plus tard cet argument rencontrera un contre-exemple. Owen a
ensuite produit le résultat emblématique de la période : en supposant que les
concepteurs voulaient le 16×16 le plus difficile possible, avec une distribution
plate et environ une solution attendue, le nombre de couleurs intérieures
devrait être (196! · 4^196)^(1/392) ≈ 17,14, soit 17 couleurs intérieures et 5
couleurs de bordure. Exactement le vrai casse-tête
(msg 1947). La répartition 17+5
n'était pas un coup de malchance ; c'était une flèche en plein sur le pic de
difficulté, et le groupe avait rétro-conçu le
ciblage.
Les affirmations théoriques étaient confrontées aux comptes de nœuds mesurés sur
des jeux d'essai partagés. Angel de Vicente,
postant sous le pseudonyme Txibilis, a construit la suite standard de plateaux de
test de type E2 (msg 1610), et un
duel s'est engagé : les ordres de remplissage
conçus à la main par Txibilis contre l'optimiseur de stratégie automatisé de
doc_s_smith, faisant chuter de plusieurs ordres de grandeur les comptes de nœuds
en recherche complète ; un jeu d'essai s'établissait à 89 794 nœuds, battu en
deux jours par 85 729
(msg 2896,
msg 2928). En plein duel, la liste
a découvert qui était doc_s_smith : Dietmar Wolz, découvreur de la plupart des
solutions connues d'Eternity I
(msg 2972).
Les estimations ont convergé elles aussi. L'article de kubzpa situait le nombre
de solutions près de 15 millions
(msg 3497) ; Owen a mesuré la
profondeur de branchement de l'arbre de recherche niveau par niveau, trouvant que
le compte de nœuds culmine à 161 pièces placées
(msg 3147) ; et en avril 2008 il a
annoncé avoir « nailed the theory » : un modèle exact de l'arbre de recherche
dont les prédictions se superposaient aux courbes empiriques, vérifié de manière
indépendante par Louis Verhaard : de l'ordre de 10^27 années-CPU par solution
(msg 5197,
msg 5193,
msg 5209). Le théoricien en chef
du groupe a agi sur la foi de ses propres chiffres : il chassait désormais le
score le plus haut, pas 480
(msg 4996).
Si un seul ordinateur était sans espoir, peut-être que des milliers ne
l'étaient pas. eternity2.net de Dave Clark, un
solveur distribué basé sur BOINC,
a été lancé avec le casse-tête en juillet 2007
(msg 756) et comptait 1 300 membres
en un mois, dont 160 aux États-Unis, où le casse-tête n'était même pas encore
sorti (msg 2122,
msg 2132). Le projet a soumis à
Tomy un partiel à 462 bords, puis 463
(msg 2663), un nombre qui allait
faire office de plafond public du score de la communauté pendant plus d'un an.
Un « Eternity 2 Syndicate » de partage des gains a suivi, rémunérant les membres
au prorata des placements apportés
(msg 3021).
Cela a duré cinq mois. En décembre 2007, Clark a fermé eternity2.net, publiant le
décompte final : plus de 1,6 TFlops de puissance de calcul agrégée, plus de
10^19 opérations CPU, meilleurs scores dans les milieux 460. Son verdict : une
solution par force brute « was always clearly going to be impossible »
(msg 3511). La liste a
immédiatement engendré des fils intitulés « Eternity2 Must Have Been Solved » ;
il ne l'avait pas été (msg 3554).
Les fichiers du projet ont été conservés dans l'archive du groupe
(msg 3633), et Clark a ouvert le
code source de son solveur de recherche
(msg 3716). Il a aussi laissé à
l'archive sa meilleure source primaire sur la création du casse-tête : un appel
téléphonique avec Monckton, qui décrivait des juges saisissant de l'entropie
dans un générateur bâti par les vainqueurs d'Eternity I, Alex Selby et Oliver
Riordan, la solution imprimée une seule fois puis mise au coffre
(msg 4177), « whilst all parties
were out of the room », selon la formule du dépliant du distributeur Tomy qu'il
avait posté au lancement
(msg 901).
Le flanc des méthodes exactes ne s'en est pas mieux tiré. Un
encodage SAT publié du casse-tête
complet s'accompagnait d'un appel à quiconque posséderait une machine dotée de
plus de 16 Go de RAM (msg 4084) ;
la programmation en nombres entiers mourait aux plateaux 8×8
(msg 5602). La vitesse brute
continuait de grimper : istarinz a franchi les 100 millions de placements par
seconde sur plusieurs cœurs
(msg 5804), puis a mesuré 558
millions sur un Core i7 flambant neuf
(msg 6212). Mais face à des
espaces de recherche mesurés en puissances de quarante, le débit était une
erreur d'arrondi.
Les scores avaient grimpé tout du long : 410 pour Pierre Schaus dans les
premières semaines (msg 1568), 453
pour philippe.dupond (msg 3998),
461 pour e2dude (msg 4440), avec
463 comme « current known high »
(msg 5688). Les méthodes ont changé
de nature à la mi-2008 : Schaus a publié son article de programmation par
contraintes, dont le coup clé (retirer un ensemble de pièces non adjacentes et
les replacer de façon optimale en résolvant un problème d'affectation) est
devenu le moteur de l'hybride d'antminder, qui atteignait un 462 par jour en
moyenne (msg 5589,
msg 5601).
Pendant ce temps, deux personnes avaient discrètement dépassé le plafond. Dans un
long échange en août, Max rapportait aller « beyond the 'don't-talk-about-limit'
quite easily » ; Louis Verhaard (« Max, you are really a dangerous man! »)
confrontait ses méthodes aux siennes et découvrait qu'ils avaient convergé vers
la même signature heuristique, promettant une divulgation complète « after
new-year », c'est-à-dire après la date d'examen du 31 décembre
(msg 5767,
msg 5780). Verhaard ne révélerait
que la géométrie : ses meilleurs ordres de remplissage à haut score ressemblaient
à un « peigne » : la plupart des rangées balayées horizontalement, le reste
verticalement (msg 6112).
Puis, le 22 septembre 2008, Verhaard a publié
son solveur que chacun pouvait
faire tourner sur fingerboys.se : « This because I am stuck and my only hope to
improve my best score is by using brute force »
(msg 5940). Tout prix serait
partagé 50-50 avec l'utilisateur au meilleur score. antminder, dont le propre
programme mettait une semaine pour atteindre 463, était sans détour : eii
« completely blows it away »
(msg 5950). Le prix lui-même
relevait encore du folklore (le règlement ne promettait qu'un « lesser prize »
discrétionnaire) jusqu'à ce que Max retrace le chiffre de 10 000 $ dans une
interview de Monckton sur le site officiel français
(msg 6073). Verhaard, trois mois
avant de le remporter, affirmait s'en moquer : il faisait cela pour l'honneur, et
seulement pour cette année-là
(msg 6072).
Le même automne, les résolveurs à la main ont fait surface : Christine Raisin
descendue à 21 pièces restant dans le couvercle de la boîte
(msg 5935), Verhaard triant les
pièces par motif avec sa fille de sept ans et organisant une mini-compétition de
résolution à la main, les fils inventant des surnoms comme « pink swords » et
« kipper ties » pour les motifs
(msg 5933,
msg 5929,
msg 5958,
msg 5959). La liste n'a jamais été
qu'un banc d'essai de solveurs.
À l'approche de la première date d'examen, la communauté était en attente :
plusieurs membres refusaient d'engager un effort sérieux tant que le casse-tête
n'aurait pas prouvé qu'il pouvait survivre à sa première échéance
(msg 6216) ; NickB avait parié 20 £
sur l'absence de vainqueur et jugeait son argent en sécurité
(msg 5979).
Le 31 décembre 2008 est venu et reparti. Rien. Des membres ont écrit aux adresses
britannique et américaine de Tomy et laissé des messages vocaux, sans réponse
(msg 6245) ; la Careline
consommateurs ne savait « no details as of yet, regarding whether or not there is
a winner » (msg 6295). Le règlement
disait que les vainqueurs seraient prévenus sous 14 jours et les résultats
publiés dans le London Times et le New York Times
(msg 6296,
msg 6336) ; aucune publication de
ce genre n'a jamais visiblement paru. Entre-temps, le 6 janvier, Verhaard a
publié la documentation de son solveur et en a dévoilé le plafond : les
utilisateurs avaient trouvé 467 plus de quarante fois
(msg 6275).
Le 15 janvier, à peu près le dernier jour de la fenêtre de 14 jours, Henk van der
Griendt a trouvé une déclaration derrière un lien discret sur le site britannique
seulement : des centaines de participations, aucune complète, le prix de 2 Mtoujoursouvert,etunprixdefinalistede10000 à Anna Karlsson de Lund,
Suède, pour 467 sur 480 (msg 6337).
Pas de communiqué de presse, pas de Times, et pas un mot de Monckton à aucun
moment. La liste a eu besoin d'environ une heure pour décoder « Lund + 467 » : la
participation venait du foyer de Louis Verhaard, soumise au nom de son épouse,
qui avait reçu le courriel de félicitations quelques jours plus tôt
(msg 6349). Les félicitations ont
afflué de tous les habitués ; Max a révélé que son propre meilleur score avait été
465, chaque bord supplémentaire coûtant à son programme un facteur d'environ 30 en
temps (msg 6348). La presse suédoise
a publié la photo de famille : plus d'un an de travail, 13 « seams » d'une
solution complète, une partie de l'argent allant au World Wildlife Fund
(msg 6374,
msg 6375).
Les suites ont eu trois piquants. Un chercheur du groupe SAT de Lleida a affirmé
qu'atteindre 470 était « rather easy » avec leurs méthodes, une affirmation
jamais étayée par la moindre participation soumise, comme Max l'a fait remarquer
avec insistance (msg 6306,
msg 6360). Tomy a dit à un membre
qu'il n'y aurait pas d'autres casse-têtes à indices,
ce que la plupart de la liste a accueilli comme préservant la pureté du défi
(msg 6381). Et Verhaard a réglé au
passage un théorème vieux de dix-sept mois : 479 est atteignable, en retournant
une pièce de bordure dont les deux bords de bordure partagent une couleur dans
une solution à 480. La preuve de parité de 2007 avait négligé les bords de
bordure tournés vers l'extérieur, que le score ne compte jamais
(msg 6317). Même le résultat
d'impossibilité le plus net de la communauté avait une faille ; le casse-tête,
non résolu, gardait toutes les siennes.
Partie II : 2009-2026
L'histoire continue dans la partie II : la
rumeur hongroise « nous l'avons résolu » tranchée, la mort du concours avec sa
solution enfermée dans un coffre, la décennie du 467, la migration qui a sauvé
cette archive à quelques jours près, et la vague de records qui a porté le
plateau à 470.