Inversion du jeu de la vie

[Coban]

Bonjour,
Je pense que vous connaissez un peu le jeu de la vie. Sinon, en voici la définition:
-c'est un automate cellulaire composé de cellules carrées
-chaque cellule peut être vivante ou morte
-à chaque tour: pour rester en vie, une cellule vivante doit être entourée de 2 ou 3 cellules vivantes, sinon elle meurt
pour naître, une cellule morte doit être entourée de 3 cellules vivantes, sinon elle reste morte

Auriez vous une idée pour inverser le temps dans le jeu de la vie?
C'est à dire trouver les antécédents d'une certaine configuration.
Merci de vos réponses.
-----

[whoami]

Bonjour,

C'est impossible.

Exemple :

- une seule cellule vivante
- un tour ==> elle meurt
- donc désormais terrain vide.

- Et il est absolument impossible de revenir à l'état initial.

[Coban]

Non, je ne parle pas d'inverser le temps en gardant les mêmes règles, je cherche un algorithme permettant de trouver les figures antécédentes d'une certaine figure donnée.

[invite765732342432]

Non, je ne parle pas d'inverser le temps en gardant les mêmes règles, je cherche un algorithme permettant de trouver les figures antécédentes d'une certaine figure donnée.

whoami a donné le meilleur exemple possible: tu as un plateau vide, il existe de très nombreux plateaux qui donnent ce résultat.
L'algorithme capable de remonter le temps sera excessivement lent et peu précis dès que la zone de travail est un peu étendue.

[A voir en vidéo sur Futura]

[Coban]

Peut importe qu'il soit lent, n’essaye pas de me décourager, je sais qu'il existe une quantité énorme d’antécédents à partir du moment où la grille atteint une certaine taille.
Ce que je cherche, c'est l'algorithme, les problèmes de performance ne m'intéressent pas pour l'instant.

[invite765732342432]

Peut importe qu'il soit lent, n’essaye pas de me décourager, je sais qu'il existe une quantité énorme d’antécédents à partir du moment où la grille atteint une certaine taille.
Ce que je cherche, c'est l'algorithme, les problèmes de performance ne m'intéressent pas pour l'instant.

Je m'en voudrais de te décourager... mais j'ai peur que tu le sois déjà, car l'algorithme fournissant toutes les possibilités sans contraite de temps prend juste quelques minutes à faire.

Je te souhaite donc bon courage, ce qui semble être la seule chose qu'il te manque pour résoudre ce petit problème.

[Coban]

Non, Non, je ne veux pas non plus cherchez toutes les combinaisons possibles et les tester!!!
Il faudrait un algo un minimum intelligent histoire que l'intervalle entre deux générations se compte quand même en secondes où en minutes.
Pas d'idée?

[kwariz]

bonsoir,

par simple curiosité, quelle serait selon toi une réponse donnée par "un algorithme un minimum intelligent" si on lui donne une grille vide de m sur n cellules ?
Si tu arrives à répondre à cette question, alors tu aura une ébauche d'idée pour créer l'algorithme, mais je parie que cette ébauche ne fonctionnera plus dans de nombreux autre cas ...
Les contraintes sont insuffisantes pour pouvoir donner quoi que ce soit de correct qui puisse correspondre à une réponse.

[Coban]

Qu’appelles tu "les contraintes"?
A partir d'une grille vide, l'algo devrais trouver tous les antécédents possibles, c'est à dire toutes figures qui, au tour suivant meurent complètement. Ensuite, il en prend une au hasard.
On est obligé de faire intervenir le hasard dans un jeu de la vie inversé puisqu'il y a plusieurs effets à une cause; c'est comme en physique quantique.

[bzh_nicolas]

Non, Non, je ne veux pas non plus cherchez toutes les combinaisons possibles et les tester!!!
Il faudrait un algo un minimum intelligent histoire que l'intervalle entre deux générations se compte quand même en secondes où en minutes.
Pas d'idée?

A première vue, tu n'as pas d'autre choix que de sortir toutes les solutions possibles mais tu ne pourras pas pour autant dire laquelle à amener à la situation actuelle.
Un exemple simple :
Sur une grille 2x2 : '.' est une cellule morte, 'x' est une cellule vivante)
tour n

. .
. .

tour n-1

. .
. .

ou

. x
. .

ou

x .
.  .

ou

. .
x .

ou

. .
. x

ou

. x
x .

ou

x .
. x

Et j'en oublie peut-être, et tu n'as aucun moyen de déterminer le cas précédent.

[Coban]

Oui, il n'y a pas un seul cas précédent, il y en a plusieurs. C'est justement ce que je cherche. Imagine que ma grille face 100*100 cellules, je ne peux pas chercher toutes les configuratios possibles et vérifier ensuite lesquelles donnent vie à la figure de base.

[whoami]

Bonjour,

Je répète : c'est strictement impossible, sauf à TOUT calculer, et encore, je n'en suis pas sûr.

Exemple : comment décider de la bonne solution ayant pu conduire à celle que tu traites ? Car il faudra toujours tenir compte de toutes les cellules ayant disparu sans laisser de traces (cellule isolée, ou couple de cellules isolées...).

[Coban]

Je crois que vous ne saisissez pas exactement ce que je cherche.
Je sais très bien qu'il y a plusieurs antécédents à une figure.
Je ne veux pas savoir lequel précédait exactement la figure, je veux trouver tous ses antécédents possibles.

[kwariz]

Qu’appelles tu "les contraintes"?
A partir d'une grille vide, l'algo devrais trouver tous les antécédents possibles, c'est à dire toutes figures qui, au tour suivant meurent complètement. Ensuite, il en prend une au hasard.
On est obligé de faire intervenir le hasard dans un jeu de la vie inversé puisqu'il y a plusieurs effets à une cause; c'est comme en physique quantique.

Disons que la contrainte que tu poses : "un algorithme minimum intelligent pour trouver un antécedant" est trop vague pour pouvoir être implémentée, minimum intelligent dépend des tes attentes et n'est pas programmable.
Le sujet reste intéressant, on peut essayer d'autres contraintes comme «trouver un antécédant tel que le nombre de cellules mourantes soit minimum», ce qui est un problème très difficile. De plus tu peux pour une configuration ne pas avoir d'antécédant, qu'attends-tu de ton algorithme dans ce cas ?
Si tu désires construire un antécédant s'il existe, le meilleur moyen pour comprendre comment il faut faire est de prendre du papier quadrillé, un crayon de papier et de teste à la main comment tu peux construire un antécédant, si tu arrives à automatiser tes actions alors on pourra éventuellement discuter d'une approche algorithmique.
Tu peux aussi te restreindre à des grilles de 6x5 pour lesquelles il a été prouvé qu'un antécédant existe pour toute configuration. Une grille de 6x5 fait 2³⁰ configurations possibles ce qui fait que dans une certaine mesure créer un graphe de toutes les configurations avec leurs transitions reste envisageable du moins accessible.

[kwariz]

Je crois que vous ne saisissez pas exactement ce que je cherche.
Je sais très bien qu'il y a plusieurs antécédents à une figure.
Je ne veux pas savoir lequel précédait exactement la figure, je veux trouver tous ses antécédents possibles.

Il n'existe pas, à ma connaissance, de moyen simple pour construire la liste (éventuellement vide) de tous les prédesseurs d'une configuration particlulières, sauf à vérifier quelles configurations parmi toutes les configurations ont pour successeurs la configuration donnée.

[Deedee81]

Salut,

Il n'existe pas, à ma connaissance, de moyen simple pour construire la liste (éventuellement vide) de tous les prédesseurs d'une configuration particlulières, sauf à vérifier quelles configurations parmi toutes les configurations ont pour successeurs la configuration donnée.

Si mon nez ne me trompe pas, la recherche des configurations valide sent le problème NP-complet à plein nez.

Et pour une grille d'une taille un tant soit peu intéressante, il risque d'y avoir des millions de configurations précédentes valides (encore plus si on considère toutes les configurations pour le calcul, 2^(nxm), c'est colossal, gigantesque).

[bzh_nicolas]

Oui, il n'y a pas un seul cas précédent, il y en a plusieurs. C'est justement ce que je cherche. Imagine que ma grille face 100*100 cellules, je ne peux pas chercher toutes les configuratios possibles et vérifier ensuite lesquelles donnent vie à la figure de base.

L'"algo" que j'ai utilisé pour obtenir le résultat de mon algo précédent :

pour chaque cellule
  lister toutes les possibilités qui ont pu mener à son état actuel

éliminer les grilles contenant des éléments "en conflit"

Il parait "intelligent" (modestie quant tu nous tiens ) mais :

par exemple
tour n

. .
. .

tour n-1
pour la cellule en haut à gauche

. x
. x

est une configuration valide. Mais ça ne fonctionne pas avec les 2 à droite.

Tu devrais pouvoir trouver tous les tests à faire pour "valider" une grille.
Ensuite tu pourras calculer le nombre d'opération à faire pour une grille de taille donnée.
Au final, je ne suis pas certain que lister toutes les possibilités et voir lesquelles sont OK représente moins de calculs. C'est peut-être ça l'algo intelligent.

[Coban]

Oui, je pense que ça peut être une bonne piste.
Je vais réfléchir à un moyen d'éliminer les éléments en conflit.
C'est forcement plus rapide que la méthode "trier toutes les possibilités":
sur un grille de 100*100, on a 2^100000 possibilités...

[bzh_nicolas]

Oui, je pense que ça peut être une bonne piste.
Je vais réfléchir à un moyen d'éliminer les éléments en conflit.
C'est forcement plus rapide que la méthode "trier toutes les possibilités":
sur un grille de 100*100, on a 2^100000 possibilités...

Et bien ça ne me parait pas si évident que ça. Surtout si tu veux retourner plusieurs grilles en arrière. Il pourrait être intéressant de calculer une fois pour toute, toutes les grilles possibles puis de te contenter ensuite de vérifier laquelle est une réponse valable.
Ca fait énormément de calcul au départ (d'autant plus que tes grilles seront grandes), mais ensuite pour valider les grilles n-1, il suffira d'exécuter un tour du jeu de la vie sur chaque grille précédemment calculée et de vérifier l'égalité avec n. Mais quel que soit la méthode, tu vas vite arriver (comme l'a dit Deedee81) à une complexité de calculs énormes (avec les problèmes de temps d'exécution et de mémoire qui vont avec).

[whoami]

Bonjour,

Oui, c'est pour ça que j'ai affirmé que c'était impossible, car je ne m'occupais que de ce qui est effectivement réalisable.

@ bzh_nicolas : ce que tu proposes est impossible en pratique, car le "Ca fait énormément de calcul au départ" est vraiment hors de portée pratique (amuse-toi à déjà le faire pour pour une petite grille, disons 10*10...).

[Coban]

Je cois que j'ai une autre idée peut être plus réalisable:

-pour chaque cellule:
-on cherche les nombres de cellules voisines au tour précédant (2 ou 3 si la cellule est vivante, 0;1;4;5;6;7;8;9 si la cellule est morte)
-on résout une sorte d’"équation" de manière à ce que toutes les cellules aient leur bon nombre de voisines.
-Si l'équation n'a pas de solution alors notre figure est un Jardins d’Éden.

[bzh_nicolas]

Je cois que j'ai une autre idée peut être plus réalisable:

-on résout une sorte d’"équation" de manière à ce que toutes les cellules aient leur bon nombre de voisines.

Tout le problème de cet algo est là.

[bzh_nicolas]

Bonjour,

Oui, c'est pour ça que j'ai affirmé que c'était impossible, car je ne m'occupais que de ce qui est effectivement réalisable.

@ bzh_nicolas : ce que tu proposes est impossible en pratique, car le "Ca fait énormément de calcul au départ" est vraiment hors de portée pratique (amuse-toi à déjà le faire pour pour une petite grille, disons 10*10...).

C'est pas faux j'avais pas chiffré... On a un super-calculateur, un cluster de serveurs ou BOINC pour résoudre le problème ?

[Coban]

Non, on a rien de tout ça....
Juste un pc.