Mon premier Algo Genetique.

Aujourd’hui, je vous présente mon premier algorithme génétique. L’idée est de faire une IA de Snake qui apprend (tout seul) a grandir le plus possible.

Chaque Snake est composé d’une série d’instruction (Aller en haut / en bas / a gauche / a droite), chacune a exécuter en fonction d’une situation précise.

Pour l’instant les informations reçues sur l’environnement sont :

  • Nourriture vers le Haut
  • Nourriture vers le Bas
  • Nourriture vers la Droite
  • Nourriture vers la Gauche
  • Nourriture vers le Haut / Droite
  • Nourriture vers le Haut / Gauche
  • Nourriture vers le Bas / Droite
  • Nourriture vers le Bas / Gauche

Chaque information est logique (seulement 2 valeurs possibles), ce qui fait un total de 28 = 256 combinaisons possibles.

Les snakes arrivent donc a se diriger vers les pommes, mais on ne règle pas le problème du snake qui reste coincé et ne peux plus bouger.

Pour ça il faudrait lui passer en information les cases autour de lui. Mais rien que pour les 8 cases adjacentes, on arrive a

4294967295 possibilité a gérer, se qui correspond a toutes les combinaison possible de 32 informations logiques. (les 256 au dessus multipliées par 3 possibilités (case vide / snake / nourriture) * 8 cases => 38=6 561).

C’est exactement le nombre de possibilité que peux stocker un int. Le problème se pose au niveau de la string qui constitue le « patrimoine génétique » du snake, a raison d’un octet par possibilité on arrive a 4294967295 octets = 4Go + 294 Mo + 967 Ko + 295o. Même en utilisant des champs de bits (2bits suffisent a coder une instruction), ça représente plus d’un Go par string.

Sachant que je fait mes test sur 250 Snakes par plateau de jeu, mes 2Go de RAM font être vite dépassés.

Pour ce qui est des résultats avec juste les 8 les information déjà codes, ca tourne depuis plus de 16h sur mon PC de bureau (C2D 1.87GHz / 2Go RAM), mon meilleur score est un snake de 34 unités de longueur (la taille de base est 4 ).

Début de l’expérience.

Après 13h de calcul est 15 phases de mutation.

Pour ceux que ça intéresse le code est dispo : https://github.com/gheaeckkseqrz/Snake

Publicités
Cet article, publié dans Uncategorized, est tagué , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s