Hacker News Reader

Comment by Symmetry | Hacker News Reader

Precomputing all shortest routes uses O(n^2) memory with the size of the map, though as opposed to the O(n) memory that this uses. For a Starcraft map that's the difference between a MB and a TB.

View on HN

Sure, but thats exactly my point. Given a set of well-stated limitations (like, cannot use more than N^x bytes of storage for an instance of size N, using the same standard library of data structures etc) we can make meaningful comparisons. I could come along with a method that uses O(n log n) memory and crushes this (maybe) - how do we declare a winner now, without some sort of context?

I think the constraints are implicit in the forum the talk was given at. This is Game Developers Conference so the constraint is that the algorithm has to run on the computers that the game buying public possess. If you think you've got an algorithm that can blow the presenter's out of the water on a typical PC then I encourage you to test it and show it to the presenter if you succeed.

Implicit constraints kind of suck for the purposes of creating and sharing knowledge though, don't you think? Even constrained to the domain, there are a wide variety of devices people play games on, so I still think its misleading to say this is 1000x faster than an alternative without the huge caveat that benchmarking is multidimensional.

No, they do not suck. For example, "This technique helps you build a frobble faster." "No, you can build a frobble much faster if you have sentient nanobots!" "We don't have those. I am speaking of techniques that actually work in reality." "But implicit constraints suck for sharing knowledge!"

One of these two voices is saying something useful about how to do things better. To borrow a sports metaphor, it is moving the ball forward. That voice is not the voice that is complaining about the use of implicit constraints.

Thats an explicit constraint, not an implicit constraint: The first person has an explicit constraint of "Lets consider only proposals that use existing technology". Thats exactly my point! Except in this case the implicit constraint was "must fit in memory for gaming applications", and I'm saying it should be made explicit. Its not that constraints are bad, just that they need to be shared along with the idea for it to be actionable.

Implicit constraints are the enemy of doing things better, as they allow people to claim basically whatever they want with hidden caveats, which makes it harder for the non-expert to figure out what they need to actually get things done.

I doubt a single person at the Game Developer Conference, watching a talk constantly referring to StarCraft, was at all struggling to understand that the technique was for game development.

Even if they somehow managed to avoid that tidbit of knowledge, the memory and runtime costs were fully explained in the talk, so any reasoned developer would be able to consider the applicability to their situation.

Reply on news.ycombinator.com