[HN Gopher] A ride that takes 10^20k years to complete in Roller...
___________________________________________________________________
A ride that takes 10^20k years to complete in Roller Coaster Tycoon
2 [video]
Author : Taek
Score : 284 points
Date : 2020-08-03 19:34 UTC (3 hours ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| sixstringtheory wrote:
| Why does he take the fourth root to find the multiplier per
| indent? That was the only part where he lost me math-wise.
|
| I wanted to ask if RCT2 was Turing complete, but looks like the
| same person made a video demonstrating this:
| https://www.youtube.com/watch?v=RQGa0DPwes0
|
| Would love to see the Game of Life implemented in it!
|
| As a fan of RCT2 in my youth, absolutely loved this. This is some
| of my favorite type of content to find on HN.
| MarcelVos wrote:
| The multiplier of 4.11 was for a tile of length for the test
| mazes, which is actually 2 more tiles of maze. Every tile has 2
| indents so one tile of length has 2*2=4 indents. Therefore we
| need to take the fourth root to go from the multiplier per tile
| of length to the multiplier per indent.
| sixstringtheory wrote:
| Thanks! Great work here :)
| evanb wrote:
| Making the maze longer by just one rule increases the number of
| indents by four. But, for his calculation the number of indents
| in the hindrance (it is valid to do it as a function of the
| number of tiles, instead, of you want) but the conversion rate
| (4:1) is in the power because it's an exponential process.
| [deleted]
| tomphoolery wrote:
| I love this guy. He's got a lot of great strategies for working
| with the tougher scenarios, like Fungus Woods, and his general
| tips for park management have ensured that I don't run out of
| money so damn quick.
| jl6 wrote:
| Fans will recognize that RCT is a descendant of Transport Tycoon,
| which was created by Chris Sawyer, who ported Frontier Elite 2
| from m68k assembly to x86 assembly (and inserted an advert,
| visible in some spaceports, for "Chris Sawyer's Transport Game").
|
| Frontier used a "Scaled Word" datatype to represent the vast
| interstellar scale of the game, and according to [0] this had a
| range of 2^65536 [?] 10^20k.
|
| So there's something relevant to compare the size of the maze
| solving time to!
|
| [0] http://jongware.com/galaxy4.html
| t0mas88 wrote:
| It's aMAZEing... Ok I'll see myself out ;-)
| bthrn wrote:
| Hopefully the probability of you finding the exit is high!
| cuddlybacon wrote:
| That's what I named my first maze ride in every park!
| ThePadawan wrote:
| I hope you consistently named the second one bMAZEing and so
| forth.
| DangerousPie wrote:
| I wonder what simple improvements one could make to the
| pathfinding algorithm to make it perform better.
|
| I appreciate that a "proper" pathfinding algorithm like A* would
| not be feasible given the number of guests but maybe taking into
| account what the guest sees ahead of them would already make it
| quite a bit more realistic?
|
| You could weight the probabilities for each direction by the
| square root of the length of the path or something like that. And
| if you can see the exit set p=0, if you can see the exit set p=1.
|
| I'm sure it would still be easy to fool though - just build very
| long indents and make sure the entry/exit are not visible until
| the last moment.
| MauranKilom wrote:
| Well, the classic algorithm for solving a planar maze with
| single entry/exit (on the outside) is to always follow the
| right wall (or always the left wall). That's what the algorithm
| in the game was apparently originally modelling, with some
| randomness thrown in so that not all guests do exactly the same
| thing.
| remcob wrote:
| With a one-off precomputation you can do a lot. If you store
| the distance to exit in each cell you can introduce a slight
| bias towards the exit. Easy to implement but not very realistic
| since it assumes things the guests can not know.
|
| More realistic would be observing that the entry and exit are
| on the outer edge and the maze is simply connected, so a
| trivial left-hand rule [1] will solve the maze in linear time.
| On its own pretty boring. You could ad some randomness to make
| it interesting. But would it still have linear expected solving
| time if you do that?
|
| [1]:
| https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_fo...
| qznc wrote:
| Might also give the guests a slight tendency to get away from
| each other so they tend to spread all over the maze. That
| might look nicer to the player. Not too strong though
| otherwise every guest stays in their own dead end.
| default-kramer wrote:
| The most efficient way is probably to "cheat" by having all the
| guests share the path data. Perhaps when a guest enters the
| maze, she only chooses a winning path 10% of the time, but as
| she spends more time in the maze she chooses winning paths more
| frequently, until she is nearly guaranteed to walk right to the
| exit.
| mxwsn wrote:
| Less than 48 hours after that video was published, OpenRCT2
| patched their pathfinding algorithm to not prefer some directions
| more than others: https://www.youtube.com/watch?v=b-5aX2oLOgU.
|
| The GitHub commit message says it was just to mess up MarcelVos,
| the videomaker
| atq2119 wrote:
| That change still leaves a small bias in the case where there
| are 3 directions to choose from. The effect is presumably small
| (I don't know how many bits are produced by scenario_rand()),
| but it would be assuming to try to figure out the maximum maze
| bias that is possible to extract from this.
| foota wrote:
| It would be interesting maybe to design a system where people
| deviate a random amount from the optimal path.
| fossuser wrote:
| I was kind of hoping they'd change it to have an easter egg, if
| it determines it's likely in a left only hedge maze the path
| finding cheats and just walks to the exit.
| MauranKilom wrote:
| According to Youtube recommending a newer video by the same
| author, you can still build impossible mazes:
|
| https://www.youtube.com/watch?v=b-5aX2oLOgU
| Taek wrote:
| For a proper fix they would probably want the guest to
| remember places they had been previously and bias against
| those places.
| SwiftyBug wrote:
| I found it very funny:
|
| https://github.com/OpenRCT2/OpenRCT2/pull/12546
| infogulch wrote:
| It's always so wholesome when devs interact positively with
| 'exploit hunter' types. I wonder why it feels like that.
| jansan wrote:
| It actually is funny.
| cuddlybacon wrote:
| I've seen this guy's videos before, and I'd imagine they'd have a
| fair bit of appeal to HN users who are familiar with Roller
| Coaster Tycoon. He manages to really get into the details are
| determine why things work they way they do.
|
| If you are nostalgic for RCT2, I'd suggest trying Parkitect on
| Steam. It feels like an updated version of RCT2. It sorta lets
| you play the game with rose tinted glasses on.
|
| There are a few things I think it does better:
|
| * A lot of modernization stuff: better OS support, keyboard
| layout support, clamping of input for multi-monitor users, steam
| workshop support, fewer obvious pathfinding issues, removing a
| few abusable strategies, etc.
|
| * The hauler system. Shops no longer conjure product from the
| ether. A new worker type, haulers, have to deliver it to the back
| of the store.
|
| * Janitors need to drop off garbage in trash chutes.
|
| * Guests don't like seeing park infrastructure (eg haulers,
| employee paths, break rooms). It's not hard to hide this, if you
| don't feel like putting effort in.
|
| * An option to copy a decoration item under the cursor. It is
| nice if you want to design a new building to match an existing
| on.
|
| * Live previews of how your ride will work as you are building
| it.
| crooked-v wrote:
| Also, there's a basic line-of-sight system for scenery ratings,
| with lower ratings for haulers, employee-only paths, and
| employee-only buildings, so you actually have a reason to build
| walls and fake scenery to block views of the 'backstage' areas
| that haulers pass through.
| MarcelVos wrote:
| OpenRCT2, the open-source project that improves RCT2, has some
| of these features as well. It has a scenery picker and it also
| has a ghost train feature for rides under construction. It also
| makes it run much smoother on modern systems and introduces a
| keyboard shortcut for almost everything, although vanilla RCT2
| also had quite a few already.
| [deleted]
| jedberg wrote:
| "If you want a new way to torture your guests, this is an
| excellent method".
| xyst wrote:
| Hell is on Earth, and it's disguised as children's park
| building game.
| Taek wrote:
| 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
|
| 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 wrote:
| This is probably a solvable number, and these 1.4 numbers are
| suspiciously close to the square root of two 1.41421...
| ironSkillet wrote:
| Seems 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.
| MarcelVos wrote:
| That was my thought as well, but I couldn't justify it being
| root 2 so I went with the number I got.
| rokobobo wrote:
| Isn't this just a Markov process, shouldn't we be able to
| calculate the exact waiting time?
| [deleted]
| sillysaurusx wrote:
| This 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.
| Animats wrote:
| Short version: Roller Coaster Tycoon has a random walk type maze
| solver, and you can create a maze which takes O(2^N) time to
| solve.
| sillysaurusx wrote:
| Is it really O(2^N)? If so, how'd you determine that so
| quickly? I'd like that intuition.
|
| I do ok at big-O reasoning, but in this case turning
| probabilities into big-O eludes me.
|
| In the video, there's an opposite maze which biases the guests
| to walk towards the exit, making it much easier to solve.
| What's the big-O of that version?
| ascar wrote:
| I'm also absolutely not an expert on this (M.Sc. CS).
|
| I would argue using Big O here is wrong and Landau symbols
| are not well defined on Markov chains/probabilistic turing
| machines. The point of Landau symbols is to give asymptotic
| bounds of functions with N approaching a certain value
| (usually positive infinity). My intuition says that the
| runtime of a probabilistic turing machine isn't necessarily a
| function tho (i.e. a deterministic association between any N
| and time(N)).
|
| Google wasn't really helpful on complexity theory of Markov
| chains and based on the research papers that pop up it seems
| far enough away that I would avoid using Big O in this
| scenario.
|
| Probabilistic turing machines even seem to have their own
| complexity classes (https://en.m.wikipedia.org/wiki/Probabili
| stic_Turing_machine).
| contravariant wrote:
| Note that they likely messed up slightly, it'll be more or
| less exponential in some base but possibly not 2. However big
| O notation does require you to get the base correct (or at
| least provide an upper bound), you can't ignore it like you
| can ignore a multiplicative or additive constant.
| jchw wrote:
| I think the key insights are:
|
| - only the most significant (in terms of exponentially)
| factor(s) matters for big O (i.e. if you have a linear
| factor, the constant time factor is ignored)
|
| - You have to determine whether you are talking worst case or
| average case or best case. Assuming average case I'd guess
| the opposite maze is O(n) because the time expands linearly
| with number of segments.
|
| (Disclaimer: I am not formally educated in computer science,
| so admittedly I am not up to snuff on the mathematical side
| of things. Hopefully I am close enough here.)
|
| edit: Oops, I failed to actually cover any time complexity
| calculation at all. I do not know if my approach is correct,
| but here's how I view the original: def
| walk_path(n): // probability of _not_ recursing
| is (1/n^2) // probability of _recursing_ is (1 -
| 1/n^2) // likelihood of recursing doubles with n
| // therefore, the average case of this loop is O(2^n)
| for (i : 0 -> n) if (random() < 0.5)
| walk(); // = O(1) else //
| Ignoring the actual walking on the branch, we just pretend we
| turn around directly. for (j : i -> 0) //
| = O(n/2) walk();
| return walk_path(n);
|
| and the opposite is straight forward, since the branches are
| 'constant time' - so it's more like a straight loop.
| nwallin wrote:
| In this instance, you're only concerned with the average
| case.
|
| Worst case is infinite: you just always take the path back
| in the direction of the entrance, and never even get past
| the first inlet.
|
| Best case is O(n): you always take the path forward.
| jchw wrote:
| Yep, sorry, it quickly became apparent after rereading
| this that the original analysis was not worst-case. I
| have revised my comment to also include how I view
| calculating the actual time complexity since I didn't
| actually do that initially.
| im3w1l wrote:
| Let's pose the problem mathematically. Initial state is (0,
| forwards).
|
| State (0, *) transitions to (1, forwards)
|
| For k > 1, state (k, forwards) transitions to (k+1, forwards)
| with 5/8 probability and to (k-1, backwards) with probability
| 3/8.
|
| For k > 1, state (k, backwards) transitions to (k+1,
| forwards) with 1/8 probability and to (k-1, backwards) with
| probability 7/8.
|
| My intuition is that this very much resembles a biased walk
| so it should take exponential time. But there is the
| "momentum" to take into account.
|
| Edit: It looks like we can use https://en.wikipedia.org/wiki/
| Absorbing_Markov_chain#Expecte...
| gbrown wrote:
| Came here for this - I knew there must be an analytical
| solution involving Markov chains.
| tetha wrote:
| I'm pretty sure this can be modeled with markov chains.
|
| Your vertices would be (x, y, f), f being facing.
|
| Edges are along the lines of (x, y, 0) - (x+1, y,
| {0,1,2,3}\1); (x, y, 1) - (x-1, y, {0,1,2,3}\0); (x, y,
| 2) - (x, y+1, {0,1,2,3}\3); (x, y, 3) - (x, y-1,
| {0,1,2,3}\2).
|
| Probabilities are modeled in the video and need to be
| rotated 4 times for the four facings.
|
| After that, I just don't recall my eigenvector
| calculation anymore. It feels like a good markov
| exercise, though.
| nitrogen wrote:
| I'm not 100% confident in my explanation below, but maybe
| it's something like this, if we don't have prior knowledge of
| the asymptotic behavior of random walks:
|
| The measured values are empirically exponential with a factor
| of 1.424 per indentation. If we assume that as an upper bound
| (which I don't think is quite right), then we have O(1.424^N)
| where N is the number of indentations.
|
| Any exponent can be written in terms of any other base by
| multiplying by a constant. Since we often use base 2, we can
| choose to rewrite it in base 2 as O(2^(K*N)), where K is
| approximately 0.51.
|
| Constant terms can be ignored in big O notation, so we can
| just drop the K to get O(2^N) (I am less sure about dropping
| a constant within the exponent).
| gopiandcode wrote:
| You can't drop constant multiplicative terms in an exponent
| - O(2^n) is not equivalent to O(2^(2n)) as O(4^n) \= O(2^n)
| (the first one grows a lot faster).
| karatinversion wrote:
| You cannot drop constant terms from exponents in big-O
| notation.
| [deleted]
| atq2119 wrote:
| Note that calling it 2^O(N) (or Omega) would be more accurate,
| unless you stumbled upon a really lucky coincidence.
| titanomachy wrote:
| Are there any functions f(n) [?] O(n) such that 2^(f(n)) [?]
| O(2^(n))? If not, then either statement is accurate.
| gnramires wrote:
| Yes, for example 2^(2n) [?] O(2^(n)). Any function of a
| different linear coefficient. Big-O notation represents a
| bound by a constant factor (by modifying the exponent
| multiplier you get an exponential factor).
| [deleted]
___________________________________________________________________
(page generated 2020-08-03 23:00 UTC)