Reprise du message précédent :

 
Oui c'est clair qu'il peut exister des personnes/mathématiciens/programmeurs encore plus fortes pour coder un algorythme en beton qui leur permettra de trouver la solution avec quelques PC plus vite que des milliers de PC sur eternity2.net.
 

 
Non, je n'y participe pas, voir mes stats BOINC : http://fr.boincstats.com/stats/boi [...] &id=779395
Actuellement je calcule sur QMC@home (chimie quantique) et Human Proteome Folding (pliage de protéines)
 
Et l'AF a mis tout naturellement le projet en non-recommandé : http://www.boinc-af.org/content/view/711/229/
 
Le projet n'est pas du tout dans la philosophie des projets BOINC qu'on soutien. Si encore ils prévoyaient de reverser une partie des gains à des actions humanitaires, ou au développement de BOINC et de projets avec peu de moyens ça aurait pu passer. Mais là rien, le responsable du projet empoche dans tout les cas les 1 millions. Sans promettre d'actions significatives.

Hum! va falloir du temps... en faisant à l'arrache, ça donne:
Sachant qu'il y a 256 emplacements possibles et 4 rotations par pièces,
la 1ère pièce a 256 emplacements possibles et 4 rotations possibles soit 1024 possibilités. La 2ème 255 emplacements possibles et aussi 4 rotations. Donc par extrapolation: (256 x 4) x (255 x 4) x (254 x 4 ) x.......x (2 x 4) x (1 x 4) = Factoriel(256) x 4 puissance 256 =
256! x 4^256 = 1,1501455970687482978298441855589 10E(+661)
Bien sûr c'est un calcul simple sans tenir compte des combinaisons évidentes (style coin ou bord...). Mais quand même, si on imagine un algorythme brut de pomme avec un ordinateur pouvant tester 1000 combinaisons par secondes, il faudrait 3,65 10E(+653) années. Alors même en reliant par la toile 100 millions de PC ça fait toujours 3,65 10E(+645) années.... et d'ici là l'univers aura disparu. Donc même ALGOFLASH devra être sacrément balèze. Peut-être les futurs processeurs quantiques...
Que l'éternity soit avec vous!!!

sauf que tu considères un paquet de combinaisons non valides.
si tu construis un jeu en apparence valide (avant les dernières pièces), tu as bcp moins de combinaisons
 
et pis 1000 combinaisons par secondes, c'est peanuts ^^
ca va tourner aux alentours de x*100K /s  
 
Avant de sortir les ordinateurs quantiques xD il faudrait sortir le cerveau.
 

Beaucoup moins qu'un nombre énorme ça reste énorme
 
Pour commencer j'avais fait un algo brut. Il mettait 4-5 secondes pour placer 14x14 pièces
en partant d'un coin.
Par contre si je voulais lui faire trouver un 15x14... il ne trouvait toujours rien après 24h...    
 

Et même si tu testes 1 milliards de milliards de milliards de milliards de combinaisons par secondes, (soit
1x10^36 ce qui est monstrueux), tu n'arriveras jamais au bout.
 

Et oui, certains problèmes ne pourront être résolus de manière brutale. Même par d'hypothétiques ordinateurs
quantiques. C'est mathématique.
 
là j'essaye de trouver une manière de continuer la recherche différemment après que l'algo
de recuit simulé se trouve bloqué.
Pour l'instant c'est plus mon temps cerveau qui est le point bloquant et mon temps CPU lui est tout tranquille.
 

 
 
240 oula c'est beaucoup, je sens que t'as positionné les dernieres pieces en fesant juste correspondre 1 coté, en finissant a l'arrache comme on peut quoi, je viens de connaitre ça, enfin avec moins de pieces 230 par la  
 
sinon ce puzzle est marrant quand meme, au debut on se dit mais ça vas etre facile, et plus on avance plus on coince  
 
 

 
ça veut dire quoi ça recuit simulé ? *noob en algo* secret professionel ?  

2 minutes et quelques dès le premier coup (ce qui m'étonne vu mes performances habituelles dans ce genre de tests ).

gagné    
c'était pour montrer qu'on pouvait penser être très proche d'une solution tout en en étant très loin !
 

http://fr.wikipedia.org/wiki/Recuit_simul%C3%A9
 
En gros on positionne toutes les pièces au hasard.
On calcule une "distance" à la solution (ex.: nb de côtés qui se touchent sans être identiques => on cherche une distance nulle)
on inverse 2 pièces au hasard et on recalcule la nouvelle distance.
si c'est plus proche de 0 : on garde ces nouveaux emplacements et on recommence avec d'autres pièces.
si on s'éloigne, on revient en arrière. sauf pour un petit pourcentage (décroissant avec le temps) ou on accepte une déterioration.
 

Bonjour.
 
Pour que l'humain ait l'avantage sur l'ordinateur,
 il faudrait que le dessin final du puzzle ait une signification.
  Par exemple que les motifs représentent une lettre, un chiffre
   ou une figure géométrique.
 
Une méthode heuristique ne donne pas la solution rigoureuse,
 ou elle met plus de temps qu'ue méthode déterministe pour y arriver.
  Elle donne un resultat qui s'approche de la solution.
   L'avantage de l'ordinateur,
    c'est qu'il mémorise la meilleure solution trouvée.
 
J'ai voulu dimensionner le problème de la méthode déterministe.
Il ne faut pas refaire les mêmes tests à plusieurs endroits différents du puzzle :
 il faut faire le test une fois pour toutes, stocker les résultats,
  et passer au niveau suivant.
 
D'où la méthode déterministe suivante :
 
0) étape préliminaire : création de puzzle aléatoire de différentes dimensions
   pour la mise au point des programmes (écrits en C).
   durée : instantanée.
 
1) regroupement des pièces en carrés de 2 sur 2 (pièces 2x2 ci-après).
   on calcule toutes les pièces 2x2 possibles, on les stocke.
   Et on ne reviendra plus sur les pièces élémentaires.
   Ce qui donne un puzzle 8 sur 8 avec un nombre de pièces 2x2
    beaucoup plus grand que les 64 case du puzzle.
     De l'ordre de 1 million sur mon cas test.
   Les figures des côtés ne sont plus symétriques :
    une figure (a,b) s'associe avec une figure (b,a)
   On interdit les côtés formés d'un bord et d'une figure intérieure.
   Les pièces 2x2 dépendent de 4 pièces élémentaires que l'on sauvegarde.
   durée : 5 secondes
 
2) regroupement des carrés 2x2 en carrés 4x4
   D'où un puzzle de 4 sur 4
   Quand on place une nouvelle pièce 2x2,
    on verifie qu'elle n'a pas une pièce élémentaire commune
     avec les pièces 2x2 dejà placées
     (d'où l'utilité de mémoriser les pièces élémentaires)
 
  Et là, les associations d'un million de pièces sont beaucoup trop nombreuses
   pour être faisable sur un PC
  durée : (ordre de grandeur : 2 ou 3 ans).
 
3) regroupement des carrés 4x4 en carrés 8x8
   D'où un puzzle de 2 sur 2
   On approche de la solution :
    on ne retient que les pièces avec 2 côtés de bord et 2 côtés intérieurs.
 
4) regroupement des carrés 8x8 en un carré 16x16
 

j'ai du mal a comprendre pourquoi le regroupement permettrai de gagner du temps. le principe de base c'est quoi ?
 
 
plus la grosseur des carrés augmentera plus il y aura de possibilité, s'il y a 1millions de bloc 2x2 differents j'ose pas imaginer le nombre de 4x4, plusieurs milliards de milliards voir bcp plus...

c'est une façon de fractionner le problème ?

Bah moi je ne suis pas un informaticien de génie ni un super mathématicien, mais en ces temps où je suis coincé au boulot alors qu'il fait super beau et que tout le monde est parti, je m'occupe bien sur mon petit PC, à programmer tout simplement sous vba/Excel.  
Pour vous situer, je résous le 9*9 en 1'30, et je suis déjà très fier de moi ! Je n'ai sans aucun doute aucune chance d'aller jusqu'au bout, mais je considère tout de même mes 50 € comme bien investis.
 
PS : heuristique ? recuit ? Je ne suis pas allé assez longtemps à l'école on dirait...

un petit cout de google/wikipedia et ça te semblera bcp plus clair ^^
 
j'ai appris ce qu'était une heuristique à l'école et ça ne m'avance pas énormément

Heureusement on peut encore apprendre des choses même une fois l'école terminée
Et si tu as moyen de programmer en C plutôt qu'en vba... tu vas exploser tes records !

bon bah j'ai fait la demo en 2:37 dommage que le jeu entier est pas aussi facile, on serait tous riche

vous connaitriez pas des forum qui parle d'eternity (a part hfr ^^) ?

un seul d'entre nous (ou un seul groupe d'entre nous) sera riche    

J'ai acheté le jeu le jour de sa sortie et il trone sur la table du salon depuis. J'y passe en moyenne 2 heures par jour et je l'ai déjà foutu 2 fois en l'air en 3 semaines.... Des techniques ??? Comme la version de test est super simple si on commence du bord, j'ai voulu faire pareil pour la 256p mais c'est une strategie super mauvaise... Maintenant j'essaie d'avancer ligne par ligne mais je suis bloqué vers la moitié... Et pourtant je fais du min max manuel dessus.

http://games.groups.yahoo.com/group/eternity_two/
c'est en anglais. Et je n'ai pas encore regardé si c'était intéressant.
 

Pour trouver une solution à la main ?
- égorger tous les poulets de la Terre
- brûler tous les cierges
- etc....

 

bonjour!

(beug)bjr donc je viens aussi d'acheter ce puzzle!
je suis à moitié bloqué car je focalise sur les formes! je m'explique:est-ce que les 2 côtés doivent-être vraiment,vraiment identiques,Ou alors on ne tient compte que de la forme en général,dans ce cas une moitié contient  les 3/4 de la forme et l'autre moitié le reste! car il y a des carrés plus grands que d'autres! j'espère que quelqu'un répondra, si'l a compris!!!lol
merci d'avance

j'ai rien compris OOO
 
les deux côtés doivent être identiques :x

 
 
ouais,identiques quoi!  ms forcément il y aura des tailles différentes de formes! certains carrés sont + grands que d'autres! bref ! merci

oui certaines pieces sont mal découpés..
 
Mais ça ne veut pas dire que 2 pieces ne sont pas compatibles si elles ont le meme motif mais que leur forme est un peu "cassé" au final.

jme suis codé une modélisation de tout ca, si qq'un a des idées géniales pour l'algo qui trouve une solution rapidement qu'il me dise et on partage

pour l'algo, je voulais établir une boule fermée contenant les solutions et ensuite projetter les solutions sur un plan et choisir celle qui offre la surface minumum. Je crée les différentes solutions en associant les pieces ayant des coté qui correspondent...

j'ai l'impression que c'est pas gagné  

2min29sec, 3ème essai sur le puzzle à 16 pièces, la démo du site. (avec un peu de chance sans doute)
 

wé mais tant que t'es obligé de toiutes les parcourir (meme pour les projeter), c'est mort
 
faut trouver un moyen de couper vachement plus en amont (sauf a dire que ta projection permette d'éliminer certaines solutions dès la 10eme piece posée par ex ^^

 
Exact. Je trouve, soit-dit en passant, que pour le prix du jeu (même si je suis conscient que c'est surtout pour payer le premier prix) c'est un peu abusé  , ils auraient pu au moins couper droit.
 

 
 
Exact, sur Eternity2.net ils viennent dejà de soumettre la meilleure solution partielle qu'ils ont trouvé pour l'instant
 
462/480
 
http://eternity2.net/submission.php
 
Voila pour ceux qui ont dejà mis au point des algo, vous pouvez comparer avec votre meilleur score, pour voir à quel niveau vous vous situez par rapport à une grille de 1 Teraflop qui calcule depuis 15 jours

wé enfin il peuvent en placer autant qu'ils veulent, tant qu'ils ont pas trouvé ils sont pas plus proches de la solution que n'importe qui d'autre ^^

 
Si justement
C'est dans les règles du jeu, si personne ne trouve la bonne solution avant fin 2008, c'est celui qui a renvoyé la solution avec le plus de pièces placés qui gagne. Si 2 personnes ont trouvé la même solution, c'est celui qui l'a envoyé en premier qui gagne.
Et comparer les meilleurs scores, c'est quand même un bon moyen pour voir si vos algo tiennent la route.

bof
a la rigueur ca permet d'evaluer la puissance de calcul qui est derriere.
justement parceque on peut placer tout les pieces sauf 2 et etre plus *loin* (au sens nombre de permutation / rotations de pieces a effectuer) de la solution que quelqu'un qui a placé toutes les pieces sauf 10.

Ou en êtes-vous ? Quelqu'un a essayé de se lancer dans une recherche différente d'un simple "je pose, je retire, je repose, etc..." ? Bref d'essayer de définir une stratégie ?

Euh, question peut-être con mais est-ce que chaque boîte de jeu contient un set de pièces unique ou tout le monde à le même jeu ??

question con en effet.

Euh ok j'assume, mais la réponse est ??
 
Ca me parait logique que chaque boite soit différente, sinon pas besoin d'acheter le jeu (juste au cas ou on trouverais la solution) mais dans ce cas tout le monde ne part pas exactement avec la même base, ce qui est quand même étrange non ?

toutes les boites sont identiques

Bon... mais alors comment se fait-il qu'il n'y ait pas des dizaines de sites qui soient apparus avec la copie des pièces du jeu ? Voir divers simulateurs ou autre outils qui permettrait de tester les combinaisons sans acheter le jeu ? Surtout dans un cas comme celui-ci ou il y a de l'argent à gagner, ça me paraît impensable qu'il ne soit pas diffusé en masse sur le net, hors je viens de rechercher (rapidement certes) et pas une trace à part les multiples images promos. Ou l'éditeur est vraiment très fort pour arriver à supprimer toute copie du net, ou il y a un truc que je n'ai pas compris (ce qui doit être le cas, ok j'assume à nouveau).

quel interet de le mettre en ligne ? tu l'as payer tu veux chercher pour toi, pas qu'un autre gagne avec les info que toi tu lui a filé

Quel est l'intérêt de ceux qui mettent en ligne des cd, des films, la première traduction d'Harry Potter, des virus qui vont bousiller tes fichiers, etc... ?? Pourtant on trouve tout ça à proffusion. D'autant qu'ici il s'agit de quelques images, c'est fait en 5 sec (contrairement à traduire un bouquin...)