Discussion :

[OZ1977]

Bonjour,

Je travaille sur un TD morpion pour ma formation et je bloque un peu sur la méthode qui permet de trouver un gagnant.
La version du morpion sur laquelle on travaille est évolutive avec une grille n*n et il faut aligner 5 pions pour gagner.

Pour le moment, j’ai une première méthode rechercherAlignement() qui recherche un alignement de pions du joueur courant.

La méthode rechercherAlignement() est appelée par une méthode coupGagnant() qui recherche après chaque coup, un alignement de pions du joueur courant dans toutes les directions (8 directions) à partir de la position du dernier pion joué.

Cet algo ne me détecte pas toutes les combinaisons gagnantes*:

exemple 1*: dernier position jouée (3,3) → gagnant non détecté

[ X ] [ O ] [ X ] [ O ] [ O ] [ O ]
[ O ] [ X ] [ X ] [ O ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ X ] [ O ] [ O ]
[ O ] [ O ] [ O ] [ X ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ O ] [ X ] [ X ]
[ O ] [ O ] [ O ] [ O ] [ O ] [ O ]

exemple 2*: dernier position jouée (4,4) → gagnant détecté

[ X ] [ O ] [ X ] [ O ] [ O ] [ O ]
[ O ] [ X ] [ X ] [ O ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ X ] [ O ] [ O ]
[ O ] [ O ] [ O ] [ X ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ O ] [ X ] [ X ]
[ O ] [ O ] [ O ] [ O ] [ O ] [ O ]

Je ne vois pas trop comment faire sans multiplier les tests tout autours de la dernière position jouée.
d’avance merci de votre aide.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
boolean coupGagnant(int x, int y) {
 
  //case courante = dernier pion joué 
  int ligne = x;
  int colonne = y;
 
  //boucle sur les tableaux de déplacements pour faire une recherche
  //dans toutes les directions de la dernière case jouée
  for (int i=0; i<8; i++) {
    //case de départ --> dernier coup joué
    //on stocke le nombre de pions alignés dans chaque direction
    alignement[i] = rechercherAlignement(ligne, colonne, DEP_COL[i], DEP_LIG[i]);
    //println("Nombre de pions alignés direction "+i+": "+alignement[i]);
 
    //Vérification des conditions pour gagner
    if (alignement[i]>=5) {
      println("Joueur "+joueurCourant+" gagnant");
      //textSize(24);
      //textAlign(CENTER, CENTER);
      //text("Joueur "+joueurCourant+" gagnant", 400, 50);
 
      return true;
    }
  }
  return false;
}
 
 
int rechercherAlignement(int x, int y, int depX, int depY) {
 
  int ligne = x;
  int colonne = y;
  int nombreAlignes = 0;
 
  //On récupère la liste des cases composant l'alignement pour 
  //éventuellement le ré-afficher
  //ArrayList<Integer> listeCases = new ArrayList<>();
 
  //5 == au nombre de pion qui doivent être alignés pour gagner
  for (int i=0; i<5; i++) {
    //si la case correspond à un pion du joueur courant
    //on incrémente le compteur
 
    //on teste que l'on est dans la grille
    if (ligne>=0 && ligne<nbCases && colonne>=0 && colonne<nbCases) {
      if (tableau[ligne][colonne]==joueurCourant) {
        nombreAlignes++;
        //sinon, on réinitialise le compteur
      } else {
        nombreAlignes=0;
      }
      //deplacement depuis la position du dernier pion joué
      //utiliser le tableau des déplacements en X et Y
      colonne+=depX;
      ligne+=depY;
    }
  }
  ligne = 0;
  colonne = 0;
  return nombreAlignes;
}

[pk960]

Bonjour,
Au lieu de chercher dans les 8 directions à partir de la position de la dernière position jouée, il suffit de chercher dans la moitié des directions mais dans les deux sens (vers l'avant et vers l'arrière).
Voici un schéma montrant ce que je veux dire sur l'exemple 1 :

[ ↖ ] [ O ] [ X ] [ O ] [ O ] [ O ]
[ O ] [ ↖ ] [ X ] [ O ] [ X ] [ O ]
[ O ] [ O ] [ ↖ ] [ X ] [ O ] [ O ]
[ O ] [ O ] [ O ] [X] [ X ] [ O ]
[ O ] [ O ] [ X ] [ O ] [ ↘ ] [ X ]
[ O ] [ O ] [ O ] [ O ] [ O ] [ O ]

[OZ1977]

bonsoir

merci pour ta réponse
mais du coup, je vais chercher 2 pions d'un côté et 2 de l'autre et dans l'exemple que tu donnes, je ne détecte pas le gagnant puisque je ne testerai pas la position 0,0 (coin haut gauche)
c'est d'ailleurs comme cela que je l'avais codé au début

[ X ] [ O ] [ X ] [ O ] [ O ] [ O ]
[ O ] [ ↖ ] [ X ] [ O ] [ X ] [ O ]
[ O ] [ O ] [ ↖ ] [ X ] [ O ] [ O ]
[ O ] [ O ] [ O ] [ X ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ O ] [ ↘ ] [ X ]
[ O ] [ O ] [ O ] [ O ] [ O ] [ O ]

[pk960]

Bonjour,
Je n'ai jamais écrit qu'il fallait chercher 2 pions d'un côté et 2 de l'autre. D'ailleurs, mon exemple trouvait 3 pions d'un côté et 1 de l'autre.
J'ai écrit qu'il suffisait de chercher dans la moitié des 8 directions (par exemple, ↖↑↗→) mais dans les deux sens.
Le coup gagnant peut être à une extrémité de la suite des pions alignés : il ne faut donc pas réduire la portée de la recherche.
Mais si le coup gagnant n'est pas à une extrémité de la suite des pions alignés, c'est qu'il y a des pions alignés de part et d'autre : il faut donc compter le nombre de pions alignés de part et d'autre.
Concrètement, il suffit d'additionner le nombre de points alignés trouvés dans un sens et le nombre de points alignés trouvés dans l'autre sens.
Ce qui donne quelque chose comme :

Code :

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

alignement[i] = rechercherAlignement(ligne, colonne, DEP_COL[i], DEP_LIG[i]) + rechercherAlignement(ligne, colonne, DEP_COL[i+4], DEP_LIG[i+4]);

[Runhide]

Je te donne une réponse d'un dimanche soir à minuit mais je pense que cela devrait t'aider à résoudre ton problème.


Partons du postulat suivant:

_ La grille est évolutive mais pas restrictive, c'est à dire que si elle contient 30 colonnes avec des cases vides, on toujours les remplir --> on est donc obligé de tout parcourir pour vérifier un gagnant (quoi que en se creusant un peu la soupière...)
_ On à simplement 2 axes, ce qui nous donne un nombre de suites à vérifier égale à "nbAxe X (( (nbCol + nbLi ) / nbAxe ) + nbAxe)" soit par exemple dans une grille 5x10 donne 17 vérifications.



Champs des recherches(colonnes/lignes)

DiagoA = 0/0 à colMax/liMax
DiagoB = colMax/0 à 0/liMax

uColonne = colOffset/0 à colOffset/liMax
uLigne = 0/liOffset à colMax/liOffset

Donc en code, on aurait quelque chose comme ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
String symbolePlayer = "x"; (setter à chaque tour de jeu...)
 
// -- Exemple pour la première diago
public final int CONS_UNDEFINED = 0;
public final int CONS_WINNER= 1;
public final int CONS_LOOSER = 2;
 
public int STATE_ACTUAL = CONS_UNDEFINED;
 
int incrConsecutif= 0;
int offset = 0;
int maxOffset = Math.min(colMax, liMax);
 
public void workDiagonalA(){
 
   while(offset <= maxOffset &&  STATE_ACTUAL == CONS_UNDEFINED){
 
   verifyConsecutifEquals(monTableau[offset,offset]);
 
 
    }
 
}
 
 
public void verifyConsecutifEqual(String symbol){
 
if(symbol).equals(symbolePlayer){ 
   increConsecutif++; 
    offset++;
 
    if(increConsecutif == 5){ 
    STATE_ACTUAL== CONS_WINNER;
 
      }else if(offset-maxOffset <5){
                 STATE_ACTUAL== CONS_LOOSER;
     }else{
           verifyConsecutifEqual(String symbol); // Récursif
    }
 
}else{
     offset++;
     increConsecutif =0; // RESET
     if(offset-maxOffset <5){  
            STATE_ACTUAL == CONS_LOOSER; // Plus assez de possibilité pour gagner
 
 
}
 
}

Voilà pour la diagonale, même principe pour les colonnes et lignes mise à part qu'il faut itérer sur leur nombres dans une boucle et bouger l'offset que sur colonne ou ligne. (A contrario de la diagonale).



De plus, si ton tableau commence à avoir énormément de ligne et colonne (qui à dit SGBD ?), tu peux itérer plus rapidement en utilisant tes processeurs avec des recursiveAction dans un forkJoinPool(Runtime.availableProcessor()).
Ceci dit, il faut au moins dépasser les 100 000 voir plus pour avoir une différence qui vaut le coup, en dessous tu va gagner des millisecondes donc aucun intérêt.




En esperant t'avoir aider, même si le code parait brouillon l'idée générale devrait être assez obvious.

[OZ1977]

merci+++ à vous.
on (car on travaille en trinome) a fini par y arriver et votre aide a été précieuse.