Doom is harder than your math homework

Yes, it turns out that Doom is PSPACE hard while StarCraft is a lowly NP problem. At least according to this paper exploring the mathematical complexity of playing Doom, Pac-Mac, Tron, Prince of Persia, etc.

Maybe that helps to answer why there aren't any single-player bots for Doom yet :)

I'm currently taking a lower-algebra math course for the third time in order to obtain a degree in graphic design, while I regularly kick ass on Brutal Doom. I beg to differ.

GoatLord said:

I'm currently taking a lower-algebra math course for the third time in order to obtain a degree in graphic design, while I regularly kick ass on Brutal Doom. I beg to differ.

Uhh, how about no? By that logic walking around without hitting walls should be easier than counting 1+1, but in fact creating robots that are able to move around without hitting things is way harder. We, as human beings, are simply adept at certain problems (especially when they are related to vision), but if you tried to "computationally solve" Doom, then that would be a quite a big problem.

For example, imagine a situation in Doom where you are in a corner with a cyberdemon rocket coming at you from one direction. It's extremely easy for a human being to deduce which way you should step to avoid it: You can clearly see where it's coming from and where the walls are. But a computer program simulating the player has no such intuitive information available. It would have to meticulously analyze everything in its sight every tick to determine what those objects are doing (if anything), it would have to figure out how far the visible walls are. It would have to try to "listen to" sounds from few rooms away and try to figure out what those sounds mean. And to top it all, it would need to have some kind of a memory: "I just turned away from an imp, so I know it's somewhat behind me, but I can't be completely sure where."

So, so many different things that you take for granted when playing, but which are actually quite complex to compute.

I'm pretty sure GoatLord was joking.

So...can I point out that I've made Doom maps and use that towards a minor in math at school?

Actually, it's more like I misinterpreted the OP. I was seeing it as "PLAYING Doom is harder than your math homework" for some stupid reason. Disregard my impulsive comment.

There are enough mundane tasks already easily done by humans and hard to program a robot to do.

Jodwin said:

So, so many different things that you take for granted when playing, but which are actually quite complex to compute.

To be fair, AIs have an inherent advantage in some of the things you mentioned, if they are allowed unlimited access to the internal resources and coordinates of everything in a map.

That's how RTS AIs appear to "cheat" simply by exploiting their intimate knowledge of the game's layout and knowing every position of every unit. Whether they always make good use of this information is debatable, but the hard fact is that as far as the game world is concerned, AIs can have a much more complete viewpoint than the player, even if a different one (e.g. even the monsters in Doom know exactly where the player or their target is when deciding which direction to take, before even using their sight functions: they are driven by a pure mechanical X-Y convergence. Hitscan and missile attacks are launched dead-center by the same technique etc.

Similarly, bounding movement through walls and objects is perfectly solvable by linear algebra at least from a purely mechanical/geometrical POV (without that meaning that it's trivial to plan a long-term strategy). However the AI can be made very good at reacting instantly: you could very well e,g, make a "bastard monster" in Doom that can dodge all missile attacks at the very last moment, or exploit purely mechanical control limitations of the player to "outsmart him".

Of course, if your idea was to make a robot that can only operate from "outside the box" just like a human player, using the same video and audio output and the same controls, and having to "build" a map in its head just like the player...well, that's a bit overboard ;-)

Shit blows my mind. Wish I was that smart.

Maes said:

To be fair, AIs have an inherent advantage in some of the things you mentioned, if they are allowed unlimited access to the internal resources and coordinates of everything in a map.

That's how RTS AIs appear to "cheat" simply by exploiting their intimate knowledge of the game's layout and knowing every position of every unit.

RTS games also cheat just by being able to direct more things at once than a player. More frustratingly, they cheat by being unaffected by resource limitations. Blowing up harvesters in C&C usually has no effect except to piss off the AI.

I see no problem with the AI being completely informed of all that's happening. It's possible that a super-fast-thinking person would be able to deduce information nearly just as fast. An AI doing this wouldn't really be cheating, unless it also gets a positive handicap (free resources and crap).

printz said:

An AI doing this wouldn't really be cheating, unless it also gets a positive handicap (free resources and crap).

What about knowing perfectly the location of your base and of all your units beforehand in a RTS where a normal human opponent would be hindered by Fog Of War?

OK, you could argue that a very tactical human opponent might gather that info pretty fast or be able to "read" into you as if the Fog of War was not there...which brings me again to a thesis I expressed time and again: to a lesser player, a cheating AI is indistinguishable, result-wise, from what an elite player can do. The only real difference is the process through which this is achieved.

This is not necessarily a bad thing: think e.g. greyhound racing. The dogs involved compete against each other, but are trained/driven by a mechanical "hare" which never gets tired and which could easily be built to run faster than any greyhound, though that's not the point of the races. The rationale is that by having the dogs run after a mechanical "opponent" which is calibrated just so they can't catch it, they are compelled to run harder and compete among themselves. Similarly, AI has a skill level which is simulated mechanically by doing things that a normal player can't do, but could adapt to eventually. Similarly, you don't expect greyhounds to grow electrical motors, gears and track wheels, but merely to go as far as their muscular anatomy would allow them.