Le Jeu de Go

Discutez d'informatique ici !
silaoju
Messages: 2
Enregistré le: 09 Avr 2015, 08:58

par silaoju » 09 Avr 2015, 09:06

C'est une merveille pour l'partage , les yeux et la découverte



Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 17 Avr 2015, 03:40

Dame are neutral points in yose, the endgame. Placing a stone on such a point won't gain either side any points. In some sets of rules however, most notably the Chinese, every stone placed on the board is worth a point. The question of whether a point is dame then becomes a question of whether the number of dame points left is even or odd. In the latter case, being the first to start playing dame is worth one point; regardless of the how many are to play (as long as their number is odd).



Pour simplifier; une dame c'est une position telle que si mon adversaire joue a un endroit, il perd toutes ses pierres dans la région concerné; mais d'une autre coté si je joue à ce même endroit c'est moi qui perd tout.

Donc au final c'est le résultat de deux intersection volontairement laissé vide pour ne pas perdre son groupement.



Mais du coup je me posais une question sur le comptage des points si on se regroupe dans un tel cas.
Considère t'on le territoire nul ? Ou bien on va donner aux deux joueurs les points potentiels qu'ils auraient pu avoir ?
J'avoue que j'ai pas réussi à trouver une règle très claire à ce sujet; et les bots que j'ai joué sur kgs semblent ne pas réagir de la même façon à ceci.
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6608
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 17 Avr 2015, 03:59

http://francois.mizessyn.pagesperso-orange.fr/JeuDeGo/yogo/dame.htm

le dame tout à droite, blanc comme noirs peuvent jouer et sont pourtant sûr de pouvoir survivre après
quand aux points...ben généralemetn dans les parties les joueurs remplissent les cases "frontières" donc au final on y compte pas.

si tu lis http://jeudego.org/_php/_4lecons/4lecons_4_5.php, tu vois que de toute facon, on ne list que les intersections vides... au sein d'un territoire.

donc pour moi tu comptes 0 si aucun des deux joueurs ne pose sa pierre sur un dame
la vie est une fête :)

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 18 Avr 2015, 15:19

Ok je compterais ça comme nul alors merci.


Je pense avoir bien avancé dans le projet; j'en suis au point de déterminer si on peut jouer dans un oeil adverse (du coup ça revient à savoir si on peut capturer une ou plusieurs pierres adverse).

Et du coup là à ce moment là je me retrouve forcer d'implémenter une classe Chaine; sinon je ne vois pas d'autre solution. Si je ne passe pas par une chaine je ne détecterais pas qu'un groupe possède plusieurs yeux et qu'il est intuable.


J'ai décidé de faire mes chaines avec une array list d'intersection et non de pierre; ce qui me permettrait en théorie de détecter des chaines vides et de faciliter la reconnaissance des territoires fermés...enfin ça c'est l'idée à la base^^
Après de toute façon si je m'assure de ne pas ajouter d'intersection vide à une chaine ça reviendrait au même.
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 27 Avr 2015, 14:26

Petit up encore =)

J'ai terminé toutes les fonctions...ça semble bien marché, comptage des libertés, affichage des chaines etc etc...


Pour que ce soit vraiment terminé il ne me reste plus qu'à faire une fonction pour déterminer les territoires à la fin de la partie.
Je pensais au début que mon implémentation avec une array list d'intersection faciliterait ça...mais en fait pas vraiment^^



Du coup j'essaie de réfléchir mais je vois pas d'algo se dégager pour déterminer un territoire.






Si je prends une intersection quelconque sur mon plateau comment déterminer si oui ou non elle fait partie d'un territoire ?
Par territoire du coup je veux dire qu'elle est comprise à l'intérieur d'une chaîne fermé. Et en théorie toute chaine adverse n'ayant pas minimum deux oeil adverse dans ce territoire sera considéré comme morte.

Mais j'en reviens toujours au même point comment déterminer que je suis dans un territoire ?



Ce qu'il faut que j'arrive à traduire finalement c'est; une intersection se trouve à l'intérieur d'une chaîne. Simple dans le cas d'un oeil; mais dès que le territoire de l'oeil s’agrandit ça devient une autre paire de manche.
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 09:03

par ampholyte » 16 Mai 2015, 23:26

Bonjour,

En discutant avec un collègue, j'ai appris que celui-ci adorait le go, j'en ai donc profité pour parler de ton projet sur ce jeu.

Mon collègue aimerait bien jeter un oeil sur le code source du jeu, est-ce que tu comptes rendre tes sources disponibles (github, ...), est-ce qu'elles le sont déjà ?

Merci d'avance pour ta réponse et bon courage pour ton rapport =).

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 17 Mai 2015, 00:13

ampholyte a écrit:Bonjour,

En discutant avec un collègue, j'ai appris que celui-ci adorait le go, j'en ai donc profité pour parler de ton projet sur ce jeu.

Mon collègue aimerait bien jeter un oeil sur le code source du jeu, est-ce que tu comptes rendre tes sources disponibles (github, ...), est-ce qu'elles le sont déjà ?

Merci d'avance pour ta réponse et bon courage pour ton rapport =).


Une fois que j'aurais reçu ma note de TER éventuellement ça me dérange pas du tout.

Surtout que le code pourra être amélioré sur de nombreux points. Là j'essaie surtout de rusher pour terminer quelque chose avant la fin du délais de deux mois.


Le gros problème pour le moment c'est qu'il me faut sensiblement 1 seconde pour simuler une partie entière...donc pour faire tourner du monte-carlo qui doit simuler masse partie pour déterminer le meilleur coup, ça prends beaucoup trop de temps.

Enfin bref, ça sera avec plaisir^^
Mais préviens ton collègue que le code sera assez sale^^

En fait je passe plus de temps à faire les documents qu'on me demande à coté qu'à réellement coder...
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 09:03

par ampholyte » 17 Mai 2015, 11:01

Rockleader a écrit:Une fois que j'aurais reçu ma note de TER éventuellement ça me dérange pas du tout.

Surtout que le code pourra être amélioré sur de nombreux points. Là j'essaie surtout de rusher pour terminer quelque chose avant la fin du délais de deux mois.


Le gros problème pour le moment c'est qu'il me faut sensiblement 1 seconde pour simuler une partie entière...donc pour faire tourner du monte-carlo qui doit simuler masse partie pour déterminer le meilleur coup, ça prends beaucoup trop de temps.

Enfin bref, ça sera avec plaisir^^
Mais préviens ton collègue que le code sera assez sale^^

En fait je passe plus de temps à faire les documents qu'on me demande à coté qu'à réellement coder...


Merci pour ta réponse, ne t'inquiète pas pour le code on en a vu passer des vertes et des pas mûres :ptdr:.

Après c'est souvent le problème de projet vu en cours, on passe plus de temps à écrire un rapport qui sera souvent lu en diagonal que de passer du temps pour optimiser et améliorer les points que l'on aimerait bien faire.

Est-ce que tu comptes le poursuivre après avoir rendu ton rapport ?

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 17 Mai 2015, 13:33

Et bien sachant qu'après ça tomberont deux mois de vacances en théorie oui c'est bien possible que je le continue.

Déjà je voulais faire une pseudo interface graphique..mais finalement je vais pas avoir le temps pour le 30 mai ça va être trop tôt ><
Surtout que là ma priorité c'était de travailler sur l'IA vu que le prof qui m'encadre a son domaine de recherche dans les IA...


Bref pour répondre à la question, oui il est possible que je le continue un peu à mon rythme, après tout c'est un truc que je trouve intéressant et qui me trottait dans la tête depuis plusieurs années comme le prouve ce sujet^^


Le genre de truc sale que tu vas trouver dans le code...tout les attributs sont public mais j'ai quand même fais des getter...que je n'utilise même pas à chaque fois d'ailleurs...fin bref x)
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6608
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 18 Mai 2015, 00:50

question bete, mais, qu'est-ce qui valorise ton ia par rapport à celles qui existent déjà?
la vie est une fête :)

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 18 Mai 2015, 01:09

fatal_error a écrit:question bete, mais, qu'est-ce qui valorise ton ia par rapport à celles qui existent déjà?



La question n'est pas bête du tout, bien au contraire, l'idée du projet c'est de pouvoir apporter quelque chose à ce qui existe déjà après tout...mais franchement en seulement deux mois, avec la quantité de paperasse que je dois faire à coté c'est pas vraiment possible///

Donc pour le moment en tout cas rien du tout :cry:

A partir du moment ou je peux simuler qu'une partie par seconde...peu importe quelle stratégie je peux employé face aux IA qui existent ça ne peut pas faire le poids..malgré tout, j'espère que l'IA une fois terminé sera au moins capable de battre une IA purement aléatoire...je ferais quelques test en jouant mon ia contre des ia faibles de kgs pour voir ce que ça donne.


Mais une fois le projet terminé, comme je l'ai dis avant je ne compte pas laissé ça de coté, je vais probablement reprendre mes structures pour pouvoir obtenir des résultats plus rapide et du tout pouvoir améliorer la capacité de l'IA.

Et encore que quand je dis une partie par seconde...je veux dire sur un plateau en 9x9...donc en fait je fais grosso modo 82 coups par seconde. C'est vraiment trop lent...peut être que je fais trop de vérification et de test et je dois perdre du temps là dessus, c'est même obligé, mais j'ai pas vraiment le temps de revenir sur ce genre de détail...en tout cas pas tant que l'IA n'est pas fini.




Après je me dis...si le temps est le seul problème à la limite c'est pas très grave si le résultat est à la clefs...si c'est le seul point à améliorer je finirais par trouver un moyen^^


Cela dis, je me suis laissé dire que les gros programmes de Go comme MoGo tournent avec énormément de ressources...alors forcément c'est pas ma pauvre IA sur ma machine 32 bits qui va faire la concurrence^^

Puis surtout si on s'intéresse vraiment au sujet, vous remarquerez que très peu d'infos sont divulgués en la matière...on sait que les meilleurs programmes utilisent Monte-Carlo / UCT mais il y a forcément autre chose, s'il n'y avait que ça, toutes les IA seraient au même niveau..enfin c'est que mon avis..
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 09:03

par ampholyte » 18 Mai 2015, 10:42

Rockleader a écrit:
A partir du moment ou je peux simuler qu'une partie par seconde...peu importe quelle stratégie je peux employé face aux IA qui existent ça ne peut pas faire le poids..malgré tout, j'espère que l'IA une fois terminé sera au moins capable de battre une IA purement aléatoire...je ferais quelques test en jouant mon ia contre des ia faibles de kgs pour voir ce que ça donne.


Une des solutions pour voir si ton ia tient la route, est de la faire se confronter à elle-même (et donc de laisser ton pc allumé pour un temps inderterminé :lol3:)


Mais une fois le projet terminé, comme je l'ai dis avant je ne compte pas laissé ça de coté, je vais probablement reprendre mes structures pour pouvoir obtenir des résultats plus rapide et du tout pouvoir améliorer la capacité de l'IA.


Et encore que quand je dis une partie par seconde...je veux dire sur un plateau en 9x9...donc en fait je fais grosso modo 82 coups par seconde. C'est vraiment trop lent...peut être que je fais trop de vérification et de test et je dois perdre du temps là dessus, c'est même obligé, mais j'ai pas vraiment le temps de revenir sur ce genre de détail...en tout cas pas tant que l'IA n'est pas fini.


Je pense que pour gagner en rapidité (après avoir fait une passe d'optimisation sur ton IA), il serait peut-être envisageable de faire du multi-threading (simuler en même temps plusieurs parties aléatoires).

Après je me dis...si le temps est le seul problème à la limite c'est pas très grave si le résultat est à la clefs...si c'est le seul point à améliorer je finirais par trouver un moyen^^


Cela dis, je me suis laissé dire que les gros programmes de Go comme MoGo tournent avec énormément de ressources...alors forcément c'est pas ma pauvre IA sur ma machine 32 bits qui va faire la concurrence^^


En effet, il ne te reste plus qu'à investir quand tu seras riche :ptdr:

"MoGo fonctionnait depuis les Pays-Bas sur un super ordinateur de 800 nœuds, chacun contenant 4 cœurs tournant à 4,7 GHz pour produire 15 Téraflops" (http://fr.wikipedia.org/wiki/Jeu_de_go_en_informatique#M.C3.A9thode_de_Monte-Carlo)


Puis surtout si on s'intéresse vraiment au sujet, vous remarquerez que très peu d'infos sont divulgués en la matière...on sait que les meilleurs programmes utilisent Monte-Carlo / UCT mais il y a forcément autre chose, s'il n'y avait que ça, toutes les IA seraient au même niveau..enfin c'est que mon avis..


Il y a les réseaux de neurones qui peuvent peut-être plus performant que le Monte-Carlo / UCT mais qui fonctionne par apprentissage (donc énormément de partie à effectuer, beaucoup de ressources, ...).

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 31 Mai 2015, 15:39

Bon..normalement je pourrais envoyer ça à ton ami à partir du 10 Juin.


Outre le codage assez dégueulasse, il y a clairement un bug récurent dans certaines situations ou en jouant un coup on supprime une pierre qui ne devrait pas l'être (en général ça n'arrive que sur les bordures de plateaux ou les coins).
C'est identifié, mais j'ai jamais pu trouver la source du problème dans le code..;surtout que j'devais travailler l'implémentation de l'IA à coté...et faire la paperasse.


Donc si ton ami veut de vrais résultats correct et surement plus rapide je pense que revoir toute la structure sera le mieux :ptdr:


Cela dit, pour en revenir à ce problème de temps d'exécution, j'ai descendu la taille de mon goban à 5x5 pour avoir des temps plus abordables.

Et je suis quand même content de voir que le simple fait de faire tourner MC semble rendre l'IA supérieure à une simple IA aléatoire.

Avec simplement deux niveaux d'arbres et deux simulations de parties par coup j'arrive à 56% de victoire pour l'IA. Le simple fait d'augmenter le nombre de simulation de deux à sept fait passer le taux de victoire à 83%
A mon avis, si je descendais sur le niveaux trois on pourrait frôler les 95% de victoire contre IA aléatoire...mais niveau temps d'exécution ça pourrait pas se tenir...




Cela dis, je suis assez content, mon objectif personnel c'était d'arriver à faire mieux qu'une IA aléatoire...ça semble être le cas :zen:

Après clairement contre un joueur un peu expérimenté, l'IA fait pas le poids, ça se voit...mais d'un autre coté, je crois pas qu'on puisse être meilleur qu'un joueur expérimenté simplement avec Monte-Carlo...du moins ça sera ma conclusion après avoir cravaché deux mois là dessus...
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 09:03

par ampholyte » 31 Mai 2015, 20:44

Ok merci beaucoup pour le suivi =), je tiendrais au courant mon collègue, et si besoin je le mettrais en contact avec toi via le forum ;).

beagle
Habitué(e)
Messages: 8677
Enregistré le: 08 Sep 2009, 16:14

Re: Le Jeu de Go

par beagle » 28 Jan 2016, 17:13

L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

Re: Le Jeu de Go

par Rockleader » 28 Jan 2016, 20:40

C'est impressionnant, par contre, le jouer reste européen, je pense pas que l'on pourra battre les meilleurs joueurs coréen ou japonais avant longtemps^^
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

beagle
Habitué(e)
Messages: 8677
Enregistré le: 08 Sep 2009, 16:14

Re: Le Jeu de Go

par beagle » 28 Jan 2016, 21:07

Rockleader a écrit:C'est impressionnant, par contre, le jouer reste européen, je pense pas que l'on pourra battre les meilleurs joueurs coréen ou japonais avant longtemps^^


Dans l'article ils disent que le niveau est proche des meilleurs mondiaux.Donc dans pas forcément dans très longtemps.
Je suis plus échecs, et je me souviens des humains qui fanfaronnaient.
Les meilleurs mondiaux se la jouaient inventivité, créativité qui suffiraient à toujours rester devant la machine.
Et j'ai vu (sur le net) la défaite de Kasparov, défait par Deep Blue.
Aujourd'hui on peut suivre les meilleurs tournois mondiaux avec les analyses de logiciels d'échecs achetables par monsieur tout le monde tournant sur des ordinateurs de monsieur tout le monde ...
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

Re: Le Jeu de Go

par Rockleader » 28 Jan 2016, 22:05

Le problème c'est que les échecs, le nombre de coups possible est limité.

Au go, ce nombre est littéralement illimité.

La méthode que j'avais employé pour mon ter, c'était de choisir le meilleur coup possible en faisant des simulations de monte carlo sur plusieurs niveau d'arbre de coups possible. Il n'y avait donc pas d'apprentissage d'une partie à l'autre.

Le soucis qui c'est vite vu, c'est que pour faire une simulation efficace il faut du temps, beaucoup de temps.

Pour te donner une idée, avec une profondeur de 2 coups prévus seulement, pour un goban de 9x9, c'était géré en environ 1 sec. (Pour une partie simulé entière).

Pour un goban en 19x19; trouver le meilleur coup après avoir simulé une partie entière...30 min environ.

Alors, avec un cluster peut être que j'aurais pu tester un truc intéressant, mais c'est clairement loin de l'ordi de monsieur tous le monde, bien que j'ai probablement programmé ça comme un manche mais bon...
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 09:03

Re: Le Jeu de Go

par ampholyte » 29 Jan 2016, 11:13

Bonjour,

Pour information , google a réussi (il y a 2 jours) avec son IA apha go à battre le champion d'Europe une grande première dans le monde de l'IA :

http://www.nature.com/news/google-ai-al ... go-1.19234
http://www.deepmind.com/index.html

Concernant ton problème, tu te compliques la vie avec tes intersections ^^. Ton plateau de jeu ne bouge, il te suffit de considérer tes intersections comme les cases de ton tableau. Par exemple l'intersection ligne 1 colonne 1 correspond à (0; 0) de ton tableau représentant le plateau de jeu.

Pour tout ce qui est evenement souris, il faut regarder du côté de la doc swing.
Voici un petit tuto résumant les fonctions principales des évènements souris (clic, coordonnées, ect...) :

http://b.kostrzewa.free.fr/java/td-even ... uris2.html


Est-ce que cela répond à ta question ?

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

Re: Le Jeu de Go

par Rockleader » 29 Jan 2016, 16:09

Je n'avais pas vraiment de question, je répondais simplement à beagle qui me signalait la même chose que toi (mais hier^^)


Pour l'implémentation, j'avais fais un truc comme ça également ,avec un tableau d'intersection, j'avais pas vraiment de soucis de ce coté là =)

Presque un an tout ça...je rajeunis pas :lol:
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite