Slashdot Mirror
The State of Game AI
Gamasutra has a summary written by Dan Kline of Crystal Dynamics for this year's Artificial Intelligence and Interactive Digital Entertainment (AIIDE) Conference held at Stanford University. They discussed why AI capabilities have not scaled with CPU speed, balancing MMO economies and game mechanics, procedural dialogue, and many other topics. Kline also wrote in more detail about the conference at his blog.
"... Rabin put forth his own challenge for the future: Despite all this, why is AI still allowed to suck? Because, in his view, sharp AI is just not required for many games, and game designers frequently don't get what AI can do. That was his challenge for this AIIDE — to show others the potential, and necessity, of game AI, to find the problems that designers are trying to tackle, and solve them."
Education can help; A lot of college CS programs don't force the breadth that an "AI game developer" would need. In my undergrad degree, graphics, AI, game programming, and distributed systems were "applications" classes, and you only needed one or two. Usually the game programmers would have to take graphics, because even if your the sound or networking guy, they'd expect you to know graphics like they did. If more game programmers had taken systems classes (such as operating systems), I don't think they would have had as rough a road with multicore either.
However, even given the current narrow classes, you can at least try to bleed through enough of the wider topics into game-oriented classes to get people footed. In the game programming course I was a teaching assistant for, I gave a couple lectures on AI (I was an AI/Robotics grad student). Then we gave them an AI-only assignment. It was a multiplayer tank game where we pitted their AIs against some test opponents, and then against one another in a tournament. It didn't allow much cheating in the AIs (only global visibility, where a player can see every unit at all times, which is nearly universal in game AIs). The assignment really seemed to be a hit, and hopefully for those students that went on to the games industry, it gave them the basis to branch out and learn other deeper AI techniques.
It would also help if the AI community wouldn't look down on things such as games as "lowly applications". In some sense I think game programmers would be best off talking to robotics people or even web machine learning people (spam filtering, web search ranking, etc). Those people are already doing applied AI, and particularly for robotics folks, working on many of the same problems that good game AIs would face.
I think that you are wrong about the AI community looking down on games as "lowly applications."
Well, at conferences such as AAAI, even robotics isn't treated as more than a "mere application". At least that's the treatment I felt going there and presenting work. Its ok I guess, because AI theory doesn't directly relate to where most work in applied AI happens (just like in applying machine learning -- most of the work is in the features, not the algorithms). However, I feel there is a real gap between what conferences such as AAAI are willing to embrace, and what happens at game development conferences or robotics conferences. Being someone who did RoboCup for many years, I really do know what it is like to span that gap -- some of the most important breakthroughs we made were not publishable in either type of conference. I really feel that the field lacks something like the AI equivalent of JGT (Journal of Graphics Tools) or Graphics Gems. If I were a more professorial type I might try to start something like that, but instead I just wait and hope someone else will, and then I could contribute to it.
I think that many posters here are confusing Artificial Intelligence with Machine Learning. The later is a subset of the former, but is often difficult to apply to games. Accepting adaptation is typically equivalent to abandoning Game Theory.
Other than the fact that applying machine learning successfully is difficult in general, I don't know if I really agree with that statement. Game theory is a subset of AI just like machine learning. Game theory is very important for abstract games such as chess, but I'd argue that most "physical simulation" games need things more like potential fields, advanced motion planning, high quality hand coded policies, and geometric stuff of that ilk. Old stuff like rule base AIs really has a place in games too -- the work done on scaling up expert systems is really like "software engineering for AI", and sadly a lot of that work didn't get published either.
A simple form of learning we used in our robotics work was weighted experts given a set of hand-coded policies (~= "a set of AI strategies" for the non AI people out there). We used that to learn during 30-minute autonomous robotics games against robotic opponents, and it worked, even during a relatively short game. All you need is a way to define successful subgoals (Ex: scoring in a team game, kills in an FPS, or areas won in an RTS) and you can get convergence to the optimal strategy in a logarithmic number of rounds. In a turn-based game, if those experts each applied game theory, you could have game theory and learning combined in a pretty reasonable way. Yes I know that would not be optimal, since you normally would just pick the strongest AI, but humans rarely play optimally, nor is even fun to always play against the same strong strategy.
Certainly there are entire fields of A.I. that are entirely unrelated, but there are many fields of A.I. whos core development is exclusively related to games.
True. I guess I just haven't really seen the dots connected. Then again, I haven't been to any AI conferences in the last year or two, so maybe that has changed already. I hope so.
Most games do not implement any heavy A.I. techniques because it is too difficult to provide skill gradients: Easy, Normal, Hard, Godlike. These skill gradients are pretty simple to implement as an escalation of "cheating," but not so simple as a tweak to AlphaBeta and pretty much futile with Machine Learning.
Well, here's another place where I think the communities need to work more closely. Coming up with search strategies that are more human-like when measured statistically would be fascinating work. Limiting search depth and random mistakes works in some games, but we could do a lot better. I think some of the commercial chess games already do a pretty good job of various skill
The problem there is that the two factors you mentioned (accuracy and commands-per-minute) are both things that AI can far exceed humans at, especially if you aren't careful to limit it.
You're correct. I've written AI for a number of commercial games. Some of the most challenging AI is for games in which the players are competing with the AI on what are supposed to be equal terms. An AI can home in on a player's forehead with a sniper rifle with little difficulty. It's a simple mathematical equation. How do you simulate the aiming a player has to do?
The solution I came up with was to put the target's aim point on a set of springs attached to the player. By jumping around and changing direction quickly, the player would tend to throw the bot's aim off (imaging the target bouncing around, attached by the springs). But, stand still or move in the same direction for too long, and the bot would home in on the player. And, of course, just like a human player, the AI would get in a lucky shot every once in a while as the target crossed in front of the player.
You have to come up with creative solutions to make the game "feel" fair. That's not the kind of stuff that's typically taught in college courses. Naturally, formal training doesn't hurt, but there are a lot of challenges unique to game development.
Irony: Agile development has too much intertia to be abandoned now.
I've been in love with NeuralNets since first sight. After a few projects i really wanted to try my hand at a game. I came up with an idea for an RTS that was something like this: The majority of your units were ai, FF nets that evolved genetically. So you don't have to micro manage your economy or patrols or anything. You say, i want a factory here and your builders will find the resources needed and build that factory. They will have to learn the optimal way of doing this. The most successful individuals are the blueprints for the next generation. If that building is destroyed your command still stands, you want a freaking factory in that spot.. so they will toil away and continue building it. The battle side was supposed to be similar but i haven't gotten around to it. But the idea is an RTS that frees you up from the micro & details and let's you focus on the strategy aspect. A side effect is your units become unique over time, so even though your untis may be very successful on one map, a different type of terrain really makes life difficult for them for a few generations.
Right now they learn how to gather materials and move it to construction sites. Actually a lot of fun to watch. But it is still a long long way from anything resembling a game.
Back on topic though. An AI that adapts to it's opponent's weaknesses is well within reach of any game developer. The tough part with genetic and nnet AI is lack of control. You can't easily script a sequence and you can't guarentee what the user/customer will experience. I have had degree's of success over "difficulty" by restricting how many ticks of "thought" a net gets per second. But even then, the net will eventually adapt to this slow thinking.
http://soylentnews.org/~tibman
As far as RTS goes, I'd like to see the AI act more human. Not just in how "smart" it plays, but in how quickly it can act.
Remember in Warcraft 2 (I've started playing it again recently, so I'll use it as an example), how you had to send roughly double the number of troops as the enemy to get a fair fight? The AI would have all its ogre-magi cast bloodlust (or all its paladins cast heal) simultaneously, while you'd be struggling to get a single spell out.
And while that was going on, they'd be effortlessly churning out more units. During the time you're looking at your base and getting some more units ready, your units in battle would be getting slaughtered.
So, what I'm really looking for in an AI is human-like delays between commands.