Journal Les échecs en échec

Posté par  (site web personnel) . Licence CC By‑SA.
44
7
déc.
2017

Le jeu d'échecs ont souvent été un lieu d'expérimentation pour l'informatique et particulièrement l'application de la théorie des jeux et l'intelligence artificielle. Il serait un peu long de retracer l'histoire des échecs et de l'informatique et ce d'autant plus qu'une page Wikipedia y est consacrée.

Pour mémoire le jeu a basculé en 1996 lorsque le programme Deep Blue d'IBM a battu le champion du monde Garry Kasparov.

Depuis un peu plus de vingt ans le fossé n'a cessé de se creuser entre joueurs et ordinateurs, le premiers atteignant un niveau de 2800 points élo alors que les seconds sont évalués à environ 3300 rendant toute confrontation stérile.

Pour autant les principes qui s'appliquaient à un moteur d'échecs reposaient sur les principes suivant: une bibliothèque d'ouverture qui compilait un grand nombre de partie jouées dans le passé, un milieu de partie ou le calcul pur était mis au service d'un algorithme alpha beta et des fonctions d'évaluation des positions obtenues à l'horizon du calculable.

Autrement dit les programmes reproduisaient le comportement humain en y ajoutant une capacité de calcul que le développement des processeurs fournissait allègrement.

PUIS VINT ALPHA ZERO.

Oui c'est bien le dernier rejeton de la société DeepMind dont il s'agit, successeur d'AlphaGo cette machine a pu en 9 heures devenir le meilleur programme d'échecs capable d'infliger à StockFish, champion du monde 2016 des modules d'échecs un score de 28 gains contre 0 sur cent parties. C'est phénoménal mais en outre dans la même journée Alphazero serait devenu le programme le plus puissant au Go et au ShOGI.

Seuls sont implémentées les règles des jeux, le deep learning et les ajustements automatiques des réseaux neuronaux faisant le reste.

Quelques liens: https://arxiv.org/abs/1712.01815 pour le papier.
Une vidéo de Blitzstream: https://www.youtube.com/watch?v=PH06mEOVVyY&list=LLcXH6W9ey_h8LEx2lFxp5fg&index=1

Je ne veux pas me lancer sur une réflexion sur la venue de la singularité et le transhumanisme même si le sujet laisse des portes grandes ouvertes sur la question. Par contre je me pose la question de savoir à quel moment un jeu peut être considéré comme résolu? A défaut de prouver une stratégie gagnante définir un programme invincible semble le terme du jeu.

  • # jeu résolu

    Posté par  . Évalué à 10.

    Par contre je me pose la question de savoir à quel moment un jeu peut être considéré comme résolu? A défaut de prouver une stratégie gagnante définir un programme invincible semble le terme du jeu.

    Un programme invincible ne te dit pas du tout que le jeu est résolu (tant que tu ne peux pas reproduire toi-même la stratégie gagnante, le jeu n'est pas résolu). Le jeu d'échec est loin d'être résolu, puisque d'après l'article AlphaZero utilise toute une variété d'ouvertures, et donc ne reproduit pas une stratégie unique : il sait gagner en jouant des parties diversifiées. Du coup, il n'a pas résolu le jeu, il est juste super-bon.

    Formellement, il y a plusieurs niveaux dans la résolution du jeu. Tu dois d'abord prouver que le jeu peut être résolu, ce qui n'est pas encore fait aux échecs (on ne sait pas si la meilleure stratégie blanche mène à la victoire ou à une partie nulle, on pense que ça mène au match nul mais ça n'est pas prouvé—formellement, on pourrait aussi aller à la victoire des noirs, mais ça surprendrait vraiment tout le monde. La raison pour laquelle on penche vers la nulle est qu'un joueur qui joue les noirs et qui n'a qu'à annuller la dernière partie pour gagner un match y arrive assez facilement ; il suffit d'échanger les pièces jusqu'à la nulle par manque de matériel.

    Si tu sais que ton jeu peut être résolu, il faut ensuite déterminer la meilleure stratégie (suite de coups qui mène à la victoire des blancs malgré la meilleure défense des noirs). Tu peux considérer à ce stade que le jeu est résolu. Sauf que si tu ne sais pas comment répondre à un coup sous-optimal des noirs, en pratique, tu ne vas pas gagner à tous les coups. Il te faut donc connaitre la stratégie qui mène à la victoire à partir de n'importe quelle réaction des noirs. Et là, tu as résolu ton jeu. Mais techniquement, il n'est pas dit que ça soit faisable pour les échecs. Même si tu contrôles les blancs (et donc, tu n'as pas à envisager tous les coups possibles des blancs), et qu'en moyenne les noirs ont 20 coups légaux, pour une partie qui s'achève en 40 coups, il te reste quand même 1052 parties à mémoriser… Si tu te concentres que sur 3 coups possibles (en partant du principe que les 17 autres coups sont tellement mauvais que tu serais capable de gagner sans l'algorithme optimal), tu restes à 1019 parties, ce qui semble difficilement faisaible avec le matériel informatique d'aujourd'hui… Bref, au delà des problèmes de calcul, stocker quelque part les suites de coups qui te permettent de gagner à tous les coups n'est peut-être même pas faisable.

    Ceci dit, d'énormes progrès ont été faits sur les fins de parties, et je crois que toutes les fins à moins de 8 pièces sont résolues dans toutes les positions, par exemple. Honnêtement, rien qu'avec ça, tu bats n'importe quel joueur humain, à moins d'arriver en fin de partie avec un gros handicap. C'est vraiment le milieu de partie qui pose problème.

    • [^] # Re: jeu résolu

      Posté par  (site web personnel) . Évalué à 3.

      Merci pour cette réponse, j'ai parfaitement en tête ce qu'est un jeu résolu mais je n'aurais pas pu l'exprimer aussi clairement.
      Ce n'était donc pas ce que j'avais en tête en parlant de résolution du jeu mais plutôt d'une sorte de résolution liée aux limitations du joueur humain et des approches heuristiques d'un jeu id est les approches humaines assistées par informatique pour pallier au déficit de puissance de calcul d'un cerveau même génial.
      Ici un programme très fort pour reprendre ton expression utilise une démarche à priori complétement différente pour parvenir à un résultat meilleur et inaccessible à un être humain fût il particulièrement génial ce qui est, à mon sens, mais pas au sens mathématique je te l'accorde humblement, une forme de résolution du jeu.

      • [^] # Re: jeu résolu

        Posté par  . Évalué à 5.

        une forme de résolution du jeu

        Je ne suis pas sûr de te suivre. Par définition, le jeu est résolu quand tu as trouvé la stratégie optimale—ou plus exactement quand tu as prouvé que tu as trouvé la stratégie optimale. Ton problème, c'est que ta définition de "résolution" tient au seul fait que tu n'as pas encore trouvé de stratégie meilleure, ce qui est une défintion super faible (en gros, tu définis "mon programme résoud le jeu" par "mon programme est le meilleur", ce qui n'a honnêtement pas grand chose à voir : à ce compte-là, DeepBlue avait déja résolu le jeu, ainsi que toute la série des meilleurs joueurs du monde avant lui). Bon, je te l'accorde, la force de AlphaZero c'est de n'avoir jamais perdu, ce qui n'exclut pas qu'AlphaZero ait peut-être résolu le jeu d'échecs (ce qui voudrait dire que la partie optimale est nulle). Une seule défaite, et tu prouves qu'AlphaZero n'a pas résolu le jeu (à moins que même en jouant parfaitement les blancs perdent, ce qui serait douteux).

        Bref, en résumé, non, je ne pense pas qu'on puisse conclure quoi que ce soit sur la résolution du jeu d'échecs. AlphaZero est un algo qui est très très fort, et visiblement plus fort que n'importe quel autre algo. Il est possible qu'AlphaZero ait résolu le jeu, mais c'est très peu probable. Il est certain que le jeu d'échecs a une solution, mais il n'est pas certain que cette solution soit un jour trouvée, et il n'est pas du tout garanti qu'un mécanisme informatique soit un jour en mesure de stocker cette solution pour l'utiliser pour gagner.

        • [^] # Re: jeu résolu

          Posté par  . Évalué à 3.

          En fait, il faudrait savoir comment il joue contre lui-même. S'il a réellement résolu le jeu, il devrait jouer toutes les parties avec le même nombre de coups, et toutes les parties devraient se terminer par le même résultat. Au passage, comme il utlise plusieurs ouvertures distinctes, ça voudrait dire qu'il y a plusieurs manières de jouer la partie optimale. Mais bon, je doute que ça soit le cas (les auteurs l'auraient facilement remarqué), donc il n'a pas résolu le jeu ; il joue vachement bien, mais il joue parfois des coups qui ne permettent pas la victoire/la nulle en un nombre minimum/maximum de coups quand il joue les blancs/les noirs.

          • [^] # Re: jeu résolu

            Posté par  (site web personnel) . Évalué à 3.

            S'il a réellement résolu le jeu, il devrait jouer toutes les parties avec le même nombre de coups, et toutes les parties devraient se terminer par le même résultat.

            Résoudre le jeu ne veut pas forcément dire trouver le nombre de coup minimum pour obtenir le meilleur résultat. Par contre effectivement toutes les parties devraient se terminer par le même résultat.

            • [^] # Re: jeu résolu

              Posté par  . Évalué à 4.

              les meilleurs joueurs ont pris l'habitude de mémoriser des ouvertures de plusieurs dizaines de coups,

              Après, ça dépend de la subtilité de la définition, mais si tu as complètement résolu mathématiquement un jeu, tu es censé pouvoir donner la solution la plus courte… Regarde pour un problème d'échecs (ce qui est exactement la même chose que de résoudre le jeu, sauf qu'on commence avec une position très avancée), la solution est généralement unique, et c'est celle qui présente le moins de coups possible. Si tu captures une pièce majeure au lieu de faire mat, tu arriveras sans aucun doute à gagner la partie après 30 autres coups, mais tu n'as pas résolu le problème posé.

              Du coup, pour moi, "résoudre les échecs", c'est comme résoudre un problème d'échecs à partir de la position initiale : les blancs jouent et font mat. Implicitement, forcément, ça sous-entend "avec le moins de coups possibles".

              Empiriquement, une IA qui a résolu le jeu pour les noirs et pour les blancs devrait toujours terminer avec le même résultat avec le même nombre de coups (il peut toujours y avoir plusieurs variantes, ça n'est pas forcément la même partie qui est toujours jouée, mais elle se termine toujours pareil). Bien sûr, cette IA contre un algorithme moins fort pourra terminer en moins de coups, mais contre elle-même, elle devrait toujours terminer dans le nombre minimum de coups (pour le gagnant) et le nombre maximum de coups (pour le perdant).

              À noter que si le meilleur résultat possible pour les blancs est une partie nulle, alors la stratégie "résolue" est de demander la nulle avant le premier coup, ce que les noirs vont accepter (vu que la nulle est aussi le meilleur résultat pour eux).

              Ceci dit, ce critère n'est pas non plus passionnant. Une IA qui a résolu le jeu jouera toujours des parties avec le même résultat dans le même nombre de coups contre elle-même. Mais jouer toujours la même partie ne prouve absolument pas qu'on ait résolu le jeu, on peut utiliser ce critère pour montrer que l'IA n'a pas encore résolu le jeu, mais pas qu'elle l'a fait.

        • [^] # Re: jeu résolu

          Posté par  (site web personnel) . Évalué à 2.

          En écrivant ma réponse j'ai eu conscience de la faiblesse de ma définition de la résolution du jeu d'échecs, effectivement le meilleur joueur ou programme à un moment donné pourrait prétendre avoir résolu le jeu si personne n'est capable de le battre…
          D'un autre côté une preuve mathématique d'une telle résolution, telle que tu la décris, supposerait non seulement une puissance de calcul mais surtout de stockage difficilement imaginable en terme physique.Ce que j'essaie d'imaginer c'est une forme de preuve qui ne serait pas parfaite mais suffisante intellectuellement, une sorte de preuve au sens légal plus que mathématique. Tout simplement parce que c'est la seule qui nous serait accessible. Mais je m'égare sans doute.

      • [^] # Re: jeu résolu

        Posté par  (site web personnel, Mastodon) . Évalué à 4.

        On peut encore faire jouer des ordinateurs entre eux. Donc pour l'instant on a un ordinateur vraiment très bon, mais on peut peut-être encore en faire un capable de le battre. Le jeu sera résolu quand on aura prouvé qu'un ordinateur est imbattable.

        Pour la petite histoire: la victoire de Deep Blue est due à… un bug, qui lui a fait jouer un coup innatendu. Cela a déstabilisé son adversaire qui a ensuite perdu la partie.

        • [^] # Re: jeu résolu

          Posté par  . Évalué à 3.

          Cela a déstabilisé son adversaire qui a ensuite perdu la partie.

          C'est une stratégie courante pour les joueurs humains qui affrontent de très bons théoriciens. Il faut jouer un coup sous-optimal dès l'ouverture, qui fait rapidement sortir la partie de la théorie, afin de se retrouver à armes égales (on trouve plein d'exemples rigolos sur Youtube, même entre grands maîtres).

          Stratégie totalement inefficace contre la plupart des ordinateurs… sauf peut-être AlphaZero, paradoxalement!

    • [^] # Re: jeu résolu

      Posté par  (site web personnel) . Évalué à 4.

      Formellement, il y a plusieurs niveaux dans la résolution du jeu. Tu dois d'abord prouver que le jeu peut être résolu, ce qui n'est pas encore fait aux échecs (on ne sait pas si la meilleure stratégie blanche mène à la victoire ou à une partie nulle, on pense que ça mène au match nul mais ça n'est pas prouvé—formellement, on pourrait aussi aller à la victoire des noirs, mais ça surprendrait vraiment tout le monde.

      Là tu confonds: On sait que le jeu peut être résolu, c'est un théorème fondamental pour ce type de jeu. Par contre on ne sait pas quel est le résultat du jeu résolu.

      La raison pour laquelle on penche vers la nulle est qu'un joueur qui joue les noirs et qui n'a qu'à annuller la dernière partie pour gagner un match y arrive assez facilement ; il suffit d'échanger les pièces jusqu'à la nulle par manque de matériel.

      Ce n'est pas un argument, cela ne s'applique qu'au joueurs humains. La raison pour laquelle on penche pour la nulle est que statistiquement il y a plus de nulles avec le niveau augmentant que ce soit humain ou machine.

      Si tu sais que ton jeu peut être résolu, il faut ensuite déterminer la meilleure stratégie (suite de coups qui mène à la victoire des blancs malgré la meilleure défense des noirs).

      Ceci n'est pas la définition de résolution, la résolution c'est quand tu connais la victoire quelque soit la défense

      Tu peux considérer à ce stade que le jeu est résolu. Sauf que si tu ne sais pas comment répondre à un coup sous-optimal des noirs, en pratique, tu ne vas pas gagner à tous les coups. Il te faut donc connaitre la stratégie qui mène à la victoire à partir de n'importe quelle réaction des noirs. Et là, tu as résolu ton jeu.

      Ca c'est la définition de la résolution faible. La résolution forte d'un jeu est d'obtenir le meilleur résultat possible à partir d'une position arbitraire, par exemple, noir gagne si blanc fait une erreur.

      Ceci dit, d'énormes progrès ont été faits sur les fins de parties, et je crois que toutes les fins à moins de 8 pièces sont résolues dans toutes les positions, par exemple. Honnêtement, rien qu'avec ça, tu bats n'importe quel joueur humain, à moins d'arriver en fin de partie avec un gros handicap. C'est vraiment le milieu de partie qui pose problème.

      La plupart des parties se terminent avec un "gros" handicap. A peu près tout pose problème aux êtres humains. Début, milieu et fin de partie.

  • # Point fixe

    Posté par  . Évalué à 6.

    Seuls sont implémentées les règles des jeux, le deep learning et les ajustements automatiques des réseaux neuronaux faisant le reste.

    Ce serait dommage de réduire Alpha(Go) Zéro au côté deep learning, l'idée d'apprendre une fonction de probabilité des coups par itération au point fixe sur la recherche arborescente de monte-carlo est quand même très très jolie. Surtout que si on en croit les auteurs, c'est ça qui permet de faire un apprentissage de zéro, par rapport à un apprentissage par renforcement qui n'est pas stable.

    • [^] # Re: Point fixe

      Posté par  (site web personnel) . Évalué à 4.

      Exact, j'avais omis la question de la méthode de Monte Carlo dans la description de l'algorithme, ce point est évoqué dans la vidéo est semble constituer une surprise quant à son efficacité qui n'avait jamais été mise en évidence dans les programmes d'échecs malgré de précédents tentatives.

      • [^] # Re: Point fixe

        Posté par  . Évalué à 2.

        On dirait qu'on avait déjà toutes les techniques qu'ils utilisent sous la main. Qu'est-ce qui est nouveau? Pourquoi ça marche maintenant et ça ne marchait pas avant?

        Est-ce qu'on pourrait faire un réseau de neurone collaboratif ou tout le monde file un peu de puissance de calcul? (tout le monde a le réseau de neurones et on parallélise l’entraînement, monte-carlo c'est super parallèle)

        • [^] # Re: Point fixe

          Posté par  (site web personnel) . Évalué à 3.

          Si tu regardes la vidéo de Blitzstream tu verras que Mathieu Acher, la caution informatique de la vidéo, pense que l'algorithme est reproductible et évoque la possibilité d'une implémentation open source. Tu peux le cas échéant lui soumettre l'idée.http://mathieuacher.com . Il semblait plutôt s'orienter vers une fondation pouvant utiliser (louer?) un gros système et payer la note d'électricité afférente. Mais c'est vrai qu'un calcul distribué serait d'avantage dans l'esprit.

    • [^] # Re: Point fixe

      Posté par  . Évalué à 10.

      fonction de probabilité des coups par itération au point fixe sur la recherche arborescente de monte-carlo

      FOUTAISE !

      • [^] # Re: Point fixe

        Posté par  (site web personnel) . Évalué à 4.

        L'idée est développée en haut de la page 3 du pdf, ce n'est pas beaucoup plus clair. De ce que j'ai compris l'algorithme consiste à choisir de manière aléatoire un certain nombre de positions possibles à venir puis à les évaluer successivement, mais mon anglais ne me permet pas de proposer une traduction.

        • [^] # Re: Point fixe

          Posté par  . Évalué à 3.

          Je pense que c'est une reference a ca.

          • [^] # Re: Point fixe

            Posté par  (site web personnel) . Évalué à 4.

            J'avais compris la référence mais le commentaire visé même assez abscons soulevait un point tout à fait pertinent et méritait plus qu'une simple remarque sur le style.

            • [^] # Re: Point fixe

              Posté par  (site web personnel, Mastodon) . Évalué à 3.

              Je pense plutôt que pour lui, comme pour moi, la citation qu’il fait est remplie de « gros mots » incompréhensible, et sortir un « foutaise » la dessus est plutôt un trait d’humour.

              • [^] # Re: Point fixe

                Posté par  . Évalué à 3.

                Bon je stoppe ce suspens insoutenable : c'était bien une référence au business loto et c'était bien pour faire un trait d'humour. Plus sérieusement, je trouve le sujet passionnant et je suis bien content que Shuba tente de le vulgariser. Mais l'occasion était trop belle quand même ;)

                • [^] # Re: Point fixe

                  Posté par  (site web personnel) . Évalué à 4.

                  Je peux comprendre la difficulté de résister à un bon mot, ceci dit pour moi FOUTAISE! renvoie à une phrase composée uniquement de buzzwords au mépris du sens.

                  • [^] # Re: Point fixe

                    Posté par  . Évalué à 3. Dernière modification le 08 décembre 2017 à 16:44.

                    C'était juste une blague le prend pas mal.

                    Je pense que pour une bonne partie des lecteurs (dont moi) c'est assez abscons. En tout cas même si je ne comprends pas tout, ça m'intrigue et je trouve plaisant que le sujet soit développé. Mais j'ai pas pu m'empêcher désolé ;)

                    • [^] # Re: Point fixe

                      Posté par  (site web personnel) . Évalué à 2.

                      J'ai oublié de préciser que ton commentaire m'avait fait sourire.

                    • [^] # Re: Point fixe

                      Posté par  . Évalué à 5.

                      Pour rebondir là-dessus, si tu veux faire une référence culturelle amusante, je pense qu'une sortie comme "kamoulox!" aurait été bien plus drôle que "FOUTAISE".

                      La première raison, c'est que quand on fait une référence, il y a toujours une probabilité non-nulle pour que l'autre passe à côté. Ça peut être une question de culture, de génération, d'origine géographique. Or, "FOUTAISE", c'est un mot qui est très agressif, c'est proche de l'insulte. Pour ton plaisir à faire un bon mot, tu prends le risque d'offenser quelqu'un d'autre ; c'est un comportement courant, mais je pense qu'il est à l'origine de la très mauvaise ambiance qui règle "sur les internets", où l'insulte, l'invective et la moquerie sont systématiques.

                      L'autre raison, c'est que je pense que tu utilises mal la référence. Le principe du business loto, c'est de se moquer de la novlangue pseudoscientifique et pédante qui a la cote dans certains milieux. Quand tu cries "Foutaise!", tu impliques que ton interlocuteur manie des concepts creux qui ne veulent rien dire, tu te moques de lui.

                      Là, en fait, tu voulais simplement dire que la phrase était trop technique et que tu n'avais rien compris. J'imagine que tu ne voulais pas impliquer que tes interlocuteurs était des marketteux qui cachaient du vide derrière des mots complexes. Ton "Foutaise" est donc beaucoup plus insultant que tu le voulais, parce que je pense que tu maitrises mal ta référence culturelle. Donc voila, il faut faire un peu attention.

                      PS: je ne pense pas être une grosse quiche en stats, mais j'avoue que la phrase m'avait fait sourire parce que je n'ai aucune idée de ce qu'elle voulait dire.

                      • [^] # Re: Point fixe

                        Posté par  . Évalué à 3.

                        L'impertinence et l'universalisme de sa réaction, l'universalisme qui est une propriété essentielle de l'humour—il me semble --, viendrait du constat que la plupart d'entre nous est incapable de distinguer—je te cite—"du vide derrière des mots complexes" d'un savoir scientifique.

                        L'insulte, s'il doit y en avoir une, est donc probablement dirigée vers notre société elle-même, incapable de nous éduquer suffisamment. Tout n'est peut-être pas perdu car il-y-a encore, heureusement, certaines âmes dont la mission est de nous élever. Pour cela, je te remercie ;o)

                      • [^] # Re: Point fixe

                        Posté par  . Évalué à 2.

                        Bon je précise, je ne l'ai pas pris comme une insule :)

                        PS: je ne pense pas être une grosse quiche en stats, mais j'avoue que la phrase m'avait fait sourire parce que je n'ai aucune idée de ce qu'elle voulait dire.

                        Et c'est un peu ma faute, j'ai voulu condenser au maximum. J'ai essayé d'être plus clair plus bas.

        • [^] # Re: Point fixe

          Posté par  . Évalué à 4.

          Oui ce n'est pas facile de faire clair, mais on peut essayer.

          En gros Alpha Zero utilise un réseau de neurone pour évaluer deux choses:

          • l'issue probable de la partie à partir d'une certaine position
          • les probabilités de chaque coup qui donnent le meilleur résultat

          L'idée de la recherche arborescente de monte-carlo est d'explorer l'arbre des coups possibles de manière randomisée, en explorant avant tout les coups les plus probables. L'algorithme permet de progressivement raffiner les probabilités des coups. Idéalement avec un temps de calcul infini il donne un coup très bon à jouer, mais c'est beaucoup trop cher.

          L'idée dans Alpha Zero c'est de faire en sorte que le réseau de neurones apprenne les probabilités qui seraient émises par la recherche arborescente de monte-carlo, et d'utiliser le réseau de neurone pour accélérer l'évaluation de la recherche de monte-carlo.

          C'est un peu la poule et l'oeuf ce problème, mais du coup la façon dont ils s'en sortent c'est de considérer que la recherche arborescente de monte-carlo est un opérateur d'amélioration du réseau de neurone, et ils cherchent une version du réseau qui soit un optimum de cet opérateur d'amélioration, donc un point fixe.

          Schématiquement on peut dire que si f est l'opérateur d'amélioration, et x les paramètres du réseau de neurones, ils cherchent un point tel que x = f(x). Pour faire ça ils utilisent une itération au point fixe, avec la suite x_n = f(x_{n-1}).

          • [^] # Re: Point fixe

            Posté par  (site web personnel) . Évalué à 3.

            J'avoue ne pas avoir compris leur encodage de la sortie d'évaluation. qu'est-ce qu'il code par plan ? il parle d'une tableau 8*8*73 mais qui contient la proba de chaque case mais de quoi ? Il parle de "stack of planes encoding a probability distribution over 4,672 possible moves".

            Ils ont 73 échiquiers mais avec quoi dedans ?

            "La première sécurité est la liberté"

            • [^] # Re: Point fixe

              Posté par  . Évalué à 6. Dernière modification le 08 décembre 2017 à 11:02.

              The first 56 planes encode possible ‘queen moves’ for any piece: a number of squares [1..7] in which the piece will be moved, along one of eight relative compass directions {N,NE,E,SE,S,SW,W,NW}

              Je ne vois pas ce qu’il y a de pas clair là dedans ?

              Le premier échiquier représente la probabilité P(i,j) que la pièce à l’emplacement (i,j) bouge d’une case vers le nord.
              Le second échiquier représente la probabilité P(i,j) que la pièce à l’emplacement (i,j) bouge de deux cases vers le nord.

              Le septième échiquier représente la probabilité P(i,j) que la pièce à l’emplacement (i,j) bouge de sept cases vers le nord.
              Le huitième échiquier représente la probabilité P(i,j) que la pièce à l’emplacement (i,j) bouge d’une case vers le nord-est.

              Le 56e échiquier représente la probabilité P(i,j) que la pièce à l’emplacement (i,j) bouge de sept cases vers le nord-ouest.

  • # qualité contre quantité

    Posté par  (site web personnel) . Évalué à 8.

    Stockfish, cette mazette classée seulement 3200 Elo, calculait 900 fois plus de positions à la seconde que Deep Mind, évalué 3300 Elo

    (rappel Magnus Carlsen le champion du monde a 2837, notre français MVL a 2789)

    Comme quoi, ce n'est pas la peine de calculer plein de positions idiotes, il suffit de bien analyser des positions pertinentes :-)

    Sur l'avantage de jouer avec les blancs ou les noirs, ce match nous éclaire

    • avec les blancs Deep Mind a joué 50 parties, pour 25 victoires et 25 nulles
    • avec les noirs 3 victoires et 47 nulles

    Maintenant il faudrait faire jouer Deep Mind contre lui-même pour voir si il gagne beaucoup avec les blancs.

    Concernant la théorie des débuts, Deep Mind a l'air de penser que 1 e4 mène à la nulle, donc il ne l'a pas joué !

    Ce résultat arrive au moment où les tournois de haut niveau comportent une écrasante majorité de parties nulles, certains disant (comme en 1920, en 1940, en 1980…) que de nombreux joueurs jouant parfaitement, la nulle est logique.
    Certains médisants ont dit, à propos du tournoi de Londres actuellement, après la première partie non nulle (victoire de Fabiano Caruana contre Serguei Kariakine à la 4 ème ronde) "il a pris une telle avance qu'il ne peut plus être rattrapé"
    Rappel du classement à ce moment-là
    1 Caruana 2,5 points en 4 rondes
    2 ème à 10 ème ex aequo avec 2 points, tous les autres
    il reste 5 rondes à jouer…

    Donc non, les meilleurs joueurs (humains) mondiaux peuvent "mieux" jouer et gagner des parties.

    Et ces parties montrent bien que sacrifier gaiement du matériel contre de l'activité est correct, Tal était dans le vrai !

    ウィズコロナ

    • [^] # Re: qualité contre quantité

      Posté par  (site web personnel) . Évalué à 3.

      Stockfish, cette mazette classée seulement 3200 Elo, calculait 900 fois plus de positions à la seconde que Deep Mind, évalué 3300 Elo

      Comme indiqué plus haut la force brute a servi de base au développement de la qualité des moteurs d'échecs, il me semble me souvenir d'articles qui évaluaient le gain des IA de l'ordre de 100 points elos à chaque palier de la loi de Moore ( je double le nombre de circuits intégrés, j'augmente ma puissance de calcul et je joue mieux)

      Comme quoi, ce n'est pas la peine de calculer plein de positions idiotes, il suffit de bien analyser des positions pertinentes :-)

      C'est justement là que l'algorithme de Monte Carlo semble supérieur à l'alpha beta du moins s'il est lié à un réseau de neurones.

      Sur les niveaux des tournois humains tu n'es pas le seul à regretter le nombre de parties nulles mais la problème n'est amha pas lié au talent des joueurs mais à la concurrence pour rester dans les dix premiers mondiaux.

    • [^] # Re: qualité contre quantité

      Posté par  . Évalué à 3.

      Ce résultat arrive au moment où les tournois de haut niveau comportent une écrasante majorité de parties nulles, certains disant (comme en 1920, en 1940, en 1980…) que de nombreux joueurs jouant parfaitement, la nulle est logique.

      Mouais, est-ce que ça n'est pas plutôt lié au manque de prise de risque? Une défaite avec les blancs est quasiment irrattrappable, et il est très dur de gagner avec les noirs. Du coup, on ne prend jamais de risque.

      Ce qui est frappant, c'est que des joueurs excellents arrivent quand même à gagner dans ces conditions. Comme quoi, c'est possible, mais il semble que l'ensemble de l'écosystème (le système de classement, etc) favorise trop les joueurs prudents.

    • [^] # Re: qualité contre quantité

      Posté par  (Mastodon) . Évalué à 2.

      Comme quoi, ce n'est pas la peine de calculer plein de positions idiotes, il suffit de bien analyser des positions pertinentes :-)

      J'aimerais bien savoir à quel point un humain calcule moins de coups d'un ordi. Ça doit etre vertigineux.

      En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.

      • [^] # Re: qualité contre quantité

        Posté par  (site web personnel) . Évalué à 3.

        regarde

        https://en.chessbase.com/post/the-future-is-here-alphazero-learns-chess/

        les commentaires sur le coup 21 Bg5 (B pour Bishop/fou g5) qui est dur à trouver pour les modules actuels, c'est pourtant nettement le meilleur coup (selon la théorie actuelle…)

        ウィズコロナ

      • [^] # Re: qualité contre quantité

        Posté par  (site web personnel) . Évalué à 4.

        Reti disait qu'il ne calculait qu'un seul coup: le meilleur, Tal disait qu'il ne calculait pas, les analyses de variantes complexes existent mais pour des êtres humains il semble que le calcul se fasse plus ou moins inconsciemment. Bref les ordinateurs jouent mieux en calculant beaucoup et il est très possible que d'autres façons de penser puissent être mise en jeu mais comparer un joueur humain à un ordinateur n'a pas beaucoup de sens. Je me souviens d'un commentaire au cours du dernier championnat du monde ou un type disait que les échecs n'étaient pas un jeu très difficile sauf pour l'homme qui n'a pas de capacités de calcul suffisantes.
        Depuis la fin des années 90 les analyses par ordinateur ont énormément fait progresser la théorie et les meilleurs joueurs ont pris l'habitude de mémoriser des ouvertures de plusieurs dizaines de coups, mais combien sont vraiment calculés en temps réels? Je pense que c'est très variable. Kevin Bordi auteur de la vidéo parle de trois coups par seconde.

        • [^] # Re: qualité contre quantité

          Posté par  . Évalué à 3.

          Je pense qu'il faut distinguer plusieurs phases dans la partie ; dans les fins de partie, on compare avec un certain nombre de "patrons" généraux (du style "si le pion est là et le roi est là alors c'est gagnable pour les blancs), et on calcule forcément (si je vais là il va là alors je vais là, etc). Dans les débuts de partie, c'est plus de la mémoire ; il faut connaitre ses ouverture et les suites de coups. Pour les milieux de partie, c'est trop complexe pour être calculé, les coups sont plutôt basés sur des considérations tactiques (contrôle des cases du centre, etc). Le plus gros "travail" pour un humain, ce n'est pas de calculer, c'est plutôt d'estimer (telle position a l'air mieux que telle autre).

          les meilleurs joueurs ont pris l'habitude de mémoriser des ouvertures de plusieurs dizaines de coups,

          C'est une chose d'apprendre les ouvertures (ça permet de retarder la perte face aux joueurs meilleurs que soi), mais ça ne sert pas à grand chose si on n'apprend pas non plus par cœur les réfutations pour les coups sous-optimaux de l'adversaire. De mon point de vue, ça n'est pas la partie la plus intéressante des échecs—certains GM s'en plaignent régulièrement, d'ailleurs. Ça fait partie du jeu, mais ça doit être pénible de systématiquement devoir remonter des positions pas terribles après un ouverture contre un joueur qui excelle au par cœur…

          • [^] # Re: qualité contre quantité

            Posté par  (site web personnel) . Évalué à 4.

            ça doit être pénible de systématiquement devoir remonter des positions pas terribles après un ouverture contre un joueur qui excelle au par cœur…

            Ca me rappelle une conversation dans une réunion Linux à Nantes il y a dix ans où j'avais parlé avec un joueur qui avait fait une section sport études échecs puis avait abandonné à cause justement de l'apprentissage de la théorie qui donnait un avantage aux "besogneux" par rapport à la créativité.

  • # On va tous mourir ... (voix de Homer Simpson)

    Posté par  (site web personnel) . Évalué à 2. Dernière modification le 08 décembre 2017 à 10:00.

    Quand plusieurs Alpha zéro seront en réseau on l'appellera Skynet ?

    A quand les premiers Terminator sur amazon ?

  • # Entrainer Leela Zero

    Posté par  . Évalué à 3.

    Bonjour. La question d'une implémentation libre de ce type d'algo ayant été posée, je me permets de relayer un mail d'un membre du club de Go de Rennes.

    Salut à tous,

    Ce mail est long, je commence par une version courte: pour entrainer un bot de go, on voudrait pouvoir utiliser la puissance de calcul d'un max d'ordi de particuliers combinés.

    Version longue:

    Commençons par les présentations. Pour ceux qui ne connaissent pas Leela, il s'agit d'un programme de go environ 6d. C'est la meilleure AI gratuite et ouverte à tous. Nous sommes assez nombreux à l'utiliser pour analyser nos parties, ou juste pour avoir un adversaire 6d à tout instant sous la main.

    Jusque-là, Leela a été développée essentiellement par un seul homme (la classe), avec ses ressources limités.

    Après la dernière publication de Deepmind sur AlphaGo Zero, il souhaiterait copier leurs méthodes pour améliorer Leela. Le problème, c'est que la méthode d'entrainement d'AG0 demande de la puissance de calcul. Beaucoup de puissance de calcul. Ca a pris 40 jours sur les super-méga-giga-ordis de google. Donc notre pauvre développeur solitaire, ben il peux faire tourner sa bécane des siècles sans avancer beaucoup.

    C'est là que nous rentrons en jeu. Rien n'oblige l'entrainement à avoir lieu sur un seul ordi. L'idée est donc d'utiliser les ordis de tous les volontaires.

    Si vous suivez les instructions ici (c'est très simple), vous pouvez lancer un programme qui génère des parties d'entrainement pour cette nouvelle version de Leela

    https://github.com/gcp/leela-zero#i-want-to-help

    Tout est automatisé, la seule chose à faire est de lancer le programme. Vous l'arrêtez et le relancer quand vous voulez. Il s'occupe tout seul de transmettre les parties obtenus.

    On approche des 40 000 parties d'entrainement, avec 750 contributeurs (données mises à jour en temps réel ici: http://zero.sjeng.org/ ). Ca parait beaucoup, mais si il faut quelques millions de parties, ca serait cool d'en avoir encore plus.

    Si tout se passe bien, ce travail de groupe devrait nous donner accès à un bot encore bien plus fort que le Leela actuel. En bonus, on va pouvoir s'amuser à le voir progresser au fil de l'entrainement (pour l'instant, il est pire que IdiotBot, on espère qu'il apprenne à reconnaitre les atari bientôt).

    Andéol

    PS : Et pour ceux qui se demandent ce qu'est le jeu de go, il y a moyen de le découvrir via le manga "Hikaru No Go"
    http://www.lemonde.fr/pixels/article/2016/03/08/hikaru-no-go-le-manga-qui-a-relance-le-jeu-de-go-dans-le-monde_4878800_4408996.html

    • [^] # Re: Entrainer Leela Zero

      Posté par  (site web personnel) . Évalué à 3.

      Personne n'a essayé d'estimer combien cela couterait de faire tourner ce programme sur des machines de cloud orienté CPU ? Si cela se trouve, cela ne serait pas si couteux.

      "La première sécurité est la liberté"

Suivre le flux des commentaires

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