Samedi 10 décembre 2011 6 10 /12 /Déc /2011 08:21

A Linux program for evaluating your level in Go

Hi;

 

you want to evaluate quickly your level in Go and you have a machine under Linux ?

 

Here a tool for doing this:

 

1) Download http://www.lri.fr/~teytaud/yourLevel.tgz ; for example

    with your favorite tool; if you like lynx, you might:

      lynx -dump -source http://www.lri.fr/~teytaud/yourLevel.tgz > ./yourLevel.tgz

 

2) Unzip it:

     tar -zxvf ./yourLevel.tgz

     cd yourLevel

 ===> if you have a 64 bits machine, remove mogo, and "cp mogo64 mogo"

 

3) Install gogui, if you don't already have it; http://sourceforge.net/projects/gogui/

 

4) launch ./testeur99

 

  ==> a board should come up; just play. When you feel you have lost, you just start a new game;

       if you have won, the machine will tell you that it resgins.

  ==> you can switch off the machine, and switch on again later; the current state is kept in memory.

  ==> after each game, the level of your opponent will be increased or decreased depending on your results.

 

5) Where are stored your results ?

   The results are stored in files with name starting with "gameRes".

   The current level of your opponent is in "currentSims"; the higher it is, the higher your rank.

   If you << cat `ls -ctr gameRes*` | grep ':[0-9]' >> you will see all your results:

    - a line "wins: 1111 3333" means that you have won

 

   If you send these files to me, I'll try to tell you the correspondence with Kyu/Dan level; I will also

   post here a correspondence table as soon as possible.

 

 

6) How can I tell the machine that I change user ?

 

  After a few games, the machine should adapt to a new opponent.

  However, you can reinit the process (remove the memory) by

  writing "10000" in "currentSims": 

  echo 10000 > currentSims

  If you assume that your level is around 3000,

  then

  echo 3000 > currentSims

  If you want to remove the logs, just remove the files:

  rm gameRes*

 

Par teytaud
Ecrire un commentaire - Voir les 0 commentaires
Vendredi 30 septembre 2011 5 30 /09 /Sep /2011 17:36

Les fourmis en une page

 

 

Un bref survol de wikipedia sur ces bestioles, à l'occasion d'un séjour à Taiwan, où chaque nourriture qui traine donne lieu à une invasion de mini-fourmis.

 

1) Colonies & Nids

Les fourmis ont des nids de 20m environ, constitués de nombreuses galeries souterraines et dans les recoins. Une colonie de fourmis est un tas de nids de fourmis qui sont copines entre elles (qui ne se font pas de guerres, et sont capables de se mettre à travailler ensemble si on les met ensemble; une colonie est faite de fourmis génétiquement proches, quoiqu'une alimentation commune semble être aussi un facteur de pacification des relations). Ca peut faire 300 millions d'individus genre sur une ville en Asie. Ca peut être très grand parfois, comme en Europe (il y en a une qui va d'Espagne à Italie en passant par la France).

 

2) Vie et combat.

Une fourmi c'est oeuf, larve, nymphe, adulte (pour la plupart des variétés de fourmis du moins). Chez certaines espèces, la fourmi de base attend 3cm. Les fourmis mordent, et certaines piquent, et certaines projettent de l'acide. Les fourmis peuvent elever des pucerons, les protégeant des prédateurs; il s'agit de la seule espèce à part l'homme à domestiquer des animaux. Dans certains cas elles élèvent des chenilles. Elles ne sentent pas la chaleur, et peuvent mourir bêtement de cuisson. Certaines espèces sont nécrophages.

 

3) Volumétrie.

Il y en a 10 millions de milliards environ sur terre. Le poids total est d'environ 4 fois le poids total de tous les vertébrés, humains inclus.

 

4) Fourmis et hommes

Les fourmis ont des morsures qui font mal mais disparaissent vite en général; les espèces pouvant déclencher un choc anaphylactique sont en fait très rares et il faut une attaque hyper-massive pour arriver à ça. Certains mangent des fourmis, et les fourmis peuvent être utilisés pour rendre une terre meuble. Des fourmis déplacées de leur habitat peuvent faire de gros dégâts en remplissant vite une niche écologique en l'absence de prédateurs; ainsi la fourmi d'argentine qui a colonisé l'Europe. Deux colonies distinctes en Europe, dont l'une très agressive, pourraient finir par la mort de l'une des deux.

Par teytaud - Communauté : Science & Avenir
Ecrire un commentaire - Voir les 0 commentaires
Lundi 29 août 2011 1 29 /08 /Août /2011 06:10

Des éducatifs gratuits et biens pour votre ordinateur

Vous voulez des jeux éducatifs bons et gratuits ? Des solutions existent; je les rassemble ici en tâchant d'avoir le lien direct vers la page utile:

Par teytaud - Publié dans : Informatique
Ecrire un commentaire - Voir les 1 commentaires
Mercredi 24 août 2011 3 24 /08 /Août /2011 04:36

Multiprecision with Octave - a dirty patch using Aribas

Preliminaries:

Octave is a just great free software, very good alternative to the expensive Matlab.

It does not handle multiprecision (to keep it simple, let's say that multiprecision is computation

with very high precision).

Aribas is a GNU free tool for multiprecision.

This page presents a simple tool for using Aribas within Octave.

 

Keywords:

- Fractals

- Multiprecision, high precision computing

- Opensource software (Octave, Aribas)

- Buggy source code

 

Why multiprecision matters ?

Sometimes, computation errors cumulate until reaching a very significant level.

It is widely claimed that the satelite-lifting rocket Ariane 5 exploded due to computation errors

(see www.intel.com/standards/floatingpoint.pdf  for more on this example and other examples).

 

Download:

you just have to put the following lines in a file "aribas_eval.m",

in the exec path of octave:

============ aribas_eval.m ===================

function r=aribas_eval(s)
  n=round(rand*10000);m=round(rand*10000);
  chaine=(sprintf('echo "%s.\nexit" | sed ''s/\\^/**/g'' > /tmp/test%d%d.ari ',s,n,m));
 system(chaine);
  system(sprintf("aribas -b /tmp/test%d%d.ari | tail -1 |sed 's/_//g' > /tmp/testb%d%d.ari",n,m,n,m));
  r=load(sprintf('/tmp/testb%d%d.ari',n,m));
 system(sprintf('rm /tmp/test%d%d.ari /tmp/testb%d%d.ari',n,m,n,m));
end

==============================================

 

How to use:

- Write your code with the Octave "eval" function for the computations that you want to see in multiprecision.

- Check that it works

- Replace "eval" by "aribas_eval"

     ==> this is supposed to be a multiprecision version

     ==> however, there are plenty of bugs

 

Example:

mod(eval("(2**250)-1"),256)

    returns 0 (which is wrong --- precision error)

mod(aribas_eval("(2**250)-1"),256)

    returns 255 (which is ok)

 

Important remarks:

- no guarantee

- known bugs: handles only a very small subset of Octave's function

- this will be maintained and improved only as long as there is no better such functionality in Octave

- if you know a better way for doing this in octave just tell me and this page will disappear

 

Contacts:

   olivier . teytaud

      at  gmail . com

I am the only responsible of any mistake in the code. The code is not guaranteed, it is even not guaranteed to do

anything which is useful for anyone - if you use it, you have to check yourself that it is ok for you.

The code is completely free (free code, free of charge).

Par teytaud - Publié dans : Informatique
Ecrire un commentaire - Voir les 0 commentaires
Vendredi 17 juin 2011 5 17 /06 /Juin /2011 21:45

MoGo & MoGoTW: des algorithmes qui jouent au Go et au-delà

 

http://www.lri.fr/~caillou/taotext-small.jpg

 

 

http://www.cgal.org/images/inria.jpg

http://www.lri.fr/~fci/Grid5000/images/logo.jpg

http://webmov.lri.fr/public/anglais/Images/lri.png

 

 

http://proval.lri.fr/logo_cnrs.jpg

 

 

 

 

http://www.bibs.u-psud.fr/images/logo-UPS11.jpg

 

http://www.ljll.math.upmc.fr/mcparis09/LogoDigiteo.jpg

 

 

 

 

 

 

 

I. Introduction

    Le Go, vieux jeu asiatique,
    résiste toujours aux machines.Il fait partie de ces jeux où la méthodologie usuelle, à base d'algorithme alpha-beta

    et de fonction d'évaluation approchée, ne donne rien de bon.

 

http://www.lri.fr/~teytaud/jeudego.jpg

 

    Forte combinatoire, pas de fonction d'évaluation
    naturelle. Depuis 2006, une méthodologie appelée MCTS s'impose comme le meilleur
    outil, et s'applique en outre à de nombreux jeux difficiles et à de nombreux
    problèmes de planification dans l'incertain.MoGo(TW) est une implémentation de MCTS pour le

    jeu de Go.

 

En 2010, MoGoTW a obtenu la certification Dan par l'association Taiwanaise de Go:
           http://mepopedia.com/forum/read.php?160,5537,5537

 

    En 2010, MoGoTW a gagné la médaille d'or à TAAI 2010 à la fois en Go 9x9, en Go 13x13 et en Go 19x19 !

     Détails sur http://ai.csie.ndhu.edu.tw:9898/eng/

taaiGo.JPG



II. Algorithmique

 

MCTS (dont on présente ici la variante la plus connue, UCT) est un algorithme pour prendre des décisions dans des environnements incertains (par exemple, quand on ignore ce que va jouer l'adversaire; mais des incertitudes de type météorologique ou climatique peuvent être envisagées). Ses principes sont:
- un arbre (sous-arbre, stocké en mémoire, de l'immense arbre des possible) grossissant itérativement;
- des simulations aléatoires pour évaluer les feuilles de cet arbre.

Algorithmiquement, dans le cas du Go (on peut généraliser à d'autres jeux et à d'autres problèmes):

  • a. D'abord, on construit en mémoire un arbre avec un seul noeud, qui est le statut actuel du goban.

Example of UCT tree: each node "knows" its number of simulations
and its number of wins. Thanks to David Silver, original author of this figure.



  • b. Alors, démarrez à la racine, et trouvez un chemin jusqu'à une feuille; à chaque noeud, pour choisir un noeud fils, vous choisissez un fils qui a le meilleur compromis exploration/exploitation: le compromis exploitation/exploration dans UCT est la somme:

    • d'un terme d'exploitation, privilégiant les noeuds qui ont donné de bons résultats au joueur qui doit jouer en ce noeud, égal au taux de victoire des simulations passant par ce fils;

    • le terme d'exploration: la racine carrée du ratio "log(nombre de simus(noeud père)) / nombre de simus du fils".
    Les motivations pour ce terme proviennent de la littérature dite des "bandits manchots" (Lai Robbins, 1985).

  • c. Une fois arrivée à une feuille, jouez aléatoirement de la feuille jusqu'à une fin de partie.

  • d. Alors, mettez à jour les statistiques dans l'arbre: mettez à jour le nombre de simulations dans chauqe noeud, et le nombre de victoires pour noir et pour blanc.

  • e. S'il reste du temps, retournez en b.

  • f. Sinon, décidez vous pour l'action la plus fréquemment simulée à la racine.

Ceci est le pseudo-code d'UCT, décrit plus formellement dans Kocsis et al, 2006. Le premier MCTS remonte

en fait à Coulom 2006. De nombreuses variations ont été formulées, dont

  • le fameux RAVE (rapid action value estimates, qui a son origine dans MoGo) qui utilise des statistiques biaisées mais à variance réduite pour guider l'exploration dans les zones où le nombre de simulations est faible;
  • des termes d'exploration différent, utilisant notamment des biais appris hors-ligne (machine learning appliqué aux patterns, implémentation dans MoGo décrite dans Lee et al 2009);
  • une parallélisation massive, décrite dans Cazenave et al. 2007, Gelly et al. 2008,
  • un apprentissage automatique sur grille pour les livres d'ouvertures, basé sur un niveau "meta" du MCTS (Audouard et al, 2009).

Des extensions au continu (Couetoux et al, 2011), des versions partiellement observables (Auger 2011, Teytaud et al, 2011) ont permis des applications variées (cf section V). MoGo(TW) a obtenu en 2010 le prix de la meilleure contribution aux jeux pour l'année 2009 (chessBase award).


III. Performances contre humains
 Le jeu de Go se joue en 9x9, 13x13, et 19x19. Le handicap mesure l'avance que le joueur
 le plus fort (ici l'humain) accorde à la machine pour compenser la différence de niveau.

   a) Palmarès de MoGo en 9x9: victoires sans handicap
    - première victoire contre un pro en 9x9
    - première victoire contre un top pro en 9x9 en tant que noir (noir est plus dur; à ma
                   connaissance on est toujours les seuls à avoir réussi ce type de perfs)

   b) Palmarès de MoGo en 13x13: victoires avec handicap modéré
    - 2010: première victoire contre un 6D à handicap 2

http://www.lri.fr/~teytaud/blo1313.jpgLa première victoire contre un joueur 6D

à handicap 2 en 13x13


    - 2011: première victoire contre un pro à handicap 2.5

   c) Palmarès de MoGo en 19x19: le chemin est encore long - fort handicap!
    - première victoire contre un pro en 19x19 à H9
    - première victoire contre un pro en 19x19 à H6
    - première victoire contre un top pro en 19x19 à H7 (record égalé depuis, mais non battu):

 

     http://img.epochtimes.com/i6/902101213481538--ss.jpg

 

 

 

http://www.lri.fr/~teytaud/H7.jpg

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

La première victoire à H7 contre un top pro

(Performance égalée par Pachi récemment:

le groupe J4 est mort et noir gagne)

 

 

 

 

 

 

Notons qu'il y a quelques années les machines perdaient même à handicap 29,
   un nombre colossal qui ne fait aucun sens pour les joueuers humains et montre l'immense progrès réalisé depuis, loin d'être explicable par le seul essort des machines.

   d) Autres variantes du jeu de Go
   (http://teytaud.over-blog.com/article-blind-go-random-go-13x13-go-rengo-73149193.html, 2010):
        - victoire contre des pros sur un match complet
            (3 parties sur 4) en go 9x9 en aveugle, dont 2/2 contre un top pro.
        - victoire contre un 6D sans handicap sur des positions aléatoires.

IV. Diffusion & importance du logiciel
    - le code MoGo a eu des dizaines de milliers de downloads
        ==> chessBase award en 2009 pour la plus grande avancée de l'année dans les jeux.

    - forte internationalisation (contributeurs sur 3 continents)

    - centre d'un MOU entre deux universités asiatiques http://www.nchc.org.tw/en/news/index.php?NEWS_ID=70

    - son utilisation de patterns dans le Monte-Carlo a influencé tous les codes existants.
    - première utilisation de la technique Monte-Carlo Tree Search sur machine
        massivement parallèle (cumulant multithreading et parallélisation à passage de messages); utilisation régulière sur

        Grid5000 et optimisation de la bibliothèque d'ouvertures sur grille.

http://www.lri.fr/~teytaud/gdx.png  
Un des clusters de Grid5000 (cluster de SMP).


V. Au delà du Go
  Le MCTS s'applique loin au delà du jeu de Go (voir ici une explication des principes du MCTS). Citons:
    - application au power management http://www.lri.fr/~teytaud/iomca.html
    - applications à des problématiques fondamentales d'IA
    - applications à des jeux de cartes partiellement observables (IA au meilleur
       niveau humain à Urban Rivals www.urban-rivals.com , jeu à 11 millions d'utilisateurs
       enregistrés)http://www.lri.fr/~teytaud/ur.gif

 

 

 

 

 

 

 

 

 

 

Un personnage d'Urban Rivals

 

 

 


Par teytaud - Publié dans : Recherche - Communauté : Science & Avenir
Ecrire un commentaire - Voir les 0 commentaires
Créer un blog gratuit sur over-blog.com - Contact - C.G.U. - Rémunération en droits d'auteur - Signaler un abus - Articles les plus commentés