Consistent Belief State Estimation, with Application to Mines

Adrien Couetoux 1 Mario Milone 1 Olivier Teytaud 1, 2
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Abstract--Estimating the belief state is the main issue in games with Partial Observation. It is commonly done by heuristic methods, with no mathematical guarantee. We here focus on mathematically consistent belief state estimation methods, in the case of one-player games. We clearly separate the search algorithm (which might be e.g. alpha-beta or Monte-Carlo Tree Search) and the belief state estimation. We basically propose rejection methods and simple Monte-Carlo Markov Chain meth- ods, with a time budget proportional to the time spent by the search algorithm on the situation at which the belief state is to be estimated; this is conveniently approximated by the number of simulations in the current node. While the approach is intended to be generic, we perform experiments on the well- known Mines game, available on most Windows and Linux distributions. Interestingly, it detects non-trivial facts, e.g. the fact that the probability of winning the game is not the same for different moves, even those with the same probability of immediate death. The rejection method, which is slow but has no parameter and which is consistent in a non-asymptotic setting, performed better than the MCMC method in spite of tuning efforts. pommt
Type de document :
Communication dans un congrès
Technologies and Applications of Artificial Intelligence, International Conference on, 2011, Hsinchu, Taiwan. IEEE computer society, pp.280-285, 2011
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00712388
Contributeur : Olivier Teytaud <>
Soumis le : mercredi 27 juin 2012 - 06:46:35
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 02:21:37

Fichier

mines.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00712388, version 1

Collections

Citation

Adrien Couetoux, Mario Milone, Olivier Teytaud. Consistent Belief State Estimation, with Application to Mines. Technologies and Applications of Artificial Intelligence, International Conference on, 2011, Hsinchu, Taiwan. IEEE computer society, pp.280-285, 2011. 〈hal-00712388〉

Partager

Métriques

Consultations de la notice

376

Téléchargements de fichiers

135