Les ordinateurs ne sont bons au jeu de go que depuis peu

Proposé par
le
dans

Contrairement aux programmes d'échecs qui ont commencé à rivaliser avec les meilleurs professionnels dès 1990, les programmes du jeu de go n'arrivent toujours pas à battre des joueurs professionnels ! Le problème du jeu de go est notamment que les combinaisons de jeu possibles sont bien plus nombreuses que pour les autres jeux.


Tous les commentaires (126)

a écrit : D'après la deuxième source, il y a au jeu de go 129 960 possibilités de déplacement juste après le premier tour, contre 400 seulement aux échecs. On comprend tout de suite mieux pourquoi les ordinateurs ont du mal à battre les joueurs humains ^^ C'est à relativiser car cela vient du fait que le plateau du jeu de Go contient bien plus de cases que pour les échecs, donc forcément ca fait gonfler les possibilités sans que le jeu soit forcément plus riche.
Si on ramene le jeu de Go a une grille de 8x8 l'écart est déjà plus raisonnable.

a écrit : Donc l'informatique actuelle comporte des limites et ça me rassure un peu quelque part.
Dans la deuxième source, il est fait mention des mathématiciens qui y jouaient en parlant d'Einstein sauf qu' il était très mauvais en maths mais bon physicien.
Einstein était très loin d'être mauvais en maths même si qon domaine de predilection était la physique.

Posté le

android

(5)

Répondre

a écrit : Pour jouer de temps en temps au go, je confirme que c'est beaucoup plus complexe que le jeu d'échecs (auquel je jouais avant): il suffit de voir une partie de go, où certains coups peuvent se méditer pendant une heure voire plus, et les parties professionnelles d'échec qui ressemblent à une course de vitesse et à un étalage d'automatismes (je sais que je force le trait mais c'est l'impression que ça me laisse).
Pour ceux qui veulent découvrir l'esprit du jeu de go, je conseille le roman de Yasunari Kawabata, Le maître ou le tournoi de go, ainsi que le manga/anime Hikaru no go :)
Afficher tout
Heu, je t'invite a aller assister a une partie de nationale (I, II, III voire IV) d'échec et tu verras que les automatismes sont finalement légers.
A partir du moment ou l'un des joueurs fait un coup qui sort de la théorie de l'ouverture jouée alors ca se joue a la réflexion et au plan de jeu.
A mon niveau, (Nationale III) je peux t'assurer qu'il m'arrive très régulièrement de passer entre 1h et 2h a réfléchir sur un seul coup.
Concrètement, s'il n'y avait pas la pendule qui limite le temps (généralement les partie longues se jouent entre 2h30 et 4h par joueurs suivant les rêgles de la compet) et qui oblige donc a gérer son temps de réflexion alors je peux t'assurer que les meilleurs joueurs réfléchiraient plusieurs heures par coup.

Sur une partie d'échec, je dirais qu'il y a maximum entre 5 et 10 coups que tu vas jouer par automatisme et par connaissance de la théorie.

a écrit : Le jeu de go est certes moins connu que le jeu d'échecs, mais les informaticiens et scientifiques s'y intéressent depuis les années 1990 justement parce que les échecs ont été "craqués".
Ensuite le jeu de go requiert est un jeu qui requiert une vision stratégique beaucoup plus poussée que les
échecs: la stratégie de l'adversaire y est tout aussi importante que sa propre stratégie, et le jeu de go est tout autant un jeu d'initiative que de réaction au jeu de l'adversaire. Et le nombre de combinaisons possible vient complexifier davantage encore le jeu de go. Il n'existe pas de "coups gagnants" à proprement parler, et c'est ce qui rend le go fascinant et plus intéressant (en mon sens) que les échecs. Afficher tout
Ca donne pas envie de s'y mettre au Go ce que tu écris.
S'il n'existe pas de coup gagnant, ca veut dire que potentiellement, quoi que tu joues ton adversaire peut avoir une réponse qui contre ton coup. Sauf que lui ne pourra pas le savoir car son coup ne sera pas un coup gagnant et donc tu pourras avoir une réponse qui contre son coup et ainsi de suite.
En gros, ca fait passer le jeu de Go pour un jeu de hasard ou les gens jouent leurs coups sans trop savoir si c'est bien ou pas.

Je suis pas joueur de Go, mais je pense que tout comme aux échecs, il y a aucune part de chance et qu'un joueur qui connait la théorie et sait calculer un peu en avant sera bon.

a écrit : Ca donne pas envie de s'y mettre au Go ce que tu écris.
S'il n'existe pas de coup gagnant, ca veut dire que potentiellement, quoi que tu joues ton adversaire peut avoir une réponse qui contre ton coup. Sauf que lui ne pourra pas le savoir car son coup ne sera pas un coup gagnant et donc tu pourras
avoir une réponse qui contre son coup et ainsi de suite.
En gros, ca fait passer le jeu de Go pour un jeu de hasard ou les gens jouent leurs coups sans trop savoir si c'est bien ou pas.

Je suis pas joueur de Go, mais je pense que tout comme aux échecs, il y a aucune part de chance et qu'un joueur qui connait la théorie et sait calculer un peu en avant sera bon.
Afficher tout
Alors là s'il y a bien un jeu qui ne relève pas du hasard, c'est le go ^^ Tu peux en effet potentiellement "bloquer" comme tu le dis chaque coup de l'adversaire, mais là n'est pas l'essentiel: ce qui est important au go c'est d'avoir l'initiative, car c'est grâce à elle (en partie bien sûr) que l'on peut se constituer des territoires, qui constituent l'objectif principal du jeu. Pour faire une comparaison avec les échecs, quand ton roi est mis en échec tu es obligé de le protéger; au go, si l'un de tes territoires est menacé, tu peux choisir de porter l'attaque ailleurs, espérant ainsi menacer suffisamment l'adversaire pour gagner l'initiative (sente). C'est pour cela que je trouve le jeu de go plus intéressant que les échecs également :)

De nombreux logiciels de jeu d'échecs (et notamment Deep Blue, qui a battu Kasparov en 97) sont basés sur l'algorithme Minimax (vraiment intéressant, et la base est très facile à coder), qui repose sur deux principes :

- à chaque état du jeu (une situation donnée) est attribué une "note", positive si l'état est favorable au joueur A, négative si il lui est défavorable

- à partir de l'état actuel (exemple : début de partie), l'algorithme "imagine" toutes les possibilités à N coups (tous les états qui peuvent être atteints en N coups) ce qui forme un arbre des possibilités (dont la racine est l'état actuel) et choisit dans cet arbre la branche qui minimise les pertes possibles, en supposant que l'adversaire joue toujours en maximisant ses gains (d'où le nom de l'algorithme).

Ceci n'est que la base de l'algo, beaucoup d'améliorations sont possibles, par exemple l'élagage alpha-beta, qui permet, comme son nom l'indique, de "couper" les branches qui semblent inutiles (car les pertes y sont trop grandes) de l'arbre des possibilités, afin de ne pas avoir besoin de les explorer et donc de gagner du temps de calcul.

Une des difficultés de programmation est la "note" attribuée : comment savoir si une situation est favorable à un joueur ? L'attribution de poids aux pièces (pion = 1, tour = 5...) est un début mais n'est pas très satisfaisant : en effet, on peut perdre sa reine pour ensuite faire un échec avec un pion. Et c'est une des raisons qui font que le jeu de go est difficile à coder suivant cet algo : comment noter un état alors que le but est de contrôler le plus grand territoire ?

La deuxième difficulté a été soulevée plusieurs fois dans les précédents commentires : je crois me souvenir qu'aux échecs, à chaque tour, environ 35 possibilités différentes de jouer sont offertes au joueur. Ainsi, un arbre des possibilités de profondeur N, non élagué, compte plus de 35^N états. Pour le joueur de go, chez qui le goban fait 19x19, on a plus de 350 possibilités au début ! Ce qui fait que l'arbre de profondeur N compte plus de 350^N états (en début de partie au moins, car le nombre de coups diminue). C'est juste impossible à exploiter par une machine. Et l'augmentation de capacité de calcul telle qu'on la connaît ne permettra jamais de supplanter efficacement ce problème : il faut donc raisonner différemment (chercher d'autres élagages ? changer complètement d'algo ? (j'imagine que les scientifiques/informaticiens ont déjà pas mal cherché)).

Je me demande d'ailleurs si l'excitation récente autour du machine learning ne pourra pas offrir une solution ou ouvrir de nouvelles perspectives là dessus.

L'expression "y aller tout de go" signifie y aller rapidement, avec empressement. Pourtant, le jeu de go est un jeu très long. On peut donc se demander quel est le rapport. Une histoire japonaise raconte l'histoire d'une partie de go entre deux généraux. Cette partie dura des années, années au cours desquelles les généraux continuèrent leur partie, l'interrompant entre les batailles. Un soir, il advint qu'ils durent recueillir une prisonnière étrangère. Pour faire court, cette prisonnière renversa accidentellement le jeu. Les généraux s'apprêtèrent à la punir quand elle s'empressa de remettre les pièces au hasard. Elle forma ainsi une combinaison qui impressionna les généraux. Mais devant leur air surpris, la prisonnière pensant qu'elle avait eu tort redéplaça les pions à toute hâte. Ainsi, elle forma de nouveau une combinaison intéressante, persuadée que ce jeu était un objet de décoration. Les généraux, impressionnés par ce qu'ils pensaient être un grand talent stratégique, gracièrent la prisonnière et la renvoyèrent avec les honneurs, eux qui mettaient des heures à jouer un coup alors qu'elle ne mis que quelques instants. L'expression "tout de go" viendrait donc de cette histoire, dans le folklore japonais.

Posté le

android

(4)

Répondre

a écrit : Alors là s'il y a bien un jeu qui ne relève pas du hasard, c'est le go ^^ Tu peux en effet potentiellement "bloquer" comme tu le dis chaque coup de l'adversaire, mais là n'est pas l'essentiel: ce qui est important au go c'est d'avoir l'initiative, car c'est grâce à elle (en partie bien sûr) que l'on peut se constituer des territoires, qui constituent l'objectif principal du jeu. Pour faire une comparaison avec les échecs, quand ton roi est mis en échec tu es obligé de le protéger; au go, si l'un de tes territoires est menacé, tu peux choisir de porter l'attaque ailleurs, espérant ainsi menacer suffisamment l'adversaire pour gagner l'initiative (sente). C'est pour cela que je trouve le jeu de go plus intéressant que les échecs également :) Afficher tout Oui, je me doute, mais la façon dont tu présente le jeu ca donne cette impression.
Comme aux échec, il y a un/des melleur(s) coups. Des coups qui font gagner et d'autres qui font perdre.

a écrit : Donc l'informatique actuelle comporte des limites et ça me rassure un peu quelque part.
Dans la deuxième source, il est fait mention des mathématiciens qui y jouaient en parlant d'Einstein sauf qu' il était très mauvais en maths mais bon physicien.
Enfait Einstein mauvais en maths c'est une légende urbaine comme il y en a temps sur lui. Il était capable de résoudre des intégrales vers l'âge de 6 ans (désolé pour ceux qui utilisé ça comme excuse pour leurs maths) en revanche il avait un problème avec l'enseignement de l'époque et donc avec ces professeurs.

Voir le très bon film " Ex machina " on en parle un peu :)

Posté le

android

(0)

Répondre

a écrit : Enfin, quand l'homme évolue par lui même, il oublie des choses

La machine elle n'oublie rien et surtout ne cesse de s'améliorer.

A mon avis, ce n est qu'une question de temps pour que l'ordinateur rivalise avec les champions de ce jeu
Dès les premiers ordinateurs quantiques :)

À noter que Go est aussi le nom du langage de programmation open source de Google.

a écrit : Aucun ordinateur ne peut rivaliser avec ma go ;) Si tu l'appelles "ta go" il t'a de forte chance que tout le monde puisse te rivaliser :)

Dommage que le côté est due être tronquée pour la publication ! Ce jeu ancestral est passionnant et on pourrait en écrire des pages :)
Si vous voulez vous initier il est facile de trouver des tutos bien foutus sur le net. Les règles de base sont vite acquises. Mais en y jouant on se rend compte que cela demande un peu d'entraînement pour les mettre en pratique sur le plateau de 19x19...
Pour la ptite anecdote, l'économiste John Nash, (génial et un peu fou) à inventé une version hexagonale du jeu de go. A priori encore plus complexe !

Posté le

android

(1)

Répondre

a écrit : Voir le très bon film " Ex machina " on en parle un peu :) J'ajoute le film Pi et Un homme d'exception (sur John Nash) !

Posté le

android

(0)

Répondre

Les ordinateurs sont tout à fait capable est très facilement... Mais aucun programmeur ne veut faire un programme (performant) pour un jeu aussi mal connu... C est valable pour tous les jeux... Seul le jeu d échec en vaut la peine car ce jeu est joué partout et c est un jeu commun et connu.

Posté le

android

(0)

Répondre

a écrit : Oui, je me doute, mais la façon dont tu présente le jeu ca donne cette impression.
Comme aux échec, il y a un/des melleur(s) coups. Des coups qui font gagner et d'autres qui font perdre.
Justement non, et je t'invite à essayer une ou deux parties pour comprendre pourquoi.

Au Go, tu ajoutes une pierre à chaque tour sur le plateau, absolument où tu le souhaites. Les possibilités sont donc immenses, et bien souvent plusieurs coups se valent (à première vue du moins) leur vraie finalité et leur intérêt pouvant se révéler plusieurs coups plus tard. De même, une pierre qui semble mal placée peut devenir un superbe coup en fonction de l'évolution de la partie.

Il n'y a réellement pas de coup gagant, il y a une stratégie qui se construit !

a écrit : On peut toujours tirer des plans sur la "comète des Terminators"... Tu as raison.
L'homme crée la machine ; jamais la machine ne créera l'homme... Sauf si un jour l'homme crée le programme pour le faire.
Que les machines soient plus fortes dans certains domaines que 99% des hommes (
parce que conçues par des "élites"), reste toujours que ces 1% seront au dessus. Afficher tout
Non il suffit juste d'attendre le moment ou l'homme programmera une machine qui pourra se programmer toute seule.
Apres ca, on est foutu..
J'arrive pas a comprendre les gens qui disent " on programme les machines donc pas de probleme..".
Oui, tant que NOUS les programmons; mais lorsqu'une machine pourra programmer toute seule..

a écrit : Ben justement ... je me serai attendu au contraire.
Il me semblait que plus les possibilités de combinaison sont nombreuses, plus il est difficile pour un humain de rivaliser avec un ordinateur.
L'explication ne tiendrait elle pas plutôt au fait que le jeu de go est beaucoup moins populaire que les éc
hecs et a par conséquent moins suscité d'engouement chez les informaticiens ? Afficher tout
D'accord avec toi. Le problème ne vient peut être pas de la capacité de calcul des ordinateurs mais du programme conçu (programme développé par les Hommes).

Einstein était nul en math ... Pour un prix Nobel de physique :)

Posté le

android

(3)

Répondre