Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
5 mai 2010 3 05 /05 /mai /2010 12:00

On me demande régulièrement de citer d'autres applications de la technologie MCTS que le jeu de Go; voici donc un bref résumé.

On trouvera une présentation de la technologie MCTS ici:
http://teytaud.over-blog.com/article-35709049.html


1) En restant dans le domaine des jeux:
La technologie dite Monte-Carlo Tree Search (MCTS; on parle parfois aussi de "Upper Confidence Trees") est appliquée avec beaucoup de succès sur des jeux difficiles, où l'humain est traditionnellement bien meilleur que la machine: Hex, Havannah, sont des exemples.
Elle est aussi très efficace pour jouer sur la simple base de règles, sans développement spécifique des jeux: ainsi
MCTS gagne toutes les compétitions de "jeu général", c'est-à-dire les compétitions où les règles sont fournies sous format informatique aux programmes, qui ignorent à l'avance à quel jeu ils vont jouer. Ainsi, les programmes peuvent s'adapter directement à de nombreux jeux, y compris des variantes originales de Go.

Le jeu de Havannah



2) Complètement en dehors des jeux

Notre équipe a réalisé avec succès (avec Carnegie Mellon university) une application à l'optimisation sur des graphes, avec notamment le cas industriel de l'optimisation de librairie de calcul linéaire (http://hal.inria.fr/inria-00379523/fr/). Ce type d'outils est crucial dans toutes les industries où les transformées de Fourier discrètes sont capitales. Ceci est déjà opérationnel, dans la librairie Spiral (http://www.spiral.net/).

Nous démarrons par ailleurs un projet dans l'énergie, conjointement avec la société Artelys; il s'agit de comparer MCTS et les techniques usuelles pour le choix de gestion d'un parc de production électrique. L'application est très préliminaire, mais les essais sur des cas tests de dimension comparable sont encourageants.



Nos confrères à Maastricht ont réalisé des applications à la gestion de stocks: en effet, choisir une action sur un stock en ayant des incertitudes sur ce qui peut entrer par ailleurs dans le stock (et à quel prix) est très proche de poser une pierre sur un goban
en ignorant où l'adversaire va poser sa pierre.

Nous avons des applications de type fondamental, appelées optimisation non-linéaire chère et apprentissage actif cher. Ces méthodes, pas encore directement utilisées dans l'industrie, donnent de bons résultats sur des cas tests; les domaines touchés possiblement sont tous ceux où choisir quel prototype construire, lorsqu'il est long et/ou cher de prédire l'efficacité du prototype; les industries automobile, aérienne, spatiale par exemple.

Globalement, tout le champ du contrôle en temps discret, sur un nombre de pas de temps modéré et possiblement en très grande dimension, est concerné. Le jeu de Go est dans une fourchette idéale, avec une grande dimension (>300 actions possibles en début de partie) et un nombre de pas de temps modéré (une partie peut difficilement dépasser 400 coups); nous sommes là dans un registre mal traité par les techniques classiques, couvrant un grand nombre de problèmes, et où MCTS apporte beaucoup.

 

 

A paper on continuous UCT: http://hal.archives-ouvertes.fr/hal-00542673/en/

Bibtex entry:

@inproceedings{COUTOUX:2011:HAL-00542673:1,
    HAL_ID = {hal-00542673},
    URL = {http://hal.archives-ouvertes.fr/hal-00542673/en/},
    title = { {C}ontinuous {U}pper {C}onfidence {T}rees},
    author = {{C}ouёtoux, {A}drien and {H}oock, {J}ean-{B}aptiste and {S}okolovska, {N}ataliya and {T}eytaud, {O}livier and {B}onnard, {N}icolas},
    abstract = {{U}pper {C}onfidence {T}rees are a very efficient tool for solving {M}arkov {D}ecision {P}rocesses; originating in difficult games like the game of {G}o, it is in particular surprisingly efficient in high dimensional problems. {I}t is known that it can be adapted to continuous domains in some cases (in particular continuous action spaces). {W}e here present an extension of {U}pper {C}onfidence {T}rees to continuous stochastic problems. {W}e (i) show a deceptive problem on which the classical {U}pper {C}onfidence {T}ree approach does not work, even with arbitrarily large computational power and with progressive widening (ii) propose an improvement, termed double-progressive widening, which takes care of the compromise between variance (we want infinitely many simulations for each action/state) and bias (we want sufficiently many nodes to avoid a bias by the first nodes) and which extends the classical progressive widening (iii) discuss its consistency and show experimentally that it performs well on the deceptive problem and on experimental benchmarks. {W}e guess that the double-progressive widening trick can be used for other algorithms as well, as a general tool for ensuring a good bias/variance compromise in search algorithms.},
    language = {{A}nglais},
    affiliation = {{L}aboratoire de {R}echerche en {I}nformatique - {LRI} - {CNRS} : {UMR}8623 - {U}niversit{\'e} {P}aris {S}ud - {P}aris {XI} - {TAO} - {INRIA} {S}aclay - {I}le de {F}rance - {INRIA} - {CNRS} : {UMR}8623 - {U}niversit{\'e} {P}aris {S}ud - {P}aris {XI} - {C}hercheur {I}nd{\'e}pendant - {A}ucune },
    booktitle = {{LION}'11: {P}roceedings of the 5th {I}nternational {C}onference on {L}earning and {I}ntelligent {O}ptimizatio{N} {LION}'11: {P}roceedings of the 5th {I}nternational {C}onference on {L}earning and {I}ntelligent {O}ptimizatio{N} },
    pages = {{TBA} },
    address = {{I}talie },
    audience = {internationale },
    day = {31},
    month = {01},
    year = {2011},
    URL = {http://hal.archives-ouvertes.fr/hal-00542673/PDF/c0mcts.pdf},
}

Partager cet article

Repost 0
Published by teytaud - dans Recherche
commenter cet article

commentaires