The Monte Carlo Limit Theorem

Information about Quackle, an analysis tool and worthy computer opponent

The Monte Carlo Limit Theorem

Postby kunjoos » Thu Mar 11, 2010 6:28 pm

Theorem: If Quackle plays the ensuing positions relatively well, and a sufficiently long simulation is run, then the difference between a 2-ply and a 4-ply represents a trend that approaches each play's true value. Thus, if two plays are simulated first as a 2-ply and then as a 4-ply, and one play does significantly better during the 4-ply relative to the other play, then the "true" value of the play that improves during the 4-ply is greater relative to the other play, since the 4-ply is more representative of the play's worth than the 2-ply. Thus, if play A wins against play B by 3 points during a 2-ply and only 1 point during the 4 ply, then the plays are nearly equal: in fact, play B might be better than play A.

Example: Let's take the opening rack BDIIKSW. Quackle's 2-ply lists KIWI at 31.9 and KIWIS at 31.1. Quackle's 4-ply lists KIWI at 34.3 and KIWIS at 31.2. Therefore, the difference between KIWI and KIWIS is greater than 3.1, and is probably somewhere around 5 or 6 points, since the trend indicates that Quackle's shortcut algorithm of evaluating leave and board position are underappreciating KIWI and will continue to do so for multiple turns. In other words, BDS is undervalued by more than the difference between the 2-ply and the 4-ply in this specific example.


Intuition: Let's say that we start with two cultures of 500 bacteria (or pigs, or any animal you want really) that we release into the wild in two different locations. Bacteria are allowed to move where they want to spawn, but obviously environment is relatively consistent over the space, and bacteria move slow, such that it will take hundreds of generations for the different strains of bacteria to meet. Each bacteria can reproduce up to twice and die. The environment strongly influences both survival rate and reproduction rate. The resources in the environment are finite.

Group 1 after one cycle of reproduction has delivered 550 offspring, while group 2 has delivered 520 offspring. After two cycles of reproduction, group 1 has delivered 580 offspring, while group 2 has delivered 560 offspring. Which group will have more offspring after reproduction cycle 3?

This is more similar to simulation than it first appears, since it appears that survival is easier for group 1, but reproduction is easier for group 2. Likewise, there is more immediate value for play 1 and more long-term value for group 2.

Thoughts? I'm not sure how useful this is long term, but it's another way to understand Quackle as a tool. While the applications for this are limited, I think that this is a good theorem to keep in mind when assessing plays using Quackle. Of course, if your understanding of Quackle is this sophisticated such as you know when the postulates are satisfied, you shouldn't need Quackle anyway...
kunjoos
 
Posts: 84
Joined: Sun Jan 04, 2009 9:27 pm

Re: The Monte Carlo Limit Theorem

Postby dak » Wed Jun 09, 2010 4:38 pm

very interesting and maybe useful, but as you've stated it, this is not a theorem but a conjecture.

It may well be that the equity difference between two plays generally follows a linear trend after the first two plies of a sim, but you haven't given nearly enough evidence for that. you'd have to look at a fairly large representative sample of opening racks and simulate for 2, 4, 6,... plies up until you're close enough to the endgame that regular sims don't work well. if you've done this and your results support your claim, I'd be interested in seeing your data. if not, then I might be motivated to take up the project myself, but this could turn into a major undertaking and eat up huge amounts of cpu time - longer sims take forever to converge.

I have a hunch that linearity will be a decent approximation in some cases but not others. the population growth model you've given as an example is not a good analogue to a scrabble board because it assumes a static environment, identical for each of the two competing cultures. but the nature of scrabble play is that each play, particularly early in the game, changes the board geometry and future evolution thereof. in some cases things might settle down to a predictable linear trend with low variance after a few plays, but it isn't at all obvious to me that this should be generally true.
dak
 
Posts: 5
Joined: Tue Jan 27, 2009 2:19 am

Re: The Monte Carlo Limit Theorem

Postby kunjoos » Thu Jun 10, 2010 9:51 pm

The evidence is intuition here. Testing this theorem is impossible because Quackle just isn't good enough and makes some pretty bad errors in future positions. Quackle makes pretty bad errors in far too many positions to be useful. These errors are too numerous and significant to test this meaningfully. Quackle will probably conclude that the worth of the error on average is less than the Monte Carlo theorem suggests, but that is in part due to its own ineptitude.

The main and central application for this theorem is that when you simulate something and get a result out of the ordinary, you can run another simulation that approximates the accuracy of the simulation. It's just an approximation; no more, no less.

The board just doesn't change that much after one play, especially since in simulations the algorithm is set to maximize equity. Considering that the Quackle function is simply to maximize equity, the board isn't going to change very much in the short term, and those changes will occur in all different ways relatively equally over time. It's not irrelevant, but it's not nearly as significant as Quackle's fallibility due to its faulty payoff function.
kunjoos
 
Posts: 84
Joined: Sun Jan 04, 2009 9:27 pm

Re: The Monte Carlo Limit Theorem

Postby kunjoos » Thu Jun 10, 2010 9:59 pm

Let me just restate very briefly the "theorem". If play 1 beats play 2 by 3 points in a 2-ply sim, and play 1 beats play 2 by 5 points in a 4-ply sim, then over the course of an infinite ply sim, the best approximation for the value of play 1 - the value of play 2 is 7 points. It depends on the factor of the board, but generally if you are simulating the position, you already have an inclination that something funky is going on.

In general, at least you have to know the answer is probably above 5. In most cases, whether the answer is 6.5 or 7 doesn't really matter.
kunjoos
 
Posts: 84
Joined: Sun Jan 04, 2009 9:27 pm

Re: The Monte Carlo Limit Theorem

Postby ar-raqis » Sun Jun 13, 2010 3:06 pm

Based on my experience with Quackle so far, I strongly suspect Kenji is right. But of course I can't prove it any more than he can.
Quinn
is a bad example and will have NOCAKES# today
ar-raqis
 
Posts: 98
Joined: Thu Jan 08, 2009 7:12 pm


Return to Quackle

Who is online

Users browsing this forum: No registered users

cron