Upon continuing to learn about the general Monte Carlo field, I've found
it seems there is a general consensus in this community about a
distinction between Monte Carlo (MC) and what appears to be commonly
called Quasi Monte Carlo (QMC). MC is defined as using
random/pseudo-random distributions and QMC using more deterministic or
designed distributions that fit the problem better.
Just do search on google web or scholar and you'll get a wealth of hits.
But here are a few links to documents or pages that specifically
address this terminology:
http://www.arts.cornell.edu/econ/CAE/final.pdf
http://www.mas.ncl.ac.uk/~ngl9/docs/MCQMC.pdf
http://www.math.hkbu.edu.hk/~gwei/sci3510/ch1.pdf
http://mathworld.wolfram.com/MonteCarloMethod.html
http://mathworld.wolfram.com/Quasi-MonteCarloIntegration.html
It also seems that today quite often "Monte Carlo" generally is used to
describe any kind of statistical sampling using random or other
distributions to approximate solutions to problems like David Doshay
pointed out.
So would it be helpful to distinguish between MC go and QMC go programs
- maybe a little.
Since I'm just learning about this I might be misunderstanding some
concepts. But besides doing obvious things like minimizing memory usage
and optimizing code so that you can increase the sample size, there are
many well known strategies to decrease the variability of the
simulation. These are called variance reduction techniques. Generally
Monte Carlo standard error decreases based on the square root of the
sample size (quadrupling the sample size cuts the the standard error in
half). I would think in part this would depend on the problem, so not
sure if this applies to MC go or how to measure. Variance reduction
methods are used to improve the distribution improving the results
(error) without increasing the simulation size as much.
Here is a list of some of them without any explanation (searching on any
of these terms with monte carlo should turn up lots of hits):
-Common Random Numbers
-Antithetic Variates
-Control Variates
-Importance Sampling
-Stratified Sampling
-Conditional Sampling
-Systematic Sampling
Most of the research using MC methods seems to be for numerical
integration, finance applications, and physics applications; not applied
to game theory. It may be be challenging to understand how to translate
these ideas to MC go or whether they would be helpful.
-Matt
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
