Hacker News Reader

Comment by bee_rider | Hacker News Reader

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.

View on HN

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

Ah, I’m glad that somebody at least tried to come up with a measure that sort of… matches the human eyeball intuition of what a difficult maze is, even if it is mathematically a bit funky.

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...

[1] "The Fastest Maze-Solving Competition On Earth" (22 min) is a nice introduction to the competition and its technical history.

[1] https://www.youtube.com/watch?v=ZMQbHMgK2rw

> But does anyone know a good metric for maze difficulty?

I think there are a bunch of problem-definition details that would need to be hammered out first, ex:

1. Is this solving the maze with perfect knowledge of its layout--a bird's eye view from above--or does it require gradual exploration to fill out the contours?

2. If it requires exploration, how far can you see? Do you need to actually spend a move to enter a square to know whether it is a dead end, or can you tell from N squares away? Is the viewer constrained by trigonometry, where they can only uncover partial knowledge about nearby rooms and small geometric quirks can have a big effect on exploration progress? Is there a distance limit to vision?

3. If it requires exploration, is there a cost to backtracking, or--like DFS--can you simply teleport between all places you've already been without a cost?

4. Is a "difficulty" rating across mazes based on a single algorithm, or the best-possible choice for that particular maze from a set, or does it represent the average expected effort expended by a particular population of different people/algorithms?

____

Right; I didn’t do any of that because I’m more curious if somebody has already done it. Generally with CS stuff I find there’s somebody who’s already poked around the maze a bit and found a neat path to explore. :)

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.

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.

One rather significant yet under appreciated difference between human and computer path finding in general is that humans cannot BFS. The closest we can get is a sort of modified beam search. But there always will be a latency added when switching heads that computers simply do not have (módulo generally insignificant cache stuff, perhaps)

This has significant implications to search spaces that are very heavily branched with many deep dead ends but a relatively shallow goal.

The number of problems in general life matching that description is… huge.

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.

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.)

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.

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.

Reply on news.ycombinator.com