Slashdot Mirror
State of Computer Game AI
irix writes "Interesting point and counter-point about how far game AI has come along. " Or not, as the case maybe. There are times that I'm really impressed with how well computer games can "reason" things out, like Dungeon Keeper for example, and others', like the original Starcraft where I just shake my head. My biggest complaint still comes in how "not-smart" games are with just moving characters in the most efficent path on the screen - if they could just get my movement right, I'd be so happy, I'd scream.
The problem with the computers in Starcraft were
- The computer can simultaneously give far more orders then a single mouse (so it can coordinate its units in a way humans cant) and can guide all units most of the way to their destinations
- The resource management of the computer AI (or lack thereof) was a joke. You could always win a scenario by digging in and grinding provided that you survived the computers initial onslaught.
- The speed at which the computer builds its initial base is faster than any human player can manage, so the computer always has weight of numbers to crush upstart enemies with
- Multiple enemy computer opponents ALWAYS work together no matter how you set up teams (Grrr...)
Oh, and so far as the crap navigation is concerned, I think that the basic unit AI plots a direct line, and then does 'follow the left' navigation (though with improvements over the WCII AI)A good example in this case would be Go. Go, for those not in the know, is an Eastern strategy game concerned with controlling areas of the board with colored rocks - this is a very simplistic explanation for a game that can be excrutiatingly complex and simple at the same time.
But Go has so many options/states that to try and set up a decision tree, similar to what the previous poster described being used for Chess or Checkers, would be completely impossible, as fairly soon into the game, the computer would be attempting to calculate several trillion possibilities. I remember reading somewhere that if Deep Blue were programmed to play Go using the same heuristic, it would take a couple years to do the moves.
However, there is still interest in making Go programs with an AI. This is an incredibly interesting field, as there are international Go tournaments devoted entirely to AIs, to see which is the best. Yet you take the best Go AI in the world, and test it against an average Go player. The AI will likely win or play very even for the first couple games. Then the human will see the patterns used by the AI (seeing patterns is very very useful in Go), start beating the AI soundly, and eventually be able to beat the AI even with very heavy stone disadvantages (somewhat like giving someone a piece advantage in chess).
One of the more interesting methods I've seen to try and build a general Go AI was to create a graph data structure, then use strongly connected components, moving up several areas of abstraction, to create an idea of "areas of influence", then using a plethora of functions (known as "generals") to analyze the situation and suggest the best move.
Obviously an AI cannot be created that will be able to defeat a human on equal standing, at least I don't see that happening in my lifetime. Computer games will continue to have to rely on creating a situation where the human is at a disadvantage to the AI in everything except for decision-making ability.
Well in Starcraft, there is a "Free-for-all" mode where the computer do exact that, the problem is that the game is too easy on the Free-for-all setting. People do exactly what you described above, grab a couple of bases early in the game, fortify them like crazy (especially if they are humans) and let the computers fight it out. A single person can easily defeat 7 computers if he or she manages to maintain a low profile throughout the game.
I think we need to wait a generation or two before computer game AIs start becoming really clever. Even longer if game developers focus on adding new units instead of the AI (as they have historically done). Each unit you add adds quite a bit of complexity to the AI.
I read the internet for the articles.
The AI in Starcraft cheats, but it doesn't magically get minerals. Now there are some maps where this is true (usually in the "Scenario" directory), but the computer players in a regular match are limited by the same resources you are.
Of course the AI is still weak, but at least it doesn't cheat on resources, although it does have full knowledge of the map which is very annoying.
I read the internet for the articles.
The monsters can dodge, hide behind things, lay down covering fire for each other, use the map's layout to surround enemies, and generally disguise the fact that they're controlled by rules. Also it avoids the fallacy this guy pointed out of having a single man defeat thousands of heavily armed monsters: Unreal's scenario only pits you against 1 or 2 enemies at a time, and a large group really will overwhelm a player.
One of the features that it boasted (and that I would believe I experienced) was an adaptable AI, where as you continue to play, the behavior of the aliens would vary to match your style. For example, if you liked to hide around a corner, then peak into a room to shoot the aliens, then go back, you'd find the aliens later in the game would be more agressive about charging you. If you were more agressive, and charged into a horde, you'd be faced later with more long range attacks and mobile aliens. (This was better implemented in the final 2 games of the series).
Again, there's still some rules base here for the AI to develop from, but it was a refreshing change from Doom/Quake (and of late, Unreal) where the monster behavior was constant through the game, and made the latter parts of the game boring. Half-life, as mentioned above, still suffers from this somewhat, but this is partially aided by the numerous types of terrain/locale that the player experiences before the game is over that it becomes hard to tell if the monsters are behavior the same throughout, or are responding to the changes in the environment.
(BTW, the folks that made Marathon, Bungie, have continued to pump out games, including the popular Myth (and Myth 2 which is reported an excellent AI), and the soon to be delieved Oni, another FPS from leaked info.)
Also, another aspect that doesn't seem to have been addressed here is how well bots for Quake or Half-Life or Unreal have been programmed. I know that I've found the learning potentials of several Quake bots to be outstanding, although it only lasts for that single DM play. Surprisingly, these are mostly written by the 3rd-party players, and not any game companies themselves. Maybe they ought to have a chat and improve the AIs in current games....?
"Pinky, you've left the lens cap of your mind on again." - P&TB
"I can see my house from here!" - ST:
The article which was linked from / that was called a counterpoint misses the point of video game AI. While serious AI research includes making robots respond intelligently, most video game AI is the rock and roll of the AI world. Everything needs to be real-time.
:)
This is where fuzzy logic lends itself best. However, there are some very commendable variants in games that I've seen in my theoretical reverse engineering.
Most action games use modes for the AI. If an entity hits a wall, he goes into Finding New Direction Mode. If the entity is in the direct line with the player, he will advance forth.
Every mode repeats throughout the gametics, with exceptions, which are the rules which make them leave the current mode.
Halflife provided an interesting variant with the marine human AI. When they switched modes, the entity played an audio sound. "Hit the deck!" meant they were in grenade lobbing mode. "Establishing Recon" meant that they were in walk-around mode.
Trespasser introduced something that I wanted to implement for a long time: Instictual probabilities. Instead of always switching to certain modes, have the entity's codebase have a few options to go to, at any given time. The probability of each could be pre-defined, or dyanmic. For example, the probability of a dinosaur's attacking you could go far down if he had just eaten. The hunger factor would be at 5%, where the thirst factor would be at 70%. He would most likely travel in a fuzzy-direct route to the nearest water supply (that he knows about).
In 3D shooters, what always impressed me was what enemies did after you drop down dead. In Jedi Knight, some of them did a dance. In Half Life, the humans reported and walked away. I thought it added a touch of realism when the tense monster started walking around casually. Savage mutilations after death with lots of bellowing are always immersive.
The key to the illusion of making a computer look like it has more cycles is to pre-render as much as possible. This could work with mode probabilities. If a player is exceptionally good at taking out a behemoth tank with mines and finishing it off with an air strike, for example, the ai probability could opt to go into "defense from behemoth tank with mines and air strike" mode. I have not seen this variant on modes in games yet.
Game AI has to be designed to live in the same CPU as a graphical rendering engine. For this reason, I don't see AI taking entirely new directions, such as Genetic AI being introduced as a replacement for Fuzzy Logic. Rather, I see game AI as getting some welcome variants to the modes such as I said above.
The AI in Civilization II is so bad, it's the best argument in favor of open source I've ever seen.
;-)
Not only are the AI's so dumb that they have to cheat in order to keep up with a human player, but even the unit movement intelligence is horrendous. I've had times when I've directed a unit to move from point A to point B which is ten squares down a straight road, and what happens? The unit's first move is to hop OFF the road onto a mountain square, or instead it gets locked in a step-forward-step-backward loop until its movement points are exhausted. Give me a weekend and I could code a pathseeker that could literally run circles around the one in Civ II.
If you're dumb enough to hand control of one of your cities to an AI advisor, you'll later find out that the computer has built lots of useless improvements there which are sucking up your income in maintenance costs.
Another example of a bad AI pathfinder was the one in Myth I. If you told your journeyman to heal an archer standing right next to him at one end of a line of archers, your journeyman would stroll in front of the archers to the OTHER end of the line, getting hit by their arrows en route, then he would turn around and come BACK in front of your archer line again, and only then would he heal the original target. Kudos to Bungie for fixing this in Myth II.
I'm glad to see discussion about bad AI's here; it gives me a chance to vent about games whose AI's have bugged me for years.
I dunno. Having played Age of Empires for a long time, I found that the computer had a range of personalities. Sometimes it sucked for no reason, other times it just wanted to kick your ass.
Having not tried Civ yet, I am not up on some of the latest technologies. But I do look forward to AOE II (years behind schedule). The overall look/feel/gameplay from AOE I was awsome.
PS: 'Daleks' had good AI and that was in the 80's.
Four-digit slashdot ID. Recognize.
And the current state of game AI is why they should all have an API that I can program my own AI to because I can do it better (or at least what I want).
If you've played Civ2 perhaps you can sympathise with the brain dead behaviour of "Automate settler" which irrigates evrything including the forests you were counting on for shield production.
AI API's would also make way for AI contests. I'd love to see a few more of those.
Gripe #2 on current state of game AI: cheating! Game programmers know that at some point the human learns and the computer has stayed the same so to up the difficulty the computer has to cheat. Civ again: building units becomes cheaper for the AI than the human, and the subjects ruled become more agreeable and easier to please requiring less expenditures freeing up effort for smashing the human.
As said in the counter-point, rule based AI is a dead end. With the exception of if the computer can generate new rules and learn. Learning must be the next step for game AI and I wish (as per gripe #1) that I could write some for some of the games I like.
Start Running Better Polls
> The computer can simultaneously give far more orders then a single mouse
This is PRECISELY why I hate, despise, revile almost every single real-time "strategy" game on the market, and for that matter, the whole genre. I can think reasonably fast, but I can't translate that into precise mouse clicking over a narrow little window to micro-manage suicidally stupid units who don't understand their general orders, just the one I immediately give them. I want a unit (meaning a GROUP, that reinforces itself) to defend an area, or scout, general orders, not "shoot at this bunch, now move here, and oh wait something across the map, just don't do a damn thing else while i give orders to that bunch, okay, now shoot here and move there".
One game I particularly hated was Age of Empires. My border guards constantly just LET THE ENEMY THROUGH, and although the game mentioned a peaceful way to win, I couldn't imagine it, since diplomacy consisted of "send an army to kill his peasants". Carrying on the stupid juggling act, I found that farms degrade and disappear unless you manually "repair them" (Aunt Mae, quick, call the repairman, the field's blowing away!). Then to add insult to injury, there's not even a PAUSE function, not even one that disables the interface while it's paused. No bathroom breaks, no wrist relaxers. Ridiculous. Worst RTS ever.
Populous 3 is an RTS I actually like. It's still a juggling act, but it feels like part of the puzzle that every level is. You have the one shaman unit, and a mindless mob that you can direct to cause havoc in general areas. The delayed order function was great for creating diversions once you had your plan layed out. It doesn't even have the pretense of having an AI, but it does model a rampaging mob very well.
I've finally had it: until slashdot gets article moderation, I am not coming back.
Poor pathing for large ground units, especially when moving with groups of smaller units. Instead of waiting for the smaller units to move (which would make sense, since the small units accelerate quickly and move out of the way quickly), the large units will slowly come to a halt and then slowly accelerate in a different direction. By that time the small units have moved out of the way, so again we slow to a halt, change course, and accelerate. Part of the problem is the accel/decel times for large units (which shouldn't be changed), but things would work a lot better if they would hesitate slightly longer to see if their way will be cleared.
Your right to not believe: Americans United for Separation of Church and
I probably sound like an idiot bringing up neural nets here, just because of the hype that is associated with them, but I am wondering if someone out there with a good background on neural nets could answer some questions I have.
I know that the basic neural net works with three layers of neurons: an Input layer, with signals fed into it, a middle layer with a bunch of connections, and an output layer. To train it, you put input signals on one side, and "correct" output on the other, and let the middle layer weight the connections appropriately to "learn" the pattern it is being taught.
What I am wondering is: Are there other arrangements/learning methods for neural nets other than that one? Could a neural net be taught to play a game by "noticing" somehow which things it tries work and which don't? Instead of a bunch of one-shot examples, could it operate in a continuous manner, with signals constantly being fed in and out, and connections constantly changing? I suppose the basic way humans attach "right" or "wrong" to events is by signals of pleasure or pain, with the network always trying to get more pleasure signals and less pain. I see I've just gone way off on a tangent here. I'll post anyway because I would really like an explanation of how much people now know about neural nets from someone studying such things.
Anyone?
Vidi, Vici, Veni
HL was the first game to scare me with how sneaky the computer could get. After playing it over and over you kinda see how the AI works and patterns begin to form, but for video games it's the best I've encountered so far.
I'm interested in the reasons that this article, and similar ones, keeping turning up in the press.
Intel keep hyping AI as the "next big thing" because more and more of the hard stuff is being taken off the processor by custom hardware - 3D cards, audio streaming and compression, etc. They want to sell their kick-butt processors so they hype the expensive stuff - currently that's Physical Simulation and "Advanced AIs", even if nobody has done physics well (it's a *very* hard problem and all the demos you'll see are cheap hacks and "special cases") and "Advanced AIs" are pure vapourware.
Having been in the business for a fair few years, I maintain that nothing significant has been invented in gaming AI for ages. Sure, there have been learning systems but they have been reserved for nieche "simulators" and "virtual pets". Mainstream games continue to plod along with rule-based AIs as always.
The only thing that has changed is that we can calculate more and more complex metrics for our rule based AIs - instead of proximity, we can do line-of-sight, instead of closest enemy we can now do spatial searches for the mean positions of groups of nasties.
Why will it always be thus? Because debugging a neural network is impossible (you just have to re-train it with a different working set) and having predictable AIs is key to shipping a game within your launch window. Having an out of control AI where nobody can pinpoint the bugs will get your project canned.
Certainly Dungeon Keeper 2 and Theme Park 2 are simple AIs - the only difference is that we can now run them on huge crowds, use flocking algorithms and have more interacting states to provide emergant behaviours. It's still all rule based though.
- Robin Green, Bullfrog Productions.
The ability of an AI to play a game well depends on the complexity of the game. The complexity of a game depends on how many possible moves there are at each turn, and how many possible game states there can be. For example:
;-)
Tic-tac-toe: very easy -- the machine can examine the whole game-tree on each move, and *always* make the best possible move (which will result in a tie if the human also makes the best possible move).
Checkers: more complex, but a deep search can be conducted, and a move database can be used to help matters also. There are some *excellent* (practically unbeatable) checkers programs in existence. And there are incredibly good human players also.
Chess: quite a bit more complex than checkers. The number of possible states for a Chess game is hopelessly huge. To create a grandmaster-comparable Chess engine, you employ tactics like:
o hardware acceleration of time-critical search code
o move database for opening and end-games (tricky part is the middle game)
o heuristics developed with the assistance of Chess grandmasters
o a big-ass computer (lots-o-CPUs and memory bandwidth)
o a very nice search engine of course
It's important to note that adding more computing power doesn't help matters as much as you may think. For example, suppose you increase the computing power by a factor of 10. In a game where the number of possible moves is 10, this would enable you to see *one* (1) move further into the future. If you wanted to see two moves further into the future you'd need *100* times the computing power. This is over-simplifying things a bit, but you see my point.
Now consider a computer game like a flight simulator or a real-time sim like StarCraft. The complexity of games like this is so massivley f'ing huge that you can't cope with the problem by using a simple min/max search -- you *must* rely *heavily* on heuristics (e.g. if...then...) to make an AI that will perform better than a monkey. A lot of AIs are given artificial assistance (e.g. they "cheat") so that they won't be easily defeated by a competent human player.