Le Jeu de Go

[Rockleader]

Salut tout le monde; aujourd'hui ce n'est pas mes cours qui m'amènent, mais bien un intérêt personnel.

Je ne sais pas si vous connaissez le jeu de go; il s'agit d'un jeu de stratégie asiatique dont le but est de construire les plus grand territoires possible avec des pierres blanches et noires.

La règle étant que si l'on "entoure" les pierres adverses par les siennes; on les élimine de la partie.

Je me suis mis à me demander comment ce genre de jeu pouvait être implémenter par le biais d'un algorithme.

car le nombre de combinaison possible pour prendre des pierres adverses est pour ainsi dire infini, traiter du cas par cas est donc irréalisable; quand à généraliser certaine chose; je ne vois pas trop comment cela pourrait se formaliser.

Enfin bref, je vous fait partager ce problème si cela vous intéresse d'y jeter un coup d'oeil (je parle ici seulement du niveau algorithmique et non de la prog bien entendue).

Pour ceux qui ne connaissaient pas le jeu de go; je vous le conseille:

Originaire de Chine, le jeu de go (;), go?), igo (;);)?) ou wéiqí (chinois simplifié : ;) ; chinois traditionnel : ;)) oppose deux adversaires qui placent à tour de rôle des pierres noires (;), kuro?) et blanches (;), shiro?) sur un tablier, appelé goban, tentant ainsi de contrôler le plan de jeu en y construisant des « territoires » qui se comptent en points (;), moku?). Chaque « pierre » représente un soldat ; les soldats encerclés deviennent des prisonniers.
Il s'agit du plus ancien jeu de stratégie combinatoire abstrait connu. Malgré son ancienneté, le jeu de go continue à jouir d'une grande popularité en Chine, en Corée et au Japon. Dans le reste du monde, où sa découverte est récente, sa notoriété est croissante. Son succès tient autant à la simplicité de ses règles qu'à sa grande richesse combinatoire et sa profondeur stratégique.
La terminologie du go est principalement d'origine japonaise.

Source Wiki: http://fr.wikipedia.org/wiki/Jeu_de_go

[Dlzlogic]

Bonjour,
Je ne connaissais pas ce jeu. Je suppose que le tablier n'est pas limité comme l'est un jeu d'échec.
Ca me fait vraiment penser à la gestion et/ou l'étude des pixels d'un raster.
Pour un raster, le principe est le suivant : on étudie tel pixel, alors on construit un pavé de 9x9 par exemple, centré sur le pixel à étudier.
Un pixel a toujours soit 4 soit 8 voisins, suivant la convention adoptée.
Concernant la "stratégie", on doit arriver à la conclusion que si S1 est meilleure que S2, on adoptera S1.
Donc il faut trouver une "note" à attribuer à une stratégie, ça peut être le nombre de coups pour y arriver, le piège tendu à l'adversaire, ou je ne sais quoi.
On peut par exemple se dire que si S a atteint la note 10, on la juge satisfaisante et on joue ça.

C'est tout ce qui me vient à l'esprit.

[Rockleader]

Le plateau "standard" qui s'appelle Goban est de 19x19.

Ceci dit; il existe plusieurs variantes de jeu, notamment pour ceux qui veulent apprendre.

Il n’est donc pas rare de croiser des goban de 6x6 ou 11x1 par exemple; du moins il me semble.

Donc; on n’est pas limité en nombre de pièces à jouer si telle était ta question en revanche on a quand même un nombre de coup qui ne pourra pas dépasser la taille du goban quel qu'il soit.


D'ailleurs si je refais un parallèle avec la thématique de définir la taille d'un tableau dont on parlais l'autre jour en C; ici on voit l'intérêt de ne pas définir une taille fixe dès le début..si le joueur ne veut pas faire une partie sur 19x19 et qu'on lui impose c'est pas top^^
Mais là n’est pas le sujet x)



La complexité du fait d'implémenter un algorithme pour ce genre de jeu est à mon sens qu'il est impossible de prévoir tout les coups possible pour prendre une pièce. Ce n’est pas comme un jeu de dame ou par exemple tu ne peux avancer qu'en faisant des bonds par dessus une pièce.


Je vais continuer à y réfléchir pendant mon temps libre; en farfouillant sur le net je n'ai trouvé qu'un seul véritable jeu en ligne de go 'KGS' et vu la complexité que cela prend; ça ne m'étonne pas vraiment, si l'on a joute à ça qu'il s'agit d'un jeu peu connu en occident.


Merci de ta réponse.

[Dlzlogic]

D'ailleurs si je refais un parallèle avec la thématique de définir la taille d'un tableau dont on parlais l'autre jour en C; ici on voit l'intérêt de ne pas définir une taille fixe dès le début..si le joueur ne veut pas faire une partie sur 19x19 et qu'on lui impose c'est pas top^^
Mais là n’est pas le sujet x)

Non, ça n'a rien à voir. Il y a des quantités de moyens de déclarer un tableau.

Donc la dimension du jeu est définie, donc le nombre de possibilités est fini, quelques centaines, c'est tout à fait abordable.

[fatal_error]

bj Rockleader,

j'ai perdu de vue l'avancement de la recherche sur le go, mais il y a genre 5 ans, les meilleures IA etaient a peu pres 7e dan? (le meilleur étant 9).

Maintenant je pense que ca a évolué.

Tout comme pour les échecs tu ne calcules pas toutes les possibilités. Tu trouves des patterns, des positions...

sinon, à part KGS, tu as aussi flyordie, et ptet même kurnik

[Skullkid]

Donc la dimension du jeu est définie, donc le nombre de possibilités est fini, quelques centaines, c'est tout à fait abordable.

Tout à fait abordable, oui...

La nombres de parties de go possibles est estimé à 10^360. Histoire de comparer, le nombre de parties d'échecs possible est estimé à 10^123.

Au niveau de l'état de la recherche, il me semble qu'un programme a réussi à battre un 9 dan avec un handicap relativement faible (genre moins de 5 pierres, à comparer avec il y a 10 ans où les ordis pouvaient se faire laminer avec 50 pierres de handicap), je vais essayer de retrouver l'article...

[Dlzlogic]

Bon, j'avais pas compris que Rockleader cherchait à battre tous les records.
Si c'est le cas tu es bien mieux placé que moi pour l'aider à écrire son algorithme.

[Rockleader]

Houlà; attention, je ne suis même pas à parler d'IA.


Admettons une partie en JcJ.

Ce que je me demandais c'est quel protocole de controle on peut mettre en place pour vérifier si telle ou telle pierres ont été capturé par l'adversaire. Car si on prend au cas par cas c'est assez simple; mais si on considère chaque possibilité je vois pas comment on peut introduire une vérification.

[Dlzlogic]

Une case peut avoir plusieurs valeurs, par exemple, soit il y a une pierre blanche, soit il y a une pierre noire, soit elle est vide, soit elle est à l'intérieur d'un encerclement de pierres blanches, soit à l'intérieur d'un encerclement de pierres noires.
Il y a plusieurs point que je ne connais pas, par exemple, une pierre blanche est encerclée si elle est entourée de 4 pierres noires (N-S-E-W) ou il en faut 8 .
Que se passe-t-il avec les limites du jeu, cela compte-t-il comme encerclement ?

Donc, il faut faire un tableau carré, par exemple en C, ça s'écrit Tab[19][19], c'est à dire 19 lignes puis 19 colonnes. Il faut aussi résoudre le problème du dessin, de la saisie etc.
Donc, bien avant de chercher des records, il y a du boulot.
Petit exemple :

Code: Tout sélectionner

int Contexte(int ligne, int colonne)
{
  switch (Tab[ligne][colonne]
  {
    case 0: // case libre
    ...
    break;
    case 1: // case occupée par une pierre blanche
    ...
    break;
    etc.
  }
}


Naturellement chaque case contiendra la décision à prendre.

[fatal_error]

slt Rock,

si tu joues un peu au go, tu peux t'inspirer trivialement des degrés de liberté.

Lorsque tu poses une pierre blanche, tu sais combien elle a de degré de liberté.

Lorsque tu poses la pierre noire adjacente à une pierre blanche, tu lui otes un degré de liberté. Si elle a 0 degrés, ca veut dire que tu captures cette pierre et tous les pierres qui lui sont connectées.

[Rockleader]

slt Rock,

si tu joues un peu au go, tu peux t'inspirer trivialement des degrés de liberté.

Lorsque tu poses une pierre blanche, tu sais combien elle a de degré de liberté.

Lorsque tu poses la pierre noire adjacente à une pierre blanche, tu lui otes un degré de liberté. Si elle a 0 degrés, ca veut dire que tu captures cette pierre et tous les pierres qui lui sont connectées.

C'est vrai que ce serait un bon point de départ en effet; plutôt intéressant à creuser.

On lui octroie une liberté de 4; puis à chaque fois qu'une pierre adverse vient à coté on peut diminuer d'un cran la liberté. Effectivement c'est bien vu et je pense que ça peut très bien fonctionner comme cela :lol3:


Bien sur, ça n'est pas aussi simple; car des pierres peuvent être connecté je pense sans pour autant être capturé.

Exemple:

-1234
1oox
2oxo
3xxx

Si x joue en (2,4) il capture o en (2,3) o (1,2) est connecté mais n'est pas capturé pour autant.








Quand à y jouer; disons que je connais les règles; mais soyons modeste; contre ne serait ce qu'un amateur un peu intéressé je ne tindrais pas je ne connais pas vraiment les stratégie qui existe. Même en partant avec un handicap; je pense que je pourrais me faire laminer^^


Pour Dzlogic; on ne peut prendre que des territoires que je dirais occupé; donc si tu encercle un groupement de case mais qu'il reste une case vide; tu ne prend pas les territoire; bien entendu, ce n’est que temporaire car il suffit de combler les trou et généralement soit tu les combles toi mêmes pour prendre un territoire rapidement; soit tu ne les prends pas du tout dans l'espoir que le joueur adverse fasse une tentative en jouant des pierres dans ce territoires et que tu puisses lui en prendre plus.

[fatal_error]

Bien sur, ça n'est pas aussi simple; car des pierres peuvent être connecté je pense sans pour autant être capturé.

non. Une chaine avec 0 degré de liberté c'est une chaine morte. C'est tout.

Exemple:

Code: Tout sélectionner

-1234
1oox
2oxo
3xxx

Si x joue en (2,4) il capture o en (2,3) o (1,2) est connecté mais n'est pas capturé pour autant

ok pour la capture en (2,3)
mais je saisis pas le rapport avec (1,2)

[Rockleader]

o de (1,2) est connecté avec o de (2,3)

De même que les x de (1,3) et (2,2) sont connecté pour capturer o.

C’est pour cela que lorsque tu disais que tout ce qui est connecté tombe je suis pas forcément d’accord.
Car tu ne prend là en compte que le coté horizontal et vertical; mais il y a aussi les diagonales avec lesquelles on peut se connecté.

Ou alors on n'a pas la même définition pour connecter.

[fatal_error]

o de (1,2) est connecté avec o de (2,3)

non.

une connexion c'est que les horizontales/verticales.
C'est aussi dans les définitions du Go me semble-t-il.

Code: Tout sélectionner

connecté  |  connecté | non connecté
..xx....  |     .     |   .x.
          |     x     |   ..x
          |     x     |
          |     .     |

[Rockleader]

Oki; autant pour moi je n'en avais pas la bonne définition alors.

[Skullkid]

Ok je pensais qu'il s'agissait de faire une AI basique. S'il s'agit de retirer automatiquement les pierres mortes, l'idée des libertés est à mon avis la bonne (puisque c'est ainsi que les règles sont définies à la base).

C'est peut-être (je n'ai pas vérifié) plus efficace de traîter directement les chaînes plutôt que les cases isolément, histoire d'éviter les "cascades" quand on capture une longue chaîne. Genre une chaîne peut se définir par sa couleur et l'ensemble de ses libertés, et on modifie la liste des libertés à chaque coup.

On peut aussi rajouter quelques attributs dans le but de compter les points, par exemple combien d'yeux elle a, si elle est fermée ou pas, combien de points elle vaut, ...

Pour une implémentation complète il faudrait aussi traîter les coups interdits. Les suicides ne devraient pas poser de problèmes, les ko sont probablement un peu plus subtiles.

[Rockleader]

Bonsoir à tous...oui je déterre le sujet ahah

Pour la bonne et simple raison que j'ai envie de proposer cela comme sujet d'étude pour ma l3; mais avant de me lancer ce défis qui me parait insurmontable aujourd'hui je me dis que refaire un petit topo ne serait pas trop mal^^



Sans avoir relu l'ensemble de la discussion, je me souviens que l'on avait dis plusieurs points.


Une pierre est défini par un nombre de liberte total (2 pour les coins / 3 pour les lignes / 4 sinon) et un nombre de liberte effectif par rapport au pierre qui viendront s'ajouter à coté.


Ma réflexion se porte réellement sur l'algorithmique de la chose.


Je crois que nous avions dis qu'une pierre était capturé si l'ensemble de ses liberté était occupé par des pierres adverses.
Je suis d'accord sur ce point; mais il s'agit de la figure la plus basique un simple Atari.


Le véritable défis serait à l'heure actuelle (pour moi) de déterminer quand est ce qu'un groupement de pierre est capturé; les formes sont tellement diverses et variés que je n'arrive pas à entrevoir un algorithme faisant cela.

Vous auriez des idées ?


EDIT:

L'idée des chaines ne m'a pas l'air mauvaise après réflexion: http://fr.wikipedia.org/wiki/R%C3%A8gles_du_jeu_de_go#Statut_des_pierres

Il faudrait donc définir la capture de chaine et non de pierres.

Hum...

[Skullkid]

Salut, oui je pense que manipuler les chaînes permet de simplifier les questions d'atari. Sans y avoir trop réfléchi je verrais bien une représentation de l'état du jeu par un objet "goban" qui contiendrait les infos basiques et des objets "chaîne" avec des champs donnant la couleur, le nombre de pierres, le nombre de libertés, leur emplacement, ...

L'état du jeu serait véritablement codé par les chaînes, mais l'objet goban servirait d'interface entre le joueur et les chaînes, permettant de traduire des instructions du type "mettre une pierre noire en (i,j)" en "mettre à jour telle chaîne" ou "créer une nouvelle chaîne". L'objet goban serait en fait un tableau d'objets "intersection", et une intersection contiendrait sa position, sa "valeur" (libre, blanc, noir) et, si elle est occupée par une pierre, un identifiant permettant de trouver la chaîne correspondante.

Tout ça à froid, hein, il y a sans doute des méthodes plus efficaces.

[fatal_error]

salut,

une variante un peu plus complexe mais plus intuitive (à mon sens)

qu'est-ce que tu fais avec un goban?
tu poses des pierres, c'est tout.

qu'est-ce que tu fais en tant que joueur?
tu sais s'il y a des chaines et tu connais la position des pierres sur le goban, tu tentes de poser des pierres sur le goban

qu'est-ce que l'arbitre fait?
il te vire les pierres capturées

Dans l'exemple de skullkid, le joueur, l'arbitre et le goban sont fusionnés.
J'aurais tendance à séparer les règles du jeu (l'arbitre), et l'analyse des chaines du goban.

Grosso:

Code: Tout sélectionner

class GobanBoard{
 //ajoute une pierre à la position position sur le goban
 putStone(position, color): true/false (false si on peut pas)

 //enleve une pierre à la position position sur le goban
 removeStone(position): true/false (false si ya pas de pierre)
}

class GobanAnalyzer{
 //retourne la chaine qui contient une pierre à la position donnée
 getGroup(position): Group

 //grosso ici tu pourris ta classe du genre :
 lorsque tu récup la chaine, tu regardes sur le gobanBoard s'il y a des pièces à coté
 libre à toi, pour chaque pièce (copiée) d'associer un pointeur sur un group pour des perfs etc
}

class Group{
 //retourne le nombre de degrés disponibles
 getFreeConnections():int
 removeFreeConnection()
 addFreeConnection()
}



cette approche est pas super optimisée pour monter une IA (dans le sens que la représentation des patterns est certainement pas la plus aisée) mais pour afficher la capture de chaines, c'est finger in ze noze

[Rockleader]

Un nouveau petit up =)

C'est désormais presque assuré que je passe mes deux prochains moi à travailler sur une implémentation jcj et ia du jeu; on a parlé de tout ce qui est algorithmique et je crois que maintenant à part commencer le codage et voir par moi même comment tout cela se passera je ne peux rien faire de plus pour le moment.




Je me pose quand même une question au niveau de l'interface graphique...cette année j'ai vu java swing; mais avec mes connaissances actuelle, j'ai du mal à voir comment je pourrais implémenter un plateau pour jouer sur les intersections.
Vous auriez des conseils à me donner de ce coté là ? Des pistes pour l'implémentation ? Par exemple si j'avais fais ça en javascript j'aurais probablement utilisé un canvas et à certaine position de la souris j'aurais déclenché les événements...j'imagine que le principe n'est pas très éloigné en java mais là comme ça sans plus d'infos je ne sais pas de quel coté regarder...

Merci à vous :)