6 ms·

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 t

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 2y ago
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 2y ago
  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 2y ago
    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.

anyfoo 2y ago

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 2y ago
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 2y ago
  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.