programmes aléatoirs en brainfuck

Le programme d' IA que j'ai fait est tout ce qu'il y a de plus "basique" en intelligence évolutive: je crée aléatoirement un programme en brainfuck, je teste si le programme permet d'atteindre le but de l' IA (ici se déplacer sur une "grille" pour ramasser de la nourriture). Le programme reste tant qu'il arrive à ramasser assez de nourriture, quand il n'a plus de nourriture il meurt et cède sa place à un autre programme, codé lui aussi aléatoirement sans lien avec le précedent.

-Le brainfuck: ce langage est très peu utilisé car il est très difficile à programmer par un être humain, et il est aussi difficile à comprendre. Par contre il est très facile de générer aléatoirement des programmes en brainfuck car sa syntaxe est très simple : la seule règle étant de refermer les paranthèses. Pour plus de détail voir : http://fr.wikipedia.org/wiki/Brainfuck

-Voilà les fonctions que j'utilise pour interpréter le brainfuck, elle prend en entrée un tableau dont on peut définir au préalable la taille, les valeurs du tableau sont comprises entre 0 et un nombreMax que l'on peut également définir. Ici j'impose au programme d'arrêter sa lecture du programme au bout d'une seconde car mon génerateur de code aléatoire de brainfuck génère très souvent des boucles infinies.

#include <vector>
#include <iostream>
#include <time.h>
using namespace std;

long maxi=200000, taille=1000;


class ruban {
vector <long> memoire;
long pointeur;
public:
const static long constTailleMemoire=300000;
const static long constNombreMax=1000000;
long tailleMemoire;
long nombreMax;
ruban(long max=constNombreMax, long taille=constTailleMemoire) {
tailleMemoire=taille;
nombreMax=max;
memoire.resize(tailleMemoire);
pointeur=0;
}
~ruban() {memoire.resize(0);}
void droite() {++pointeur; if(pointeur>=tailleMemoire) pointeur=0; }
void gauche() {--pointeur; if(pointeur<0) pointeur=tailleMemoire-1; }
void increm() {++memoire[pointeur]; if(memoire[pointeur]>=nombreMax) memoire[pointeur]=0; }
void decrem() {--memoire[pointeur]; if(memoire[pointeur]<0) memoire[pointeur]=nombreMax-1; }
void ecrire(long donnee) {memoire[pointeur]=donnee;}
long lire() {return memoire[pointeur];}
bool nul() { return !memoire[pointeur]; }

};

vector<long> BF_evaluer(string commande, int tailleResultat, vector<long> parametres)
{
time_t debut=time(NULL);
time_t actuel=time(NULL);

ruban mem(maxi,taille);
long i=0, longueur=commande.size();
vector <long> boucle;

int tailleParametre=parametres.size();
for(int j=0; j<=tailleParametre-1; j++)
{
mem.ecrire(parametres.at(j));
mem.droite();
}

while (i<longueur && difftime(actuel, debut)<1) {
actuel=time(NULL);
switch (commande[i]) {
case '+' : case 'p' : mem.increm(); break;
case '-' : case 'm' : mem.decrem(); break;
case '>' : case 'd' : mem.droite(); break;
case '<' : case 'g' : mem.gauche(); break;
case ']' :
if(boucle.size()==0)
{
cout << "ERREUR : manque debut de boucle" <<endl;
i=longueur;
break;
}
else if(!mem.nul())
{
i=boucle[boucle.size()-1];
}
else boucle.pop_back(); break;
case '[' :
if(mem.nul()) { //faut aller au prochain ']'
long depth=1;
do {
switch(commande[++i]) {
case '[': ++depth;
case ']': --depth;
}
} while(depth);
}
else{
boucle.push_back(i);
}
break;
default: ;
}
++i;
}

vector<long> resultat;
for(int j=0; j<=tailleResultat-1; j++)
{
resultat.push_back(mem.lire());
mem.gauche();
}
return resultat;
}












-Voici maintenant le générateur aléatoire de brainfuck.


#include <stdlib.h>
#include <time.h>
#include <iostream.h>
#include <string>
using namespace std;

int reste(int a, int b)
{
int resultat=a;
while(resultat<0 || resultat>=b)
{
if(resultat<0) resultat+=b;
if(resultat>=b)resultat-=b;
}
return resultat;
}

string codeAleatoire(int indiceDeLongueur=5)
{
string resultat;
srand(time(NULL));
int boutDeCode;
int hauteurParenthesique=0;
int onContinue;
do
{
boutDeCode=(reste(rand(),6));
switch (boutDeCode)
{
case 0:
resultat.append("<");
break;
case 1:
resultat.append(">");
break;
case 2:
resultat.append("-");
break;
case 3:
resultat.append("+");
break;
case 4:
resultat.append("[");
hauteurParenthesique++;
break;
case 5:
if(hauteurParenthesique>0)
{
resultat.append("]");
hauteurParenthesique--;
}
}
onContinue=reste(rand(),indiceDeLongueur);
}
while(onContinue!=0 || hauteurParenthesique!=0);

return resultat;
}

j'trouve ca original

2,3 details:
-les indentations aident un peu à la lecture du code :p

-reste(a, b) => a%b mais j'suis pas sur que ca marche avec des nombres negatifs

-sinon la ca risque de pas mal depasser l'indiceDeLongueur si jamais il y a plusieur '[' d'apres ce que j'ai pu comprendre du code, mais bon ca a pas tellement d'importance.

sinon un gros probleme d'apres moi:
"codé lui aussi aléatoirement sans lien avec le précedent."
du coup c'est beaucoup moins evolutif lol, enfin ca fait une recherche aleatoire de solution quoi, le probleme c'est qu'il faudrait que les solutions futures aient une chance plus grande que les precedentes d'etre bien

sinon c'est super pratique pour creer des fonctions aleatoire.

-Pour les indentations je suis tout à fait d'accord. En fait le texte que j'ai copié est indenté mais j'ai l'impression que le forum supprime les doubles espaces.
-Pour le reste, c'est effectivement avec les nombres négatifs que j'avais un problème. (-7)%(3) me donnait -1 si je me souviens bien. Alors que j'attends 2.

-L'indice de longueur est là pour qu'on puisse régler la longueur moyenne du programme. Mais effectivement, en prenant un indice de longueur de 5, j'ai eu des programmes de quelques dizaines de lignes. Un des programmes les plus concluants que j'ai eu dépasse les 600 lignes!

-Par rapport au fait qu'il n'est pas évolutionniste, c'est vrai, c'est le gros problème de mon programme. En fait par "évolutif" je voulais dire que le meilleur programme est sélectionné par la sélection naturelle. Mais on peu difficilement faire évoluer un programme en brainfuck: si on change ne serait-ce qu'un '>' le résultat sera totalement différent.

Dans l'état actuel des choses, ce n'est pas du tout la solution optimum pour qu'une IA s'adapte à son environnement. Par contre on pourrait imaginer une IA composée de nombreux sous-programme. Ces sous-programmes serait écrit aléatoirement de la même manière que ce que j'ai fait. Par contre d'une génération à l'autre, certains sous-programmes sont gardés, d'autres sont reprogrammé comme ça, il ne restera que les sous-programmes vraiment efficaces.