Journal Le Go et les ordinateurs

Posté par (page perso) .
1
23
fév.
2007
Au hasard de mes pérégrinations sur le net je suis tombé sur cet article qui évoque les programmes de jeu de Go => http://interstices.info/display.jsp?id=c_21056&qs=id%3Dj(...)

Pour info c'est un article de l'excellent site Interstices qui propose de la vulgarisation sur la recherche en informatique. Souvent j'y pige que pouic mais c'est très amusant à lire.

Alors revenons à l'article sur le Go : Il faut savoir que l'analyse de ce jeu entraîne une explosion combinatoire encore plus démente que les échecs (10^50 coups possibles aux échecs et 10^170 au Go). Le résultat c'est que, si les programmes d'échecs actuels sont meilleurs que les humains, les programmes de Go en revanche sont des grosses bouses qui se font écraser par ce malin d'Homo Sapiens.

L'article est écrit par Sylvain Gelly, un doctorant de l'INRIA, qui explique que la situation à long terme pourrait bien changer sur le front des programmes de Go.
MoGo est le meilleur des prétendants actuels et il s'approche d'un niveau assez correct. Conçu en collaboration entre l'INRIA et l'école Polytechnique, MoGo a obtenu un classement ELO 2323 (le second,Valkyria, est à 2000).
C'est bien mais il faut savoir que MoGo n'est relativement performant que sur un damier réduit (9x9 au lieu de 19x19).
Quand on accepte cette limitation on constate les progrès accomplis : un joueur 2e dan s’est proposé pour affronter MoGo en 9x9 et MoGo a gagné une partie sur deux.

De plus, du fait même de sa conception, MoGo profite très largement d'une amélioration de la puissance de calcul. L'organisation de tournois lents (plusieurs heures de réflexion par coups) a montré que MoGo était compétitif ce qui augure bien de l'avenir quand les machines seront plus rapides.

L'article d'Interstices détaille toutes les astuces techniques de MoGo (l'algorithme UCT, la méthode de Monte-carlo, l'identification des motifs...etc) et il est très pédagogique...Pour tout dire il m'a donné bougrement envie de me mettre au Go !

Hop, n'écoutant que mon courage je me lance : sudo apt-get install gnugo qgo
.
.
.
.
Deux heures et demie plus tard : sudo apt-get remove --purge gnugo qgo

Message personnel à l'attention de Sylvain Gelly :

Monsieur,
Plus besoin de travailler sur l'amélioration de votre logiciel.
Je vous confirme que les programmes actuels écrasent déjà comme une merde un représentant (honteux) de la branche Sapiens.

Salutations piteuses.

PG
  • # Il n'y a pas que l'explosion combinatoire

    Posté par (page perso) . Évalué à 3.

    Je n'ai pas été lire l'article, mais a ce que j'en sais ce qui rends le go compliqué à coder c'est surtout qu'il est très difficile d'évaluer si une position est meilleur ou pire qu'une autre. Non seulement l'arbre des possibilité de jeu est énorme, mais en plus il est donc difficile de choisir quelles parties ne pas explorer.

    Sinon je te conseille de vite lacher GnuGo pour aller jouer contre d'autres joueurs par exemple sur KGS. Tu devrais trouver rapidement d'autres débutants et c'est vachement plus sympa.


    (Ça me donne envie de rejouer tient, ça me changerait du poker)
    • [^] # Re: Il n'y a pas que l'explosion combinatoire

      Posté par (page perso) . Évalué à 2.

      >ça me changerait du poker)

      Y'a t'il de bon jeu de poker sous linux (en réseau)
      • [^] # Re: Il n'y a pas que l'explosion combinatoire

        Posté par (page perso) . Évalué à 2.

        Il y a pok3D qui a un client libre en 3D. Le jeu est encore en béta, mais on peut déjà jouer sur leur site. Il y avait une bonne ambiance en janvier avec des tournois gratuits et des utilisateurs qui tenaient un classement sur le forum.
        Actuellement les tournois sont suspendus donc c'est moins intéressant à mon sens (en partie libre, sauf si on joue des vrais sous, les parties sont lourdingues), mais ça va revenir il paraît.
        Et puis c'est développé par des Français.

        Sinon il y a des sites qui marchent avec une applet, et sont donc utilisables sous GNU/Linux si tu as une JVM suffisante.

        (Je ne colle pas d'URL ici parce que bon ça reste des sites de jeux d'argents limites légal (surtout depuis jeudi si j'ai bien compris (mais bon je suis joignable par les messages privés)))


        Pour le go je conseille KGS car j'y trouve l'ambiance bonne (mais je ne fréquente plus trop dernièrement).
        Pour le coup : http://www.gokgs.com/ (Nécessite Java lui aussi)
    • [^] # Re: Il n'y a pas que l'explosion combinatoire

      Posté par . Évalué à 1.

      Si tu avais lu l'article, tu te serais rendu compte que l'article est complet. Le début parle de l'explosion combinatoire et sa résolution avec l'algo UCT, puis parle de la fonction d'évaluation qui dans le Go est très importante.
      En effet, par rapport aux échecs par exemple, évaluer une position au Go est très difficile. L'algorithme présenté, du nom de Monte Carlo, est très intéressant, parcequ'il offre une manière simple et "relativement" rapide pour évaluer un coup. Son amélioration dans le cadre de MoGo est également pertinente. En résumé, le problème par le passé (la dernière fois que j'avais étudié la chose) était résolu grâce aux algo de reconnaissance de forme, et donc très complexe, et pas forcement pertinent. MonteCarlo s'amuse à remplir plus ou moins aléatoirement le reste du plateau, avec quelques règles simple, et évalue le score final. Avec plusieurs évaluation par position pour une moyenne.
      Cela montre que ce n'est pas toujours le plus complexe qui est le meilleur, ou qu'il faut un niveau de complexité nettement supérieur avant de pouvoir outrepasser les algorithmes dit "naif".
  • # ah ah

    Posté par (page perso) . Évalué à 4.

    2h30 euh aux échecs tu y as passé combien de temps avant de découvrir qu'il y avait des programmes d'ordis ? Tu as mis combien de temps à y jouer au niveau 3 (parce que bon le niveau 1...) et continuer à les battre ?

    Tu veux pas essayer plus longtemps pour le Go un peu quand même ?




    (c'est surtout que j'ai eu un peu le même souci alors bon, si ça peut m'économiser du temps et montrer que je ne suis pas le seul à être une tanche au Go même avec un peu plus d'acharnement... :p)

    PS : ya l'othello / reversi qui permet de se rassurer et reprendre l'ascendant sur la machine, non mais ! ;-)
    • [^] # Re: ah ah

      Posté par (page perso) . Évalué à 9.

      PS : ya l'othello / reversi qui permet de se rassurer et reprendre l'ascendant sur la machine, non mais ! ;-)


      Ca fait longtemps que l'homo sapiens se fait purger à l'othello. =)
    • [^] # Re: ah ah

      Posté par (page perso) . Évalué à 10.

      >> Tu veux pas essayer plus longtemps pour le Go un peu quand même ?

      Moi si je gagne pas tout de suite je me drape dans ma dignité et je part comme un prince ;-)
      • [^] # Re: ah ah

        Posté par . Évalué à 3.


        > >> Tu veux pas essayer plus longtemps pour le Go un peu quand même ?
        >
        > Moi si je gagne pas tout de suite je me drape dans ma dignité et je part comme un prince ;-)


        Il y a un proverbe qui dit: "perd tes 50 premières parties le plus vite possible"

        C'est effectivement un excellent moyen de rencontrer tous les coups de base, et ne plus se faire avoir comme un papoose :-)

        Une partie 19x19 vite jouée ne devrait pas prendre plus de 30-40 minutes. Si tu y passes 2 heures, tu réfléchis bien trop. Au Go tu ne peux pas vraiement te comporter comme un algo - c'est facile à comprendre : les ordi sont bien plus performant que toi pour ce genre de calculs, or ce sont des bouses à go... CQFD: ne calcule pas trop, vas-y au feeling, retiens les motifs, etc.


        (et personellement, je prefère perdre, tu peux mesurer ce que tu a apris pendant la partie, et progresser. Gagner... mouai... ca ne m'apporte pas grand chose)
  • # Le niveau moyen...

    Posté par . Évalué à 2.

    ... de gnugo est, il me semble, 15ieme kyu. (en lui laissant le temps de tourner...)

    Il y a 30 Kyu. (et des Dan ensuite)
    Comme tu viens de commencer, tu es 30ieme :)

    c'est comme un classement.

    donc a moins que tu arrive à un niveau proche du 15ieme kyu, tu ne risques pas de gagner... (et surtout sans maitriser certaines techniques de jeux basiques, tel que les yeux par exemple, tu risques de meme pas comprendre comment il ta battu)
    • [^] # Re: Le niveau moyen...

      Posté par (page perso) . Évalué à 7.

      D'après ses résultats sur kgs,il semblerait que gnugo soit plus proches de 7-8kyu actuellement.
      Le problème est que les classement des différents serveurs et échelles nationnales ne sont pas vraiment comparables.

      Qu'oi qu'il en soit je suis actuellement 2dan amateur sur kgs, et je donne sans problèmes 13 pierres d'avance à gnugo. La partie deviens sérée a 17 pierres, mais j'ai l'avantage sur gnugo que je connais ses faiblesses et je peux provoquer des situations ou je sais qu'il va se planter.

      Pour la petite histoire, un ami à voulut une fois tester gnugo à l'aveugle et sans que je le sache ma fait jouer plusieurs parties à handicap contre lui. Il a créé un compte humain et jouait les coups que gnugo lui indiquait.
      Les deux premières parties ont étée beaucoup plus sérée que mes parties habituelles de l'époque contre gnugo, mais à la troisième j'ai finit par repérer le style de gnugo et l'écraser.
      Preuve que l'écart de niveau viens aussi de l'exploitation des grosse faiblesses de ces programme.

      Ces pour quoi, à mon avis il y a deux choses à amméliorer dans les programmes actuels, ils doivent continuer leurs progrès, ce qui est la voie actuelle. Mais il est aussi nécéssaire de comprendre leurs faiblesses et de les corriger.

      La deuxième voie est plus ingrate puisqu'il y a peu de progès visible imédiatement, mais permet d'obtenir un niveau plus stable sur le long terme.

      Si mes souvenirs sont bon, lorsque les premiers programmes d'échec on commencé à battre les meilleurs humains, ils ne le faisait que sur les premières parties. Sur un nombre plus importants de parties l'humain sortait victorieux.
      • [^] # Re: Le niveau moyen...

        Posté par . Évalué à 2.

        D'après ses résultats sur kgs,il semblerait que gnugo soit plus proches de 7-8kyu actuellement

        Ça m'intrigue: je bat gnugo sur ma machine environ deux fois sur trois, et je doute d'être magiquement devenu 8 kyu sans jouer (la dernière fois que je jouais régulièrement sur KGS, j'étais 13 kyu). Gnugo aurait-il des paramètres par défaut qui le rendraient moins bon qu'un gnugo bien configuré ? (D'ailleurs, il joue très vite.)

        Quoi qu'il en soit, le plus gros reproche que je lui ferais, c'est que les parties ne sont pas très intéressantes. Il n'a pas de plan, aucune idée du plan de son adversaire, et quand il me bat c'est sur une erreur de calcul de ma part.
        • [^] # Re: Le niveau moyen...

          Posté par . Évalué à 2.

          Les logiciels ont une facon particuliere de jouer, donc c'est difficile de leur donner un rang. En gros, la strategie a adopter face a un logiciel est differente de celle a adopter contre un humain.

          Par exemple meme si tu bat gnugo, un joueur plus experimente que toi mais qui n'a jamais joue contre un ordinateur pourrait se faire battre parce qu'il ne connait pas les strategies qui marchent contre un programme.
        • [^] # Re: Le niveau moyen...

          Posté par (page perso) . Évalué à 3.

          Il y a beaucoup de bot basé sur GnuGo qui trainent sur KGS. Tous ne sont pas classé, et ceux qui le sont, n'ont pas tous le même classement.

          Le classement dépend de la version utilisée, la dernière stable de GnuGo, la 3.6, date quand même de fin 2004. Donc beaucoup de joueur qui mettent en place des bots utilisent une version de dévelopement. Mais comme c'est du developement et que chacun ne récupère pas la même révision, il y a pas mal de différences.

          Ensuite il y a la configuration qui influe énormément sur le niveau de jeu. Il y a plein de paramètres à tuner pour obtenir le meilleur de GnuGo. Les paramètres par défaut ne sont pas forcément les meilleurs, mais surtout des petits changements dans les paramètres peuvent influer sur la manière globale de jouer de GnuGo, et donc perturber un adversaire qui chercherait à exploiter les faiblesse classique. Mais en modifiant trop certains paramètres on obtient l'éffet inverse, GnuGo est capable de devenir une vrai merde si on lui demande gentillement...

          Bref tout ça pour dire que le niveau de GnuGo varie énormément d'un bot à l'autre sur KGS et que c'est parfaitement normal. Les meilleurs bots utilisant le moteur de GnuGo sont actuellement 7-8kyu c'est une constatation.

          Alors comment expliquer qu'un joueur 13kyu batte régulièrement un bot 7-8kyu :
          - 1ère possibilité, tu utilise une version plus vielle de GnuGo, qui à énormément évolué depuis,
          - 2ème possibilité, tu connais les faiblesses de GnuGo, ce qui n'est pas le cas de la majoritée des joueurs qui jouent avec lui sur KGS, donc sont niveau KGS ne reflète pas sont niveau face à joueur qui le connait bien,
          - 3ème possibilité, tu était 13kyu avant fin septembre 2006 date à laquelle l'échelle des niveau de KGS à été modifiée. Avec cette modification les joueurs 13kyu on gagner en gros 4kyu, donc tu te serrai retrouver 9kyu. Cette modification à été fait pour compenser la dérive de l'échelle de KGS et pour rapprocher l'échelle de KGS des échelles nationale.

          En combinant les trois on arrive a une victoire faicle de ta pars contre GnuGo...
  • # au go

    Posté par . Évalué à 3.

    L'avantage c'est que tu peux toujours prendre un handicap pour jouer avec quelqu'un de plus fort que toi.

    Je te conseille quand meme de prendre un bouquin pour apprendre la base des strategies.

    A part ca, si c'est vrai que les programmes de Go se font battre par des pro, ils arrivent tres bien a bout d'amateurs comme moi...
  • # Taille de goban

    Posté par . Évalué à 10.

    Merci pour le lien. Je suis moi-même un joueur de go régulier, et cet article m'a vraiment intéressé.

    Par contre, progresser sur le goban 9*9 - et même 13*13 - n'apporte pas forcément de progrès sur la vraie taille de goban 19*19. Il faut savoir que l'aspect stratégique du jeu est presque entièrement détruit sur ces petits goban, et qu'il se limite principalement à des problèmes de "lecture" et de "vie et mort". Or, ça fait un moment que les programmes de go ont un niveau raisonnable sur ces deux points.

    Pour rassurer l'auteur du journal, je démolis gnugo en lui donnant 9 pierres de handicap, et je suis pourtant encore loin du niveau des forts joueurs. Notamment, le programme fait de temps en temps des fautes catastrophiques, qui permettent d'anéantir toute une position. Quand on a l'habitude des programmes de go, il est facile de construire volontairement des situations qui pousse le programme à la faute. C'était vrai en 1997, et malgré de petits progrès, ça reste vrai aujourd'hui.

    Je donnerais un seul exemple : celui des séquences classiques dans les coins. Contre un joueur humain, il est souvent dangereux de s'en écarter parce que si jamais l'adversaire connaît une "réfutation", ça peut faire très mal. Contre un ordinateur, c'est l'inverse. Il connaît la séquence classique, et donc si on ne s'en écarte pas, le résultat final va être "équilibré". Du coup, pour perturber le programme, il suffit de s'écarter très vite des séquences habituelles, quitte à faire des mauvais coups pour ça. Le programme se retrouve vite dans le noir complet et son niveau baisse dramatiquement.

    Allez, message subliminal: n'hésitez pas à faire l'effort d'apprendre le jeu de go. Le démarrage est un peu difficile, mais ça se révèle vite un jeu passionnant.
    • [^] # Re: Taille de goban

      Posté par . Évalué à 2.

      je ne suis pas joueur de go, mais l'article m'a bien intéressé également, même si je n'ai pas toujours tout compris dans le détail.
      J'avais déjà tâtonné un peu le go (gnugo), cela m'a donné envie de m'y remettre, et peut-être de m'inscrire sur un serveur avec de vrais joueurs !

      Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

      • [^] # Re: Taille de goban

        Posté par . Évalué à 1.

        J'ai appris beaucoup de choses, mais il m'a semblé que l'article n'était pas très clair.

        Merci à l'auteur du journal, en tout cas.
  • # LiveCD spécial Go

    Posté par . Évalué à 5.

    Il y aussi l'excellent LiveCD dédié au Go (pour tous les niveaux, bonne documentation pour commencer) :
    http://www.hikarunix.org/

    (Basé sur DSL)
  • # jeudego.org

    Posté par (page perso) . Évalué à 5.

    Voilà un site pour apprendre le go : http://jeudego.org/mori/mori_set.htm

    Au moyen d'applets Java, Il propose des problèmes de difficulté croissante. J'ai trouvé les explications excellentes et la progression est régulière.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.