Eternity II

Le
JL
J'ai entendu parler de ce jeu ce soir sur BFM :
http://fr.eternityii.com/

Le principe est simple, il suffit d'assembler 256 carrés sur une grille
16x16 de manière à ce que les bords correspondent. Sauf que ça ne doit pas
être aussi simple, parce que celui qui y arrive avant fin 2010 gagne 2
millions de dollars !

J'ai testé leur version de démo en ligne à 4x4 cases sur
http://fr.eternityii.com/essayer-eternityii-en-ligne/ et en tâtonnant au
hasard sans aucune formalisation préalable j'ai fini par trouver en 15
minutes une solution (http://cjoint.com/?hBbaBZXnmZ pour les pressés). Cela
dit je n'ose même pas imaginer pouvoir y arriver comme ça avec la grille à
256 cases.

Une employée de l'éditeur était interviewée, et a indiqué qu'il y avait
20.000 solutions, et que seules 3 personnes au monde les connaissaient : le
mathématicien inventeur du jeu, et les 2 gagnants de Eternity I (je ne
connais pas la différence) avec qui il a mis au point cette 2e version. Et
que l'intérêt du jeu, c'est qu'il est _impossible_ de trouver la solution
par ordinateur.

À priori c'est un problème que l'on doit pouvoir résoudre par force brute,
sauf qu'en calculant rapidement j'arrive à un maximum de 256!x4^256
possibilités (256! pour le choix de chacune des 256 pièces sur une case,
avec à chaque fois 4 orientations possibles). En fait ça fait un peu moins
parce qu'il y a des pièces qui ne peuvent aller que dans les coins ou sur
les bords. Mais même avec ça, ça reste trop pour une bête attaque par force
brute en l'état actuel de l'informatique. Donc en comptant comme cela, la
fille semble avoir raison.

Mais en fait on sent bien qu'il y a moyen d'être un peu plus intelligent,
parce qu'une fois quelques pièces disposées, on voit vite que le nombre de
combinaisons compatibles diminue fortement. Donc j'aurais tendance à penser
qu'en l'état actuel des mathématiques et de la cryptographie, il doit bien y
avoir quelques chercheurs capables de trouver un aglorithme pour résoudre ça
avec un ordinateur pas trop futuriste.

Qu'en pensez-vous ? Quelle vous semble être la complexité du problème ?
Avez-vous déjà vu des études sur ce sujet ?

Ah, et pour finir, le jeu sort demain, au prix de 50 ¤. Je ne vais
certainement pas l'acheter, personnellement pour le prix je m'amuse beaucoup
plus avec un bon jeu sur PC, mais je trouve intéressant le concept d'essayer
de "casser" le jeu.

JL.
Questions / Réponses high-tech
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 3
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
JL
Le #585884
Ah, et un article du monde -- intéressant mais un peu pompeux -- sur
http://www.lemonde.fr/web/article/0,,36-938345,0.html . On y
apprend notament que l'inventeur a été ruiné quand deux étudiants ont cassé
la première version, comme quoi il y a de l'espoir...

JL.
Denis Feldmann
Le #585883
Ah, et un article du monde -- intéressant mais un peu pompeux -- sur
http://www.lemonde.fr/web/article/0,,36-938345,0.html . On y
apprend notament que l'inventeur a été ruiné quand deux étudiants ont
cassé la première version, comme quoi il y a de l'espoir...

JL.
Par force brute, aucun espoir : 256!*4^256=(environ)10^661, or il n'y a,

par exemple que 10^130 parties d'échecs plausibles, 10^80 particules
dans l'univers, et un ordinateur calculant à une cadence de 1
YottaHz,avec 10^80 processeurs séparés, ne résoudra en force brute les
échecs (en explorant toutes les parties plausibles) qu'au bout de 10^26
secondes, soit cent millions de fois l'âge de l'univers...

Tiens, un peu de pub : j'ai écrit sur ce genre de questions une page que
j'aime bien : http://denis.feldmann.club.fr/grands.htm

Serge Paccalin
Le #585882
Le vendredi 27 juillet 2007 à 06:39:51, Denis Feldmann a écrit dans
fr.misc.cryptologie,fr.sci.maths :

Par force brute, aucun espoir : 256!*4^256=(environ)10^661, or il n'y a,
par exemple que 10^130 parties d'échecs plausibles, 10^80 particules
dans l'univers, et un ordinateur calculant à une cadence de 1
YottaHz,avec 10^80 processeurs séparés, ne résoudra en force brute les
échecs (en explorant toutes les parties plausibles) qu'au bout de 10^26
secondes, soit cent millions de fois l'âge de l'univers...


Je ne trouve que 256! possibilités si les pièces sont indifférenciées,
et 3!×56!×192! si on distingue les coins et les bords comme sur la
version d'essai à 16 pièces.

Je choisis un ordre de remplissage du plateau (la spirale depuis un coin
m'a l'air prometteuse), et je teste tous les ordres de pièces possibles.

Bien entendu, avec les motifs à raccorder, ça doit chuter.

--
___________
_/ _ _`_`_`_) Serge PACCALIN -- sp ad mailclub.net
_L_) Il faut donc que les hommes commencent
-'(__) par n'être pas fanatiques pour mériter
_/___(_) la tolérance. -- Voltaire, 1763

Serge Paccalin
Le #585881
[Supersedes: 192! -> 196!]

Le vendredi 27 juillet 2007 à 06:39:51, Denis Feldmann a écrit dans
fr.misc.cryptologie,fr.sci.maths :

Par force brute, aucun espoir : 256!*4^256=(environ)10^661, or il n'y a,
par exemple que 10^130 parties d'échecs plausibles, 10^80 particules
dans l'univers, et un ordinateur calculant à une cadence de 1
YottaHz,avec 10^80 processeurs séparés, ne résoudra en force brute les
échecs (en explorant toutes les parties plausibles) qu'au bout de 10^26
secondes, soit cent millions de fois l'âge de l'univers...


Je ne trouve que 256! possibilités si les pièces sont indifférenciées,
et 3!×56!×196! si on distingue les coins et les bords comme sur la
version d'essai à 16 pièces.

Je choisis un ordre de remplissage du plateau (la spirale depuis un coin
m'a l'air prometteuse), et je teste tous les ordres de pièces possibles.

Bien entendu, avec les motifs à raccorder, ça doit chuter.

--
___________
_/ _ _`_`_`_) Serge PACCALIN -- sp ad mailclub.net
_L_) Il faut donc que les hommes commencent
-'(__) par n'être pas fanatiques pour mériter
_/___(_) la tolérance. -- Voltaire, 1763

Serge Paccalin
Le #585880
Le vendredi 27 juillet 2007 à 07:17:19, Serge Paccalin a écrit dans
fr.misc.cryptologie,fr.sci.maths :

[Supersedes: 192! -> 196!]

Le vendredi 27 juillet 2007 à 06:39:51, Denis Feldmann a écrit dans
fr.misc.cryptologie,fr.sci.maths :

Par force brute, aucun espoir : 256!*4^256=(environ)10^661, or il n'y a,
par exemple que 10^130 parties d'échecs plausibles, 10^80 particules
dans l'univers, et un ordinateur calculant à une cadence de 1
YottaHz,avec 10^80 processeurs séparés, ne résoudra en force brute les
échecs (en explorant toutes les parties plausibles) qu'au bout de 10^26
secondes, soit cent millions de fois l'âge de l'univers...


Je ne trouve que 256! possibilités si les pièces sont indifférenciées,
et 3!×56!×196! si on distingue les coins et les bords comme sur la
version d'essai à 16 pièces.

Je choisis un ordre de remplissage du plateau (la spirale depuis un coin
m'a l'air prometteuse), et je teste tous les ordres de pièces possibles.


Et j'oublie les rotations... mais pour les pièces intérieures
uniquement ; les bords et les coins n'ont qu'une orientation possible,
une fois leur emplacement choisi.

3!×56!×196!×(4^196)

--
___________
_/ _ _`_`_`_) Serge PACCALIN -- sp ad mailclub.net
_L_) Il faut donc que les hommes commencent
-'(__) par n'être pas fanatiques pour mériter
_/___(_) la tolérance. -- Voltaire, 1763


Denis Feldmann
Le #585879
Le vendredi 27 juillet 2007 à 07:17:19, Serge Paccalin a écrit dans
fr.misc.cryptologie,fr.sci.maths :

[Supersedes: 192! -> 196!]

Le vendredi 27 juillet 2007 à 06:39:51, Denis Feldmann a écrit dans
fr.misc.cryptologie,fr.sci.maths :

Par force brute, aucun espoir : 256!*4^256=(environ)10^661, or il n'y a,
par exemple que 10^130 parties d'échecs plausibles, 10^80 particules
dans l'univers, et un ordinateur calculant à une cadence de 1
YottaHz,avec 10^80 processeurs séparés, ne résoudra en force brute les
échecs (en explorant toutes les parties plausibles) qu'au bout de 10^26
secondes, soit cent millions de fois l'âge de l'univers...
Je ne trouve que 256! possibilités si les pièces sont indifférenciées,

et 3!×56!×196! si on distingue les coins et les bords comme sur la
version d'essai à 16 pièces.

Je choisis un ordre de remplissage du plateau (la spirale depuis un coin
m'a l'air prometteuse), et je teste tous les ordres de pièces possibles.


Et j'oublie les rotations... mais pour les pièces intérieures
uniquement ; les bords et les coins n'ont qu'une orientation possible,
une fois leur emplacement choisi.

3!×56!×196!×(4^196)



Là, d'accord. Mais bon, ça vaut quand même 10^560... D'autres symétries
permettent sûrement de réduire un peu ce nombre, par un facteur 10^10,
pourquoi pas... Hélas, ça ne change rien à l'impossibilité d'une
approche par force brute...



Serge Paccalin
Le #585878
Le vendredi 27 juillet 2007 à 07:36:45, Denis Feldmann a écrit dans
fr.misc.cryptologie,fr.sci.maths :

3!×56!×196!×(4^196)


Là, d'accord. Mais bon, ça vaut quand même 10^560... D'autres symétries
permettent sûrement de réduire un peu ce nombre, par un facteur 10^10,
pourquoi pas... Hélas, ça ne change rien à l'impossibilité d'une
approche par force brute...


Avec les motifs qui réduisent les possibilités de pièces le long du
parcours, on peut peut-être arriver à quelque chose...

Par exemple, pour remplir les bords, la force brute donne 3!×56!, mais
une fois posé le premier coin, je doute que les 56 pièces de bord
conviennent, et ainsi de suite...

Mais bon, ça doit rester astronomique, quand même.

--
___________
_/ _ _`_`_`_) Serge PACCALIN -- sp ad mailclub.net
_L_) Il faut donc que les hommes commencent
-'(__) par n'être pas fanatiques pour mériter
_/___(_) la tolérance. -- Voltaire, 1763


Sylvain
Le #585877
"Denis Feldmann" message de news: 46a9771e$0$21143$
Ah, et un article du monde -- intéressant mais un peu pompeux -- sur
http://www.lemonde.fr/web/article/0,,36-938345,0.html . On y
apprend notament que l'inventeur a été ruiné quand deux étudiants ont
cassé la première version, comme quoi il y a de l'espoir...

JL.
Par force brute, aucun espoir : 256!*4^256=(environ)10^661, or il n'y a,



Ce serait plutôt : 4! * 56! * (196! * 4^196)

par exemple que 10^130 parties d'échecs plausibles, 10^80 particules dans
l'univers, et un ordinateur calculant à une cadence de 1 YottaHz,avec
10^80 processeurs séparés, ne résoudra en force brute les échecs (en
explorant toutes les parties plausibles) qu'au bout de 10^26 secondes,
soit cent millions de fois l'âge de l'univers...

Tiens, un peu de pub : j'ai écrit sur ce genre de questions une page que
j'aime bien : http://denis.feldmann.club.fr/grands.htm



ast
Le #585876
"JL"
J'ai entendu parler de ce jeu ce soir sur BFM :
http://fr.eternityii.com/



Résolu en 4 mn 21 s
Qui fait mieux ?

http://cjoint.com/?hBl7pwjg7G

Olivier Miakinen
Le #585875

http://fr.eternityii.com/


Résolu en 4 mn 21 s
Qui fait mieux ?


Maître Po, sur frje, a fait 2 mn 7 s à son premier essai. Mais,
comme déjà signalé, certaines solutions valides sont refusées.


Publicité
Poster une réponse
Anonyme