Comment effectuer une rotation de matrice à deux dimensions ?

Bonjour à tous,

Je rencontre un problème dans un projet que j'ai à faire en java.

Ce projet consiste à créer un puissance4 en java (sans interface graphique, tout est affiché en console) et un des modes de jeu permet de faire une rotation de la grille de jeu soit à droite, soit à gauche.

Le problème c'est que je visualise à peu près comment je dois m'y prendre pour tourner la matrice de caractère mais je ne suis pas capable de le coder...
Pourriez-vous m'aider svp ?

J'aimerais une réponse le plus rapidement possible svp, car je dois rendre ce projet le 6/01/2016 et il me reste la rotation et le mode joueur vs pc à faire.

Merci de vos futurs réponses
MrghURss

Salut,

Si tu vois comment le faire, je ne vois pas très bien où est ton problème pour le coder. Il s'agit juste de changer la position d'élements dans un tableau, en parcourant le tableau d'origine et en créant un tableau copie (attention à l'inversion des abscisses pour la rotation à gauche, et des ordonnées pour celle à droite). Quel est ton algorithme ? Quelle partie n'arrive-tu pas à traduire en Java ?

J'avais commencé ce sous programme :

Code:

---

1 2 3 4 5 6 7 8 9 10

public static char [][] RotationGauche (char [][] grilleJeu){ char [][] grilleRotation; grilleRotation = new char [7][7] ; for (int i=0; i<=6; i++) { for ( int j=0 ; j<=6; j++) { grilleRotation [i][j] = grilleJeu [j][i]; } } return grilleRotation; }

---

Il s’avère que cette rotation "marche", mais l'ordre des caractère n'est pas le bon et je n'y arrive pas pour la rotation de droite.
(désolé pour la mise en page pas très lisible)

J'ai finalement, avec un peu de réflexion réussi à faire les deux sous programmes qui marchent.
Les voici : http://pastebin.com/e04m5G5a

Pourrais-tu me dire ce que tu en pense stp ?

Déjà, en toute logique, j'écrirais grilleRotation [fx(i)][fy(j)] = grilleJeu [i][j];, où fx(x) et fy(x) sont des fonctions (plutôt que ce que tu as écrit : grilleRotation [i][j] = grilleJeu [fx(i)][fy(j)];). Cela me semble plus simple de raisonner dans ce sens, mais ça ne change pas grand chose en réalité (juste un échange entre les notions d'abscisses et d'ordonnées).

Tu constates en affichant la matrice résultat que l'ordre n'est pas bon. Donc, tu dois constater qu'il n'est pas bon seulement sur un axe (les abscisses, ou les ordonnées, selon la rotation à gauche ou à droite). Que faudrait-il faire pour inverser l'ordre ? Sachant que l'axe varie de 0 à nb-1 (nb le nombre de valeurs), alors qu'il devrait varier à l'inverse, donc de nb-1 à 0? Quelle fonction f(j) permet de passer de 0 à nb-1, de 1 à nb-2, de 2 à nb-3... ?
Tu verras que la rotation à droite se fait avec le même algorithme, mais avec l'inversion sur l'autre axe.

Je n'avais pas vu que tu avais trouvé la solution entre-temps. Bravo ! Seule remarque : utiliser plutôt l'attribut length de tableau qu'une taille en dur, pour avoir une fonction de rotation qui fonctionne quelque soit la taille de la matrice (seule condition tout de même que la matrice soit complètement rectangulaire, soit que toutes les lignes aient bien la même taille, mais c'est une limitation qu'on peut admettre en général).

Merci, je n'avais pas mis length car étant donné que la matrice à une taille fixe tout le long du programme (qui correspond à la grille 7x7 du puissance 4 dans le projet), je me suis dis que ce n’était pas la peine.
Cependant, je rencontre maintenant un autre petit probleme, lorsqu'un joueur effectue la rotation, les jetons (représentés par des caractères 'X' et 'O') ne "tombent" pas comme ils devraient le faire, alors que j'utilise un sous programme de "gravité" pour les faire tomber le plus bas possible.

Sans voir le code, je ne peux pas te dire quel est le problème.

Oui c'est vrai désolé ^^
voici le sous programme de gravité :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public static char [][] Gravite (char [][] grilleJeu){ //gravité de pieces (chaque tours + retournement) for (int i=0; i<=6; i++) { for ( int j=0 ; j<=5; j++) { if (grilleJeu [j][i] != ' ' && grilleJeu [j+1][i] == ' '){ grilleJeu [j+1][i] = grilleJeu [j][i]; grilleJeu [j][i] = ' ';     } } } return grilleJeu; }

---

En fait, le vrai problème est que la gravité marche lorsque l'on joue un jeton, mais ne marche plus correctement pour les rotations.

En fait, pas exactement. Que fait ton algorithme ? Il parcourt toutes les cases dans un ordre donné. Pour toutes les cases non vide ayant une case vide "en dessous", il "bouge" le contenu de la case non vide dans celle qui est vide, et la case non vide devient vide. En conséquence, on peut obtenir une configuration qui répond aux conditions mais qu'on a déjà parcouru, et donc qu'on ne traitera pas, puisqu'on déplace des trous vers le "haut" de la grille (le haut correspond à j=0).


2 façons de traiter ce genre de problème :

1. la simple, un peu bourrine et pas du tout optimisée
   On refait la boucle entière tant qu'il y a (au moins) un mouvement. Petit à petit on va finir par tout bouger.
   
   Code:

   ---

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   public static char [][] Gravite (char [][] grilleJeu){ //gravité de pieces (chaque tours + retournement) boolean mouvement; do { mouvement = false; for (int i = 0; i <= 6; i++) { for (int j = 0; j <= 5; j++) { if (grilleJeu[j][i] != ' ' && grilleJeu[j + 1][i] == ' ') { grilleJeu[j + 1][i] = grilleJeu[j][i]; grilleJeu[j][i] = ' '; mouvement = true; // on fait un mouvement   } } } } while (mouvement); // tant qu'il y a mouvement return grilleJeu; }

   ---

2. La méthode qui consiste à faire la boucle dans l'autre sens : ainsi, on déplace les trous vers une position qu'on aura pas encore traité, et donc qui sera traité le coup suivant. Mais ça oblige quand même à faire plusieurs boucles, parce qu'on peut très bien avoir ce genre de configuration :
   
   

   x

   x

   
   Et donc après la première double boucle, on aura :
   

   x

   x

   Donc nécessiter de refaire une passe. Mais on limitera le nombre de passes par rapport à la première méthode.
   
3. La méthode optimisée qui consiste à bouger non plus une case, mais une colonne entière. En gros, lorsqu'on trouve une case vide (en [j+1][i]), et qu'il y a une case non-vide juste au-dessus (en [j][i]), on parcourt la colonne (par k) de j jusqu'a 0 et tant que la case [k][i] soit non-vide, puis on déplace la colonne [k..j][i] en [k+1..j+1][i], ce qui correspond à faire une boucle for(int l = j; l>=k; l--), pour déplacer par grilleJeu[l + 1][i] = grilleJeu[l][i];... et de completer par la case vide grilleJeu[k][i] = ' '. Comme on parcourt les lignes de 0 à 5, on va déplacer progressivement des tronçons de cases non-vides se trouvant au-dessus d'une case vide, ce qui va les fusionner avec le tronçon en dessous : si celui-ci est aussi au-dessus d'une case vide, le parcourt se faisant de 0 à 5, on va retraiter le mouvement de la colonne entière. Le tout en une boucle globale. Mais on aura de nombreuses petites boucles pour le déplacement des tronçons
4. On peut donc optimiser encore plus, en complexifiant légèrement. Il faut traiter chaque colonne séparément déjà, pour simplifier. Le mouvement d'une colonne étant indépendant des autres. Ensuite, on part du bas de la colonne (donc j=6), et on remonte pour chercher une case vide (ou le début, j=0 ), on mémorise sa position, on continue en cherchant une case non-vide, puis on continue en cherchant une case vide, et donc là on obtient un "trou", avec une série de pions au-dessus, qu'on peut déplacer d'un bloc. La taille du trou au dessus de ce qu'on vient de déplacer s'agrandit d'autant de la taille du trou qui'l y avait en dessous, et donc s'il y a encore une série au dessus, elle se déplacera d'autant plus. On va ainsi limiter le nombre de boucles.

Merci pour ton aide !
Je vais du coup opter pour la première solution, vu que je n'ais pas bien compris la 2e et qu'il va falloir probablement que j'explique cela à mon prof lorsque je rendrais le projet.
Je préfère donc quelque chose de moins optimiser mais plus simple.
Merci encore
ps : si je n'arrive pas à faire la partie joueur vs pc, pourrais-je te redemander des conseils stp ?

Citation:

---

Envoyé par MrghURss

Je vais du coup opter pour la première solution, vu que je n'ais pas bien compris la 2e et qu'il va falloir probablement que j'explique cela à mon prof lorsque je rendrais le projet.
Je préfère donc quelque chose de moins optimiser mais plus simple.

---

La 2ième solution consiste à faire la boucle sur les lignes en partant du "bas" (en faisant j allant de 6 à 0 (dans le sens classique, la ligne 0 est en haut et la ligne 6 en bas). Parce qu'on déplace un pion vers la borne de départ de boucle, donc le trou se déplace vers la borne de fin (les pions tombent donc les trous montent), donc vers des valeurs qu'on n'a pas encore traité dans la boucle. C'est exactement la même idée qu'on applique dans un tri à bulle : lorsqu'on tri, on "pousse" la valeur la plus grande vers la fin du tableau (ou la liste) : ainsi, lors de la première passe, on est sûr que la valeur la plus grande est bien à la fin, ce qui permet d'optimiser en ne la traitant plus lors de la passe suivante. Pour faire un tri décroissant, on inverse le sens de la boucle, pour pousser les valeurs minimales vers le début du tableau.



Quand tu fais la boucle de 0 à 6, tu va faire :

x x x

x x x

x x x

x x x

Alors qu'en bouclant de 6 à 0 :

x x x

x x x

x x x

Citation:

---

Envoyé par MrghURss

ps : si je n'arrive pas à faire la partie joueur vs pc, pourrais-je te redemander des conseils stp ?

---

Pour ça, il y a des techniques algorithmiques très particulières. Normalement, tu devrais avoir vu ça en cours. Une technique courante est celle dite de la force brute, qui se base sur trois parties :

1. Un générateur de coup : lister tous les coups possibles à partir d'un état donné de la grille de jeu;
2. Une fonction d'évaluation : pour tous ces coups possibles, qui de l'ordinateur ou du joueur a l'avantage. Il s'agit d'une fonction qui retourne un entier, tel que la valeur soit plus grande si le "joueur" gagne , et plus petite si l'"adversaire" gagne (entiers négatifs) ;
   A toi de réflechir à une fonction d'évaluation qui détermine un entier plus grand lorsqu'on obtient 4 pions alignés, et plus petite (négative). Au début, tu peux considérer une fonction générale qui ne favorise pas spécialement d'autres coups que ceux qui tombent sur un alignement plus grand (donc un alignement de 2 doit donner un meilleur score qu'aucun alignement, un alignement de 3 un score meilleur qu'un de 2, etc... en faisant par exemple la somme de tous les scores, on obtient une valeur valable pour estimer le score total. Pour l'adversaire, on met moins devant, et on obtient une valeur comparable.
   Ensuite, tu peux chercher à améliorer la fonction d'évaluation sur la base d'heuristiques (des coups spécifiques au puissance 4 dont on sait qu'ils sont préférables (chercher éventuellement sur Internet des sites qui parlent de stratégies gagnantes au puissance 4). Je n'ai pas de connaissances particulières du puissance 4, mais je commencerais par étudier l'impact sur la fonction d'évaluation en essayant des heuristiques simples :
   
   1. privilégier un alignement plus grand : donc préférer de jouer un alignement de 3, que de 2. Pour faire ça, au lieu de compter un score de 2 pour un alignement de 2 et 3 pour un alignement de 3, donc de faire la somme 1 + 1 + ... + 1, je ferais 1 + 2 + 4 ... + 2ⁿ. Le score serait d'autant plus grand que les alignements seraient longs.
   2. Peut être certaines positions sur la grille sont préferentielles (les coins ? le centre ? peut-être un emplacement à côté d'un pion déjà joué ?) : au lieu de compter 1 pour n'importe quel pion, on peut donner une valeur pour chaque case, et utiliser cette valeur dans le calcul du score. Attention, il ne s'agit pas de remplacer la fonction de sélection : il s'agit simplement d'appliquer des règles simples de stratégies connus (on sait démontrer qu'en jouant là, on ouvre plus de possiblité de gagner). Ces positions ne peuvent être vallables que pour le premier coup joué d'ailleurs, ou pour n'importe quelle situation spécifique identifiable).
   3. ...
   
   
3. Un sélecteur de coup pour sélectionner le coup qui a le meilleur score : un algorithme simple couramment utilisé est le min max. Cet algorithme permet de gérer l'anticipation (pas seulement le prochain coup joué, mais également les suivants, en alternant "joueur" et "adversaire", en commençant bien sûr tel que le premier "joueur" soit l'ordinateur).

PS

Citation:

---

Envoyé par MrghURss

Merci, je n'avais pas mis length car étant donné que la matrice à une taille fixe tout le long du programme (qui correspond à la grille 7x7 du puissance 4 dans le projet), je me suis dis que ce n’était pas la peine.

---

Utilise au moins une constante dans ce cas.

Là est le problème, je n'ai jamais vu ca en cours...
Ce que me dit le sujet pour cette partie ressemble un peu a ce que tu as expliqué mais je n'arrive pas à démarrer.


Voici ce qu'il dit :

Citation:

---

"Un mode IA : l’ordinateur peut suivre différentes stratégies de la plus naïve à la plus complexe.
Malheureusement les outils théoriques et pratiques que vous avez vus jusque là vous limitent à
des stratégies de base non optimisées.
Par ailleurs, sachez que la version sans rotation a été étudiée par L. Victor Allis dans sa thèse A
Knowledge-based Approach of Connect-Four (1989). Il a montré que la personne qui
commence a toujours la possibilité de gagner (sur la grille standard 7x6) si elle joue selon une
certaine stratégie définie dans la thèse.
Pour le moment, on pourra se contenter de la stratégie naïve suivante :
Supposons que l’IA ait les jetons jaunes. Si une rotation permet de gagner, l’IA la joue. Sinon,
pour chaque case libre, l’IA calcule combien au max elle peut aligner de jetons en mettant un de
couleur jaune et combien l’adversaire peut au max aligner en mettant un jeton de couleur rouge.
On score maintenant les cases de la manière suivante :
7 si l’IA peut aligner 4 sinon
6 si l'adversaire peut aligner 4 sinon
5 si l’IA peut aligner 3 sinon
4 si l'adversaire peut aligner 3 sinon
3 si l’IA peut aligner 2 sinon
2 si l'adversaire peut aligner 2
1 sinon
L’IA ordonne alors les coups possibles selon le score de chacun. Elle commence ensuite par le
coup X ayant le plus grand score et teste si en le jouant l’adversaire pourrait gagner en faisant
de suite une rotation. Si ce n’est pas possible alors l’IA joue le coup X sinon elle refait la même
chose avec le coup ayant le second meilleur score et ainsi de suite.
Remarque : l’IA proposée ne sera pas extrêmement forte. Afin d’éviter qu’un joueur puisse se
contenter de mémoriser une partie gagnée contre l’IA et de la répéter pour gagner à chaque
fois, il est utile d’introduire un peu d’aléatoire dans la stratégie ! On recommande par exemple
de tirer aléatoirement l’ordre dans lequel seront considérées les cases de même score dans la
stratégie précédente. Le choix parmi deux cases équivalentes (il y en a beaucoup en début de
partie) sera ainsi aléatoire et les parties seront moins facilement reproductibles. "

---