Sur la route d’Oxiane disgressions diverses

Cet article est en deux parties. Retrouvez ici la première partie de cet article .

Une machine s’impose face à un professionnel

Le 07 Août 2008, Le programme Mogo Titan, développée par l’université de Maastricht et par l’INRIA, a battu Kim MyungWan, un joueur professionnel coréen 8ème dan.

Cependant, quelques bémols:
A l’instar de Deep Blue, le programme tourne sur un supercalculateur, conçu par IBM. La machine, le «Power 575 Hydro-Cluster» est dotée de 3328 processeurs POWER6, cadencés à 4,7 GHz et de près de 15 To de mémoire vive. Elle est capable d’atteindre 60 000 milliards d’opérations à virgule flottante par seconde (60 TéraFLOPS). A titre de compaison, elle est plus de 1000 fois plus puissante que Deep Blue… Ce qui la place cependant assez loin des plus puissants supercalculateurs du monde.
La partie est jouée avec 9 pierres de handicap (à l’avantage de Mogo), ce qui représente environ 120 points d’avance
Kim MyungWan utilise moinsde 6 minutes de temps pour jouer la partie
D’ailleurs, le joueur coréen avait facilement battu Mogo à plusieurs reprises lors des phases de test

Mais au final, la machine gagne….. De 1,5 points!

Cependant, l’événement reste de taille. Mogo reste le programme ayant obtenu le meilleur résultat face à un joueur professionnel.

Quel est son secret ?

Les trois atouts principaux de Mogo

MoGo utilise principalement trois techniques :
Exploration de l’arbre des coups possibles par l’algorithme UCT
Evaluation des positions fondée sur des algorithmes de Monte-Carlo
Parallélisme afin de disposer de la puissance de calcul nécessaire pour qu’une évaluation Monte-Carlo donne des résultats suffisamment précis

L’algorithme UCT – issu de recherche de travaux en IA - est une méthode pour explorer des arbres min/max gigantesques. L’idée étant de se focaliser sur un coup et d’éliminer les autres.
Je ne rentrerai pas en détail là-dessus - surtout que je n’ai pas tout compris…

La partie intéressante est l’algorithme de Monte-Carlo.

Méthode de Monte-Carlo

Une méthode de Monte-Carlo est une technique visant à calculer une valeur numérique en utilisant des procédés aléatoires.

C’est utilisé notamment dans le domaine de la finance pour faire des mesures de risque (du coup on se dit que ça ne marche pas toujours très bien…).

Pour illustrer la méthode, je vais honteusement reprendre l’exemple de Wikipedia,. Il s’agit de faire une estimation de la superficie d’un lac :

Prenez un lac, inclus dans une zone rectangulaire (image de gauche).
Bombardez au hasard N coups de canon dans cette zone (deuxième image).

Comme vous connaissez la superficie du terrain, le nombre total de boulets de canon (X), et le nombre de ceux tombés en dehors du lac (N), vous pouvez estimer la superficie du lac par la formule:

Superficie lac ~= ( ( X – N ) * superficie terrain ) / X

Méthode de Monte-Carlo appliquée au Go

La méthode de Monte Carlo est utilisée par Mogo pour évaluer une position sur le Goban (l’une des principales difficultés du Go).

L’idée est, pour évaluer une position, de jouer des pierres noires et blanches au hasard,
excepté sur les intersections correspondant à des yeux (un «oeil» est une intersection vide unique entouré de pierres de la même couleur, c’est à dire un territoire minimal).

Le but est de terminer aléatoirement la partie, afin d’obtenir une position finale facile à évaluer (on sait qui gagne et de combien, il suffit de compter les territoires).
Puis on répète l’opération à partir de la position initiale.
Plus on répète l’opération, plus l’estimation de la position devient fiable (on fait la moyenne des estimations).

Pour être plus efficace encore, Mogo ne joue pas les coups totalement au hasard, mais essaie de jouer des coups crédibles, selon certains patterns pré-définis.

La combinaison de l’algorithme UCT et des méthodes d’évaluation basées sur Monte-Carlo ont fait de MoGo le meilleur programme de Go à ce jour. Mais il reste encore loin du niveau professionnel.

Pour conclure

Depuis 2006, la programmation du jeu de Go a fait des progrès importants, grâce à la méthode de Monte-Carlo notamment, et à des techniques avancées d’IA.
Le jeu de Go étant un terrain d’étude privilégié pour les sciences cognitives, il est probable que les rencontres entre machine et joueurs professionnels se multiplient dans le futur.

Mais la profondeur du jeu, sa complexité, et les qualités humaines qu’il requiert, font du Go un jeu qui restera encore longtemps l’apanage d’Homo sapiens sapiens! Enfin.. C’est mon avis

Auteur : Mikaël Lester

Annexe

Ressources diverses sur le Go
gobase.org
goproblems.com
http://igo-kisen.hp.infoseek.co.jp/news.html, pour trouver les parties professionnels des tournois coréens, chinois et japonais.
www.gnu.org pour télécharger le programme GnuGo.

Pour rappel : retrouvez ici la première partie de cet article .

Humour et Go

Voici une petite blague tordante (glacée et sophistiquée) qui prouve bien que l’humour du joueur de Go n’a absolument rien à envier à celui de l’informaticien:

Dernière petite remarque

Une prétérition se cache dans ce mini-dossier, saurez-vous la retrouver ?

Suite de notre série de l’été consacrée à Android. Après la présentation générale de cet OS pour mobile et la description de ses principaux concepts (Activity, Intent, notion de composant, etc.), voici comment écrire un Hello World grâce au plugin Eclipse et au SDK Android. Ce petit programme nous permettra de faire le tour des principaux aspects du développement sous Android.

Voir également : Introduction à Android - Feuilleton de l’été 2009 épisode 1

Développer sous Eclipse avec ADT (Android Development Tool)

Le plugin ADT pour Eclipse vous permet de créer et de déboguer facilement et rapidement les applications.

• Il vous fournit un nouveau gestionnaire de projet, qui vous aide à initialiser tous les fichiers de base dont vous avez besoin pour une nouvelle application Android.
• Il vous fournit un éditeur Android qui vous aide à écrire des fichiers XML valide pour Android.
• Il vous permet aussi d’exporter votre projet dans un fichier APK signé. Il est important de noter que pour être installé sur un système Android, tout package APK doit être préalablement signé.

Nous supposons à présent que vous avez Eclipse installé. Si tel n’est pas le cas, rendez-vous sur www.eclipse.org pour les instructions de téléchargement et d’installation de l’IDE Eclipse. Les instructions que nous donnons dans la suite concernent Eclipse 3.4 (Ganymede).

Préparation de l’installation

Android requiert une version 5 ou supérieure du JDK.

Après avoir télécharger le SDK d’Android, extrayez l’archive dans un répertoire de votre choix. Notons Rep_Android ce répertoire. Nous en aurons besoin lors de l’installation du plugin. Vous pouvez télécharger le SDK sur http://developer.android.com/sdk/.

Installation du plugin

Le processus d’installation du plugin est le suivant :

1. Démarrez Eclipse, sélectionnez Help/Software Updates…
2. Dans la boite de dialogue qui apparaît, cliquez l’onglet Available Software, puis sur Add site…
3. Entrez l’URL : https://dl-ssl.google.com/android/eclipse/
4. Cliquez sur OK.
5. De retour dans la vue Available Sofware, vous verrez le plugin listé par son URL, avec «Developer Tools » en dessous. Sélectionnez la case à cocher à côté de Developer Tools et cliquez sur Install…
6. Dans l’écran d’installation suivant, « Android DDMS » et « Android Development Tools » doivent être tous cochés. Cliquez sur suivant.
7. Lisez et acceptez le contrat de licence, puis cliquez sur Finish.
8. Redémarrer Eclipse.

Modifiez à présent vos préférences pour pointer sur le répertoire d’installation du SDK d’Android, le répertoire Rep_Android. Pour cela suivez les étapes suivantes :

1. Sélectionnez Windows > Preferences… (Mac: Eclipse > Preferences).
2. Sélectionnez Android depuis le panel de gauche.
3. Pour l’entrée SDK Location du panel principal, cliquez sur Browse… et localiser le répertoire du SDK
4. Cliquez sur Apply, puis Ok.

Bien ! Si vous n’avez rencontré aucun problème, alors votre environnement est prêt pour le développement d’applications Android.

Lire la suite du bllet »

Voilà un petit billet pour se détendre, et sortir un petit peu des sujets technologie.
Confucius disait : «Mieux vaut jouer au Go que de rester oisif».
Ce dossier va donc aborder le jeu de Go, et particulièrement les efforts en cours pour développer une IA de Go correcte.
Et revenir également sur l’événement qui a (un petit peu) secoué le monde du Goen 2008 : La victoire d’un programme sur un joueur professionnel.

Le jeu de Go ? Késako ?

Le jeu de Go est originaire de Chine, il s’agit du plus ancien jeu de stratégie connu.
Des légendes anciennes lui attribuent un âge vénérable d’environ 4000 ans, et lui prêtent des origines diverses. En vérité, les premières références au jeu datent d’environ 722 à 481 av JC.
Il s’agit de l’un des 4 Arts chinois, avec la poésie, la calligraphie, et l’art pictural.

A partir d’un matériel simple (un plateau de jeu appelé Goban, des pierres noires et blanches), les règles du jeu se sont progressivement développées au fil des siècles, pour aboutir aux règles actuelles.
Celles-ci sont très simples et peu nombreuses, il s’agit essentiellement des règles de capture de pierres.

Cependant le go n’est pas un jeu facile. Les stratégies et tactiques possibles sont quasi-infinies, l’apprentissage du jeu est très long.

Certaines mauvaises langues (que je ne citerai pas) affirment que le jeu de go est aux échecs ce que les échecs sont au morpion! No comment. J’ajouterai juste que Bobby Fischer, célèbre champion américain d’échecs affirmait : «Les extra-terrestres ont peut être inventé les échecs, ils ont certainement inventé le jeu de go»

Lire la suite du bllet »

Nous commençons aujourd’hui une série de l’été qui consacrée à un sujet technologique particulier. Cette année, ce sera Android, le système d’exploitation pour équipements mobiles.

Retrouvez cette série par épisode tout au long de l’été.

Android, Qu’est ce que c’est?

La prochaine génération de systèmes d’exploitations libres ne sera pas sur pc ou sur mainframe mais bien sur les équipements mobiles que nous promenons tous les jours. Développée par le consortium Open Handset Alliance (OHA), Android est une plateforme qui inclut un système d’exploitation, un middleware et quelques applications clés. La motivation du consortium OHA à l’origine d’Android est d’accélérer l’innovation dans la technologie mobile et d’offrir à ses utilisateurs une expérience riche et peu onéreuse.

Le SDK d’Android fournit les outils et les APIs nécessaires au développement d’applications en java. A noter qu’un  NDK permet également depuis quelques semaines d’envisager le dévelloppement de composants en code natif.

Dans ce tutoriel, vous allez apprendre comment développer une application d’entreprise simple avec le SDK d’Android. Vous ferez tourner cette application à l’aide de l’émulateur d’Android ou sur votre téléphone Android. Notre prototype consistera à consulter depuis son téléphone, la liste des filières de formations inter-entreprises disponibles chez Oxiane, d’obtenir à partir d’une filière sélectionnée la liste des cours dispensés et finalement le détail (durée, objectifs, public, pré requis, tarif, et calendrier) d’un cours donné. L’utilisateur pourra aussi s’inscrire à un cours à partir de son téléphone. Pour ce faire, Oxiane met à disposition des Web services REST-style (XML-RPC) qui retournent au format XML respectivement le catalogue de formation (liste des filières), la liste des cours d’une filière sélectionnée, et le détail d’un cours. Ces services seront appelés à partir de l’application Android.

Vous conclurez après ce tutoriel que le développement d’application Android est assez simple. C’est encore plus simple si vous utilisez Eclipse comme environnement de développement. Google fournit un plugin qui prend en charge la création et la gestion de votre projet afin d’accélérer votre cycle de développement. Nous allons donc au cours de ce tutoriel supposer que vous travaillez sous Eclipse. Si vous utilisez un autre IDE, adaptez nos instructions à votre environnement.

Avant de commencer le tutoriel proprement dit, nous allons d’abord procéder à une présentation des fondamentaux d’Android, nécessaires pour comprendre la suite.

Lire la suite du bllet »

Le Google Web Toolkit (GWT) est devenu en quelques semaines un outil particulièrement mis en avant par Google.

C’est avec GWT que Google a développé son innovant outil collaboratif Google Wave. Voici un “ proof of concept ” particulièrement impressionnant.  GWT a permis de créer une application web rapide, complète et innovante. Voilà qui devrait convaincre les plus sceptiques devant la possibilité de faire de ” vraies applications” avec GWT.

GWT est également le framework désormais proposé en standard pour le développement sur Google App Engine (pour ceux qui se demandent ce que c’est, nous en avons déjà parlé ici … et là).

Aujourd’hui, GWT sort sa version 1.7 - version mineure qui propose le support de Internet 8, Firefox 3.5 etSafari 4.

Avec GWT, on peut développer en java une application Web performante, basée sur Ajax, tournant sur les meilleurs navigateurs, et tout cela sans avoir à écrire une ligne de javascript.

GWT n’est plus seulement cette librairie géniale maintenue par une bande d’ingénieurs fous chez Google, c’est devenu un outil de premier plan pour les développements d’applications web.

Nous en profitons pour vous mettre à disposition le support de formation GWT dans sa version 1.5.

N’hésitez pas à le consulter et à nous faire part de vos remarques !

Depuis mon arrivée à Oxiane, une question m’est régulièrement posée : “C’est quoi un SMA ?”
En effet, avant d’arriver, j’avais passé un peu de temps dans la recherche dans ce domaine.
Puis est venu une discussion avec Jennifer, sur un système permettant de suicider des tortues… Et là, c’est le drame…
Il fallait absolument que je fasse un article pour présenter le domaine de recherche des systèmes multi-agents (SMA).

Ce domaine est né de l’intelligence artificielle et des systèmes distribués.
Pour définir un système multi-agent (”multi-agent” étant maintenant considéré comme un adjectif, il ne porte pas de “s”), dans (Briot et Demazeau, 2001), les auteurs prennent la définition usuelle du système  “un ensemble organisé d’éléments” pour poser qu’un SMA est « un ensemble organisé d’agents ».
Dans un SMA, il existe une ou plusieurs organisations qui structurent les règles de cohabitation et de travail collectif entre agents. Il s’agit d’une métaphore de l’organisation collective. Chaque agent a ses propres compétences et a besoin d’interagir avec les autres pour résoudre des problèmes.
L’objectif d’un SMA est de résoudre des problèmes (combien de temps met la tortue à traverser la plage de Brest, si elle pèse 10kg, et a des courses à faire) ou bien de modéliser des phénomènes complexes à l’aide d’un ensemble d’agents (le phénomène de marées, les nuits sur les plages de Brest, qui potentiellement vont perturber les tortues).

Un système multi-agent est donc un système où un certain nombre d’agents coexistent… lorsque l’on a dit ça, se pose la question cruciale : qu’est-ce qu’un agent ?
Lire la suite du bllet »

Mardi 12 mai, de 19h15 à 22h30 dans les locaux de l’ISEP, le Paris JUG vous propose une soirée spéciale Grid computing.

19h15 à 19h30 : Accueil

19h30 à 20h25 : Point sur le Grid Computing. Seront abordés successivement les thèmes suivants : Cache distribué, Network Attached Memory, Data Grid et le Cloud Computing.

21h35 à 22h05 : “How to stop waiting for build/deploy and enjoy coding again” - Also known as “Watching the logs roll by” (Présentation en anglais) Présentation sur des techniques d’augmentation de la productivité, autour notamment du produit Java Rebel.

22h30 à … : 3ème mi-temps des juggers au Falstaff

ATTENTION : Victime de son succès, le Paris JUG ne se contient plus dans la salle qui l’accueille. Pour des raisons évidentes de sécurité, les personnes non inscrites à l’évènement ne pourront donc plus y assister.

N’oubliez pas de vous inscrire !

Proche par certains cotés d’Oxiane (siège social Boulogne Billancourt à 300 m de chez nous, 17 ingénieurs, date de création 2005, actionnariats salariés), Blue Way réalise et commercialise un bus applicatif orienté utilisateur.

Les sociétés participantes : Orphanet (portail des maladies rares et des médicaments orphelins), l’Inserm, la MGET (Mutuelle Générale de l’Equipement et des Territoires), CUC (grossiste en accessoires informatiques fournisseur entre autre de cdiscount, pixmania, … http://www.abix.fr/ ; http://www.cuc.fr/ ), IGA (éditeur français d’ERP et de CRM).

Blue Way a fait un gros travail de R&D pour choisir les meilleures briques logicieles (JBoss, …) et les intégrer dans un outil global permettant d’interconnecter différentes applications sans avoir à écrire de code. Elle compte aujourd’hui 80 clients grands compte et PME.

La vision du produit est de fournir des technologies ad-hoc, très robustes, d’en assurer l’intégrité afin qu’un non informaticien (ou plutôt « informaticien non développeur ») puisse réaliser facilement et rapidement un workflow entre plusieurs nœuds applicatifs. L’approche est résolument métier et permet un passage entre back et front office.

Aujourd’hui la société s’est ouverte à des partenariats (Micropole, Altran, …) pour assurer le conseil et l’aide aux utilisateurs.

Lire la suite du bllet »

Depuis quelques jours, Google a annoncé le support de Java 6 sur son infrastructure de Cloud Computing, Google App Engine  (autrement dénommée GAE).
Cette nouvelle est tempérée par le fait que toutes les API de java ne sont pas supportées. Ainsi, interdiction par exemple de créer un Thread, d’écrire un fichier…
La plupart des limitations sont structurelles et dues au fait que l’on est “on the cloud” - où la notion de Fichier, de Thread… est largement abolie, puisque l’on ne sait pas sur quelle machine sera déployée l’application.

Mais il existe d’autres limitations. Certaines sont des choix - comme l’impossibilité d’utiliser le package java.awt.* D’autres sont des erreurs due à la jeunesse - et au caractère novateur du produit - comme l’impossibilité d’utiliser l’annotation @MappedSuperClass de JPA (mais on peut utiliser JPA) ou l’obligation de créer un serialVersionUID pour les classes sérialisables. Ou cette erreur carrément mystérieuse, un  ClassNotFoundException sur java.util.Collections.unmodifiableList(<ma liste>)… Erreur que j’ai repéré lors d’un déploiement sur la plate-forme cible, alors que tout se passait bien sur la plate-forme de test en local…. Erreur de jeunesse là encore.
Google a écrit une White List qui liste les packages de la JRE autorisés sur son infrastructure. ( http://code.google.com/intl/fr/appengine/docs/java/jrewhitelist.html ) (et on trouve pourtant bien le support de la classe Collections).

Depuis cette annonce du support de java6 par la plate-forme GAE, tous leurs mainteneurs de frameworks Java se demandent si le fruit de leur travail fonctionneront sur GAE. Le test a été positif pour Groovy, Scala, Restlet, moins pour Jersey, pas bon les WebServices (JAX-RPC or JAX-WS) , OK pour Spring mais on ne peut pas utiliser la gestion de la transaction pour JPA, etc…
Le tableau de la compatibilité avec GAE est complexe, et n’a pas fini d’être rempli. Vous trouverez ici une liste des tests actuellement en cours sur chacun des frameworks.

Aujourd’hui nous allons voir qu’il est possible de déployer une application Wicket sur GAE - nous le verrons sur une application simple de type Hello World, partant de la création de l’application jusqu’à son déploiement.

Lire la suite du bllet »

Image par “Combined Media“, sous licence creative-commons by-nc

Du management…

Un collègue m’a récemment envoyé un papier de Steven Kerr intitulé “On the folly of rewarding A, while hoping for B“¹. Il montre que, très souvent, le discours officiel d’une organisation est de vouloir un comportement tout en mettant en place un système de récompense/punition qui, dans les faits, pousse les gens à un comportement tout autre, voire opposé. Par exemple on demande à un joueur de sport collectif d’avoir “l’esprit d’équipe” et pourtant on ne félicite que les actions individuelles : on ne résume un match de football que par les noms des buteurs. Autre exemple sportif, agacé qu’un joueur fasse trop de passes à l’adversaire, un entraineur sanctionne chaque passe ratée ; au match suivant personne ne fait plus aucune passe et le jeu est bloqué.

Exemple parfait de contre-productivité : une clinique veut réduire le nombre de décès. On met donc en place une prime qui doit récompenser le chirurgien qui a moins de X décès dans le mois sur le billard. Que va-t-il se passer ? On peut parier que dans les mois suivants tous les chirurgiens vont toucher la prime… En effet, dès qu’ils s’approchent du quota fatidique, ils repoussent toutes leurs opérations délicates au mois suivant ! Du coup les gens décèdent dans leur lit en attendant l’opération, mais ça n’est pas le problème du chirurgien. Tout le monde touche sa prime, cependant le nombre global de décès dans cette clinique augmente…

Cette théorie semble être un grand classique du management (le papier remonte à 1975) mais je n’en avais jamais entendu parler. Et quand je l’ai lu j’ai eu une illumination. Tenez, imaginez que vous vous tenez sur une grande étendue de sable, une sorte de drap rouge à la main ; vous le secouez un peu en vous demandant pourquoi vous avez ça à la main , quand vous entendez un bruit de sabots tagadam-tagadam dans votre dos et *vlan*.

… au génie logiciel.

J’ai compris beaucoup de choses sur le projet de développement en lisant cela.  Finalement, qu’est-ce que l’on demande aux développeurs ? Comportement ‘A’ : “Produire du code de qualité, maintenable par autrui”. Qu’est-ce que l’on récompense ? Les délais de livraison : comportement ‘B’. Je n’ai jamais vu un développeur se faire sanctionner pour du code mal écrit, non commenté ou conçu de traviole. Par contre, prenez du retard sur le développement, vous allez vous faire enguirlander et vous devrez rester tard tous les soirs pour faire bonne figure. Donc, si vous avez envie d’une vie de famille ou de loisirs : bâclez votre code. Ne commentez surtout pas, et ne testez que si l’on vous le demande. De toute façon c’est votre successeur qui sera pénalisé par le code non-maintenable. C’est lui (ou elle) qui ratera ses deadlines *niark niak niak niak* (<- rire façon méchant dans James Bond).

Rendre ‘A’ inévitable, récompenser  ‘B’

Je pense qu’il est impossible de changer la façon de fonctionner de la gestion de projet à un tel niveau de profondeur. Alors que faire ? Eh bien continuons à récompenser les délais (’B'), tant pis, mais à condition de considérer ‘A’ comme acquis. Il faut intégrer le contrôle qualité continu et automatisé à tout environnement de développement. Il doit être impossible de réussir un “build” (et donc de livrer) si l’artefact en question ne respecte pas tous les standards en vigueur. J’ajouterai même une revue obligatoire de tout code, du stagiaire au chef de projet, avant de pouvoir placer le post-it dans la colonne “fait” du tableau blanc. Passez par la colonne “en revue”, ne touchez pas vingt-mille francs. Enfin pas tout de suite… Soyons fous, récompensons la qualité .

[¹] Stephen Kerr, On the Folly of Rewarding A, While Hoping for B, The academy of Management Journal, Vol. 18, No.4 (Dec., 1975), 769-783.

Auteur : Guillaume Rams

Ressources : Je ne l’ai pas encore lu personnellement, mais Gabriel recommande le livre “Les stratégies absurdes“.

PS :  merci à Majirus pour l’article