[Blunderov] I have been fortunate enough to acquire the latest chess engine from the Chessbase stable - Deep Rybka 3 - which has a rating of approximately 3250. One of it's features is what is called "Monte Carlo" analysis. What the engine does is that, from a given position, it will play thousands of games against itself, generate a statistical analysis of which moves were the most successful and then produce a tree of variations derived from this. A very, very powerful tool. This approach is now beginning to yield results in the Japanese game Go.
By Mig on March 11, 2009 02:36 | Permalink | 8 comments
And then they came for the Go players. A Wired article on how Go computers are suddenly beating professionals after years of being patzers, or however you say patzer in Japanese. Interesting they use the Monte Carlo method, originating in physics and prevalent in economic and behavioral modeling of all sorts. And of course in chess analysis as implemented in ChessBase's Rybka and explained here. In 2002 I suggested that computers might use this method in search for endgames, mostly to extend the computer's reach into tablebases and to find/avoid blockades that often confound search. Straightforward search is now so fast that it might not be of much use.
Re:Go-ing Monte Carlo
« Reply #1 on: 2009-03-13 02:49:50 »
[Blunderov] I have been finding out some more about the Monte Carlo Method. It is utterly fascinating. This Wikilink is well worth a shot even though it might appear very dry and technical at first. It seems more to have been written by a philosopher than a mathematician and is thus more accessible to people like me who have zero mathematics. (The link has enough hyperlinks to keep even Marvin occupied until the final coffee and cheese phase of the proceedings.)
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used when simulating physical and mathematical systems. Because of their reliance on repeated computation and random or pseudo-random numbers, Monte Carlo methods are most suited to calculation by a computer. Monte Carlo methods tend to be used when it is infeasible or impossible to compute an exact result with a deterministic algorithm.[1]
Monte Carlo simulation methods are especially useful in studying systems with a large number of coupled degrees of freedom, such as fluids, disordered materials, strongly coupled solids, and cellular structures (see cellular Potts model). More broadly, Monte Carlo methods are useful for modeling phenomena with significant uncertainty in inputs, such as the calculation of risk in business. These methods are also widely used in mathematics: a classic use is for the evaluation of definite integrals, particularly multidimensional integrals with complicated boundary conditions.
The term Monte Carlo method was coined in the 1940s by physicists working on nuclear weapon projects in the Los Alamos National Laboratory.[2]
...
Overview
The Monte Carlo method can be illustrated as a game of battleship. First a player makes some random shots. Next the player applies algorithms (i.e. a battleship is four dots in the vertical or horizontal direction). Finally based on the outcome of the random sampling and the algorithm the player can determine the likely locations of the other player's ships.There is no single Monte Carlo method; instead, the term describes a large and widely-used class of approaches. However, these approaches tend to follow a particular pattern:
Define a domain of possible inputs. Generate inputs randomly from the domain. Perform a deterministic computation using the inputs. Aggregate the results of the individual computations into the final result. For example, the value of π can be approximated using a Monte Carlo method:
Draw a square on the ground, then inscribe a circle within it. Uniformly scatter some objects of uniform size throughout the square. For example, grains of rice or sand. Count the number of objects in the circle, multiply by four, and divide by the total number of objects in the square. The proportion of objects within the circle vs objects within the square will approximate π/4, which is the ratio of the circle's area to the square's area, thus giving an approximation to π. Notice how the π approximation follows the general pattern of Monte Carlo algorithms. First, we define a domain of inputs: in this case, it's the square which circumscribes our circle. Next, we generate inputs randomly (scatter individual grains within the square), then perform a computation on each input (test whether it falls within the circle). At the end, we aggregate the results into our final result, the approximation of π. Note, also, two other common properties of Monte Carlo methods: the computation's reliance on good random numbers, and its slow convergence to a better approximation as more data points are sampled. If grains are purposefully dropped into only, for example, the center of the circle, they will not be uniformly distributed, and so our approximation will be poor. An approximation will also be poor if only a few grains are randomly dropped into the whole square. Thus, the approximation of π will become more accurate both as the grains are dropped more uniformly and as more are dropped.
...
Applications As mentioned, Monte Carlo simulation methods are especially useful for modeling phenomena with significant uncertainty in inputs and in studying systems with a large number of coupled degrees of freedom. Specific areas of application include:
[edit] Physical sciences Monte Carlo methods are very important in computational physics, physical chemistry, and related applied fields, and have diverse applications from complicated quantum chromodynamics calculations to designing heat shields and aerodynamic forms. The Monte Carlo method is widely used in statistical physics, in particular, Monte Carlo molecular modeling as an alternative for computational molecular dynamics; see Monte Carlo method in statistical physics. In experimental particle physics, these methods are used for designing detectors, understanding their behavior and comparing experimental data to theory.
[edit] Design and visuals Monte Carlo methods have also proven efficient in solving coupled integral differential equations of radiation fields and energy transport, and thus these methods have been used in global illumination computations which produce photorealistic images of virtual 3D models, with applications in video games, architecture, design, computer generated films, special effects in cinema.
[edit] Finance and business Monte Carlo methods in finance are often used to calculate the value of companies, to evaluate investments in projects at corporate level or to evaluate financial derivatives. The Monte Carlo method is intended for financial analysts who want to construct stochastic or probabilistic financial models as opposed to the traditional static and deterministic models. For its use in the insurance industry, see stochastic modelling.
[edit] Telecommunications When planning a wireless network, design must be proved to work for a wide variety of scenarios that depend mainly on the number of users, their locations and the services they want to use. Monte Carlo methods are typically used to generate these users and their states. The network performance is then evaluated and, if results are not satisfactory, the network design goes through an optimization process.
[edit] Monte Carlo Simulation versus “What If” Scenarios The opposite of Monte Carlo simulation might be considered deterministic modeling using single-point estimates. Each uncertain variable within a model is assigned a “best guess” estimate. Various combinations of each input variable are manually chosen (such as best case, worst case, and most likely case), and the results recorded for each so-called “what if” scenario. [4]
By contrast, Monte Carlo simulation considers random sampling of probability distribution functions as model inputs to produce hundreds or thousands of possible outcomes instead of a few discrete scenarios. The results provide probabilities of different outcomes occurring. [5] For example, a comparison of a spreadsheet cost construction model run using traditional “what if” scenarios, and then run again with Monte Carlo simulation and Triangular probability distributions shows that the Monte Carlo analysis has a narrower range than the “what if” analysis. This is because the “what if” analysis gives equal weight to all scenarios.[6]
For an application, see Quantifying uncertainty under Corporate finance.
...
See also
[edit] General Statistics portal Auxiliary field Monte Carlo Bootstrapping (statistics) Demon algorithm Evolutionary Computation Las Vegas algorithm Markov chain Molecular dynamics Monte Carlo option model Monte Carlo integration Quasi-Monte Carlo method Random number generator Randomness Resampling (statistics)
[edit] Application areas Graphics, particularly for ray tracing; a version of the Metropolis-Hastings algorithm is also used for ray tracing where it is known as Metropolis light transport Modeling light transport in biological tissue Monte Carlo methods in finance Reliability engineering In simulated annealing for protein structure prediction In semiconductor device research, to model the transport of current carriers Environmental science, dealing with contaminant behavior Search And Rescue and Counter-Pollution. Models used to predict the drift of a life raft or movement of an oil slick at sea. In probabilistic design for simulating and understanding the effects of variability In physical chemistry, particularly for simulations involving atomic clusters In polymer physics Bond fluctuation model In computer science Las Vegas algorithm LURCH Computer go General Game Playing Modeling the movement of impurity atoms (or ions) in plasmas in existing and tokamaks (e.g.: DIVIMP). Nuclear and particle physics codes using the Monte Carlo method: GEANT — CERN's simulation of high energy particles interacting with a detector. CompHEP, PYTHIA — Monte-Carlo generators of particle collisions MCNP(X) - LANL's radiation transport codes MCU: universal computer code for simulation of particle transport (neutrons, photons, electrons) in three-dimensional systems by means of the Monte Carlo method EGS — Stanford's simulation code for coupled transport of electrons and photons PEREGRINE: LLNL's Monte Carlo tool for radiation therapy dose calculations BEAMnrc — Monte Carlo code system for modeling radiotherapy sources (LINAC's) PENELOPE — Monte Carlo for coupled transport of photons and electrons, with applications in radiotherapy MONK — Serco Assurance's code for the calculation of k-effective of nuclear systems Modelling of foam and cellular structures Modeling of tissue morphogenesis Computation of holograms Phylogenetic analysis, i.e. Bayesian inference, Markov chain Monte Carlo
....
</snips>
[Bl.] Enjoy
PS. All those "π" strings are, as I'm sure everybody realised, supposed to be "pi".
With or without religion, you would have good people doing good things and evil people doing evil things. But for good people to do evil things, that takes religion. - Steven Weinberg, 1999
Re:Go-ing Monte Carlo
« Reply #3 on: 2009-03-13 15:01:21 »
Quote:
And what flavor was the pi? Could we have key lime? Kindest Hermit
Even as I anticipate a suitable retaliation from the Dark Continent, I will offer my interpretation. In the mid West of North America, the video shows the most common understanding of "Monte Carlo" and its function, plus the concept that Pi are Round vs Cake are Square; it's the burden of those timid 'Prairie Folk'. That Key Lime rather then Apple was chosen, is inconsistent and possibly has political overtones.
And what flavor was the pi? Could we have key lime?
[Blunderov] Yes. I admit that my first thoughts are instinctively of a culinary rather than a mathematical bent when I hear the sound pəī. In these parts we get more meat than sweet; a real opening in the market here perhaps...? I hear good reports of American pəī. Key lime in particular. "Punkin" too -whatever that might be...
Could this be it (looks pretty punkin' to me)?
What is the proper post punkin' dining protocol if I may enquire? May one use one's hands as well?
Re:Go-ing Monte Carlo
« Reply #5 on: 2009-03-14 16:23:31 »
The hairier Hermit looked round to make sure nobody was watching and then admitted to having been possessed of or by (the relationship was never completely clear) an Australian Holden Monaro (rebadged as a Chevrolet SS) with a rather extensively reworked and supercharged Chevy 5.7l engine and 500 very thirsty ponies hiding somewhat unsuccessfully under the tower of equipment poking through its hood, sometime in the mid 1970s. So the feeling of sitting on the deck of an aircraft carrier sliding its tail around while converting petroleum distillate to noise, usually involving the accompaniment of expensive smoke, is not entirely unknown to him*. The workshop manual now resides on a shelf along with manuals for other hydrocarbon to noise conversion technologies from the interesting and exotic to the mundane and agricultural.
The Blue Thing, as it was known, did go like the clappers of hell when its gold plated linkages were prodded appropriately, but doing so with meaning was safe only when you had a long stretch of open road ahead, as neither the brakes nor the suspension were in the same class as the power production and delivery system. In fact, if you visualized an aircraft carrier's propulsion fitted to a dingy, you might be close to an accurate picture of the degree of control - or lack of it - exercised by the driver whose near supine view of the world was, without extreme exertions, largely confined to patches of the sky before and behind; and a hint of the feelings of trepidation that thoughts of clambering into the dark cave like and inevitably musty smelling interior should have evoked. Instead, it triggered massive adrenaline releases as, probably through lucky happenstance more than by design (nothing else showed much sign of design), a drive in The Blue Thing combined sheer exhilaration interspersed with moments of pure terror and accompanied by head splitting effects from the 8 Track tape player which added massive reality and acoustic distortion to the mix; all of which seemed the perfect prelude to, as Monty Python put it, "getting the juices flowing," in preparation for passionate - though desperately uncomfortable - couplings.
Given that there really wasn't a way to see what you were doing to put on a condom in the weird postures enforced on the occupants, it was lucky that, in those pre-H days**, safe sex merely meant remembering to put on the handbrake before paying attention to other things, and with the advantage of hindsight it is clear that it was as an oversized sex aid that The Blue Thing, scored (like its fortunate owner) its greatest successes.
Kindest Regards Hermit&Co
*Including observing the failure of such machines when the factory installed smoke which actually does all the work in really expensive systems is accidentally released.
With or without religion, you would have good people doing good things and evil people doing evil things. But for good people to do evil things, that takes religion. - Steven Weinberg, 1999
Author
Logged
