Algorithmique : jeux de GO

[fsadki]

Salut !

Mon problème n'a pas vraiment pour thème le codage (quoique).
On vient de nous passer un nouveau projet de programmation orienté objet. En effet, nous devons crée un jeux de go ;)
Ceci dis, je bloque sur un point qui est la conception même de l'algorithme de base. C'est à dire, que je me demande comment faire pour vérifier si par exemple : il y a des pièces noirs qui sont encerclées par des blanches, eh bien je dois retirer les noirs. Mais comment le coder ? (d'un point de vue algorithmique).
Comment pourrais-je vérifier ?

Merci d'avance pour toute idée(s) ou aide(s).
(Je ne suis pas censé commencer le projet, mais why not ? :hein:).​

ps : si vous souhaitez le sujet, je l'ai.

Amicalement ;

 

[drov]

Ton jeu de go c'est 2 joueurs ou contre un ordi ? Parce que c'est un des jeux les plus durs à simuler du monde.

 

[fsadki]

Nan c'est deux joueurs réels.

 

[Evaelis]

Vérifier s'il y a une pièce adjacente d'une même couleur dans la direction inverse à la pose de la pièce ?

 

[fsadki]

Vérifier s'il y a une pièce adjacente d'une même couleur dans la direction inverse à la pose de la pièce ?

Le problème c'est qu'il faut revenir au point de départ (là ou on pose la pierre).
Donc, faudrait peut être marquer chaque pierre comme visité mais celle qu'on a posé on l'a marque différemment comme ça on sera si on a fait le tour.
Le problème c'est de savoir si il y a des pierres noirs encadrer par les blanches donc le mieux c'est de chercher des pierres d'une couleur différentes et de voir si elles sont encadrés ?
Mais je bloque dessus.

 

[Evaelis]

Sauf que tu peux retourner des pièces uniquement quand tu pose : tu peux entourer des blancs avec des noirs par prise de colonne, ça ne retourneras pas les noirs entre les deux.

 

[Bwisingw]

Tu devrais checker toute les pièces à chaque tours, tu met un tableau, et tu regardes les changements

 

[casimir]

intéressant comme travail ce truc .

effectivement tu te crée un tableau de la taille de ta grille ,
case a 0 vide , 1 blanche et 2 noir
tu check avant de posé l'occupation des position haut bas droite gauche
attention au bord également
et après avoir posé tu re-check voir si tu as mangé un pion adverse

 

[Evaelis]

J'ai trouve un open source en .net, je l'analyse un peu
Wow, c'est pas la simplicité née.

Private Sub VerifPierreJuxta(ByVal MaPierre As ClassPierres)
Dim x As Integer
For x = 1 To 4
Dim TmpPierre As ClassPierres = VerificationPresence(x, MaPierre, Groupe.Ennemi)
If Not (TmpPierre Is Nothing) Then CreationGroupe(TmpPierre)
mColGroupe.Clear()
Next
End Sub

Et

Private Sub CreationGroupe(ByVal MaPierre As ClassPierres)
mColGroupe.Add(MaPierre)
RechercheGroupe(MaPierre)
If RechercheLiberte(mColGroupe) = False Then
Dim Tmp As ClassPierres
For Each Tmp In mColGroupe
Me.Goban.Controls.Remove(Tmp)
Next
End If
End Sub

Private Function VerificationPresence(ByVal x As Integer, ByVal MaPierre As ClassPierres, ByVal choix As Groupe) As ClassPierres
Dim distX As Integer, distY As Integer
Select Case x
Case Cote.Droite
distX = MaPierre.Left + Goban.EspaceX
distY = MaPierre.Top
Case Cote.Haut
distX = MaPierre.Left
distY = MaPierre.Top - Goban.EspaceY
Case Cote.Gauche
distX = MaPierre.Left - Goban.EspaceX
distY = MaPierre.Top
Case Cote.Bas
distX = MaPierre.Left
distY = MaPierre.Top + Goban.EspaceY
End Select
Dim Tmp As ClassPierres
Select Case choix
Case Groupe.Ennemi
For Each Tmp In Me.Goban.Controls
If ((Equals(MaPierre.ColorPierre, Color.Black) = True And Equals(Tmp.ColorPierre, Color.White) = True) Or (Equals(MaPierre.ColorPierre, Color.White) = True And Equals(Tmp.ColorPierre, Color.Black) = True)) And (Tmp.Left = distX) And (Tmp.Top = distY) Then
Return Tmp
End If
Next
Case Groupe.Ami
For Each Tmp In Me.Goban.Controls
If ((Equals(MaPierre.ColorPierre, Color.Black) = True And Equals(Tmp.ColorPierre, Color.Black) = True) Or (Equals(MaPierre.ColorPierre, Color.White) = True And Equals(Tmp.ColorPierre, Color.White) = True)) And (Tmp.Left = distX) And (Tmp.Top = distY) Then
Return Tmp
End If
Next
End Select
End Function

 

[fsadki]

J'ai trouve un open source en .net, je l'analyse un peu
Wow, c'est pas la simplicité née.

Je dois le faire en C++, avec l'utilisation de minimum deux classes.
Le but n'est pas en soi de réaliser le jeux de Go, mais de maîtriser les classes. Et au vue des cours d'amphi et des TDs, une grosse partie de l'évaluation sera sur les classes.
Et vue que je ne comprend pas le code que tu as cité xD.

intéressant comme travail ce truc .

effectivement tu te crée un tableau de la taille de ta grille ,
case a 0 vide , 1 blanche et 2 noir
tu check avant de posé l'occupation des position haut bas droite gauche
attention au bord également
et après avoir posé tu re-check voir si tu as mangé un pion adverse

Tout à fait intéressant, ça change de certains devoirs :) !
Le problème est qu'il y a aussi la "diagonale" a prendre ne compte :

Ce lien n'est pas visible, veuillez vous connecter pour l'afficher. Je m'inscris!

Tu devrais checker toute les pièces à chaque tours, tu met un tableau, et tu regardes les changements

Oui c'est sur, je pense que c'est la meilleur méthode.
Après reste à savoir comment faire.
J'ai déjà essayer de coder avec des petits tableau à deux dimensions, disons que ça ne marche pas dans tout les cas.

Sauf que tu peux retourner des pièces uniquement quand tu pose : tu peux entourer des blancs avec des noirs par prise de colonne, ça ne retourneras pas les noirs entre les deux.

C'est à dire ?
C'est plus dans ce cas que je bloque :

​

 

[Bwisingw]

J'ai peu être la solution :

Tu regardes dans un premier temps les pions qui sont à coté (dans le cas que tu as montrés, ça te retourneras un blanc)
Ensuite tu regardes les pions qui sont à coté du pions blanc (dans le cas que tu as montrés, ça retourneras 2 noir et un blanc)
Il faut que tu définisse des positions X et Y des cases où peuvent être placés les pions, et à chaque vérification, avec une fonction, tu vérifies les pions, et avec le X et le Y tu regardes si ça entoure des pions ! Je sais pas si je me suis fais comprendre, mais c'est comme ça que tu dois fonctionner ;)

 

[fsadki]

J'ai peu être la solution :

Tu regardes dans un premier temps les pions qui sont à coté (dans le cas que tu as montrés, ça te retourneras un blanc)
Ensuite tu regardes les pions qui sont à coté du pions blanc (dans le cas que tu as montrés, ça retourneras 2 noir et un blanc)
Il faut que tu définisse des positions X et Y des cases où peuvent être placés les pions, et à chaque vérification, avec une fonction, tu vérifies les pions, et avec le X et le Y tu regardes si ça entoure des pions ! Je sais pas si je me suis fais comprendre, mais c'est comme ça que tu dois fonctionner ;)

Tu viens de me donner une solution magnifique, je viens d'avoir un déclic xD.
Je vais utiliser une pile pour se faire.
Le code sera défini en plusieurs fonctions qui ne seront lancer que sous certaines conditions.
Si il y a un pion adverse, je vais lancer la recherche. Au quel cas si je retombe au finale sur des pions de la même couleurs que les noirs (dans notre cas) l'algo prend fin et les pions devienne noirs.
Plus précisément, Je vais plutôt chercher les pions adverses et regarder autour d'eux en créant une boucle tant que je n'ai pas que des pierres qui sont les miennes (dans ce cas, les blanches deviendront noirs) sinon c'est qu'ils ne sont pas encerclé (dans ce cas je vais trouver une vide, si je trouve une vide, ça quittera la boucle.
Je sais pas si je me fais bien comprendre :)

En tout cas merci bien.
Je vais faire des tests demain et je vous tiens au courant.

 

[Evaelis]

Tu cherches le pion adverse adjacent, puis pour tout pions adverse adjacent à celui ci : cherche une case vide dans les 4 directions (Et non 8), si il n'y a pas de case vide : tout retourner.

 

[fsadki]

Tu cherches le pion adverse adjacent, puis pour tout pions adverse adjacent à celui ci : cherche une case vide dans les 4 directions (Et non 8), si il n'y a pas de case vide : tout retourner.

Oui c'est sur que regarder uniquement les 4 directions suffit mais le problème c'est qu'il y en deux qui sont adjacents.

 

[Evaelis]

Je te fais un schema attend.

---------- Message ajouté à 10h23 ---------- Le message précédent était à 10h16 ----------

En rouge : Case posée : Chercher un adjacent (Une seule case représentée)
For Each (Case adjaçantes trouvées) : Vert : Recherche une case vide
----If(Vide dans une des quatres directions)
--------Arrêter la recherche
----ElseIf(Pas de vide mais cases blanches)
--------For each case blanche
-----------Recherche encore une fois(Bleu)
----Else(Tout est entouré de noir (Sans compter la case de provenance) donc on retourne)

Et ainsi de suite

 

[fsadki]

Je te fais un schema attend.

---------- Message ajouté à 10h23 ---------- Le message précédent était à 10h16 ----------

En rouge : Case posée : Chercher un adjacent (Une seule case représentée)
For Each (Case adjaçantes trouvées) : Vert : Recherche une case vide
----If(Vide dans une des quatres directions)
--------Arrêter la recherche
----ElseIf(Pas de vide mais cases blanches)
--------For each case blanche
-----------Recherche encore une fois(Bleu)
----Else(Tout est entouré de noir (Sans compter la case de provenance) donc on retourne)

Et ainsi de suite

Je comprend bien, mais cela marche dans ce cas uniquement.
Car, on peut tout à fait observer des cas plus complexe.
Avec plusieurs lignes et colonnes.

 

[Evaelis]

Et ça marche de la même façon :
Tu retiens la liste des cases déjà traitées et si il y a un croisement, je t'ai dis For Each (Pour chaque).

 

[fsadki]

Et ça marche de la même façon :
Tu retiens la liste des cases déjà traitées et si il y a un croisement, je t'ai dis For Each (Pour chaque).

Ok, j'avais pas compris le For Each, je vais faire des tests durant la semaine et aujourd'hui alors.

 

[Bwisingw]

Dit moi si ce que je t'ai dit fonctionne :)

 

[fsadki]

Dit moi si ce que je t'ai dit fonctionne :)

Oui cela fonctionne.
Du moins, actuellement je ne l'ai coder que dans le cas ou une seul pierre est encercler.
Je te tiens en courant ;)

 

[Evaelis]

Résolu ?

 

[fsadki]

Oui résolu !
Pas plus tard qu'avant hier.
Merci bien.