Overblog
Suivre ce blog Administration + Créer mon blog
30 mai 2016 1 30 /05 /mai /2016 09:44

Reader-friendly introductions to AI topics, for dummies (like me :-) )

olivier.teytaud@gmail.com

A lot of “reader’s digest” versions of tutorial or famous articles :-)

(usually no original research, just an overview of existing works; I’ll try to satisfy all requests for clarifying something, because if it’s unclear, it means that it is not clear enough in my own mind and this matters a lot for me :-) )







Absolutely not related to AI (sometimes I do something else :-) ):

Partager cet article
Repost0
3 juillet 2012 2 03 /07 /juillet /2012 12:11

 

 

Zenity is just a great program for doing quickly a Graphical User Interface on Linux.

 

I am sure you can understand the following program, which asks if you want to increase or decrease,

and runs "./increase" or "./decrease" accordingly:

 

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

 

#!/bin/bash

 

while [ true ]

do

#uses zenity to ask first.

zenity --question --title "Difficult level" --text "Increase ?" --ok-label="Increase" --cancel-label="Decrease"

if [ "$?" -eq "0" ]

then

./increase

else

./decrease

fi


done

===========================================
Isn't it easy ? The loop is here so that the user can call increase or decrease many times...
zenity.jpeg
And you get this =======================>
and a great tutorial:
Partager cet article
Repost0
19 juin 2012 2 19 /06 /juin /2012 10:11
MCTS algorithm
Input: a state S
Output: a decision D
Global variable: a tree T, each node having nbSims
    initiliazed at a single node with state S and nbSims=0 and totalReward=0
While (I have time)
{
    Do one simulation from state S until a game is over 
            ==> we get a sequence s(0), s(1), s(2), s(3),..., s(k)     (with s(0)=S and s(k) a final state)
            ==> we get a reward r
    Consider i minimal such that s(i) is not in T
    If such an i exists, then add s(i) in T, with an edge from s(i-1) to s(i)
    For each i such that s(i) is in T:
                 s(i).nbSims++
                 s(i).totalReward+=r
}
Procedure for doing one simulation from state S until a game is over:
s=S
while (s it not terminal)
{
    choose child s' of s such that UCB(s') is maximum
    s=s'
}
Procedure for computing the UCB score of a node s':
{
    meanReward=s'.totalReward / s'.nbSims
    fatherSims=s'.father.nbSims
    UCB = meanReward + sqrt( log(fatherSims) / s'.nbSims)   
}
Based on research in the TAO team
Partager cet article
Repost0
4 mars 2012 7 04 /03 /mars /2012 00:26

I am French and spend one year in Tainan, a city in the south of Taiwan. I had been told, prior to coming, that Tainan

was particularly friendly, even compared to Taiwan which is a particularly friendly country.

 

I have spent 7 months here, and there are things that I find just great here - in particular, I've collected a short list of the 4 most surprising recommendations in a list of politeness rules displayed on a wall in my children school. The rules were translated in English, so no mistake in translation (except in case of mistake in reporting...).

 

1. "Surprise others by performing random acts of kindness". The main thing is that this is really taught to children, implicitly and explicitly - and that really works. Beyond the very strict honesty of people here (a seller can find you 300 meters away and 5 minutes after you bought something a few cents too expensive due to a mistake he/she has made, so that he can give you back the few additional cents...), people can take a lot of time and energy for helping people they have never met before.

 

2. "Be positive and enjoy life". 

 

3. "If you are asked a question in conversation, ask a question in return." This is less widely appreciated by westerners, in particular in countries like France in which we have a very strong focus on privacy - as a matter of facts, people who don't know you can ask questions that only close friends might ask in France. Keep in mind that it is intended to show interest.

 

4. "On a bus, always face forward." This is quite a mistery to me, I can understand that some people find that more comfortable to face forward, but I don't understand why it's a matter of politeness. If someone has an explanation please tell me :-)  in trains for example, all seats face forwards.

 

All is not perfect; for example, when it's about gifts, the notion of conflict of interest is not considered.

Also there is a very strong sense of hierarchy; even politeness is very related to hierarchy - for this I prefer the French culture of equality - French people know that when you have a high position it probably means that you have stolen it. But many people here are masters in this special kind of politeness which both makes the world nicer and opens all doors; some kind of courtesy which is both a pleasure and a strength. 

 

If you spend time here, you will also notice that children, or students, are extremely quiet here, and it is considered as a main politeness requirement - you can have a meal in a restaurant with a group of students sitting next to you, the noise will be very low. A teacher in Taiwan told me that there is a very strong pressure on parents here, and that children are supposed to be perfect and quiet for everything, and that this is why people have almost no children here (I don't know how Taiwan will look like in 2050 with so few babies...). The result is impressive to me; nonetheless, maybe there are bad consequences as well, the social pressure being, I guess, much stronger than in Europe.

 

There's much more to say, in particular the fact that politeness includes gestures more than in western countries - but I guess the rules above are less widely known. I don't speak Chinese, and people with both Taiwanese and Western culture are more than welcome for commenting - I might miss plenty of important points and deeply misunderstand some elements. Anyway, if you have the opportunity of spending one year in Taiwan, just do it - it's a real change!

 

 

Partager cet article
Repost0
10 décembre 2011 6 10 /12 /décembre /2011 08:21

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*

 

Partager cet article
Repost0
30 septembre 2011 5 30 /09 /septembre /2011 17:36

 

 

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.

Partager cet article
Repost0
29 août 2011 1 29 /08 /août /2011 06:10

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:

Partager cet article
Repost0
24 août 2011 3 24 /08 /août /2011 04:36

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

Partager cet article
Repost0
17 juin 2011 5 17 /06 /juin /2011 21:45

 

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

 

 

 


Partager cet article
Repost0
17 juin 2011 5 17 /06 /juin /2011 21:40

 

What is rengo ?

Rengo consists in having two players playing Go as a team, without communicating - each player plays in turn.

 

What is this page about ?

You have two programs which play Go in GTP and you want to use them as a Rengo pair - this page is for you.

 

Where can I download this script ?

http://www.lri.fr/~teytaud/rengo1.1.tgz

 

How to use it ?

- uncompress the archive: "tar -zxvf rengo1.1.tgz"

- Modify gtpmogo1 and gtpmogo2 - these are the two scripts which are called by the rengo program.
   They are supposed to speak GTP, or sufficiently of GTP for your use.
   For example, "gtpmogo1" might be simply "/usr/games/gnugo --mode gtp" and
   "gtpmogo2" might be simply "/usr/games/mogo --9 --nbTotalSimulations 5000". Then, gnugo and mogo
   will play the rengo together.
- Then the script "rengo" is a GTP program which uses the two programs above in turn. The first
   player is randomly chosen.
- The script "compa" launches games between "rengo" and another script, "gtpmogo".
- The script "check" gives results of the "compa" script.

 

So what ?

- you can use it in gogui

- you can use it in gogui-twogtp

   so you can do experiments like "what if program A plays againt programs B and C"

   or "what if programs A and D play againt programs B and C".

 

Bugs:
- There are more bugs than I can list here. Only the main ones below :-)
- Sometimes some codes are not properly killed. Kill manually :-)

- Some time is lost in some "sleep" commands (yes, it's dirty programming). So the CPU is not fully used.

    But with non-negligible time setting this should be negligible (maybe :-) )

 

Help:

- send an email if you have troubles - I'm happy when my codes can be useful to anyone :-)

Partager cet article
Repost0