Tricks with Monte Carlo Simulations(countbayesie.com)
countbayesie.com
Tricks with Monte Carlo Simulations
http://www.countbayesie.com/blog/2015/3/3/6-amazing-trick-with-monte-carlo-simulations
2 comments
I think the most interesting application of Monte Carlo that I've come in contact with is for pruning the game trees for Go (the game). It was similar to using minimax, except the tree was only evaluated at points chosen by Monte Carlo and decisions were made from there. From what I know, this seems to be one of the better methods for playing go ATM.
This approach is known as Monte Carlo Tree Search, which usually follows a weighted search by how good the move is until it finds a leaf in the explored tree. Then it makes a new set of leaves for its moves and scores the path by randomly making moves until the game is finished and propagating the result up the path to the root. The wikipedia article has a better explanation: http://en.wikipedia.org/wiki/Monte_Carlo_tree_search
From what I understand, it is also commonly used to predict optimal poker plays.
The number of in-the-circle counts is S ~ binomial(N,p) where N=1e5 and p=π/4, which we'll take to be 0.75. Then
and the standard deviation of S is the square root of this, or about ∆=137.
(If we weren't willing to use a guess for p in the variance above, we could use the universal bound of N/4.)
The estimate of π is (S/N) * 4, so the sdev on the estimate of π is (∆/N)*4 = 0.0055.
So the estimate turned out to be a little less than one standard deviation higher than π. Which is satisfying.
--
The point being that, for just a little extra work, you get not only a Monte Carlo estimate, but also a bound on its error. Sometimes the bound is just as important as the estimate.