Monte carlo method - anyone got .net example? | Tech Off

alexmac

Has anyone got a good example in .net of using a monte carlo method I can use to help me understand the concept?

Alot of the examples I can find assume a good knowledge of maths.

Dr Herbie
Horses for courses

You'll have to be more specific about which 'Monte Carlo' method.
In simulations, a Monte Carlo method is any algorithm that is driven by random numbers. (Can I get away with a quick self-promoting plug for my own blog entries here? They don't have any real maths, only basic arithmatic, and the code is all in the C9 sandbox.)

Herbie

alexmac

In reply to Dr Herbie

#Sep 10th, 2008 @ 12:10 AM

Thanks for your reply Dr Herbie.

Monte Carlo is a term I have heard banded around alot so I wanted to understand what it is and what you might use it for.

One of the articles I looked at was:
http://en.wikipedia.org/wiki/Monte_carlo_method

This has an example of a game of battle ships. Obviously in battleships you dont know where the oponents ships are so you have to make a few random shots to begin with (I guess this is where the random bit comes in!).

Its probably (or is it?) better to space the shots out a bit so there is the potential to hit more than one ship. Then if you score a hit you can then make educated guesses about where the whole ship is.

Dr Herbie
Horses for courses

In reply to alexmac

#Sep 10th, 2008 @ 6:00 AM

For the battleships strategy, yes spacing out the initial shots is the best strategy. After a hit, you make shots closer to the first hit.

This is how Blackbirds search for food, and they know all about optimal foraging strategies, they've had millions of years of evolution.

Funny how I always turn to biology when algorithms are mentioned Smiley

Herbie

alexmac

In reply to Dr Herbie

#Sep 10th, 2008 @ 6:25 AM

Yes your genetics example took me back to A level Biology!

So basically a Monte Carlo method can be anything where you employ random sampling in order to score closer to a "hit" such as the battleship game?

Dr Herbie
Horses for courses

In reply to alexmac

#Sep 10th, 2008 @ 6:42 AM

Yup, that's pretty much it.

I think I had the following on my Blog:

<BR>    if(random.NextDouble() < 0.5)<BR>        Console.WriteLine("Heads");<BR>    else<BR>        Console.WriteLine("Tails");<BR>

That's a Monte-Carlo simulation is 4 lines of code Smiley

Herbie

figuerres
???

In reply to alexmac

#Sep 10th, 2008 @ 6:42 AM

well not always even a "hit" per se.

for example:

a few years back someone wanted a "sample database" to test how a system would perform when the database had grown over time.

so I built a set of tables of real data ZIpCode,AreaCode,PhonePreFix (the 3 digits of a local number), StreetNames, Peoples Names(fake)
and then wrote a very long running program that simulated new billing accounts beeing created, it populated about 200,000 accounts with different but "real looking" names,addresss, phone numbers etc....

then a second peogram did "billing" cyles, each day of "real time" it did a month of billing of all accounts.

when you looked at the code it had a number of while loops and random number calls that selected different rows from each table to create a fake address and person.
it also selected different service plans based on a semi random process.

not fast really, but then it was making the sql server go nuts with workload.

then we could tune indexes and test speed of the system with a good load.

also look up "Drunkards Walk" -- go Random(distance) then Turn Random(angle) then repeat....
this can be used for things like crude AI in a game amoung other things.

in each you may have to create a "weight" to some selections if you want to have it directed at a goal.

and if you make it "learn" by altering the weight based on results then you are starting in the direction of a "nural net"
-- very crude but that's a start.

alexmac

In reply to figuerres

#Sep 10th, 2008 @ 10:49 AM

Thanks Figuerres.

Drunkards walk looks an interesting book that I will order a copy of. This site tells a bit about it: http://www.iht.com/articles/2008/06/06/arts/idbriefs7B.php

Off on a tangent from the original question but what is your understanding of neural networks?

I am intending on doing an AI course distance learning course next year as find this subject interesting - Anyone else in the uk who finds this interesting might want to take a look at: http://www3.open.ac.uk/courses/bin/p12.dll?C01M366)

figuerres
???

In reply to alexmac

#Sep 10th, 2008 @ 1:24 PM

Interesting... I did not even know about that book, I was just refering to the other randomness thing...
see how we are randomly influenced by stuff....

like the idea of "The Butterfly Effect"

AI and stuff... I have read a bit but no real background... I was just giving you a connection ... it all relates.

some of the AI stuff I have read about and I saw a PBS thing on years back was based in LISP
other stuff is C++

as for my POV I think we are missing some key things...

most of the work I have heard of was trying to use more and more transistors to get to an AI, Transistors are part of how we build computer memory and CPU's

but look at small life forms, say a cockroach.... how many total nerve cells does it have? with that small number it does all of the things it needs to live and reproduce.

we may ned to go from binary to say Quadanary (base 4) DNA is I think 4 basic symbols.
or some form of analog -- living things are not digital.

just a few of the things we may have to examine to really get to a true AI

Matthew van Eerde
AKA Maurits

My favorite use of the Monte Carlo method:

Take a flat surface scored by parallel lines one unit apart.
Drop a whole bunch of unit matchsticks onto the surface from a great height; these land at random locations and orientations.
Count the number of times a matchstick landed on a line.
Using this information, approximate pi.

Matthew van Eerde
AKA Maurits

In reply to Matthew van Eerde

#Sep 10th, 2008 @ 4:03 PM

Slightly different approximation of pi via a Monte Carlo simulation, in Python:

http://niallohiggins.com/2007/07/05/monte-carlo-simulation-in-python-1/

Matthew van Eerde
AKA Maurits

In reply to Matthew van Eerde

#Sep 10th, 2008 @ 4:05 PM

The original is known as "Buffon's Needle problem"
http://mathworld.wolfram.com/BuffonsNeedleProblem.html

alexmac

In reply to Matthew van Eerde

#Sep 10th, 2008 @ 4:08 PM

The python example in .net.

Im not too sure I understand why the PI example works but it is interesting as you can get a reasonably accurate value of pie from fairly few throws.

[Code]

Dim DARTS As Integer = 10000
        Dim hits As Integer = 0
        Dim throws As Integer = 0
        Dim pi As Double= 0
        Dim dist As Double= 0
        Dim objRandom As New Random(23452)
        Dim x As Double = 0
        Dim y As Double = 0

        For i = 1 To DARTS
            throws += 1
            x = objRandom.NextDouble
            y = objRandom.NextDouble
            dist = System.Math.Sqrt(System.Math.Pow(x, 2) + System.Math.Pow(y, 2))

            If dist <= 1.0 Then
                hits = hits + 1.0
            End If

pi = 4 * (hits / throws)
MessageBox.Show("pi = " & pi)
[/Code]

The trouble with some of the AI stuff I have seen at the mo is it basically boils down to a load of if statements or quantifing a measure. Who knows what the solution to this is but this is probably an approach that is limitied in its scope.

Dr Herbie
Horses for courses

In reply to alexmac

#Sep 11th, 2008 @ 12:49 AM

Well, rather like the generic term 'Monte-Carlo method', the term 'AI' is generic too: it covers neural networks, 'knowledge systems' (like the 'load of if statements' you mentioned), artificial life (like 'swarm intelligence' systems), genetic algorithms and genetic programming, and probably others I haven't heard of.

Herbie

evildictaitor
if( !succeed( try() ) ) { while(true) try(); }

In reply to Matthew van Eerde

#Sep 10th, 2008 @ 4:03 PM

@ Matt van Eerde

I've never seen that one before. That's a rather wonderful little problem actually.

@alexmac:

The reason it works is because you are generating a point inside a unit square, and checking whether it lies within a half-unit circle.

.-----..-----.
|  .'    '.  |
| .         '|
|      <.....|
|  .   0.5 . |
|    . . '   |
.-------------.
<---- 1.0 ---->

The probability that the dart lands inside the circle is P(lands in circle) = P(lands in square) * (ratio of areas, square to circle). The ratio of areas is (AREA(circle(r=0.5)) / AREA(square), and the area of the square is 1x1 = 1 square unit. By construction the probability that the dart lands inside the square is 1, and therefore P(lands in circle) = Area(circle with radius 0.5) / 1 square unit

= PI * r *r / 1

= PI * (0.5 * 0.5) = PI / 4

Therefore if I throw n darts at the dartboard, I should expect (n * PI / 4) to land in the circle. In your code, you compute hits, which is the number of darts that land in the circle and throws which is the total number of darts (n), so for large number of throws, ((4 * hits) / throws) is PI, (or more strictly, as the number of throws becomes very large ((4 * hits) / throws) becomes very simmilar to PI)