[HN Gopher] Physicists have created the most fiendishly difficul...
___________________________________________________________________
Physicists have created the most fiendishly difficult maze
Author : jhncls
Score : 109 points
Date : 2024-07-10 21:20 UTC (1 days ago)
(HTM) web link (www.sciencealert.com)
(TXT) w3m dump (www.sciencealert.com)
| russellbeattie wrote:
| Part of me wants to write up a quick path finder script to do the
| maze to see how long it would take. The solution seems like a
| straight line though, so it could get lucky and zip to the
| middle.
| ianbicking wrote:
| Kind of an aside to the purpose of the maze, but I noticed their
| maze has no designated exit. You just have to escape the maze
| from an interior starting point, adding to the challenge because
| there are many false exits. You can't start from both ends, nor
| is there a sense that you are getting "closer" to the exit.
|
| I don't think I've seen this maze building technique, even though
| it seems simple.
| Someone wrote:
| You can turn any such maze into one with a single exit by
| surrounding it with a small "moat" with a single exit. For
| large mazes, I don't think the price you pay for it is too
| large, as it only adds _O(\[?]#cells)_ of area to the maze, and
| I think any good measure for complexity of a maze scales by
| _#cells_ (if you don't scale by _#cells_ , you can make a maze
| harder by glueing multiple ones together, and the trivial maze
| where there only one straight line will get harder by making it
| longer)
| tedunangst wrote:
| That doesn't do anything to assist solving, though. Once
| you're in the moat, it's the same problem.
| bee_rider wrote:
| I suspect the bit about the maze difficulty is just some
| throwaway bit of description that the journalist got caught up
| on.
|
| But does anyone know a good metric for maze difficulty? Or what
| the study of maze difficult would really look like? The classic
| maze solving algorithm (right hand rule/DFS) is deterministic
| anyway.
| andrew_eu wrote:
| Super interesting question.
|
| I didn't, but found this [1] 2001 paper without much
| difficulty. Getting much out of it is more difficult. As I
| understand it, the complexity measure they propose is somewhat
| related to the difference of arctans of turns to take "forward"
| vs turns to take "backward", summed up for every fork and
| scaled with some length measurement. There are definitely
| plenty of other complexity measure though (e.g. number of
| forks, number of incorrect paths, etc) -- correlating that to
| practical difficulty is less straightforward.
|
| [1] https://archive.bridgesmathart.org/2001/bridges2001-213.pdf
| IIAOPSW wrote:
| You said yourself the algorithm is DFS. The obvious measure of
| difficult then is going to be the average number of branches b
| raised to the average depth d of the tree.
|
| This is just another way of saying the size of the search space
| is (b^d), and DFS "walks the tree" until it finds the exit,
| which means on average its going to iterate half the entire
| search space before getting there. Furthermore, unless there is
| some other information available which correlates with the
| correct path at a given intersection, there's no possible way
| to do better than testing the possible branches sequentially
| (as in DFS) and therefore no way to improve on searching half
| the entire space.
| anyfoo wrote:
| You're formulating the problem with a lot of implicit
| assumptions. That is ignoring a lot about how human visual
| perception works.
|
| Look at a very simple maze, you will likely "intuitively"
| solve it immediately without performing an actual DFS.
| Implementing that as an actual computer algorithm would be
| insane since your algorithm would now rely on the
| computational needs of a human perception system, which
| decreases algorithmic efficiency by many orders of magnitude.
| But humans with their weird squishy brains have what they
| already have, and on the flip side are simply not optimized
| for algorithms on all but the smallest data structures. (You
| can very easily read even distorted text, but you have an
| extremely hard time balancing a simple red-black-tree in your
| head or even on paper.)
|
| EDIT: Relatedly, humans use heuristics a lot. And there are
| many NP-hard problems where we can solve lots of "reasonable"
| points in the problem space in reasonable time (computers or
| humans alike), at the risk of having to time out, maybe try
| with another approach, and eventually just give up. Traveling
| salesmen _are_ actually traveling the country after all. So
| worst case is not always a good measure for games.
| IIAOPSW wrote:
| Well now you're posing a different problem, namely one
| about mazes where the entire structure is visible at once
| from the top down and (likely) follows certain drawing
| conventions. This violates my caveat about there not being
| any information at the intersections which correlated with
| which branch to look at next. If you can see the whole maze
| at once, you very much have a hint.
| bee_rider wrote:
| Right; DFS is the solution to this one type of well-
| covered maze problem. But I think it is less interesting.
| I guess what I was trying to ask is, if there are other
| more interesting problem/solution pairs that could allow
| for more interesting types of difficulty.
| kleiba wrote:
| Well, usually we measure the difficulty of a problem by the
| run-time complexity of a solution to the problem. If the
| approach is deterministic, we'd usually care for the complexity
| of the best solution for the worst-case kind of problem; but it
| could as well be an expected run-time for a probabilistic
| approach.
|
| Interestingly, you don't always actually have to _have_ an
| actual solution - it can be possible to determine run-time
| bounds (that tell you how hard your problem is at least) just
| on theoretical grounds. This could be, e.g., by comparing it in
| complexity to another problem that has already been studied and
| whose complexity is thus known.
| anyfoo wrote:
| That's algorithmic complexity/"difficulty", and somewhat
| assumes that we only care about computers solving the maze.
|
| Since solving mazes is however (also) something to be enjoyed
| by humans, it's possible that perceived maze difficulty could
| be dependent on factors that wouldn't really matter for a
| straightforward algorithm. For example, a very "jagged" maze
| could feel more difficult for humans because it's harder to
| follow with your gaze, while an optimal maze solution finding
| algorithm wouldn't be impacted.
|
| In cases like this, formulating difficulty can be more of an
| art than an optimization problem.
|
| EDIT: See also andrew_eu's reply (which I only saw now),
| where multiple "interesting" notions of "difficulty" are
| proposed.
|
| EDIT: Relatedly, humans use heuristics a lot. And there are
| many NP-hard problems where we can solve lots of "reasonable"
| points in the problem space in reasonable time (computers or
| humans alike), at the risk of having to time out, maybe try
| with another approach, and eventually just give up. Traveling
| salesmen _are_ actually traveling the country after all. So
| worst case is not always a good measure for games. But I see
| you mentioned that already.
| yencabulator wrote:
| Micromouse is primarily a robotics competition but they care
| about their algorithms greatly. It's a rectilinear maze and
| concerned about turning accuracy and acceleration etc, but
| there should be plenty of more abstract stuff in that space
| about most effective maze solving algorithms.
|
| https://en.wikipedia.org/wiki/Micromouse
|
| For example: https://swati-mishra.com/wp-
| content/uploads/2020/02/advanced...
| UI_at_80x24 wrote:
| When I was a kid I was really good at mazes. I would just stare
| at the maze, kinda zone out for a minute unfocusing on the entire
| thing, and eventually one path would look brighter to me somehow.
| I could never solve a maze by tracing my finger along a route,
| but if I 'un-focused' it would jump out of the page at me.
|
| My mother has told me I would have them done within seconds, and
| I'd have a whole book before she'd finish putting the groceries
| away.
|
| I've never thought much about it other then, 'I used to like
| doing mazes'; but I wonder if it was a special gift I could have
| developed.
| bee_rider wrote:
| Slightly silly question--did you actually check the validity of
| your solutions? It would be extremely funny, and certainly the
| type of thing I would have done as a kid, to just assume the
| path I'd found was the right one, haha.
| UI_at_80x24 wrote:
| Nope I checked. I was wrong a couple of times but it was
| rare.
| bee_rider wrote:
| Maybe in an alternate life you are a real wizard at
| designing PCBs.
| ordu wrote:
| _> I wonder if it was a special gift I could have developed._
|
| Seems that you managed to train your neural networks to do a
| parallel search. Probably visual cortex neurons. GPU
| acceleration rocks.
| qup wrote:
| I had a middle school friend who was a great artist, but also
| he drew mazes. "Brain mazes" he called them, because of the
| noodly look.
|
| Anyway, I always wondered how he could do it. To me he was just
| drawing lines everywhere, but there would eventually be a
| complete maze with only one solution.
|
| Maybe it was a memorized algo--like a party trick basically.
| Jach wrote:
| That's a fun name. I used to draw sort of noodly-ish mazes as
| a kid, too, though they didn't always have a unique path as
| there could be branch loops. Did they look at all like this 7
| minute mouse drawing version? https://imgur.com/a/lat8S6N
| There's no fancy process to it, though. I can picture a much
| more impressive maze deserving of the "brain maze" name.
| smokel wrote:
| 10PRINTCHR$(INT(RND(1)+0.5)+109); 20GOTO10
| leptons wrote:
| I made the mistake of walking into a maze at Burning Man, and as
| I was walking in there were people begging us if we had seen the
| entrance recently. I didn't think much of it, until I understood
| just how "fiendishly" designed the maze was. It wasn't very
| large, maybe 150 foot square, 8 foot tall plywood sheets, so you
| couldn't just climb out. At the center of the maze was a ladder
| you would climb up to a platform where you could see the whole
| maze except the part under the 20 foot square platform you were
| standing on. And that was the tricky part. It seemed that when
| you went through the center part of the maze you would end up in
| an unexpected part of the maze, and even though we could see the
| maze from above, none of it made any sense to how we might get
| out. It took us about 30 minutes to get to the platform and
| another hour to get out. I will never go into another maze again.
| bee_rider wrote:
| Speaking of burning men, how do maze organizers typically
| handle fire safety?
| leptons wrote:
| Fire extinguishers?
| anyfoo wrote:
| I don't know anything about mazers (or fire safety), but,
| assuming flammable materials like wood, how do they
| extinguish the fire before it takes over the whole
| structure?
|
| I guess "professional" mazes may have sprinkler systems.
| Still, it seems that even in buildings that do, a lot of
| value is put into maintaining escape routes.
| klyrs wrote:
| Panic
| bell-cot wrote:
| Unless someone is splashing gasoline around, fire will spread
| _very_ slowly in an open-topped plywood maze. And heat
| /fumes/smoke will head skyward, not accumulate as they would
| for an indoor fire.
|
| As an organizer, I'd be much more concerned about medical
| emergencies and inter-personal crime in the maze.
| gwbas1c wrote:
| Maybe try a corn maze if you have a chance?
| xivzgrev wrote:
| that's the way to go. one time got "lost" in a corn maze
| about 2/3rd way thru, going in circles, so just finally
| hopped a row, and followed the path out 30 seconds later.
| it's supposed to be fun, not stressful.
| temporarely wrote:
| Plywood walls that can be trivially written on.
|
| > I will never go into another [plywood] maze again [...]
|
| ... without a marker.
| marssaxman wrote:
| Do you remember which year that was? I'm fairly sure I
| encountered that project, and I think I found some way to cheat
| my way out of it without actually solving the maze, though I
| can't recall the details.
| bell-cot wrote:
| Any reason why "follow the right-hand wall" (and perhaps a
| few little scratches on the plywood) wouldn't work?
| cortesoft wrote:
| "Follow the right-hand wall" only works if all the walls
| are connected. It does not work if there are free standing
| walls.
| masfuerte wrote:
| Very true! I was here [1] a few weeks ago. I'd never done
| a real-life maze before and assumed it would be easy but
| with free-standing walls it was quite challenging. I
| think I explored every branch before reaching the centre.
|
| [1]: https://mazes.co.uk/
| yencabulator wrote:
| Outdoors, I guess you could use direction of sun as a guiding
| beacon, to decrease the confusion of which way you're pointed.
| 8ft tall walls in a desert will hide other landmarks I assume.
| ballenf wrote:
| Part of the difficulty seems to be the style of jagged edges,
| making it hard to visually parse.
| hoseja wrote:
| And then you see it's just an artefact of constructing the maze
| from connected triangles.
| IIAOPSW wrote:
| Mildly off topic, but I sometimes re-imagine the myth of the
| Minotaur as a parable about how the only bars which can't be bent
| by brute force are the ones made of computational hardness.
|
| Why did they build a maze for the Minotaur with a possible escape
| route rather than just an ordinary prison? Why leave the
| possibility of escape open?
|
| Well see, the Minotaur was arbitrarily strong. No material could
| build a wall strong enough that he couldn't bash through nor a
| door that he couldn't break down. But, he wouldn't try and break
| down anything if there was obviously a path right there he could
| use to go around it normally. By putting him in a maze, he will
| always keep trying the next path thinking it might be the exit,
| never attempting to break any wall. The puzzle is harder than any
| material they could have used to build a prison, as it cannot be
| bent by the Minotaurs brute force.
|
| Computation (eg cryptography) can be "unbreakable" in a way that
| bank vaults and deposit boxes can't.
| ilikecakeandpie wrote:
| I know it's a myth, but what would stop the Minotaur from just
| going full Juggernaut and smashing through all the walls should
| the Minotaur realize the paths are too difficult to traverse?
| reaperman wrote:
| Only the mythical head-canon of the Minotaur's psychology.
| Whereas I tended to believe that the Minotaur had everything
| it wanted to a reasonable degree of comfort as long as it
| continued to be fed.
| hoseja wrote:
| Why doesn't Sisyphos simply stop pushing the stone?
| eastbound wrote:
| Because he was condemned to do it.
|
| Perhaps what all those Greek epics taught me, is that once
| someone condemns you to a destiny, then that's it. No other
| destiny can open up.
| klyrs wrote:
| What, and do _nothing_ for eternity instead?
| Detrytus wrote:
| Because he was promised that once he gets it to the top,
| he'll be free. So, he keeps pushing, hoping that this time
| he'll succeed.
| simpaticoder wrote:
| Hades has total control over the (physical) rules of the
| underworld[1]. Hades can make the stone roll back for
| arbitrary reasons. But keeping hope alive in Sisyphus is
| the harder problem. Hades can essentially force Sisyphus to
| keep trying by making it arbitrarily painful to stop
| trying, but then hope is no longer his motivation. Hades
| could reset Sisyphus' memory such that hope remains, but
| then this loses the profundity of an eternal punishment.
|
| The more interesting case is that Sisyphus can contemplate
| the nature of the system, and reason toward an out that
| involved undermining Hades power over the Underworld. If he
| could pause and do experiments, discover the limits of the
| enchantment, and work around them, that would be ideal.
| However such an option would also be an excellent way for
| Hades to extend and deepen the severity of the punishment.
| A god's arbitrary power is arbitrarily powerful, after all.
|
| 1 - https://en.wikipedia.org/wiki/Sisyphus
| lawlessone wrote:
| >what would stop the Minotaur from just going full Juggernaut
| and smashing through all the walls
|
| Imposter Syndrome
| Vapormac wrote:
| Scorpion and frog
| zakki wrote:
| Follow the rule principal.
| IIAOPSW wrote:
| He never has that realization, for he is arbitrarily strong
| not particularly bright.
| darby_nine wrote:
| It ain't cryptography, though, it's just a a shortest path
| algorithm on a graph, which has wide and obvious applications
| for trade networks. Most computational problems we consider now
| were outside the scope of the easily expressible terms at hand.
|
| This is a great observation! I just hesitate to romanticize the
| applicability of modern concepts to classical situations.
| booleandilemma wrote:
| _I just hesitate to romanticize the applicability of modern
| concepts to classical situations._
|
| Check this out:
|
| https://en.wikipedia.org/wiki/Ariadne%27s_thread_(logic)
| Anarch157a wrote:
| >Why did they build a maze for the Minotaur with a possible
| escape route rather than just an ordinary prison? Why leave the
| possibility of escape open?
|
| Because it was not a maze, the Minotaur lived in the center of
| a labyrinth. A labyrinth is a continuous path that leads to the
| center. The objective was to send people into it so they would
| end up in the Minotaur's lair and be devoured. The reason the
| monster stayed was that he had everything he needed there,
| especially food.
| asdiovjdfi wrote:
| Interesting how the choice of design of ancient coins will,
| many years later, lead to comments like this.
| x3n0ph3n3 wrote:
| That's a really interesting distinction between the words,
| but sources from Wikipedia indicate that the minotaur was
| trapped in a maze:
|
| > Although early Cretan coins occasionally exhibit branching
| (multicursal) patterns, the single-path (unicursal) seven-
| course "Classical" design without branching or dead ends
| became associated with the Labyrinth on coins as early as 430
| BC, and similar non-branching patterns became widely used as
| visual representations of the Labyrinth - _even though both
| logic and literary descriptions make it clear that the
| Minotaur was trapped in a complex branching maze._
| aidenn0 wrote:
| Surely, if it wasn't a maze, then there would have been no
| need for Ariadne to have given Theseus a ball of thread to
| find the way back out.
| croemer wrote:
| TIL that one can say "very extremely rarely" in English
|
| > Quasicrystals are a form of matter only found very extremely
| rarely in nature.
| its_ethan wrote:
| Just because you can say it, doesn't mean you should... that's
| a pretty clunky sentence in my opinion. Then again, it will
| only occur very extremely rarely in writing, so maybe it's OK.
|
| ;)
| anigbrowl wrote:
| You are in a maze of twisty little passages, all alike.
| washedup wrote:
| No, thanks :)
| leni536 wrote:
| It looks like that only a small part of the actual maze is
| reachable from the starting point, which surely reduces the
| complexity somewhat[1]. But maybe the cutoff for the perimeter in
| the picture is not at the ideal point to show off the complexity.
|
| [1] https://imgur.com/a/3paGJOk
|
| I discovered a somewhat similar fractal-maze when playing around
| with the dragon curve[2], maybe I should publish that.
|
| [2] https://en.wikipedia.org/wiki/Dragon_curve
___________________________________________________________________
(page generated 2024-07-11 23:00 UTC)