Polymorphic Artificial Intelligence

[child of Thor]

This is the best link i've found in reference to what i was mentioning earlier, its a chat transcript. here

Its from 2001, which would be about the correct time, but i'm not sure if this was exactly the experiment i was thinking of - it does sound like it though.

found another link here .

I guess it really is a robitics experiment, but the software running them must be pretty interesting form an AI point of view

[LDiCesare]

This experiment is a breed of neural networks and evolutionary algorithms. The neural networks let each robot (ai) learn, with the pitfalls I mentionned (it requires filtered input in order to behave properly and can learn by heart if not dimensionned correctly). Then the evolutionary algorithm weeds out the weakest ai's and lets the others learn and refine. I'm not sure how they mutate, though.
The best thing such a scheme could provide for a game is probably a set of different, flawed ai's, each with different flaws and strengths, like UR has been talking about in that 'Castles' game.

I disagree that modding is changing the rules. To me, rules are what's written in the code, and thus the ai which is written in the code must be able to handle all of that. Then if you start modding more than just units (think the SLICs in CtP2), you have to be able to mod the ai too, so opening the rules for modding means you have to open the ai for modding too. If the learning algorithm takes a long time (and it usually does), then you can't use learning algorithms to manage the modded game unless you spend hours teaching the ai how to play the game.

I think the ai should compare various possibilites, and use a somewhat random algorithm instead of systematically picking the best-looking choice, but don't think you can evolve a complex game with current technology.

[Blake]

Usually in games, there are a few strategies that work really well. If you play Warcraft 3, you know of the Archmage and Mountainking hero combination - it's simply the best. If you played C&C Generals you know of the scorpion rush and mass chinese drivel + gatling tank strategies. Once discovererd, inventing new strategies and active adaption becomes distinctly unimportant, instead implementing the cookie-cutter strategies as good as possible becomes the thing to focus on, in other words, practise. I don't know how you make an AI practise. But the point is, these strategies are VERY WELL DEFINED. In SMAC you tech to Ind.Auto, or you might tech to impact rovers, random deviation is *NOT* going to improve your game, sticking to the plan is the best thing you can do.

The time (and only time) for real adapation is *CHOOSING THE STRAETGY*, you can generally choose a teching strategy, an expansion strategy, or a conquest strategy - note that in most games expansion > teching > conquest > expansion (assuming a teching player builds defense). As it turns out, theres no real need for intelligence in choosing the strategy either, choosing the best strategy is quite mechanical, even if it involves a mixed strategy (like rushing 50% of the time, expanding 40% of the time, teching 10% of the time). There is remarkably little need for intelligence in strategy games.

How do you apply this to AI?
The very best thing you can do is allow the experts to directely train the AI, this is much more effective than learning from experience, because the experts will learn and define the best strategies far quicker than the AI can - if it ever can at all. So making the AI very scriptable is a good thing indeed.

Once the AI can implement a number of strategies, you take a game theory approach to deciding which one to use, it should stick with that strategy unless it *really* needs to change - it is important that it can change strategies otherwise it becomes 100% predictable. Like if by chance the enemy has done the perfect counter to the chosen strategy, adaption is nessecary.

There is some scope for adaption, but it is mostly still mechnical, if they get air units, add enough anti air units to your forces - that sort of stuff. Theres still no need for the AI to learn what to do, an expert can tell it the proper counter just fine.

The major failing of AI's for nearly all RTS games is they use a Generic Strategy, like build 6 tanks, attack. Build some defense, tech after a while, expand at some point, keep sending attacks. The Generic Strategy cannot be improved, the AI needs to use entirely different strategies, and stick to the chosen strategy. It needs to pull of the meanest tank rush, OR it needs to tech hardcore with static defenses, OR it needs to expand like a whore. It needs to mix these strategies by choosing which one to use, not by trying to implement all of them at the same time.

I'm not saying that polymorphic AI's don't have some place in strategy games, just that in the vast majority of strategy games most players get along just fine with simple imitation, and to make the AI decent, the same approach should be taken. I feel that Game Theory is far underused in making Game AI's, kinda reverse-iorny seeing superficially game theory has little to do with computer games.

I'm not saying that an AI will never be invented that can beat humans without being trained by humans, one day that AI will be invented, it will have the properties of imagination and creativity, it may well have rights as a sentience. But the day before that AI is invented, the best approach will still be using human experts to train the AI (and forcing a sentient AI to just play one computer game might be considered immoral)

[LDiCesare]

There is remarkably little need for intelligence in strategy games.

Errr... Disagree.

expansion > teching > conquest > expansion

There are variants. Most games require an initial expand phase, but it's mostly because the ai has been trained that way. I once modded Galciv to make initial expansion impossible. You had to build constructors to move them to a sector with a star in order to be able to build a colony there. By changing the techs, I offered various choices: You could either expand at the cost of tech and production, or learn tech, or boost your production and ships (turtle). The problem is: The ai couldn't do it, as it didn't know it could use a constructor to let it build a colony. It learnt techs based on wrong suppositions (that it could expand) and generally behaved very badly.
However, the ai does behave in various ways. For instance, in Galciv, it can try to out-culture you or to ally itself with another opponent in order to beat you (or bribe them). There are many strategies that work in galciv. You can use allies, trade with an opponent in order to make it less profitable for them to fight you, etc.
Although the initial moves are, as you implied, pretty much always the same.
But then in civ/civ2, if the ai would have been taught "You're on an island far from everything with 4 whales nearby, go for One City Challenge", it could have been pretty annoying to beat them on a huge map.
A game where there is a single, nest strategy, is a poorly balanced game. It's not that strategy games don't require intelligence, it's that some don't because they are badly coded/balanced.

Anyway, I agree with most of what you say. It's far easier to train the ai by giving it goals (e.g. build strong units - maintain disorder as low as possible) than by letting it learn through trial and error.
I also agree that mimicking (if you see your opponent is using lots of units of type X, then it's probably a good idea to use the same kind of units) and adapting(build a kind of unit which is strong at countering X's) are important, but they belong to a more tactical level.

[child of Thor]

In CTP2, the modders are constantly being constrained by the features they can impliment and wether or not the AI can do it too(particularly when using SLIC).
It would be possible to do many things, but all to the advantage of the player - so its been tricky for the modding guys to keep their dreams in check
Some people have been looking at the source code to see what's possible, but its still very early days and its a huge undertaking for a volunteer project.

[LDiCesare]

But at least, CtP2 has SLIC. Modded ai can compete far better than the out-of-the-box ai. That's probably because the game was rushed out.
AI should provide some modding ability to the players. The problem is goal-driven, choice of strategies, etc. have to be coded at some point, so unless the whole game logic is written in a scripting language (why not), there will always be shortcomings.

[child of Thor]

scripted AI, goal lists etc are the way its gone, but i remember from ages ago when programers like Chris Crawford and David Brabbam would talk about creating adaptive or learning AI stratagies. As this was in the 80's and early 90's i'm sure it was at a fairly simplistic level.
Still it seems that as pc power/storage capability went up, these idea's were left alone in games and the selective list type systems we now use took its place.

Which is kinda a shame as people could do some pretty amazing things in 32kb back then

I kind of dream that one day, someone might re-adopt this kind of 'efficient'(for want of a better word) thinking and come up with some really clever code.
I think its why i've bought games like 'Creatures' and am kinda interested in the Sims......the games might not be great(?) but the AI is quite interesting from my laymans perspective

[LDiCesare]

The ai in Sims or creatures is, unfortunately, quite simple. One has a few basic sensors, and each input must be at a good level, otherwise the creature/sim feels bad. It will learn how to avoid bad feelings. There are very few problems however that these ai's must overcome. In particular, unless the player plays that role, there is no intelligent coordinated action against them. If you leave civ's ai alone, it will do a quite good job of building a civilisation too.
The interesting thing with creatures etc. is that you can by using a few simple rules create a pretty complex simulation. However, evolving a strategy that ways is not something I think possible.
A sim-ai could be:
Goal 1: Do not to starve.
When can that happen? One condition only, if you don't have eaten for a long time.
How to avoid that? Eat.
How to eat? Buy food and cook it.
How to cook? Learn it.
How to buy food? Get money.
How to get money? Get a work.
It's all simple and linear.
A civ-ai has a goal like:
Don't lose control of city X.
When can that happen? Enemy takes it militarily OR enemy bribes it OR enemy asks for it in a treaty OR city revolts due to culture/unhappiness.
That's already a lot of possibilities to account for for something which is really very basic in the civ game.
How to avoid all that? Avoid losing it militarily... Well, defend it with garrison troops is a possibility. Being at peace is another one. Getting rid of all enemies is yet another one. Even the simple garrison thing is harder than it looks because it depends on the opponent, which forces are unknown unless you can spy upon them.
In order to find out simple rules that would lead to simple ai core which could learn how to accomplish individual actions (cook, get food), you'd have to first find out what these rules are for civ, and that's not simple.

[Kuciwalker]

Originally posted by LDiCesare

There is remarkably little need for intelligence in strategy games.

Errr... Disagree.

Actually, computer and video games really aren't particularly important applications of AI. AI covers a lot of things that you wouldn't necessarily think of as "artificial intelligence". These problems can often be a LOT more complicated than a game.

[Kuciwalker]

Originally posted by LDiCesare
The ai in Sims or creatures is, unfortunately, quite simple. One has a few basic sensors, and each input must be at a good level, otherwise the creature/sim feels bad. It will learn how to avoid bad feelings. There are very few problems however that these ai's must overcome. In particular, unless the player plays that role, there is no intelligent coordinated action against them. If you leave civ's ai alone, it will do a quite good job of building a civilisation too.
The interesting thing with creatures etc. is that you can by using a few simple rules create a pretty complex simulation. However, evolving a strategy that ways is not something I think possible.
A sim-ai could be:
Goal 1: Do not to starve.
When can that happen? One condition only, if you don't have eaten for a long time.
How to avoid that? Eat.
How to eat? Buy food and cook it.
How to cook? Learn it.
How to buy food? Get money.
How to get money? Get a work.
It's all simple and linear.

Actually, what you're calling the "AI" in the Sims is only the tip of the iceberg. That's simply deciding, in general, what sort of thing to do. It's not too difficult to do. It's after that that it becomes difficult.

In fact, you know what is probably the most complicated part of the Sims AI, the part that uses the most advanced techniques and really applies AI theory?

The pathing algorithm.

Finding a route between two points is the classic AI problem. In fact, it turns out that problems that can be modeled as finding the shortest path between two points is probably the largest category of problems in AI. I can only think of two categories that can't really be represented as that: constraint satisfaction problems and logical calculus. And "deciding what to do next" in the general terms of "eat", "sleep", etc. are definately not any of those.

[Panzeh]

In my experience playing games, there's a sort of slider.

On one side is the heavily scripted AI, the kind found in many FPS games. They can respond to you in no way other than what the script says. This AI is good at what it does, but when you do anything that the developers didn't see, it falls apart.

On the other is the non-scripted 'dynamic' AI, the kind found mostly in wargames. These AIs respond to you, but often in erratic and silly ways. This AI can do everything, but it's very random and has a difficulty forming coherent strategy, making it far weaker than a human.

Most games strike a balance somewhere, with FPSs, a few RTSs, and a couple special-case wargames forming the 'scripted' side, and wargames and a few RTSs forming the 'dynamic' side.

Two wargames are special cases. War in the Pacific is a monster Gary Grigsby wargame that takes a long time to play. The AI has a set plan, and when it stops executing that plan it falls apart quickly. There's also Axis and Allies, a '98 computer port of the board game. The AI had some decent opening moves, but once it got past that it really had no ability do anything useful.

There's an FPS with somewhat 'dynamic' AI, Operation Flashpoint. Its units can work without exact scripting to the 'T'. The AI is excellent fighting at long distances, but loses its effectiveness in close quarters(unlike most FPSs, where it's exactly the opposite).

[LDiCesare]

Kuciwalker, pathfinding is AI, but the A* algorithm exists for quite a long while. Even if it's complex, it's well-known and just about every programmer learns it at some stage, so I don't think it's worth calling it difficult or complicated. The only problem with this algorithm is that it is slow, but it's usually pretty easy to correct that by adding intermediary points along a path. Decision-making is what makes a strategy game strategic, and constraint satisfaction is in my opinion the most common problem (sales traveller problem).
Note that A* is the best algorithm but games like chess have been using alpha beta searches for quite a long time and got good results with that too.
Anyway in terms of civ, pathfinding is not that much of a problem. It can if you add constraints like avoiding enemies, but in the Sims, you can just stop when you would collide with someone else and decide of a strategy to go around (f.e. decide to always go around moving obstacles by the right).
Optimisation is definitely a much harder ai problem htan path finding.

[Natalinasmpf]

random deviation is *NOT* going to improve your game, sticking to the plan is the best thing you can do.

Oh it does....

There are situations where a beeline to Ind Auto does not work. A situation where you are severely crippled and have to fight it out at all times; or a situation where you are hard pressed, or where its impossible to get Ind Auto within the next fifty years but you have say, the Caretakers on your back.

Situations on deciding whether planned or free market is best for sth goal.....

Then what happens after getting Industrial Automation? It gets confused again.