4 ms·
In the video, Marcel Vos essentially runs a monte-carlo simulation to try and figure out the growth rate of adding more elements to the maze. Though it is true-
by Taek 6y ago
In the video, Marcel Vos essentially runs a monte-carlo simulation to try and figure out the growth rate of adding more elements to the maze. Though it is true-to-life, it's also very computationally inefficient.
Based on the logic presented in the video, I wrote a program that does a more efficient simulation, so that we could get a better estimate of the growth rate. Note that my simulation estimates a guest always takes the exact same amount of time to make 1 step, and there may be incorrect edge cases in my simulation.
In my simulation, I attempt each size of make 50,000 times and record the average number of steps it took to complete a maze of each size 1-25.
https://play.golang.org/p/FglwpqbsPPr https://play.golang.org/p/FglwpqbsPPr
Results:
<output truncated for ease of viewing>
20 size: 9966 steps (1.397 growth)
21 size: 14057 steps (1.410 growth)
22 size: 19738 steps (1.404 growth)
23 size: 27372 steps (1.387 growth)
24 size: 38660 steps (1.412 growth)
25 size: 54266 steps (1.404 growth)
Marcel estimated a growth rate of 1.424 per added indent, and my larger sample simulation estimates a growth rate of about 1.4, slightly smaller but very much in a similar ballpark.
- koverda 6y agoThis is probably a solvable number, and these 1.4 numbers are suspiciously close to the square root of two 1.41421...
- MarcelVos 6y agoThat was my thought as well, but I couldn't justify it being root 2 so I went with the number I got.
- crdrost 6y agoFor the simplest case you have a system of transitions Start → Mid(1, ↑) prob: 1, time: 1? Mid(1,↑) → Start prob: ⅜, time: 3 Mid(1,↑) → End prob: ¼, time: 1 prob: ⅜, time: 3 (not 100% sure about those times, here they are in units of the timesteps that a person spends to go from one square to another, so the 3 is “go to the left square, go to the middle square but coming from the left, go from here up/down having the normal orientation again”). There seem to be two ways to do this. First you could determine the average time to leave the park by pumping 1 person into the park every timestep until it reached a steady-state where one person was leaving the park, then just count how many people there are in the park. Assuming steady state, you do not need to use travel times to calculate that exactly 1.6 people occupy Start and 1.6 occupy Mid, with 0.6 making the journey back and 0.4 making the fast journey out and 0.6 making the slow journey out. These two slow journeys taking time 3 can be viewed as having (3–1)•0.6 occupation, or 1.2 people in each, so the total is 1.2 + 1.2 + 1.6 + 1.6 = 5.6 people in the park, so this should be the number of timesteps. Or if you prefer a straight calculation it is S where S = 1 + T T = ⅜(3+S) + ¼(1) + ⅜(3) S being the average time from Start → End and T bring the average time from Mid → End. This can be solved to similarly find S = 28/5 = 5.6 timesteps. I think the former approach is going to be theoretically easier to understand when you are asking, “I want to convert End to Mid(n+1, ↑) and introduce a new End and also a node Mid(n, ↓), how does adding these three nodes change the system?” In fact I think to solve it you will want to always calculate three different flows. I have only given you one of them, a steady state where one person arrives in Start and then they leave out of End. The other one is that they arrive in Mid(n–1, ↑) at a steady rate and then leave out of End at that same rate. And finally there is the flow where they arrive in Mid(n–1, ↓) at a steady rate and then leave at the same rate. [I think Mid(0, _) is just Start here.] If I have those three populations/average travel times then I have a way to add those 3 nodes to the system at each stage and this gives me a recurrence which can calculate the thing exactly. I would need to think a bit about how to program all of that.
- ironSkillet 6y agoSeems like you could come up with a recursive formula to compute the expected number of steps to reach hedge N. Along the lines of how you compute the expected number of coin flips to get K heads in a row. I'm too lazy to figure it out right now though, so there may be some nuance I'm missing.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- rokobobo 6y agoIsn’t this just a Markov process, shouldn’t we be able to calculate the exact waiting time?
- deleted 6y ago[deleted]
- senkora 6y agoYep, this is just a standard Markov process which should be easily solvable.
- deleted 6y ago[deleted]
- sillysaurusx 6y agoThis assumes the code works exactly as described in the video. For old games, this has historically been false; it’s very, very hard to reimplement most game mechanics faithfully, often due to small corner cases that matter. Many gameplay mechanics are an emergent effect of bugs. The small discrepancy of 1.424 vs your 1.41 is worth digging into. It might have a surprising reason. Or you might be right. Games are simulations, and simulations have emergent behaviors when you throw in a time dimension.
- Taek 6y agoThe discrepancy is fully explained by variance. Some of the results that went into computing 1.424 had less than 20 samples, which is not enough to get a precise answer for such a highly variant task. That doesn't necessarily mean that my simulation is perfect (and, another commentor has made an improvement on it!), but it does mean that this evidence alone is not enough to suspect the simulation.
- Veedrac 6y agoDoing a more sophisticated simulation, I think it's trending towards 1.4 exactly (42 to 43 is 1.400003). Idk how to prove it though.
- hervature 6y agoSmall nitpick with your code, you define a step to be both a forward/backward movement and going into the corner and coming back (which I would define as 2 steps because the person has to spend twice as long completing that). Also, you didn't use floats for the expected times. I have made both changes and added them here: https://play.golang.org/p/dnCuu05Dupc https://play.golang.org/p/dnCuu05Dupc
- Taek 6y agoThanks for the changes! Interestingly enough, it seems to have had very little / no effect on the growth rate. Nice to have the precision in the outputs. Run with 5 million iterations per size: 15 size: 2514.4287536 steps (1.413 growth) 16 size: 3543.3930332 steps (1.409 growth) 17 size: 4986.7099864 steps (1.407 growth) 18 size: 7008.892906 steps (1.406 growth) 19 size: 9834.1058896 steps (1.403 growth) 20 size: 13806.3093036 steps (1.404 growth) Also seems like it converges to a value below sqrt2, which doesn't surprise me. The function that drives the behavior just doesn't feel like it would end up on an irrational number for a growth rate.
- eutectic 6y agoInstead of running random simulations you could deterministically transport probabilities around an array, (or just set up a linear system whose solution gives the expected time).