Severed bunny head
Register | User Profile | Member List | F.A.Q | Privacy Policy | New Blog | Search Forums | Forums Home
Doomworld Forums : Powered by vBulletin version 2.2.5 Doomworld Forums > Misc. > Everything Else > Doom is harder than your math homework
 
Author
All times are GMT. The time now is 19:42. Post New Thread    Post A Reply
david_a


Posts: 1350
Registered: 09-02


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 :)

Old Post 01-27-12 15:54 #
david_a is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
GoatLord
Senior Member


Posts: 1414
Registered: 07-02


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.

Old Post 01-27-12 17:19 #
GoatLord is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
Jodwin
Forum Staple


Posts: 2741
Registered: 02-05



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.

Old Post 01-27-12 17:55 #
Jodwin is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
Xaser
Senior Member


Posts: 1630
Registered: 07-03


I'm pretty sure GoatLord was joking.

Old Post 01-27-12 18:35 #
Xaser is offline Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
yukib1t
Will DDR for food


Posts: 2160
Registered: 06-02


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

Old Post 01-27-12 19:10 #
yukib1t is offline Profile || Blog || PM || Email || Search || Add Buddy IP || Edit/Delete || Quote
GoatLord
Senior Member


Posts: 1414
Registered: 07-02


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.

Old Post 01-27-12 19:10 #
GoatLord is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
printz
CRAZY DUMB ZEALOT


Posts: 6847
Registered: 06-06


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

Old Post 01-27-12 21:18 #
printz is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
Maes
I like big butts!


Posts: 8662
Registered: 07-06



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 ;-)

Old Post 01-27-12 22:33 #
Maes is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
Alientank
stupidest isn't a word.


Posts: 1153
Registered: 05-02


Shit blows my mind. Wish I was that smart.

Old Post 01-29-12 21:49 #
Alientank is offline Profile || Blog || PM || Email || Search || Add Buddy IP || Edit/Delete || Quote
Aliotroph?
postCount++


Posts: 1809
Registered: 03-02



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.

Old Post 01-29-12 22:00 #
Aliotroph? is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
printz
CRAZY DUMB ZEALOT


Posts: 6847
Registered: 06-06


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

Old Post 01-30-12 00:00 #
printz is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
Maes
I like big butts!


Posts: 8662
Registered: 07-06



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.

Last edited by Maes on 01-30-12 at 00:17

Old Post 01-30-12 00:10 #
Maes is online now Profile || Blog || PM || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
All times are GMT. The time now is 19:42. Post New Thread    Post A Reply
 
Doomworld Forums : Powered by vBulletin version 2.2.5 Doomworld Forums > Misc. > Everything Else > Doom is harder than your math homework

Show Printable Version | Email this Page | Subscribe to this Thread

 

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is OFF
vB code is ON
Smilies are OFF
[IMG] code is ON
 

< Contact Us - Doomworld >

Powered by: vBulletin Version 2.2.5
Copyright ©2000, 2001, Jelsoft Enterprises Limited.

Forums Directory