Article
i/2008/04/atom

Is There a Core Building Block of AI?

Dave Mark on April 8, 2008

This week’s discussion on AiGameDev.com is introduced by this article from Dave Mark, the AI guru behind Intrinsic Algorithm. Feel free to answer at least one of his open questions in a comment below!

Chris Hecker is quite a character. Neil Kirby passed on to me that he once heard Ernest Adams (admittedly another character in his own right) describe Chris as a cross between Albert Einstein and Winnie the Pooh’s bouncy pal Tigger. If you’ve seen him speak, you know that is dead on. However, he is also a visionary in the game world that also brings back memories of the old E.F. Hutton commercials… When Chris Hecker talks about the game industry, you had better listen — there’s likely something important that he’s thinking about.

At GDC 2008, this was again the case. Tigger Chris made an interesting suggestion about the path of future game AI. In his lecture entitled Structure vs. Style, he pointed out that the cusp in graphics presentation technology was when the atomic building block was settled on — that of the the texture-mapped triangle. Once that technique was “discovered”/”invented”, graphics technology then built upon it in a variety of ways (e.g. bump mapping, normal mapping, etc.). However, the core always came back to that simple concept — the texture-mapped triangle. It became a standard in the industry and is, literally, the piece from which everything we see in games is built upon. And why is that? Because, as the title of his presentation alluded to, it is the nexus point of “structure” and “style“. Structure, as defined by Chris, because the computer can reason about it at a deep, complicated level. Style, because the artist can use it, as I mentioned, to create… well… anything and everything! Given enough time and enough texture-mapped triangles, you can build entire cities. It’s simply a question of scale. Look closely enough and you get right back down to that cute little 3-sided polygon with something spray-painted onto it.

The point of his lecture, however, was not a worship service dedicated to this Holy Trinity of Vertices. His point was that there is a major component of the game experience that hasn’t yet found the spark for it’s Big Bang of development such as the one that occurred in the graphics universe. Game AI has yet to find that “one thing” that their world can be reduced to. And, as such, there can be no “Photoshop for AI”, as Chris put it. Yet.

The Search for Standards

There has certainly been plenty of progress at standardizing terms, concepts, definitions, and even code over the past 20 years. As AI programmers, we all know what A* is. In fact, we all are familiar with the what the letters f, g, and h. stand for when we talk about it. Not too many people need to “roll their own” pathfinding algorithm any more. Sure, they may tweak and nudge and add layers of complexity — but at the core, it is still the same A* algorithm.

“No one wants to build their world around the model required of a middleware.”

However, even something as simple as this is not without its controversy. The creators of AI middleware will tell you that they are fighting an uphill battle of sorts. One of the major pans on their products — and even the concept of middleware in general — is exactly the point of standards. No one wants to have to build their world around the model required of a middleware piece — and that is even the case with something as relatively standardized as pathfinding! The amusing irony is that the navmesh idea is also based on the idea of creating something out of polygons. It would seem that even the pathfinding problem hasn’t gotten the definition of a basic building block figured out either.

If Not Atoms, Maybe Just Molecules…

But that only solves pathfinding. In the past, that used to do it for AI. Move around the maze and you’re good to go. The problem gets worse. AI is so much more than pathfinding now. And that is where we run into problems (but at least not walls, I suppose).

The graphics world operates on an economy of scope. They can create a lot of scale by simply iterating one thing. Unlike building a city with near infinite polygons, the purview of AI covers many disciplines. Perception, strategy, tactics, animation, communication… each of which has their own subsets of specialization. What is at the nexus point of all of those? Is there anything that is the core, atomic building block off all of that? Or are we, perhaps, hurting ourselves too much by lumping all of those disciplines under the one banner of AI? Maybe there is a common thread in each or any of the categories above that doesn’t necessarily apply to the others?

AI Shop

Screenshot 1: AI Shop coming soon to a computer near you!

Can we come to an agreement on, say, animation AI? Just looking at the books on the subject, the proceedings of GDC and other such conferences, and web sites dedicated to animation AI, it seems like there are a lot of dogs in the race (and some are even running on different tracks). While there have been standard-like leanings on things such as skeletal systems, there are lots of ways that you can implement those. The skeleton itself is not AI — what we do with it is. That involves motion and, really, the reason for such motion. Is it due to the physics acting on the skeleton or is there purpose and intent from the actor itself? How is that represented? Is it both? At what point does it cease to be physics and become AI?

How about perception? Or is perception not really AI but physics? (Here we go again.) Sure, a ray-cast is easy enough for line-of-sight checks… but is that AI or just geometry? How do we represent sound transference in a way that everyone can use and build upon? That would mean that we have to all agree on standards for things like acoustical reflectivity and absorbency that we can then embed into our surfaces. Walls, floor, furniture and the ubiquitous crates and exploding barrels would all have to be “painted” with information on how to handle sound. Is that feasible?

Higher-Level AI

Strategy and tactics are simply insane to try and boil off down to a stock. However, one thing that may be atomic is the concept of a “task”. Planning algorithms and hierarchical task networks certainly seem to think so! But what is a “task” comprised of? And, to complicate matters, you would need things like preconditions and results of those tasks in order to connect them properly. Both of those require definitions of world states that can be tested and changed respectively. Wouldn’t we have to standardize the world model in order to standardize the task model?

We can’t even get close to finding common threads in some of the new, leading edge concepts that AI is delving into of late. Emotion? Psychology? Heck, psychologists can’t even come up with a core building block for real humans much less one for artificial ones.

So, what is holding us back? Is this a solvable problem? Does it need to be solved? If it is not solved, are we forever doomed to build and rebuild from scratch? Will there eventually be entire camps or schools of thought about the construction of AI?

Can there ever be, as Chris Hecker put it, a “Photoshop for AI”? Post your comments below.

Discussion 16 Comments

ChrisJRock on April 9th, 2008

Is it intelligence your after or just a clever robot? A* finds paths, but it doesn't find paths the way a brain does. Brains have limited information, associations, and assumptions--like you said, psychology. I think taking even a tool as basic as A* for granted is a mistake.

Andrew on April 9th, 2008

I did read about this talk before - I think that if physics can't be easily dropped into games (and it can't without careful planning) pathfinding will be the same. But an entire AI system? Wow, talk about problematic. Even if you only had "AI Tool for FPS" then it'd have some limitations, which would inflict serious gameplay decisions just to use it - what if it had no way for the AI to control vehicles? or to climb ladders? (how many today climb ladders anyway? I can count them on one hand ;) ) or to find "cover", or to act like an alien warlord rather then a human? For an FPS I see it as a distinct probabilty no generic AI package would work out of the box. Certain elements might, but the toolset would have to be rewritten or taken apart to add functionality, since no way is there a filter for "additional functionality" :) You could perhaps generalise RTS gameplay, but then how would you work if the game was in a 3d plane and not 2d plane? Or if there were no "resources"? or different needs for strategic planning? Or what if number crunching "unit stats" didn't work effectively? What about racing and sports games - surely, these, must have photoshop-like toolkits right? Well, a specific game type might, but you wouldn't be able to apply a Rugby toolkit AI to American Football! Let's not get into RPG (turn based? real time?) action and platformers, where AI is random at best, or perhaps puzzle games, or chess? and tons more gameplay types besides, and nevermind the theme of the game - a space age game has very much different needs to a fantasy game, and both would have things no "realistic" game would have (magic and lasers) which would break a "standard" AI perhaps. Man, so many different types of AI, how would you make a fast-running, lightweight package which had a tool to pick and choose the required behaviours? And have that package have enough behaviours to fit all possibilities? Sure, Photoshop might not have every single filter, but it only deals with images - it'd be poor at dealing with audio, or film, and likewise AI toolkit would have to deal with one area, not every area, to be workable in my opinion :)

alexjc on April 9th, 2008

ACTIONS & CONDITIONS! I doubt it's possible or desirable to cover all the things you mentioned with a "standard" but at a low-level there's hope. From programming perspective, you have chunks of code that get information from the world (conditions), and pieces of code that instead make changes (actions). This is as standard as it gets really; you're either running those bits of code or not! This makes sense from the design side too. I think I could build a whole bot based on those actions and conditions only. Even the actions and conditions that deal with fuzzy information are active on a boolean basis: you're either perceiving or you're not, acting or not -- regardless of how little it is... On a higher level, you could consider building the whole AI based on the superset of actions and conditions: TASKs -- which is what I discuss at length in the blog. There are minor things that you may argue over the API, but effectively the functionality is there. Many of the features you mention should emerge as patterns by plugging in these TASKs into a data-representation... But you probably can't standardize those any time soon! Alex

gwaredd on April 9th, 2008

It might be worth bearing in mind that whilst the humble triangle is the core building block of modern computer game graphics it is not the only way to render a scene (nurbs, voxels, ray-tracing, etc). It was more a case of people standardising on one techique because it was the most efficient for a given level of quality. So any AI building block needn't try and encompass everything - just standardise on a particular technique that gives good resulsts. For example FSMs are pretty wide spread. BTs and HFSMs being extensions on the core idea of a 'state'?

zoombapup on April 9th, 2008

One thing to note. That this "128 simple processor" model is actually already there, in the machine. Its called a GPU! Its not just for graphics anymore, its a general purpose, high speed parallel processing system. I'm right now looking at using it for some of the fundamental tasks for AI. Maybe the idea of "Hardware based AI" is about to become relevent, I dont really know, I just know that its going to become a more appicable method of using simple scalable processing systems, which is basically where we're headed right now.

Eric_Gilbert on April 9th, 2008

The idea of a hardware "AI Processor" solution is already being looked at by a company called AI Seek. Below is the link to the page about "The Intia Processor." [URL="http://www.aiseek.com/Intia.html"]http://www.aiseek.com/Intia.html[/URL] It will be interesting to see how this works out for them, who their competitor will be, and what CPU company will buy them up when they get popular...the same thing that happened with GPU's and PPU's ;-)

gwaredd on April 9th, 2008

[QUOTE=Eric_Gilbert;1991]It will be interesting to see how this works out for them, who their competitor will be, and what CPU company will buy them up when they get popular...the same thing that happened with GPU's and PPU's ;-)[/QUOTE] Because the AGEIA cards were very popular :P Sales were at least in double figures ;) CUDA from nVidia is the more likely route if you are looking for hardware accelleration.

zoombapup on April 9th, 2008

Exactly. I think CUDA is definitely the way to go to convince people of the need for AI hardware at least. A seperate add-on card would need to be VASTLY more capable than software, which is where the PPU falls down. Weirdly enough, the same could be said for early 3D accelerators, we had VASTLY superior render speed out of our software rasterizer than the majority of the early 3D cards (creative 3D blaster springs to mind). It was only when the 3DFX came out that we actually saw a speed+quality improvement that we took 3D hardware seriously. I think the same will be said of AI hardware. Personally, I think its better to look at retasking GPU's because the hardware is very very fast, is in gamers machines NOW and because NVIDIA want me to :)) Sorry for derailing the thread btw. Maybe we can start another one for GPU based AI :)

Andrew on April 10th, 2008

Grahpics programmers won't give up the GPU timeslices to something like AI ;) they're very specalised too, fast for certain applications. It'd be interesting to see how far you get research-wise zoombapup, but it might not be that much of a good thing. And the PS3/Xbox360 are typically geared well towards fast processing of algorithms on its many cores - more so then PC's. PC's might benefit from a new card, but honestly? Once we get quad-core being common, AI will be one of the major things (like Physics) running to keep those cores at capacity I think. There won't be a demand for a separate unit. Already happening a bit with dual-core too.

zoombapup on April 10th, 2008

Yeah, I agree that nobody would want to have thier graphics card doing AI while its not rendering. However, the fact is that we already have dual graphics cards, plus its pretty inevitable that we'll face the same moore's law issue on GPU's that CPU's faced that caused the split to multicore in the last few years. So faced with multicore CPU and multicore GPU, I think research in those areas for potential uses is generally useful. Even if it ends up that the GPU isnt the ideal platform, it certainly drives the debate about the shape of AI methods (plus frankly, it gives me something interesting to do that touched on my own preferences). I've been talking with Gabe, my phd student about buying a 16 core CPU machine with a quad core GPU in a few years time and seeing exactly whats possible with it. I mean it sounds crazy, but I think 2-5 years will see us in that sort of territory. Better get our skates on and learn how to do multicore AI code pretty bloody quick :) BTW: I'd be happy to have a go at an SPE version too. Bloody sony :)

JonBWalsh on April 10th, 2008

It'll be interesting to see what happens with PPUs (or to a less extent physics being offloaded onto the GPU) later on as well. With PPUs and GPUs freeing up some of the CPU use that right there is room for some extra AI processing time. Even more exciting to me is if PPUs catch on how feasible would it be to use the PPU to calculate AI for games without high physics demands (for example a game like the Sims or a 2d side scroller).

gwaredd on April 11th, 2008

Returning back to the original idea of defining the 'core building blocks' of AI ... I think planning algorithms define the scope quite well. AI is an interest rather than a speciality for me so I apologise if this is covered in some paper I haven't read ;) So, as I understand it - the world is currently in a given (percieved) state (the initial state). I want to change it to a new state that is desireable given my 'goals' (the goal state) which I may or may not be able to do by performing 'actions'. This pretty much covers the core building blocks for me. A planning algorithm will search the space to find a set of actions to achieve the desired goal states. Rule based approaches are essentially programmer/designer created scripts to follow that should achieve the desired goal. Learning systems are rule based approaches that can iteratively self modify based on some 'success' criterion. The 'core blocks' are all there, the question then becomes what is the best technique that gives you the behaviour you are after. Note that agents may have their own perception of the current 'world state' (belief) which may or may not be the same as the actual world state. They will have ways of perceiving the world and they may also be able to reason about possible future world states and actions of other agents. Similarly one agents actions may not be the same as anothers and naturally the goal states and goal selection will differ. Actions may have pre-conditions and effects. So if I had to boil game AI down to the absolute fundamentals it would be those ... world states (and perception of) and actions. If you could specify those in an abstract and flexible way then it may be possible to drop them into a planning system or BT or FSM and mix and match as you please. Similarly you could take a behaviour from one game and drop it into a different game quite easily. Just my $0.02 :)

Dave Mark on April 12th, 2008

gwaredd: I alluded to what you are talking about in the article itself when I suggested that a potential "atom" would be a "task". That actually came out of a conversation that Alex and I were having as I wrote the column. We agreed that with the rise of planners and BTs, having that core "node" of a tree is something that could be easily definable. Also, for the reasons of portability that you mentioned, we can start to see reusable code based off of a stock collection of these "tasks". The caveat of all of this is that the world state itself would have to be somewhat standardized - or dealt with through a pretty robust interface - in order for things like the preconditions and effects to be addressed.

gwaredd on April 14th, 2008

A "task" slightly confusing terminology to me. Mainly because when I think of "tasks" I instantly think of scheduling and multi-threaded systems - but thats probably more to do with me than anything else ;) In AI terms "task" conjours up pictures of specific behaviour patterns. In that sense a task isn't atomic in the way a polygon is in a rendering engine. It sounds more like a composite object that encapsulates something else - to belabour the rendering metaphor - it might be akin to model? By task do you mean node in a state machine?

Dave Mark on April 16th, 2008

Yep. By task, Alex and I are referring to the way Jeff Orkin used them in F.E.A.R. In that case, any movement or action was a task. Move, duck, aim, fire, turn head, flinch, jump, roll, etc. The entire NPC existance was a string of individual tasks - each with an associated animation. The same could be said of RTS games as well. Build X, Group Y, Send to Z. It's a stretch, but it's a good concept.

psamtani on April 21st, 2008

I think the big problem is that raster graphics are to a large extent a solved problem, and graphics is a simulation of a well-understood physical system that can be observed and understood through experiments. Whereas AI attempts to simulate a system that is very poorly understood, undefined, and can barely be observed (MRI can only show which parts of the brain are active, but the underlying process is not observable at this time).

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!