Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Olivier Teytaud <>
Submitted on : Wednesday, June 27, 2012 - 6:46:35 AM
Last modification on : Thursday, June 17, 2021 - 3:46:29 AM
Long-term archiving on: : Friday, September 28, 2012 - 2:21:37 AM


Files produced by the author(s)


  • HAL Id : hal-00712388, version 1



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. pp.280-285. ⟨hal-00712388⟩



Record views


Files downloads