4 ms·

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,

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

by anyfoo 2y ago

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.