bonjour à tous,
 
je réalise en ce moment un projet en java où un calcul d'arbre se fait, seulement l'arbre peut comporter quelques millions (voir des dizaines de millions) de noeuds qui sont numérotés et stockésdans un tableau.
au bout d'un certain nombre de noeuds calculés j'ai une exception OutOfMemoryError. le truc est visiblement trop gros pour la ram. est-ce que c'est dû au fait que le tableau soit un mauvais type de stockage ou autre chose? chose qui m'inquiète aussi le calcul est très très lent alors qu'il tourne sur un ppc g4 à 1,33 avec 768mo de mémoire vive.
 
merci

La RAM n'est pas en cause, mais plutôt la taille du heap de la JVM.
 
1. Essaye d'augmenter substantiellement le heap size de ta JVM, p.e. 256Mb ou 512MB. Ceci se fait généralement à l'aide du switch -Xmx<size> (si nécessaire, java -X t'affiche les options non standards).
 
Fais attention si tu vas au-délà, car tu vas atteindre la limite de la mémoire physique de ta machine et ça va commencer à swapper.
 
2. Vérifie que toutes les resources non utilisées sont bien désallouées.
 
3. Donne un coup de pouce au garbage collector en déréférencent les variables non utilisées dans la parite critique du code.
 
4. Après ça, essaye un System.gc() bien placé, juste pour voir si ça donne un résultat différent, s'il échet.
 
5. Limite le nombre d'objets en mémoire au minimum. Préfère des arrays et des types primitifs quand c'est possible.
 
6. Et avant tout... optimise tout ce qui est possible ! Tu pourrais avoir besoin de faire du profiling.

elle est comment ta classe Node ?
 
y a des outils pour estimer la fragmentation mémoire ?

ça commence déjà à swapper : j'atteinds les 100mo en ram et plus d'un demi giga en swap. sinon qu'est ce que tu appelles désalouer? free en c mais en java c'est quoi? sinon la classe noeud est on ne peut plus banale, avec le pere, le numéro, et les fils.
 
de plus j'ai du mal à concevoir comment un jeu d'echecs peut etre implémenter alors qu'on estime le nombre de positions possibles à 10 puissance 150, et que moi avec mes 10 puissance 7 ou 8 je peine à l'exécuter en un temps minim. j'explique, c'est un jeu que je suis en train de programmer.

ben parce qu'on calcule pas au delà de 4 ou 5.
 
PS: vive les allocateurs mémoires spécialisés

Une idée:
Tu stockes tes noeuds dans un truc style BD et tu n'accedes qu'a ceux dont tu as besoin aun moment donné.
A+,

bof, j'ai déjà tenté des trucs comme ça en python avec un module qui te fournit une table de hachage, identique au 'dict' classique, sauf que y
un fichier derrière : c'est catastrophique, et ça bouffe autant de RAM. Mieux vaut changer d'algo

Oui enfin bon, des acces ca se cache, ca se traite en lot...
Sur que si tu fais un update par noeud, ca risque pas d'etre rapide.
Là est tout l'art de la mise au point efficace quand on a des algos deja largement optimises et neanmoins gourmands.
A+,

Ca commence mal, hein.
 

Tu n'a pas l'équivalent en java, mais tu peux faire truc = null pour déréférencer. C'est supposé être un indice pour le garbage collector. Mais la garbage collection est loin d'être une science universelle et exacte, malheureusement.
 

Ca va peut-être rien résoudre et ça certainement être très moche, mais tu devrais peut-être essayer sans classe, dans la mesure du possible. Les objets en mémoire, tels que ta classe noeud, ça coûte. Je ne dis pas que ça va forcément changer qq chose, mais j'esseyerais de fortement limiter dans le cas d'espèce.    
 

Ne rêve pas : aucun programme d'echecs ne calcule toutes les possibilités 10 coups à l'avance pour obtenir naïvement le meilleur coup à jouer. Et même en se limitant à 4-5 coups, toutes les branches ne sont pas systématiquement évaluée. Sinon, Deep Junior & co auraient déjà mis la patée à Kramnik et à Kasparov depuis longtemps.
 
 
Je cruserais sérieusement du côté des optimisations du code avant de chercher à pousser la JVM dans ses derniers retranchements.

Ca c'est une bonne question.
 

Certainement, mais une JVM conçue sainement ne devrait pas se retrouver à cours mémoire sous prétexte que le heap serait fragmenté. Que cela ait comme conséquence une gestion moins efficace et une tendance à bouffer plus rapidement la place allouée, oui. Que cela force le GC à passer un solide coup de balai, quitte à lagger un bon coup, passe encore. Mais de là à jeter l'éponge, je dis non.    

 
Parce que tu ne peux pas calculer toutes les branches possibles (tu imagines ton programme te dire au début de la parie : 'toi mon bonhomme, je te met mat en 57 coups  '), même 7 ou 8 c'est énorme (ça a déjà du être dit).
Il faut que tu developpes une fonction dite d'"Heuristique" si je me souviens bien, qui va évaluer "en l'état" une position, tu l'utilise quand tu arrive à la limite (que tu aura choisi) de profondeur de recherche dans l'arbre.
Tu peux prendre en compte des choses comme le nombre de pièces/pions (avec des valeurs genre Dame=10, Tour=6, Fou=4, Cavalier=3, Pion=1), en prenant aussi en compte les pions risquants d'aller à dame, pièces clouées, roi en échec, lignes ouvertes devant le roi, pions liés (situé sur deux colonnes contigues) mieux que pions alignés sur la meme colonnes, etc...  
 

ce n'est pas un jeux intelligent pour calculer une heuristique, le but du projet, qui reconnaissons le est nullissime mais essentiel pour booster la note, est de calculer à partir de l'arbre créé une stratégie gagnante.
donc pour calculer une stratégie il faut monter d'en bas, donc parcourir l'arbre à partir de toutes les feuilles jusqu'au sommet.  
 
ce n'est pas un jeux d'echec les gars, je n'ai pas encore atteint ce niveau en plus c'est un projet d'algorithmique et non d'ia.
 
edit : j'explique ce que fait le programme, il calcule les noeud et les stock dans un vecteur, à la fin je crées un tableau donc la taille est celle du vecteur et je transfere les élément du vecteurs vers le tableau pour facilité l'accès aux objets. le truc c'est que lors du calcul des noeud la mémoire clamse et le prog fait la gueule. je précise que l'initialisation du tableau se fait après que le vecteur ne soit complet, donc quand le programme s'arrête le tableau n'est même pas initialisé. seul le vecteur ou une partie du vecteur du moins est en mémoire.

 
Ah oki, c'est quoi comme jeu si c'est pas indiscret ? il n'y en a pas tant que ça où on peut se permettre de descendre jusqu'aux feuilles sans heuristique... C'est un jeu avec adversaire ou la résolution de quelque chose du genre Taquin ou Pentaminos ? T'es sur que ton programme ne boucle pas en répétant des positions ?

c'est un jeu qui s'appelle chocobar, qui consiste en une tablette de chocolat (donc matrice) où chaque joueur mange un carré quand c'est son tour de jouer, quand tu mange un carré tu prends avec tous ceux qui sont à sa droite et en dessous. donc si tu as une latrice de 3x3 et que tu mange le 1,1, tu prends avec le 1,2 le 2,1 et le 2,2. le but est de ne pas manger le carré 0,0 sinon il peut t'arriver de graves problèmes de santé. pour cela il faut forczer l'adversaire à manger le carré 0,0.
l'heuristique sert à estimer plus qu'autre chose, tu n'es jamais certain de gagner avec. sinon une stratégie gagante calcule un chemin UNIQUE du sommet à une feuille ou l'adversaire s'empoisonne
 
le programme consiste donc à faire une construction de l'arbre en profondeur, c'est à dire de créer le sommet, et d'appeler la fonction create récursivement.
 
create(Sommet s) {
   bla bla bla
   créer le fils t;
   create(t);
}

Je vais peut-être dire une connerie, mais bon...
 
10 puissance 8 = 100 000 000.
Rien qu'un pointeur 32bit par noeud ça nous fait : 400 000 000 = 381 Mo
Plus un pointeur pour le père, 2 pour les fils, on arrive à : 1.49 Go...
 
Bref, t'as plus qu'à trouver un autre moyen pour calculer ta stratégie.

je n'utilise pas de pointeur pour les pères/fils, j'ai fait en sorte que le numéro du noeud soit l'indice de sa position dans le tableau, le père et les fils sont donc de simples numéros

 
Bon, écoute, ton problème est hyper connu : c'est le principe du jeu des allumettes qui est :
Tu as un tas de X allumettes, chacun (toi et l'adversaire) a tour de role doit retirer entre une ou trois allumettes. Celui qui retire la dernière a perdu.
Un problème comme celui la met en avant direct l'application du "minimax". En gros dans ton prog tu fixes une bonne constante : il s'agira de la profondeur d'exploration maximale de ton arbre. Ainsi tu crees tout l'arbre de solution jusqu'à la profondeur X (X=constante). Ensuite tu evalues TOUTES les feuilles de la profondeur X. Dans ton exo, evaluer signifie juste dire "j'ai perdu" (I) ou bien "j'ai pas perdu" (II) ou bien "j'ai gagné" (III). A partir de la, tu fais remonter l'information dans l'arbre intelligemment. C'est a dire qu'a la profondeur 0, c'est le plateau a partir duquel tu es exposé (vient du coup joué de l'adversaire), ensuite les noeuds se trouvant en profondeur 1 sont les coups que tu peux jouer, ensuite en profondeur 2 sont les coups que ton adversaire peux jouer ... et ainsi de suite jusqu'a la profondeur X.
deux cas à distinguer :
- Les noeuds de profondeur X sont les coups joués par l'adversaire : donc trois etats possibles : ou bien des noeuds valent l'état (I) dans ce cas le noeud parent est satisfaisant pour toi (a garder). Si etat (II), on ne peut rien dire. Si etat (III), tu oublies le noeud parent (en gros il ne faudra pas prendre les chemins d'arbre qui passent par ce noeud !.
- Les noeuds de profondeur X sont les coups joués par toi, dans ce cas le raisonnement a faire est l'inverse du 1er cas.
 
Une fois que tu as fais remonter l'information, les noeuds de profondeur 1 (les coups que tu peux jouer) tu pourra voir les coups "banni" qui te font perdre ! donc ce seront des noeuds a ne pas prendre...et tu prendra alors les noeuds qui ne te font pas perdre (ou bien qui te feront gagné ou bien qui t'amenent a un etat "j'ai pas perdu".
 
Bon voila c'est pas plus complique. Il existe plein d'algo sur le "minimax". Sache que c l'algo utilisé a la base de tous jeu avec un adversaire (comme le jeu d'echec Deep Blue qui a battu kasparov) ... normal c'est un algo qui calcul les coups a l'avance en fait pour voir les meilleurs coups a jouer et les pires coups a ne pas jouer. Bon ensuite il y a toujours moyen de l'ameliorer avec notamment l'algo "elagage alpha beta" qui te coupe des branches dans ton arbre (comme par exemple si le fils d'un noeud est perdant, ca ne sert a rien d'aller parcourir les autres fils de ce noeud), tu gagneras en rapidité.