Discussion :

[Amnael]

Bonsoir à tous, je viens vous voir, non pas pour un problème de code en soit, plutôt pour une réflexion.


J'ai une structure d'arraylist, dont chaque membre est également une array list.

Bon, une array list d'array list, vous allez me dire c'est pas immense.

Oui mais voilà, étant donné le traitement que je réalisé, je suis quasiment obligé pour mettre ces listes à jour de parcourir la totalité des éléments après chaque instructions.
Sa commence donc à devenir un peu volumineux tout ça^^


Par exemple, j'ai voulu faire jouer une partie entièrement aléatoire à mon IA. Pour une taille de plateau de 9x9.
La génération de la partie entière a pris environ 5 secondes.


Je trouve ce temps de 5 secondes pour générer une seule partie aléatoire relativement énorme.
Le but de l'ia ça sera quand même de jouer des centaines de parties aléatoire pour choisir le meilleur coup. Hors je me rends compte que je ne vais pas pouvoir en faire autant que je voudrais à cause de cette contraintes temporelle.

Du coup, je me demandais s'il y avait des astuces pour améliorer le temps de parcours d'une array list. je ne peux pas simplement ignorer des éléments, je suis obligé de tous les regarder à chaque fois.
Après je suis conscient d'être sur un ordi portable, de tourner seulement en 32 bits et que je n'aurais pas des performances extra...mais le but de mon projet est d'essayer de faire tourner une IA potable pour un jeu de Go, et sans améliorer le temps d'exécution cela me semble être mission impossible.

[eulbobo]

L'ArrayList fait partie des implémentations les plus performantes en terme de parcours, donc je pense que ton problème vient d'ailleurs (parce que 5 secondes pour parcourir un tableau 9x9, y'a un soucis)

Si tu as le code de parcours, on pourra te dire ce qui cloche. Le problème vient peut-être du côté "aléatoire"...

[thelvin]

Apparemment les 5 secondes c'est pour jouer une partie entière, avec notamment détection des coups illégaux, des prises et de la fin de partie.
Ça fait beaucoup de parcours, déjà, et ça peut facilement prendre du temps sans une détection bien programmée.

En tout cas il n'y a pas d'astuce du genre "parcourir plus vite" mais plutôt du genre "ne pas avoir besoin de parcourir."

[Amnael]

Oui les cinq secondes sont bien pour la partie entière.

Et effectivement le jeu de go a des règles assez simples mais pour que tout soit bien à jour on est obligé de faire des vérification en permanence.


Après, peut être que le problème vient finalement de l'aléatoire...à chaque coup généré je dois m'assurer qu'il est valide, mais plus je m'approche de la fin de la partie et plus il est probable que je tape des coups déjà joués ou des coups illégaux.
Je pourrais tenté de biaiser cela, mais je risque de sortir du contexte monte carlo à ce moment là.


SI j'ai bien compris je devrais plutôt chercher des cas dans lesquels refaire tout mes parcours n'est pas utile.

Par exemple détecter la fin de la partie lors du premier coup joué ça sert à rien, c'est aussi très rapide remarque, mais si je peux généraliser une valeur minimale ça pourrait réduire le nombre de parcours inutile surement.


Bon en tout cas merci pour vos réponse.