A lire sur: http://www.infodsi.com/articles/131248/ordinateurs-peuvent-battre-humains-jeu-go.html?key=
Des
ordinateurs capables de battre les meilleurs joueurs de go(1) ? C'est
encore impossible mais la donne pourrait bientôt changer grâce aux
travaux de deux théoriciens du CNRS des laboratoires de physique
théorique (Université Toulouse III-Paul Sabatier/CNRS) et de physique
théorique et modèles statistiques (Université Paris-Sud/CNRS).
Après les dames, les échecs, le backgammon, les échecs, le poker ou le jeu télévisé Jeopardy, les chercheurs s’attellent à la tâche pour battre les humains au jeu de go. (1) Originaire de Chine, le jeu de go est un jeu de stratégie, opposant deux adversaires qui placent à tour de rôle des pierres noires et blanches sur un plateau appelé goban. Les joueurs tentent ainsi de contrôler le plan de jeu en y construisant des « territoires » qui se comptent en points. Chaque « pierre » représente un soldat ; les soldats encerclés deviennent des prisonniers (source : Wikipedia).
Pour la première fois, les deux chercheurs ont appliqué la théorie des réseaux à un jeu de stratégie. Leurs résultats, publiés dans la revue Europhysics Letters (The game of go as a complex network) devraient améliorer les futurs programmes de simulation.
L'étude
des réseaux complexes a connu un intérêt grandissant au cours des
dernières années, notamment en raison du développement des réseaux de
communication et d'information. Ce nouveau champ de recherche se révèle
très utile pour la description des systèmes complexes tels que les
réseaux sociaux ou Internet. Par exemple, si on applique la théorie des
réseaux à Internet, chaque page est un nœud et les liens hypertextes
sont les liens entre les nœuds.
Cependant, une telle approche n'avait jamais été envisagée pour l'étude des jeux de stratégie comme le go (1) ou les échecs. Ces jeux, riches d'une très longue histoire et forts de millions de joueurs dans le monde, sont très difficiles à modéliser. En effet, les ordinateurs ne sont capables de battre des champions d'échecs que depuis une quinzaine d'années seulement, tandis que le niveau des professionnels reste encore inaccessible aux meilleurs programmes de go actuels.
A partir d'une base de données comportant près de 5 000 parties jouées par des professionnels et amateurs du jeu de go dans des tournois internationaux, Bertrand Georgeot du laboratoire de physique théorique (Université Toulouse III-Paul Sabatier/CNRS) et Olivier Giraud du laboratoire de physique théorique et modèles statistiques (Université Paris-Sud/CNRS) ont appliqué la théorie des réseaux à ce jeu de stratégie. Ils ont construit un graphe dont les nœuds sont les motifs locaux du plateau de jeu et les arêtes (qui représentent les liens) reflètent la succession des coups. Ainsi, ils ont capturé une partie de la stratégie locale du jeu.
Pour la synthèse des complexités des différents jeux, « l’article publié dans la revue Artificial Intelligence de 2002 intitulé Games solved: Now and in the future donne une idée de la complexité des différents jeux, commente Olivier Giraud, et de l’espace d’états (ensemble des positions légales accessibles. La complexité du Go (10^172 positions légales accessibles et un arbre de jeu de 10^360 positions) en fait le jeu de stratégie le plus difficile à simuler (voir la table 6 publiée dans l'article). L'anticipation des progrès des ordinateurs est très difficile à prévoir dans la mesure où les progrès notables viennent souvent d'idées nouvelles et par essence imprévisibles (comme l'idée toute récente d'introduire des processus aléatoires dans les simulateurs de Go) ».
Dans le jeu go où les joueurs placent leurs pierres aux intersections d'un quadrillage de 19 lignes par 19 (soit 361 intersections), les chercheurs ont étudié des motifs locaux de 9 intersections. Ils ont montré que la distribution statistique de la fréquence de ces motifs est une loi de Zipf (1), semblable à la distribution de fréquence des mots dans une langue.
Le réseau du jeu de go présente des caractéristiques proches de celles d'autres réseaux réels (réseaux sociaux ou Internet) mais il montre également diverses propriétés spécifiques. Si les programmes de simulation les plus récents intègrent déjà des données statistiques issues de parties réelles mais à un niveau encore rudimentaire, ces nouveaux résultats devraient permettre une meilleure modélisation de ce type de jeux de plateau.
A partir de leur graphe, les chercheurs ont obtenu ces motifs (de 9 intersections chacun) qui montrent les coups les plus fréquents ou regroupent des coups stratégiques (il s'agit de motifs sur lesquels se localisent les vecteurs propres associés à trois grandes valeurs propres de la matrice d'adjacence pondérée du graphe). La 1ère ligne correspond aux dix motifs les plus fréquents dans le jeu de go. La 2ème ligne isole des motifs dont la plupart correspondent à une situation bien connue dans le jeu de go : le Ko (éternité). Quant à la 3ème ligne, la majorité de ses motifs correspond à des situations où des chaînes de pierres se connectent. Noir joue à l'emplacement de la croix.
Après les échecs, les dames, le backgammon…
L’ordinateur défie l’homme au poker
Elémentaire mon cher Watson !
Le système d'IBM Watson défie les champions du Jeopardy
Watson d’IBM : après le jeu, place au business
_________
(1) La loi de Zipf est une observation empirique concernant la fréquence des mots dans un texte. Elle a pris le nom de son auteur, George Kingsley Zipf (1902-1950). Cette loi a été par la suite généralisée par Benoît Mandelbrot.
Pour lire l’article de Wikipedia
jeudi 12 avril 2012
Des
ordinateurs capables de battre les meilleurs joueurs de go(1) ? C'est
encore impossible mais la donne pourrait bientôt changer grâce aux
travaux de deux théoriciens du CNRS des laboratoires de physique
théorique (Université Toulouse III-Paul Sabatier/CNRS) et de physique
théorique et modèles statistiques (Université Paris-Sud/CNRS).Après les dames, les échecs, le backgammon, les échecs, le poker ou le jeu télévisé Jeopardy, les chercheurs s’attellent à la tâche pour battre les humains au jeu de go. (1) Originaire de Chine, le jeu de go est un jeu de stratégie, opposant deux adversaires qui placent à tour de rôle des pierres noires et blanches sur un plateau appelé goban. Les joueurs tentent ainsi de contrôler le plan de jeu en y construisant des « territoires » qui se comptent en points. Chaque « pierre » représente un soldat ; les soldats encerclés deviennent des prisonniers (source : Wikipedia).
Pour la première fois, les deux chercheurs ont appliqué la théorie des réseaux à un jeu de stratégie. Leurs résultats, publiés dans la revue Europhysics Letters (The game of go as a complex network) devraient améliorer les futurs programmes de simulation.
L'étude
des réseaux complexes a connu un intérêt grandissant au cours des
dernières années, notamment en raison du développement des réseaux de
communication et d'information. Ce nouveau champ de recherche se révèle
très utile pour la description des systèmes complexes tels que les
réseaux sociaux ou Internet. Par exemple, si on applique la théorie des
réseaux à Internet, chaque page est un nœud et les liens hypertextes
sont les liens entre les nœuds.Cependant, une telle approche n'avait jamais été envisagée pour l'étude des jeux de stratégie comme le go (1) ou les échecs. Ces jeux, riches d'une très longue histoire et forts de millions de joueurs dans le monde, sont très difficiles à modéliser. En effet, les ordinateurs ne sont capables de battre des champions d'échecs que depuis une quinzaine d'années seulement, tandis que le niveau des professionnels reste encore inaccessible aux meilleurs programmes de go actuels.
A partir d'une base de données comportant près de 5 000 parties jouées par des professionnels et amateurs du jeu de go dans des tournois internationaux, Bertrand Georgeot du laboratoire de physique théorique (Université Toulouse III-Paul Sabatier/CNRS) et Olivier Giraud du laboratoire de physique théorique et modèles statistiques (Université Paris-Sud/CNRS) ont appliqué la théorie des réseaux à ce jeu de stratégie. Ils ont construit un graphe dont les nœuds sont les motifs locaux du plateau de jeu et les arêtes (qui représentent les liens) reflètent la succession des coups. Ainsi, ils ont capturé une partie de la stratégie locale du jeu.
Pour la synthèse des complexités des différents jeux, « l’article publié dans la revue Artificial Intelligence de 2002 intitulé Games solved: Now and in the future donne une idée de la complexité des différents jeux, commente Olivier Giraud, et de l’espace d’états (ensemble des positions légales accessibles. La complexité du Go (10^172 positions légales accessibles et un arbre de jeu de 10^360 positions) en fait le jeu de stratégie le plus difficile à simuler (voir la table 6 publiée dans l'article). L'anticipation des progrès des ordinateurs est très difficile à prévoir dans la mesure où les progrès notables viennent souvent d'idées nouvelles et par essence imprévisibles (comme l'idée toute récente d'introduire des processus aléatoires dans les simulateurs de Go) ».
Dans le jeu go où les joueurs placent leurs pierres aux intersections d'un quadrillage de 19 lignes par 19 (soit 361 intersections), les chercheurs ont étudié des motifs locaux de 9 intersections. Ils ont montré que la distribution statistique de la fréquence de ces motifs est une loi de Zipf (1), semblable à la distribution de fréquence des mots dans une langue.
Le réseau du jeu de go présente des caractéristiques proches de celles d'autres réseaux réels (réseaux sociaux ou Internet) mais il montre également diverses propriétés spécifiques. Si les programmes de simulation les plus récents intègrent déjà des données statistiques issues de parties réelles mais à un niveau encore rudimentaire, ces nouveaux résultats devraient permettre une meilleure modélisation de ce type de jeux de plateau.
A partir de leur graphe, les chercheurs ont obtenu ces motifs (de 9 intersections chacun) qui montrent les coups les plus fréquents ou regroupent des coups stratégiques (il s'agit de motifs sur lesquels se localisent les vecteurs propres associés à trois grandes valeurs propres de la matrice d'adjacence pondérée du graphe). La 1ère ligne correspond aux dix motifs les plus fréquents dans le jeu de go. La 2ème ligne isole des motifs dont la plupart correspondent à une situation bien connue dans le jeu de go : le Ko (éternité). Quant à la 3ème ligne, la majorité de ses motifs correspond à des situations où des chaînes de pierres se connectent. Noir joue à l'emplacement de la croix.
Après les échecs, les dames, le backgammon…
L’ordinateur défie l’homme au poker
Elémentaire mon cher Watson !
Le système d'IBM Watson défie les champions du Jeopardy
Watson d’IBM : après le jeu, place au business
_________
(1) La loi de Zipf est une observation empirique concernant la fréquence des mots dans un texte. Elle a pris le nom de son auteur, George Kingsley Zipf (1902-1950). Cette loi a été par la suite généralisée par Benoît Mandelbrot.
Pour lire l’article de Wikipedia
Source: infoDSI.com
Aucun commentaire:
Enregistrer un commentaire