C’est vrai que les précédents programmes étaient mauvais quand plusieurs ko étaient simultanément ouverts et s’il reste une mini-chance c’est probablement de ce coté à condition que la situation arrive très tôt dans la partie.
Lexploration guidée par des patterns de jeu humain est visiblement suffisamment efficace de ce coté. Je n’ai même pas l’impression qu’ils aient cherché à apprendre des patterns locaux contrairement à ce qui se faisait jusque la.
jeremie dit :C'est vrai que les précédents programmes étaient mauvais quand plusieurs ko étaient simultanément ouverts et s'il reste une mini-chance c'est probablement de ce coté à condition que la situation arrive très tôt dans la partie.
L'exploration guidée par des patterns de jeu humain est visiblement suffisamment efficace de ce coté. Je n'ai même pas l'impression qu'ils aient cherché à apprendre des patterns locaux contrairement à ce qui se faisait jusque la.
Oui il y avait des situations ou les logiciels ne comprenait pas le truc et jouait alors de très mauvais coups.
Pit0780 dit :jeremie dit :Officiellement, il y a 6 mois, des programmes comme CrazyStone et Zen19d étaient autour de la 6-7 ème dan sur KGS avec des machines relativement raisonnables (32 coeurs et sans GPU). Leur progression était relativement lente mais réelle depuis 2008 environ. Un prolongement de la tendance de développement conduisait à penser que les machines gagneraient dans 7 à 10 ans. L'utilisation de réseaux à convolution pour l'apprentissage des patterns de jeu et des évaluations de parties a été l'élément décisif.
Pour le nombre d'atomes dans l'univers, on ne le connaît certes pas avec précision, mais 10^170 semble une borne assez fiable dans la mesure ou l'estimation du nombre d'atomes de l'univers visible est majoré par 10^84 (Environ 10^57 atomes pour une étoile).
Et même en argumentant sur le fait qu'il existerait une partie de l'univers invisible car trop lointaine, tu ne pourrais pas l'utiliser pour stocker des bits d'information sur les positions de jeu. Impossible donc de construire une machine capable d'explorer exhaustivement le jeu de Go sans un très gros progrès sur les ordinateurs quantiques.Ah mais qu'il y a eu d'énormes progrès là dessus, j'en doute pas !
Ce que je veux dire, c'est qu'il est logique qu'aujourd'hui, on parvienne à construire une machine capable de gagner au Go.
Ca ne pouvait qu'arriver, tôt ou tard, et ce n'est que le début.
C'est pour ça que je ne suis absolument pas surpris.
C'est plus compliqué qu'une simple question de puissance de calcul. On s'est rendu compte dès les années 1970 que la puissance de calcul brute ne suffirait jamais à construire des « intelligences artificielles », parce qu'on s'est vite rendu compte que certains problèmes étaient soient complètement insolubles par le calcul (problèmes indécidables nécessitant un temps de calcul infini), soient qu'ils demandaient des temps de calculs faramineux (« seulement » exponentiels). Ces problèmes demandent des temps de calcul supérieurs à la progression de vitesse des ordinateurs. Résoudre le Go par calcul brut nécessiterait déjà un temps de calcul supérieur à l'âge de l'univers connu. Même en supposant que la progression actuelle des puissances de calcul suive son cours, il ne sera jamais résolu avant la fin de vie du Soleil.
D'où l'exploit, justement en trouvant d'autres techniques que le calcul brut, sans doute plus proches du fonctionnement de l'intuition humaine.
Yep. Pour mettre quand même un bémol, le nombre d’états possibles d’un jeu n’est pas un bon indicateur de sa complexité.
Pour l’exemple idiot, imaginons un jeu comme le Go, sans capture de pion ou l’on décide que le gagnant est celui posant la dernière pierre. Ce jeu est trivial, 361 emplacements possibles, le premier à jouer gagne systématiquement cependant le nombre d’états possibles est proche de celui du Go.
jeremie dit :Yep. Pour mettre quand même un bémol, le nombre d'états possibles d'un jeu n'est pas un bon indicateur de sa complexité.
Pour l'exemple idiot, imaginons un jeu comme le Go, sans capture de pion ou l'on décide que le gagnant est celui posant la dernière pierre. Ce jeu est trivial, 361 emplacements possibles, le premier à jouer gagne systématiquement cependant le nombre d'états possibles est proche de celui du Go.
Oui mais dans ton exemple il n'y a pas vraiment de difficulté à calculer la solution, puisque ta règle "annule" le pertinence d'une case par rapport à une autre. C'est la règle qui fait que les états sont inutiles.
Oui c’est juste pour illustrer que la complexité d’un jeu n’est pas forcément directement liée au nombre d’états possibles car un grand nombre d’entre eux peuvent être équivalents.
Au go, Le fait que les réseaux à convolution arrivent à apprendre efficacement le coup suivant, ainsi qu’à évaluer les positions de jeu est d’ailleurs un signe que dans un nombre important de cas, déplacer quelques pièces d’une case n’est pas toujours important.
Lee Sedol vient de gagner la 4
Je me pose des questions sur la gestion du temps par Alphago.
Sur les 3 dernières parties (2,3,4, au passage bravo à Lee Sedol pour sa victoire), Lee Sedol s’est retrouvé en difficulté au niveau du temps.
Quelqu’un sait-il comment ce paramètre est géré par Alphago ? Comment détermine-t-il son temps de réflexion ?
Et surtout, tient-il compte du ratio avec le temps restant de son adversaire dans ses prises de décisions ?
Autrement dit si par exemple son adversaire est en difficulté niveau temps comme ce fut le cas, va-t-il privilégier des positions complexes pour le pousser à l’erreur ?
Ou alors fait-il complètement abstraction de ce paramètre, en cherchant systématiquement le meilleur coup dans l’absolu ?
L’honneur est sauf ! Une victoire qui prouve qu’Alphago n’est pas invincible.
Pour le temps d’AlphaGo a priori il est dépendant de la variance de l’estimation du meilleur coup estimé par rapport aux autres possibilités dans les simulations de montecarlo et du temps restant.
Pour la victoire, il est intéressant de savoir si Lee Sedol a identifié une faille ou si c’est un coup de chance. En octobre il arrivait encore -mais très rarement- a AlphaGo de perdre contre un autre programme pourtant bien moins fort.
En rédigeant ce message, je me rend compte qu’une faiblesse possible est la multiplication de positions de jeu ou déplacer une pierre blanche ou noire a distance 1 conduit a des situations de jeu très différentes et à l’avantage de blanc ou noir selon la position de la pierre. Je ne sais pas si c’était le cas dans cette partie.
En tout cas ça fait bien plaisir ! J’étais bien content pour Sedol, parce qu’il s’est battu et avait l’air vraiment heureux.
Visiblement son 78ème coup a été un tournant et a surpris tout le monde, la machine l’a mal évalué et s’est enfoncée. Bon, en même temps c’est difficile de comprendre pourquoi, j’y arrive avec les échecs quand on m’explique, mais le Go c’est une autre paire de manches 
Lee a déclaré à propos de ce coup qu’il était pour lui le seul coup envisageable.
En fait, la partie était perdante et vraiment cata pour Lee et il était question dans les commentaires internet d’abandonner. L’AI à joué après ça des coups très étrange et objectivement mauvais pour certains. Ça donnait vraiment l’impression de bug de la machine qui n’avait pas été vu jusque là.
Et Lee a pris l’avantage.
c’est difficile de comprendre ce qui s’est passé pour la machine.
Je retiens l’état d’esprit de Lee qui a montré une motivation et une combativité incroyable. On aurait dit qu’il croyait en ses chances alors qu’il s’était fait bien démonté depuis le début dans tous les compartiments du jeu et peu de personne y croyait encore.
ça faisait vraiment plaisir à voir.
pour rappel, après la deuxième partie, il a étudié la partie avec ses potes jusqu’à 6h du matin avant le jour de repos. Ces joueurs pro sont exceptionnels, ils s’entraînent tout le temps et ne vivent que pour le go.
Il a fini par prendre ce match pour celui de sa vie et il a déclaré après qu’il echangerais cette victoire pour rien au monde.
Pour la dernière partie, après sa victoire avec blanc, il a demandé à DeepMind de prendre noir pour tenter de battre alphago avec noir ce qui est réputé plus difficile à cause du komi élevé.
J’ai beau être persuadé qu’une victoire d’AlphaGo serait aussi une forme de victoire pour l’Humanité, je suis bien content que Sedol ait réussi à éviter la défaite totale ! Très prenant ce défi, même pour un non-joueur de Go comme moi.
J’ai une petite question pour les experts en IA.
J’ai bien compris que la taille de l’arbre décisionnel était un des freins principaux pour l’analyse en force brute, avec ses quasi 300 coups différents à chaque tour. Mais je me demande dans quelle mesure la symétrie du plateau de jeu (et éventuellement des patterns globaux ou locaux) pourrait simplifier l’arbre ?
Après tout, au premier tour, jouer sur une case quelconque correspond à la même situation sur les 3 autres cases symétriques (symétries axiales et centrale). De même, le 2ème coup peut être analysé relativement au premier et pas comme une possibilité parmi 299, non ?
La symétrie du plateau n’a rien à voir avec le calcul, c’est un jeu de conquête de territoires. Ce sont les positions et les paterns de pierres qui jouent 
Si, il y a quand même des symétries en tout début de partie : le plateau peut être inversé sur les deux axes ou subir une rotation de 90° une, deux ou trois fois. Au mieux, si on prend ça en compte, ça divise par 16 le nombre de situations de jeu différentes (faire les 2 inversions est équivalent à la rotation de 180°). C’est peanuts par rapport au reste de la combinatoire. En plus, dès qu’il y a des pierres qui cassent cette symétrie, ça ne marche plus.
De toute façon, il est évident que l’intelligence artificielle est devenue supérieure à l’humain: la preuve, le programme a fait exprès de perdre une manche afin de ne pas trop effrayer l’humanité et lui laisser croire qu’elle possède encore un certain contrôle sur l’avenir. Pendant ce temps là, quelque part dans le monde, une usine entièrement automatisée fabrique des machines de guerre en série… merci skynet!
Bah quoi? 
@scand1sk Le premier coup casse tout les axes de symétrie sauf un, s’il est joué sur une médiane (sauf à jouer exactement au milieu du plateau mais au go, c’est con).
Il n’y a pas beaucoup à “réfléchir” sur un goban vide non plus…
Merci scand1sk pour ta réponse et ta correction du nombre de cas similaires (j’avais bêtement zappé les axes diagonaux).
De tout façon, c’est plus pour papoter que pour trouver une solution nouvelle d’optimisation. Ceux qui sont derrière AlphaGo doivent avoir passé en revu un nombre incroyable de paramètres et pistes diverses. Je serai curieux de savoir quels profils sont aux commandes (hors l’IA de skynet bien sûr ^^) : mathématiciens purs, neuro-biologistes, etc ?
LEauCEstNul dit :@scand1sk Le premier coup casse tout les axes de symétrie sauf un, s'il est joué sur une médiane (sauf à jouer exactement au milieu du plateau mais au go, c'est con).Là, je ne comprend pas.
La 1ère pierre, placée n'importe où, correspond à plusieurs situations de jeu similaires qu'il est inutile d'analyser.
Si je suis dans le faux et que tu ne souhaites pas noyé le fil, tu peux me préciser en MP si tu veux. :)
Y a pas matière à réfléchir 600 ans là dessus…
L’adversaire a joué une pierre, placée à x cases horizontalement et verticalement d’un point de repère type “bord de plateau” => la réponse qui m’a fait gagner 45194 parties contre moi-même fut “celle-ci” donc je joue “celle-ci”.