## monte carlo algorithm

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### monte carlo algorithm

i personally don't really understand how it works. if it plays random moves for both sides then it would seem to me that it would have a 50/50 shot of winning, and thus whether it wins or loses shouldn't give you any new info.
for example take tic-tac-toe.

we have 9 possible moves for the first move, 8 for the second one and so on, making a small enough game that Monte Carlo shouldn't have much trouble with. here's a random sequence i generated from random.org.
5 1 4 2 6 3 8 9 7.
so, x starts off in the center, o top left, x plays side underneath, o plays top mid, x plays winning 3 in a row.
now how much more likely should the first move be in the center?
good luck have fun

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3888
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: monte carlo algorithm

Monte Carlo is 'just' a scattergun. 50:50ness comes (if at all, giving the possibility of outliers skewing by non-zero probability) from the thing being scattershot being a 50:50 thing in the absence of any intelligence.

And you're scatter shooting noughts and crosses? I think that's supposed to have twice as many "first player wins" games as "second player wins" games, if played without any strategy at all by either player. And ends upon an inevitable draw if both players play as perfectly as possible, instead. Or do I misread what you're doing?

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### Re: monte carlo algorithm

i'm trying to get a handle on how monte carlo works by applying it to a simple problem.
good luck have fun

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3888
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: monte carlo algorithm

Oooo, that's definitely a kettle of fish that you can shoot into the cocked hat I'm talking out of.

Might I then suggest that you do (or get the results from elsewhere1) a full quantitative analysis of all the possible OXO games (it'd be a simple count of 1Wins, 2Wins, Draw), then use your randomiser method to run one random game (tally one result, will be a bit all-or-nothing) then redo to tally over two games (chance of double tally, or one result then another), three games (depending on luck, might get one of each result!), and onwards.

Do each sequence of 1…N concurrently, because reasons3, but also keep a master tally (of N(N+1)/2 total results) because you might as well, having put the effort in.

Then plot the proportions against N (including your master-total, at the end) and observe how these results probably2 converge upon the precalculated 'true' results from every actual game.

A more meta way would be to try every possible way the N trials might have gone (that would including "1 2 3 4 5 6 7 8 9" (potentially, though it would win on "7") every single one of the N times, and see how the results cluster, i.e. you see how 'tightly' you might expect the Monte Carlo to meet base probability, and also how loosely. But that's way more computing time.

Also, there are simpler problems. Try it on coin-flips. By actually flipping N coins (fair) or a different N coins (⅓/⅔-biased) and seeing how many coins seem to flip either way on low and high cumulative counts. It's quicker than messing with tic-tac-toe games, but does something similar, and doesn't require the (approaching) 9! pre-calculated full results, because you're actually dictating the proportions to compare to, not needing to find out.

I've probably misunderstood sonething, though. And/or let fly with far too much overthinking. Still, good luck with your endeavours, and tell me if you think I ought to waffle away even more about sonething

1 Though the actual numbers will differ depending on whether it's reduced for rotational/reflective duplications, so if you can do it yourself, you'll know exactly that you're not getting mixed up over that.
2 You're looking at the possible distortion factor of randomness by using randomness, which conceivably could give you random results that actually show divergence. There's a very very very small chance, depending upon your rigour.
3 Ok, I'll tell you the reasons. If your 1-test through to your 10-test were all horribly fated to be biased towards one ending, that's like skipping straight to 55 inadvertently biased tests. The next 55 tests might be inadvertently biased oppositely (though they should, in an average world, be actually biased to non-bias, each prior pick being not 'remembered' by the RNG). If you'd just used them to continue to 110 tests, that'd be like 14.5 sequentially increasing tests added together, but if you see the first 10 bias one way and the next 4 or 5 bias the other way, then you've got a very interesting result. And I'd lay odds that you can't do it again. But, if you do, I'm perhaps asking you for my next lottery numbers. (And both playing the ones you suggest and seperately playing any numbers but the ones you suggest. You'll have something weird going on, and I don't know which.) Was that worth explaining? Probably not. Ignore me then.

raudorn
Posts: 370
Joined: Mon Jun 13, 2011 11:59 am UTC

### Re: monte carlo algorithm

The way I understand it is that "Monte Carlo" as a noun describes a set of methods to approximate a solution to a problem that has only one solution via "averaging" (slightly more complex) over a set of equally randomly distributed points in the parameter space. For example for numerical integration we could either do a regular integration over a grid over whatever we we want to integrate, or we choose random points and average over the volume of a test domain, which is just hypercube that fits around the domain we want to integrate over.

Now, I'm not sure what algorithm is meant to be used here and what it tries to calculate. Do we want to know what's the chance of winning for the starting player? Let's assume so: We can construct a function f that has a set of moves as input and outputs a number; -1 if the player lost, 0 for a draw and 1 for a win. For our test domain we use sets of nine numbers selected from 1 to 9 and reject any that don't represent a valid game.

If we sum over the output of the function with N valid sets, we expect the chance of winning to be c/N * sum(f(x_n)), where x_n is a set of numbers and c is the volume of domain of all valid games. That is indeed a bit tricky to calculate. The first dimension has nine possibilites, the second eight, the third seven, the fourth six and the fifth five, but then it get's a bit murky because now we have to subtract the games that have already been won/lost. So I guess 9! is an upper bound for the volume, but it's actually lower.

Anyway, this "chance" of winning isn't really that useful because we know that the second player can force a draw with perfect play. Maybe I misunderstood the question?