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 ?

[-gma-]

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 ?

Quelque chose de cet ordre là. Mais l'impact sur le temps d'exécution dépendra de comment (et avec qu'elle fréquence) tu utilises tes matrices et de leur taille aussi. Au lieu de regarder la Couleur dans la matrice aux coordonnées (i,j), tu regarde si le coup a été joué à partir ou vers (i,j) et en fonction de la réponse et de l'état de (i,j) dans le parent tu en déduis la Couleur.

Ca devrait accélérer la construction de ton arbre puisque tu n'auras plus toute la matrice à copier, en contrepartie le parcours de l'arbre sera peut être sensiblement plus long mais généralement le temps de lecture des données est très inférieur au temps d'écriture. Encore une fois ça dépend du reste de l'algo, donc je ne peux que te le suggérer

[Logan Mauzaize]

Un arbre de décision ne devrait comporter que les coups joués (voir les exemples de notation aux échecs).

Pour simplifier(optimiser) la représentation du plateau après "simulation" de n-coups, il est possible de créer une matrice de Case plutôt que de Couleur. Chaque case permettant de stocker une couleur et les décisions/éventualités/simulation de coups.

[ballerssd]

Quelque chose de cet ordre là. Mais l'impact sur le temps d'exécution dépendra de comment (et avec qu'elle fréquence) tu utilises tes matrices et de leur taille aussi. Au lieu de regarder la Couleur dans la matrice aux coordonnées (i,j), tu regarde si le coup a été joué à partir ou vers (i,j) et en fonction de la réponse et de l'état de (i,j) dans le parent tu en déduis la Couleur.

pour le moment ça me parait encore abstrait, mais j'y réfléchirai à tête reposée.

Pour simplifier(optimiser) la représentation du plateau après "simulation" de n-coups, il est possible de créer une matrice de Case plutôt que de Couleur. Chaque case permettant de stocker une couleur et les décisions/éventualités/simulation de coups.

Avec cette solution, je pense que cela reviendrai au même, car même si dans une seule case du plateau je stocke la couleur, et le(s) coup(s) possible(s), il faudra bien que je développe plus loin et que je copie cette matrice de Case.


Je vous remercie d'avoir répondu à ma question.

Pas que je ne veuille pas continuer sur cette conversation là mais ce n'est plus dans le cadre du sujet original, je vais appliquer le tag et si j'ai de nouveau besoin d'aide, je rouvrirai un sujet.

Merci encore, bonne continuation.

Ballerssd

[Logan Mauzaize]

Avec cette solution, je pense que cela reviendrai au même, car même si dans une seule case du plateau je stocke la couleur, et le(s) coup(s) possible(s), il faudra bien que je développe plus loin et que je copie cette matrice de Case.

Non tu ne copies pas la matrice justement. Chaque case stocke ses éventualités (une liste triée comme les feuilles d'un B-Tree). Les cases non-sollicitée prennent toujours autant de place et tu ne stockes qu'une information par éventualité.
Dans ton cas tu copiais la matrice pour chaque éventualité.

L'arbre des éventualités d'une case devrait présenter qu'une branche par changement et pour trouver la valeur de la case lors d'une itération il faudrait identifier chaque embranchement de l'arbre de décision (ex : On part de l'état 0, on a 3 éventualités, on a donc les état { "0", "0.0", "0.1", "0.2" }.
La case associée à "0.0" voit sa lister devenir ["0" => B, "0.0" => N]
Disons qu'à l'itération suivante cette case est également sollicité par "0.1" => [ "0" => B, "0.0" => N, "0.1.0" => N ]
On arrive par exemple aux éventualités suivantes pour une case [ "0" => B, "0.0" => N, "0.1.0" => N, "0.1.0.1" => B, "0.2.0.1" => N, "0.2.1" => N, "0.2.1.0" => B]
A partir de cette liste et d'une simple recherche binaire, je peux donner l'état de la case pour les différents éventualités

|                                                                                                           0                                                                                                           |
|                                                                                                           B                                                                                                           |
|                                  0.0                                  |                                  0.1                                  |                                  0.2                                  |
|                                   N                                   |                                   B                                   |                                   B                                   |
|         0.0.0         |         0.0.1         |         0.0.2         |         0.1.0         |         0.1.1         |         0.1.2         |         0.2.0         |         0.2.1         |         0.2.2         |
|           N           |           N           |           N           |           N           |           B           |           B           |           B           |           N           |           B           |
|0.0.0.0|0.0.0.1|0.0.0.2|0.0.1.0|0.0.1.1|0.0.1.2|0.0.2.0|0.0.2.1|0.0.2.2|0.1.0.0|0.1.0.1|0.1.0.2|0.1.1.0|0.1.1.1|0.1.1.2|0.1.2.0|0.1.2.1|0.1.2.2|0.2.0.0|0.2.0.1|0.2.0.2|0.2.1.0|0.2.1.1|0.2.1.2|0.2.2.0|0.2.2.1|0.2.2.2|
|   N   |   N   |   N   |   N   |   N   |   N   |   N   |   N   |   N   |   N   |   B   |   N   |   B   |   B   |   B   |   B   |   B   |   B   |   B   |   N   |   B   |   B   |   N   |   N   |   B   |   B   |   B   |