Discussion :

[ballerssd]

bonjour,

voila dans le cadre de mes études j'ai eu un projet à effectuer en java :
l'intelligence artificielle du jeu othello.
on nous a fourni l'interface du jeu et à nous de faire le reste.

Maintenant le projet est fini mais je cherche toujours à l'améliorer et à optimiser les traitements.

j'ai mis en place une recherche de coup possible puis une création d'un arbre N-aire avec l'élagage alpha beta, où chacun des fils à une copie de la matrice (le plateau de jeu) du père ou il est ajouté le coup possible.

la matrice en question est de taille 8x8 de type Couleur (NOIR, BLANC, VIDE).

Mon problème se porte sur la copie de cette matrice

au départ j'ai écrit ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
private Couleur[][] copyMatrice(Couleur matrice[][]){
    int tailleMatrice = matrice.length;
    Couleur matriceCopy[][] = new Couleur[tailleMatrice][tailleMatrice];
    for(int i = 0 ; i < tailleMatrice ; i ++){
        for(int j = 0 ; j < tailleMatrice ; j ++){
            matriceCopy[i][j] = matrice[i][j];
        }
    }
    return matriceCopy;
}

mais mon IDE (NetBeans 7.0) m'a dit d'utiliser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
System.arraycopy(matrice[i], 0 matriceCopy[i], 0, tailleMatrice);
 
//plutôt que ceci : 
 
for(int j = 0 ; j < tailleMatrice ; j ++){
    matriceCopy[i][j] = matrice[i][j];
}

Le tout fonctionne bien, mais avec un niveau de recherche de profondeur 5 dans mon arbre, je trouve le programme long à répondre.

C'est pourquoi j'ai utilisé l'outil de profilage intégré à NetBeans et je passe plus de 300ms dans cette fonction à chaque appel.

ce qui au bout d'un certain nombre de coup représente des secondes.

Enfin la question :

existe-t-il un moyen de copier cette matrice plus rapidement que cela ?



Merci d'avance,

Ballerssd

[Robin56]

mais mon IDE (NetBeans 7.0) m'a dit d'utiliser :

Vraiment Ton IDE te dit les optimisations possibles dans ton code ?

existe-t-il un moyen de copier cette matrice plus rapidement que cela ?

Via un tableau, je dirais non. J'ai comme principe de me dire que s'il y a une méthode dans la JVM pour faire ce que je veux, il faut mieux que je l'utilise, elle sera surement mieux testée et optimisée que la mienne.

Du coup, j'aborderais ton problème d'une autre façon en me posant les questions suivantes :
- Pourquoi dois-je copier cette matrice autant de fois ?
- Pourquoi les objets que je copie contiennent-ils autant de données ?
- ... etc

En espérant que ça t'aide.

[tchize_]

Vraiment Ton IDE te dit les optimisations possibles dans ton code ?

Ouais, on est parfois surpris des mauvaises pratiques détectées par l'IDE. Et encore plus de celles détectées par des outils comme findBugs :p

exemple, dans eclipse, si je tappe:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (Object o : maMap.valueSet()){
   //faire des trucs
}

eclipse me met un warning disant "pour parcourir un map, utilisez plutot entrySet(), qui évite la création d'un Collection temporaire"

Blague à part, oui System.arrayCopy est de loin plus performant. Car il n'effectue qu'une seule fois la vérification des limites du tableau, alors que la boucle le fait pour chaque itération. Autrement dit, si t'as 2000 entrées à copier, ta jvm va faire 2000 fois

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
if (indexDestination > tailleTableau) 
  throw new ArrayIndexOutOfBoundException()

[ballerssd]

merci de vos réponses,

Pourquoi dois-je copier cette matrice autant de fois ?

Je copie autant de fois cette matrice, car à chaque fois que je trouve un coup possible, je crée un nœud dans mon arbre.
Dans ce nœud, il y a un copie de la matrice du père, le coup à jouer.
Lors de l'instanciation de ce nœud, je positionne le pion sur la matrice et je retourne les pions capturés.
Cette copie est importante pour ne pas impacter la matrice du père voire même la matrice du plateau

Pourquoi les objets que je copie contiennent-ils autant de données ?

Il s'est avéré que toutes les données de mes nœuds sont nécessaire pour le développement de l'arbre (à un ou deux objets près).

oui System.arrayCopy est de loin plus performant.

Il n'y a donc pas de moyen plus rapide pour la copie de matrice, je vais donc être amené à changer le plateau de jeu.

Pour cela, quel type de collection vous me conseillerez (ArrayList, Vector, Map, ...) ?


merci d'avance

Ballerssd

[tchize_]

Ca ne vas pas vous avancer, toutes ces collections utilisent des tableau en backend


Êtes vous sur que c'est la copie qui vous pose problème dans votre algorithme? N'est-ce pas plutot l'algorithme en lui même qui est à revoir? Vous pouvez toujours gagner un peu de temps en utilisant un tableau à 1 dimension [tailleMatrice*tailleMatrice] pour copier l'intégralité en un seul appel, mais après faut voir la taille des données et combien de fois vous les copiez.

De plus, une matrice de jeu d'othello, ça doit pas être bien grand, c'est 64 cases, un byte par case, c'est pas la copie de 64 malheureux octets qui vont jouer sur vos perfs.

[-gma-]

Pour cela, quel type de collection vous me conseillerez (ArrayList, Vector, Map, ...) ?

Je ne crois pas que tu trouves de collection miracle pour ça, les tableaux sont généralement ce qu'il de plus efficace et la plupart des collections utilisent des tableaux en interne.

Mais puisque tes données sont déjà organisées en arbre, pourquoi ne stockes tu pas que les éléments qui ont changés dans un enfant et pour connaître les autres éléments tu demandes au parent ?

Edit: orthographe

[ballerssd]

merci pour vos réponses rapide.

Ça ne vas pas vous avancer, toutes ces collections utilisent des tableau en backend

Bon alors je n'ai rien à changer de ce coté là.
Je vais essayé de voir les optimisations possible dans mes algorithmes de recherche et de création de nœuds fils.

pourquoi ne stockes tu pas que les éléments qui ont changés dans un enfant et pour connaître les autres éléments tu demande au parent ?

Si je comprends bien tu me conseilles de n'avoir qu'un "tableau" de coup joué et et la couleur associée au pion et de ne garder que ça en mémoire et de ne plus utiliser la matrice de Couleur ?