4 ms·

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 car

by kleiba 2y ago

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

by kleiba 2y ago

anyfoo 2y ago

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.

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