Slashdot Mirror
Emergent AI In an Indie RTS Game
x4000 writes "My recent RTS game uses a new style of AI that hybridizes rules-based AI with emergent AI logic. As a disclaimer, I'm really not an AI programmer at all — my background is in databases, financial modeling, etc. But it just so happens that database experience, which often involved distilling data points from multiple sources and then combining them into suggested decisions for executives, also makes a great foundation for certain styles of AI. The approach I came up with leans heavily on my database background, and what concepts I am familiar with from reading a bit about AI theory (emergent behavior, fuzzy logic, etc). The results are startlingly good. Total development time on the AI was less than 3 months, and its use of tactics is some of the best in the RTS genre. I'm very open to talking about anything and everything to do with the design I used, as I think it's a viable new approach to AI to explore in games, and I'd like to see other developers potentially carry it even further."
could you catalog user actions and use them as possible inputs for your AI?
like this: http://slashdot.org/comments.pl?sid=1165583&cid=27243769
it would seem this might make for the most challenging AI - one that
learns and mimics good human players. I have yet to see any games
that can do this well
Sadly not!
I was ~12 and I had just understood looking ahead - so in my naivety I made something that was capable of looking ahead for pretty much the entire game.
it annihilated me.
Still it amused my family who mocked my pain as much as they could. Still, I was heartened to see that none of them could defeat Frankenconnect4 either.
In short, it segregates the controller AI from the unit AI.
I can remember when playing SupCom against easy opponents, if I didn't build any defenses, the opponent would stop sending units into my base for a while, instead moving them around in circles somewhere outside it. Even an easy/stupid AI has to make decisions that a stupid person would make. Mainly - CHARGE!
But at the same time, the best AIs were omniscient. They'd target your first fusion reactor with bombers as soon as you build it... It became so predictable that I'd build a shield, turn it off, build a fusion, then turn the shield back on.
But in SupCom there were all the modded AIs which chose more interesting tactics, and you could enable cheating for any AI to give them a resource and difficulty boost.
I think to be realistic, AI has to be segregated even more. You need an Advisor, which decides the direction things should be going. Do we need more resources? Do we have an urgent matter to deal with, like artillery pelting the base? The Advisor should just decide what to tackle, and then pass that on to the other AI subsystems. Like a player, the AI subsystems should take time to do stuff. An AI can't instantly decide what's an entrance to his base. He has to study where the units usually come from, and locate possible landing zones for air transports, etc.
To ramp up the intelligence, you let it assign more issues to its subordinates more rapidly, and you let it learn across missions. Pretty soon the AI can tackle any frequently played map.
The human brain is simply a pattern matching engine designed to find the most appropriate response in order to maximize survival.
The average adult brain contains a huge database of experiences stored in a format that it is easily retrievable when signals arrive from the external triggers. When such a signal or signals appear on the brain, the brain does a pattern matching on the database, and produces an output. The output is a response or responses that are transmitted to the body so as that the entity reacts positively or negatively to the current event.
The same principle can easily be replicated on a computer, and it is simply a matter of data organization for efficient retrieval.
Thinking about it a bit more, I wonder how this compares to the AI used in hack n slash games where you get swarms of enemy's all over the place. I'm thinking of the Diablo I & II (and future III) series from Blizzard. I suspect these games use a similar idea in their monster AI.
These games use fairly simple monster AI that usually follows simple rules, so it may be much simpler than what this guy claims. However I think it must be applied per creature. Some types of monster will run and cower when you kill their nearby friends, others run off to heal but some of those Hell Bovines will chase certain targets in multiplayer games. I never got the feeling there was an overseeing god directing all the units with these games.
...then it is worthwhile remembering that centralisation was its' most fatal
weakness.
In the original story, (the end of the T2 novel, or thereabouts) Connor won by
blowing up the central core under Cheyenne Mountain. SkyNET's primary
exploitable weakness was that it was never willing to truly reproduce, for
fear of losing control; that is, to create another AI with fully the same
level of functional intelligence that it had. (I believe personally that a
compelling case could be made for the assertion that SkyNET, as depicted, was
not truly strong AI, but I digress)
The point is that as far as creating genuinely effective weak artificial
intelligence is concerned, the decentralised/segregationist approach is the
correct one.
Given my own experience with FPS mapping, I also concur with the author of TFA
when he says that making AI choose the "best" choice 100% of the time, is
not the best tactical approach, over time. My own experience gradually
suggested that around 75% appears to be the magic number, as far as creating a
truly emergent, unpredictable opponent that humans will be unable to overcome.
Granted, said 75% is also only effective where there are a large number of
divergent solutions to a given problem, each with close to an identical level
of effectiveness, but with a few subtle points plus or minus, each way.
Even with a fuzzy, emergent system, the best trees still have a maximum number of
branches. The real trick however is not to hand code said trees at all,
because then you simply end up with static, rote heuristics. Rather, as the
author possibly implied, it is far better to attempt to code
observation/deduction capabilities, guided by the above percentage, and let
the system do the rest on its' own.
I still remain extremely skeptical, however, that humanity will ever see the
emergence of truly strong (human level or greater) AI. It is worth remembering that
strong AI is a fundamentally and profoundly atheistic concept; the possibility of it more or less presumes a definitely atheistic universe as a prerequisite. For those of us who believe in the existence of God, (or at least the soul) the idea (at least
in terms of non-biologically generated, acorporeal AI, a la SkyNET; AI derived
biomechanically is a seperate concept) therefore has some fairly
serious problems.
From my experience I'd award the best AI to Civilization.
Love many, trust a few, do harm to none.
You're giving the game far too much credit. Master of Orion was a fantastic game (MOO2 even more so), but the AI was not its strong point.
The main difficulty in the game came from the AI's massive advantage (read: cheating) in production. Or from map position (if you got unlucky and started somewhere without many good planets nearby, you're in trouble).
MOO2 also suffered from poor AI, as well as several crash bugs. It also included deeper gameplay in many areas, and IMHO most significantly, multiplayer capability.
#include <sig.h>
I agree that this is very interesting, but the sheer asymmetry of the setup (players begin with four ships versus 20,000+ for the AI) means that we don't really have a chance to compare the AI to human intelligence. The concepts seem sound, but they need to be implemented in combination with an economic model which will allow symmetric human v. AI showdowns. Something like this would be very cool, for example, in the next iteration of the Civilization series.
To his credit, the author acknowledges these limitations and admits that the concepts need to be taken farther. With this I agree, and I hope they do!
... the RTS-like game of Neuro Evolving Robotic Operatives. Instead of controlling your units directly, you had bots that you'd develop with a genetic alogrithm in a training mode. (And you'd train them by killing off "family-lines" of the bots that sucked, and using bots with interesting behavior as seeds for sucessive generations.) Then once trained, you'd give them a fairly general waypoint and they'd do the rest on their own. Which was a very cool concept, but in practice it would hang up the CPU/RAM once some really interesting emergent behavior stated to develop. (By the time you "taught" your bots to do something "useful", the game would freeze. And the data files that recorded the behavior would be HUGE!)
Only other thing to be said about NERO is that it's a shame that jack-shit hasn't been done with it since 2007. I think it would have some interesting potential if somebody on the development side could actually figure out how to make things more efficient and not have it freeze up.
There's also supposed to be some OpenNERO derivative, but it appears to be stillborn. :( Looks like it would be an interesting project though.
It's a great approach. It's one of those quasi-obvious AI schemes which people have been kicking around for years but typically haven't wanted to expend the CPU cycles on in major projects. I remember an article around 1997 wherein they asked game development studios to explain how games were going to change in the next couple of decades, and one of the chief topics that kept coming up was more natural AI (less rigidly rule-based) which could learn by observing outcomes. Modelling AI on military organization is fairly clever for the same reason that military organization (at least in battle) is clever - the individual soldier needs little autonomy or smarts, just so long as everybody further up the chain from them is at least incrementally smarter, if less capable in direct conflict.
The most notable use of a system like this in recent years has to be the Director in Left 4 Dead, which is an overarching control scheme which issues orders to the game world and the units in it. These units are free to do what they do best - navigate around the map and eat players without having to worry about strategy. The Director is free to select the paths by which the units will arrive without having to waste significant time on fine pathfinding, as the units themselves will do the bulk of the work.
I look forward to more games with heirarchical AI. I've written some basic tests of this exact sort before (basic "burds"-looking stuff) and the resulting behavior is extremely intuitive and ordered-looking.
The land shall stone them with the bread of his son.
Evolutionary algorithms tied to your NNs (they're competing, remember?) seem like a good way to eliminate that problem. You can also use a separate NN for each function, such as path-finding, targeting, and cover, and use recombination to pull out the best NN for each from the population.
The case you mention - you're stuck at a local maxima and can't reach the global one - can be overcome via the introduction of NNs which have evolved in a different environment: take an AI from one population and have it compete in another. If you've designed your game correctly, there will be no perfect strategy, and an AI that builds artillery will quickly wipe out the one that uses defensive structures (you're worried about a tied game - that provides less "fitness" than a win).
Also remember that you can trade AIs between players, so it can keep on learning and improving indefinitely.
Obligatory Soundbite Catchphrase
The second article is much better, thank you.
You're solution is indeed very fine for what you're doing, and uses a fraction of the computational resources that a NN solution would. If you're looking for a solution that is more adaptable (the NNs I proposed would learn what strategy you use, and find better and better ways of countering it, forcing you to constantly shift your strategy) and has broader applications in the AI world, NNs are clearly superior.
I should probably have been a bit less technical in my original post, let me try to clarify here:
Neural networks are something that works like a biological organism, it's a type of fuzzy logic. It's similar to your database system, but a bit more abstract, making it easy to change randomly (evolve). These accept inputs based on local surroundings just like your database. They work as a sort of black box, (similar to human consciousness, they are poorly understood) but will generally find a best output for the given inputs. Wikipedia has a good article on artificial neural networks that's worth skimming if you're interested.
The evolutionary algorithm I would apply simply changes a few of the weights at random. The good changes are kept, while the bad ones get discarded. What's good and bad is determined by the competition of neural networks against each other. Eventually (a few hundred games) later, you'll get an AI that's learned to play in exactly the same way* humans do, making it almost indistinguishable from a human player.
*OK, I lied. The human brain uses a different learning rule (Hebbian and Antihebbian) which is less efficient computationally than a evolutionary algorithm. Consult Wikipedia or Pubmed if you really care about the semantic differences.
Obligatory Soundbite Catchphrase