Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
Posté par Adrien le Mercredi 11/04/2012 à 00:00
Le réseau complexe du jeu de go
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 (La physique théorique est la branche de la physique qui étudie l’aspect théorique des lois physiques et en développe le formalisme mathématique.) et modèles statistiques (Université Paris-Sud/CNRS). Pour la première fois, ils ont appliqué la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une...) des réseaux à un jeu de stratégie (La stratégie - du grec stratos qui signifie « armée » et ageîn qui signifie « conduire » - est :). Leurs résultats, publiés dans la revue Europhysics Letters, devraient améliorer les futurs (Futurs est une collection de science-fiction des Éditions de l'Aurore.) programmes de simulation.


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 (En géographie, la situation est un concept spatial permettant la localisation relative d'un espace par rapport à son environnement proche ou non. Il inscrit un lieu dans un cadre plus...) 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 (La joue est la partie du visage qui recouvre la cavité buccale, fermée par les mâchoires. On appelle aussi joue le muscle qui sert...) à l'emplacement de la croix.
© O. Giraud et B. Georgeot

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 (La communication concerne aussi bien l'homme (communication intra-psychique, interpersonnelle, groupale...) que l'animal (communication intra- ou inter- espèces)...) et d'information. Ce nouveau champ (Un champ correspond à une notion d'espace défini:) de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également...) se révèle très utile pour la description des systèmes complexes tels que les réseaux sociaux ou Internet (Internet est le réseau informatique mondial qui rend accessibles au public des services variés comme le courrier électronique, la messagerie instantanée et le World Wide Web, en utilisant...). 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 go1 ou les échecs. Ces jeux, riches d'une très longue histoire et forts de millions de joueurs dans le monde (Le mot monde peut désigner :), 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 (En informatique, une base de données (Abr. : « BD » ou « BDD ») est un lot d'informations stockées dans un dispositif informatique. Les technologies existantes permettent d'organiser et de...) 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 (La physique (du grec φυσις, la nature) est étymologiquement la « science de la nature ». Dans un sens général et ancien, la physique désigne la connaissance de la...) 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. Dans ce jeu 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 (La statistique est à la fois une science formelle, une méthode et une technique. Elle comprend la collecte, l'analyse, l'interprétation de données ainsi que la présentation de ces ressources afin de les rendre...) de la fréquence (En physique, la fréquence désigne en général la mesure du nombre de fois qu'un phénomène périodique se reproduit par unité de temps. Ainsi...) de ces motifs est une loi de Zipf (On nomme Loi de Zipf une observation empirique de 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 Benoit...), semblable à la distribution de fréquence des mots dans une langue.

Le réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets »,...) 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 (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) 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.

Notes:

(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).


Commentez et débattez de cette actualité sur notre forum Techno-Science.net. Vous pouvez également partager cette actualité sur Facebook, Twitter et les autres réseaux sociaux.
Icone partage sur Facebook Icone partage sur Twitter Partager sur Messenger Icone partage sur Delicious Icone partage sur Myspace Flux RSS
Source: CNRS