Slashdot Mirror
Talking 'Bout Game AIs
Steven sent over an interview Feedmag has got with the lead AI programmer for Black & White. He talks about some of the creature/villager routinues in the game, which is interesting for the game, but also interesting in terms of how much the world of AIs for games has changed in the last few years.
...a game called Galapagos? It was made by a company named Anark, which seems to have fallen off the face of the earth (anark.com is now a provider of web tools).
Basically, you had a pet insect-sort-of-thing that you had to help escape from a 3D puzzle world. The trick was that you didn't control the creature, you only manipulated the environment and let the creature react to it. The creature was driven by Anark's AI technology with a buzzwordy name, but you could see it working. After it fell off a certain place a few times it would be reluctant to go back there, and would try to ignore your commands (you could poke it with the mouse) and get back to a safe place.
Anyway, my point is that B&W might not have the most advanced AI in gaming history after all.
The problem with Quake bots as an AI challenge is that you can give them perfect aim, making the challenge into one of who has the best gun when, which could then break down into deathmatch spawn points.
Also, it's impossible with Q3 to get clientside bots to connect to the server as the protocol is unknown. You'd have to edit the DLL source that Id released, and getting two bots in one source tree is more than a whim.
I would like to see an environment where the hardships in overcoming it would all lie on the programmer instead of a user, like with Quake's aiming. The general idea would be to have every decision be one of the type of 'no best answer' as opposed to Quake's aiming 'there is a best answer', at least for every hitscan weapon.
almost all of these questions can be answered with a variable holding a certain numerical value.
The problem (and what makes these games fun) is that the answer to the question depends on more than a simple number -- they all depend on the state of the other questions, and all sorts of other factors in the game. It's the emergent properties that are interesting -- and that are hard to quantify.
There is a problem with having the AI play against itself though. I can't remember the exact reason but it can only learn so much that way.
The problem is that the AIs will become good at beating other AIs - not at beating humans. If the competing AIs are all stupid in one particular way, they won't clue into it by themselves. Also, if you have deterministic AIs, you might enter a closed loop (endlessly replaying the same set of games with the same set of learning variations).
Careful design of the AI can minimize these effects (e.g. by forcing speculation on random strategies to discover new techniques by brute force), but it's not easy and not very efficient most of the time.
Humans are very good at showing AIs where the holes in their techniques are, so mixed human/AI games will provide the best learning environment for them most of the time.
According to the article, game AI has traditionally been forced to use a meager .1% of the CPU in games, due to the huge resource requirements of making the pretty pictures. However, this has all changed with an earth-shattering 250% average improvement in the amount of CPU time allocated to AI-- leaving us with a remarkable .25% of the CPU dedicated to AI!! That's amazing!
I'm not going to flame you. You are essentially correct. The problem is the practical difficulty.
There is a backgammon program that learned, from scratch, how to play backgammon. It is now a world-class player. So clearly, we can learn how to play games.
One little catch: The program played millions of games of backgammon with itself before it got that good.
As you might imagine, Alpha Centauri is significantly more difficult then backgammon. Chess hasn't even been "learned" yet (all the best approaches I know have heavy dollops of brute-force searching). Plus, as the problem increases in difficulty, the time necessary grows. Ouch.
It's a good idea, but we don't know how to do it practically yet. That's why B&W really is interesting to me; while the algorithms aren't necessarily ground-breaking, it is an interesting application of real-time AI in an environment where the AI really shines (as opposed to input difficulties).
this is pretty standard in the industry, btw. otoh, it would take a skilled ai programmer easily more than a month-and-a-half to implement and debug an inference engine in C++. and you can forget about something like writing a compiler for building behavior-based networks - that takes too much time.
Seems to me that there would be a niche for a company to invest heavily in developing a flexible AI framework to be used in multiple games. Or does something like an inference engine so much customization to a particular ruleset that this wouldn't be worthwhile?
Otherwise, though it represents a big up-front cost, a company with a variety of titles, or a well-established series, should be able to spend a little extra time on AI and gain a competitive advantage.
--
"As recently as 1999, most games devoted only .1% of the CPU's resources to running the AI."
...snip...
"According to a recent article on the game development site Gamasutra, an average of 250% more of a computer's resources are now devoted to AI."
So... A whopping 0.25% is now devoted to game AI? Step back.
Seriously though, processing power is a really weak way of assessing the sophistication of an AI. It's really easy to max out a chip on a neural net that ends up going almost nowhere, and a well-programmed behavior engine could create an extremely realistic AI on a Palm. Like most anything, it's all about the coders. It's great to see that more attention is being given to cognitive realism (Sims, B&W, etc.) instead of/in addition to kinematic realism (Trespasser, <insert latest FPS here>, etc.).
I can't wait until this kind of dedication to learned and adaptive behavior makes its way to War/Star/foo-craft... Or Microsoft Bob...
Kevin Fox
--
Kevin Fox
i>My GF thinks Counter-Strike is cool....
Propose. Today.
Can we get some AI routines that will keep the villagers from walking right through a four-foot-high piece of poop?
I just can't be impressed with AI until then.
-- Mojo Tooth : exploring our world as only an idiot can.
"decisions trees have not been used in games before".
I'm willing to bet that's a load of bull. Maybe noone called it a "decision tree" but I'm sure there have been AI structures that perform exactly the same function in some game, somewhere. There have been *alot* of games, and they have explored *alot* of options. Maybe they didn't have 6 million dollars of personal cash make them famous like B&W, but they were still there.
I was glad to see him acknowledging its limitations though.
What he describes is nothing special to the AI world, very basic techniques. I'd like to see something more complex, perhaps a backprop neural net and adaptive planner (which would give them foresight) instead of a perceptron and a decision tree. For a single creature, the CPU hit would be trivial. The real limitation is the human time required to design it.
I'd rather it did cheat than provide such an easy win. The scenarios are incredibly complex and challenging at the outset. But over time, human victory is assured if you can hold out long enough.
It would be a great multiplayer game, but its nature isn't very easy to multiplay with.
It's not that the developers are stupid, they know how to play their game and they can usually fill in decent values for all of those variables.
The problem is that being good at a strategy game involves much more than the variables you list. Learning to plan out attacks and spot weakness are not things that the AI can easily do, nor pick up from observation of a person playing.
These are the achilles heel of AI in a strategy game, and there is no simple fix.
I'm aware that a perceptron is a neural net, but being limited to one layer really gimps its ability to generalize.
But I think you sell neural nets short, while they are pattern recognizers, they are capable of finding extremely complex relationships between variables, relationships that are hard to code as boolean values.
But I think in practice it would prove difficult. Mining data from a set with so much variance in player skill would prove very difficult. And again, you still have the problem that figuring out a huge array of optimal variables is not going to give you a good AI. It will be better, probably, but still woefully inferior to a human. It all comes down to foresight and insight. Until we can put that into an AI, forget it.
Actually, one way to make AI's challenging is to paly to the computer's strengths, real time games with lots of things to do are great for computers because they can handle it all. A human needs the game to go at a certain pace or they lose it.
So Europa Universalis, for example, is a game that is much more difficult to win at if you don't allow pausing.
Well writing a strategy game AI isn't like writing a novel, but its no small feat either. Take the time to consider everything you think of while playing a game. Yes 95% of it is probably set ahead of time, but that last 5% is what really sets an AI opponent off from a human one, and that's where the challenge in programming an AI is. An example is when I play games there are certain things I might consider a few turns in advance, while others I ignore. Having the computer decide what to consider in depth though is hard. Does it consider the long range implications of launching an attack or for expanding. It doesn't necessarily have CPU time to do both, just as a human only has so much real time to think about the situation. It's very easy as a human to quickly judge the situation and say "I'm pretty safe I'll expand for now" but telling a computer how to do that is much harder.
The idea of the computer learning after every game is nice though. There is a problem with having the AI play against itself though. I can't remember the exact reason but it can only learn so much that way. What might be interesting is an internet site that could collect the AI's from many users games and combine them, distributing new AIs. That way every person playing against the computer is helping to train it.
And I definatly like the idea of an API to build your own AIs or expand the one currently there. It would be fun to load up Starcraft and go on BNet and start a game with someone and see if your computer program can beat them. Or even just playing your own AI to train it.
In 3.3 milliseconds, an Athlon 550 can go ahead and read/write ram a few hundred times, do a few hundred thousand instructions, etc. When you consider that it has 1 click tick every 1/550,000th of a second, 0.0033 seconds (or 1,815 clock ticks) don't seem like that short a period of time at all.
Think of popular and succesful games: Half-Life had neat AI for the Marines. If it had just been the odd aliens and Sci-fi plot, I probably would've have played the game through twice in a row. That game performed well on a 300Mhz machine!
--
--
Internet Explorer (n): Another bug -- that is, a feature that can't be turned off -- in Windows.
Just a guess, but if each node in a tree was a decision (do I eat this?, is this compatible with my alignment?) and the left and right had strengths (60% sure I'd say yes), then you could tweak that bias as you monitored feedback from the actual outcomes.
It's a bit more crisp and reflective than a neural net, in that you know the specific purpose of each node. In a neural net, it's hard to reflect: "why exactly did you make that choice?"
[
I can make a few guesses. Perceptrons and other neural networks basically map a set of inputs to a set of outputs. An external error is generated each time the network runs and the network is adjusted to try to reduce this error. In the case of a game the error would be derived from the success of the unit. Each sample theoretically drive the network to minimise the error, however it is a rather random process, especially with such a non-linear system.
The real problem is to choose the right inputs and outputs for the network, and to get the thing to actually work. The inputs and outputs must be general enough that the network can analyse them, but specific enough to represent the environment and control the unit.
As for decision trees, they would be useful to breaking down the situations a unit is faced with, and isolating them so that the decision making is effective. It also provides a look ahead mechanism to try to predict what will happen. The decision tree would be the main memory of previous experiences. I think in the case of a game it would be very difficult to recognise similar circumstances to fit branches of the tree.
AI is a very interesting area, and not really that difficult to get started in. I suggest looking up some of the terms on the net and seeing what turns up, although a good textbook will be much better.
She's cruising through the tutorial having a great time when she is supposed to bring a rock back to the village sculptor. She fails to zoom in far enough, and drops the rock right on top of him. "No! I didn't want to kill him. Oh, no." She quits the game, turns off the computer (we never turn the computers off), goes downstairs and crawls under the covers.
Someday people will realize this is what its like to "play like a girl" and write a game accordingly.
t
An another article discusses how an AI researcher is developing bot's with cutting edge AI.
The Economics of Website Security
The Creature uses a noddy state machine
So that's why my character acts so wooden.
Will I retire or break 10K?
A 250% increase in 0.1% of CPU time means it goes to 0.35%. Learn some simple math, yeesh.
--
Oceania has always been at war with Eastasia.
Some of it at least was written in C/C++. I know this because I found a bug where if you click on a workshop that is in your area of influence, but which you do not control, you get: "Percentage complete: %3.0f%%". Someone didn't do their sprintf correctly. :)
Anyone have any insights into this "decision tree learning" that Evans mentions? It seems to me to be one of those fuzzy terms that could refer to any of a dozen things.
Like "perceptrons" -- unless he's actually referring to the algorithm described in Marvin Minsky's book of the same name, which would actually surprise me quite a bit, based on (what little) (and I mean little) I know about the book.
Seems to me that a "decision tree" is a simple deterministic programming construct, so the real interesting part would be how you change it in response to stimuli. Anybody have any inside knowledge (grin) on what he's actually doing?
--
Accountability on the heads of the powerful.
Power in the hands of the accountable.
You know, this game is starting to make me wonder if we're not just individual threads in some massive "Black and White II" game, a la Thirteenth Floor. Forget Descartes, can you think non original thought is actually original if you're programmed to ignore the source?
funny munging
Are AI routines still computed during the vertical refresh with today's multi-threaded OSes?
;-) Of course, "vertical refresh" is a CRT concept, so fortunately, developers can simply draw or blit into abstract frame buffers. OS drivers then get that bitmap representation onto a physical screen (LCD/CRT/VR goggles).
You'll have to ask the task scheduler of the OS when it's executing the AI threads, now.
Joking aside, I recall not too long ago having to count cycles to keep my AI code from "leaking" outside of the vertical refresh period on a Game Boy.
Duh.
The point is that the theoretical stuff is what is the bleeding edge, not the gaming industry. The fact is that they don't pick up on stuff until its well past the theoretical stage.
Immersion is one thing, games do it rather well, but the study of AI isn't all about "wowing" the audience. It is a serious mathematical, philosophical, and electrical study of the limits of computer programs. The gaming industry doesn't have time for this stuff. They are busy making money, like they should be.
Nor really... The AI in games is minimal at best when compared to the capabilities of AI in a theoretical sense. The problem is that AI is difficult to design and takes alot of time, and developers are out to make money, so they invest in technologies that will immerse the player in the game to get them addicted to it.
Its a new type of addiction for me, because I'm not playing to see how far I get, or see how big my avatar will get, its to see what he does next when he's off my leash. Was he watching when I was throwing the rocks, and start throwing villagers? Was he watching me pickup and move villagers to do the same?
So, it may be a long time before some really sophisticated AI gets into games, if ever. Think about it, if a chess computer can beat the world champion, don't you think there are strategies in many of these games that would be similarly difficult to beat?
If you want cutting-edge AI, don't look at games, look at OSCAR at the U of Arizona, or at the MIT Media Lab , or at the stuff going on at CMU or RPI. That's where the real progress and research is being done. Not in some programming sweatshop at EA.
Wifey: Can I see your new game? Me: Sure. It takes a long time to load, but here... Wifey: Oh! She's so cute! Me: It's a he! And my creature is not cute, he's 'neutral'. Wifey: What's he doing. Me: No, don't poop on the villagers! Bad boy! Wifey: Oh my god! He's about to eat that little girl.
The next Slashdot story will be ready soon, but subscribers can beat the rush and slashdot the links early!
Since I've been spending all my time on the 3rd level of B&W lately, I haven't gotten the chance to do much creature training. But just watching how the villagers act on their own, and develop their own 'community' is quite interesting. What will be really interesting is to see all the new offshoots of this game, much like CounterStrike was to Half-Life. And as a previous poster mentioned, gaming always pushes the envelop of what a PC is capable of, so it should be a joy to watch PC AI evolve over the next couple of years.
Seems to me that there would be a niche for a company to invest heavily in developing a flexible AI framework to be used in multiple games.
:)
several independent developers have tried that - and the game ai page has links to pretty much all game ai sdks attempted thus far.
the problem is that while high-level ai can be pretty general, the low-level ai (pathfinding, collision detection, world physics) is completely tied to the internal representations of the world inside the game engine. it's a similar problem that you have in physics sdks.
also, given the game development characteristics (18-month dev cycles, ai being one of the last steps in development because it requires a working game engine), it's rare for studios to design a game in such a way that a general solution like an ai sdk could be just 'plugged in' that late in the development cycle. unless the workings of the sdk are well understood, it's easier to just build your own (especially if you're not doing anything complex).
on the other hand, if a company with a hit game licenses their ai engine to others, that would be a big step in the right direction - the same way that id and epic licensed their graphics engines after the success of quake and unreal. and sure, many studios will write their own anyway, but those who don't want to rewrite a* for the nth time could instead concentrate on writing high-level behaviors.
My other car is a cons.
IMO, machine learning (ML) is the way to solve this.
And that's what Evans is doing here:That's aka Reinforcement Learning. For decision trees, the feedback is the "evidence" that the tree has to explain, so presumably his system saves some/all of the feedback and intermittently updates the decision tree. If you give consistent feedback, it should converge to a point where your monster can guess what the outcome of an action is, and thereby avoid the smacks. As a side effect, it looks like it "knows" what you want. Similarly for perceptrons / neural networks.
The bit about Moore's Law is certainly apropos. I recently ran a genetic algorithm program that searches for good solutions for the travelling salesman problem, and on a late model x86 desktop system the program was evaluating 1000 candidate solutions a second for a 2000 city problem. Our resource-intensive GUI desktops obscure just how fast our desktop supercomputers really are.
Also, contrary to what someone suggested in another thread, games are not the state of the art for AI. You can easily find tons of papers on this kind of stuff with your favorite search engine, and in some cases download the code for the program described in the paper.
That's not to knock it; games will probably be AI's killer app.
--
Sheesh, evil *and* a jerk. -- Jade
Have you been smacking the shit out of your creature when he does that? My creature ate a villager once, but I beat him stupid (it's a guilty pleasure... I'm good, honest!) and he hasn't done it since.
-grendel drago
Laws do not persuade just because they threaten. --Seneca
CPU's these days are more capable of provididing good AI than they are given credit for. In my opinion, it not a CPU bottleneck that has kept AI at .1% of system resources, rather it's design time. The amount of human time required to develop and debug a proper AI, one that makes a significant use of computational resources, is enormous.
Therefore, it's done half-assed. I don't blame the developers for this, they are operating in a market in which the average selling game loses money, so they are under alot of pressure to cut corners. Truth to be told, a crappy AI is probably not going to cripple sales of your game too much (unless that's the central theme like B&W).
We're going to need to see the computer industry actually become profitable before we see more decent AI like B&W.
Note thet B&W was developed with personal cash from Peter, and therefore wasn't subject to the same tight budget/publishing requirements that most games are.
It's a credit to Lionhead that they got the product out the door without a publisher breathing down their neck.
Lets face it. Cutting edge graphics, and killer AI always show up in the gaming industry before anywhere else.
They continue to impress us. Unfortunately, people think this is more important than gameplay, but I digress. Graphics were the fad the past few years, but perhaps AI will be the new fad for the coming years...
I have a small background in AI, and I must say, I have played Tribes2 only once (had it since it was released), because I'm so extremely impressed with the AI for Black&White (if you haven't played it yet, go grab yourself a copy!!). Its a new type of addiction for me, because I'm not playing to see how far I get, or see how big my avatar will get, its to see what he does next when he's off my leash. Was he watching when I was throwing the rocks, and start throwing villagers? Was he watching me pickup and move villagers to do the same? Its one of the first games I enjoy playing without touching the keyboard... I just watch what he'll do next...
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
--
When all you have is a hammer, everything looks like a skull.
I threw one villager into the ocean. ONE! My creature happened to be standing nearby. Now even though my power is strong because I'm being worshipped by just about everyone, it sucks because I'm becoming an evil god now because my damn creature keeps throwing people into the ocean!!!
is that they become predictable. Once you learn the exploits and how they work, the game is no longer fun. Take Alpha Centauri or Master of Orion 2, easily 2 of the best, if not the best, strategy games around (IMHO of course). However I can play both of them on impossible levels and win almost every time.
And what really bugs me is that to make up for deficiencies in their AI, as the levels increase in difficulty, the computer just cheats more. I was abhorred when I found out first hand how badly the AIs cheated at the higher levels in the 2 aforementioned games.
So what my question is, is this: How can this be fixed?
I have a few ideas. One is that you need one that learns. Before you flame me about this, let's think about this for a second. We're not talking about an AI here that can learn how to write a novel, we're talking about relatively straightforward strategies and mechanical play in these games. I know that 95% of of my strategy for these games is down to an art, it's just an automated system until I get to the few points at which I need to make a new decision, or something new crops up. So if I can do this by a predefined strategy, then why can't the computer do that? Keep in mind too that the computer can simply try variations on it's current strategies, and see what happens. If I beat the computer 9 out of 10 times, and one time with some wierd method the computer CLOBBERS me, then hey, maybe it should keep that method around. Also the computer can play against itself, with many different strategies, seeing how each one works. Keep in mind here folks that the strategies that I'm talking about have a few variables: how fast do I expand? at what point to I build an army? how big do I build my army? When do I stop expanding? When to I attack, and who? These can be values that can be changed and experimented with, and hence the computer could learn.
Secondly, one of the things I loved about Alpha Centauri is that just-about all settings were configurable through text files. This was amazing. You could make things easier or harder, change global settings, pollution rates, everything. You could even make new factions and trade them with your friends. If somehow settings for the AI were configurable this way, then people could learn how to tweak the AI to make it a more formidable opponent, and then share this information with others.
Combining those two ideas, throw it on the internet. If you have 5,000 people that are connected (not necessarily at the same time), you can try out hundreds of thousands of strategies for the AI to see what works well, and then upgrade the AI. Actually I think that is a necessity. The AI needs to be easily upgradable, otherwise it'll just get boring as you learn how it works and you can cream the game.
I'd love to hear some (constructive only please) comments about this, as it's been something I've been thinking about for a while.
Want to check out about the new Master of Orion 3? Awesome stuff happening there. -- Telek
If God gave us curiosity