AI changes

[softcoder]

I have updated the AI to be a bit smarter.

1. The AI will harvest before its in critical trouble for consumable resources
2. The AI will recall very active locations where it had battles and scout those areas.

[softcoder]

Tried a test game with Tiger and Elimnator and he AI is MUCH harder now.

Enjoy.

[NoQ]

Emm may i write a little essay? Cause i've been doing some AI scripting for another rts game.

It seems that there are three things that boost the AI's strength significantly.

1. Implement a reasonable build order, based on mutliplayer experience. It is usually easy enough and will remove the few-minutes delay of AIs compared to humans.

2. Teach the AI to group up his units before engaging in combat (or just keep them grouped constantly). This is a bit more tricky, because most of the naive implementations like "constantly move units to the mass center of the army" seem to fail miserably.

(click to show/hide)

The most natural way of doing this i found is to implement a simple cluster analysis. A certain algorithm (even the trivial O(n^2) implementation would be fast enough on ~150 combat units) finds the biggest cluster of units in the list, then all units of all other clusters are ordered to move towards the middle of the biggest cluster. Here is an example from my AI work, written in javascript:

(click to show/hide)

(whoops, why is the code section so small?)

Code: [Select]

// find clusters in the 'list' of objects that have x and y coordinates,
// where 'size' is the maximum diameter of the cluster.
// return a list of clusters, their middle positions, index of the largest
// cluster in the list and number of objects in it.
_global.naiveFindClusters = function(list, size) {
var ret = { clusters: [], xav: [], yav: [], maxIdx: 0, maxCount: 0 };
for (var i = list.length - 1; i >= 0; --i) {
var x = list[i].x, y = list[i].y;
var found = false;
for (var j = 0; j < ret.clusters.length; ++j) {
if (distBetweenTwoPoints(ret.xav[j], ret.yav[j], x, y) < size) {
var n = ret.clusters[j].length;
ret.clusters[j][n] = list[i];
ret.xav[j] = (n * ret.xav[j] + x) / (n + 1);
ret.yav[j] = (n * ret.yav[j] + y) / (n + 1);
if (ret.clusters[j].length > ret.maxCount) {
ret.maxIdx = j;
ret.maxCount = ret.clusters[j].length;
}
found = true;
break;
}
}
if (!found) {
var n = ret.clusters.length;
ret.clusters[n] = [list[i]];
ret.xav[n] = x;
ret.yav[n] = y;
if (1 > ret.maxCount) {
ret.maxIdx = n;
ret.maxCount = 1
}
}
}
return ret;
}
Complete AI code, for another game, of course, is here, you may also see the tactics file if you like, where this is actually being used.

The biggest cluster itself is ordered to either proceed with its attack if it's big enough, wait for other units to join if it's peacefully standing in the middle of nowhere, or retreat to base if it doesn't have enough units (less than a certain threshold) and has engaged in combat recently. If certain units are below a certain health threshold and you want them to go for repair, just filter them out from the list before clusterisation.

With this approach you no longer need to mass up units at base, then send an attack order once every 5 minutes, then watch them die, then get a new army. On the other hand, you send an attack order every 5 seconds or something like that, and this attack order starts with a regroup order. This way newly produced units don't remain at the base until the next attack, but instantly join the combat.

3. Teach the AI to adapt, by countering any human's failure to use combined arms effect. For instance, use catapults if the opponent over-uses metal army, or use anti-air capable stuff when the enemy over-uses flyers. This is most useful in 1x1 matches and least useful in FFA matches.

(click to show/hide)

Since there are quite a lot of units in the game, the AI should categorize them somehow. Probably some AI hints in the faction definition may be used, or probably the AI could use any understanding of units provided by the API.

For instance, suppose the AI is capable of distinguishing between "light" (archers?), "heavy" (behemots?) and "air" (dragons?) units on the enemy side, and between the "anti-light" (guards?), "anti-heavy" (catapults?) and "anti-air" (air ballistas?) units on his side. Then compute their cumulative costs (or, at least, numbers) on the respective sides: their.light, their.heavy, their.air, our.al, our.ah, our.aa. Assume their.total is sum of the three their numbers and our.total is sum of the three our numbers.

Then calculate ratings of the three:
rating.al = their.light / their.total - our.al / our.total;
rating.ah = their.heavy / their.total - our.heavy / our.total;
rating.aa = their.air / their.total - our.aa / our.total;

If rating.al is the largest, the AI should spam anti-light units (build structures where they are produced, etc.). If rating.ah is the largest of three, the AI should spam anti-heavy units. Etc. This is scalable on any amount of unit classes and weapon classes, as long as weapon classes directly counter respective unit classes.

One of the main problems here is that the AI should not be actually able to see player's units until he encounters them; based on the posts above, i believe this game doesn't provide AIs with full visibility or ability to enumerate all units on board inside the script. The alternative would be to queue all seen units for analysys and keep summing up the statistics every time a new unit is seen.

There are a few other gameplay aspects i've been trying to work on, which haven't proven to be effective. For instance, not much can usually be done on AI micromanagement. Even though you can teach them to "rotate units" (move units being focused on behind, and move healthy units to the front), or concentrate fire during combat, this will be nothing compared to what a good human can do. The same applies to army placement and formation movement, and also to more advanced worker management.

[titi]

In general there are already done many tweaks to the AI. The last one which was new with 3.7.1 is a new behaviour while fighting. Ultra and Mega will attack standing units in range first as they are easier to hit. This is ( like many many of the AI decisions) combined with random decisions. Random is important because you will never know exactly what the AI will do.

About your 3 suggestions:
1. This is already done but with a more random way than a strict order and based on the AIs need and unit orders. (just talking about CPU-ULTRA and MEGA here )

2. I already thought about this, but from my experiences playing multiplayer games this is not too important and fixed in some way as the AI cheats with resource multipliers and typically has many units by this.
Grouping units also has the probem that there is not enough place in many maps to group units in many places and this will cause more trouble. This is something Glest typical, so this might be different for other games.

3. yes, but how should the AI know what the humans do?  If it cheats and looks into the internals it would be no fun to fight vs humans and if it does not cheat humans will react much smarter and use this as an advantage!
For example a human will send 5 airplanes to attack the enemy making the AI build anti-air units and so on. But hen he attacks him with ground units and wins....

The most important thing to improve the AI I can imagine at the moment is to make the AI expand much earlier. It should build new Bases near ressources and expand their territory by this. This is something good humans players do a lot and its VERY effective. ( more ressources more place to build and so on... ). But I think its not so easy to do ...

[NoQ]

I'm not asking for anything (: just sharing what i learned. So that whoever would one day like to do some work here could have a look at what has been done.

AI aspects such as "when to expand", "when to attack", "when to build defensive structures", "how much to spend on upgrades and how much on rush" are really difficult, human intuition seems to be unmatched for this, even though some approximation can be made.

this is not too important and fixed in some way as the AI cheats with resource multipliers and typically has many units by this.

Well, with just these three tweaks, it has become possible for me to make a non-cheating AI that is already impossible to beat 1x2 on a fair three-player map (or 1x1 with double power cheat). Even in non-cheating 1x1 it can teach many newcomers a few lessons. And the fact that it's non-cheating is really inspiring. A good AI is the one that prepares newbies for multiplayer action, while a bad AI is the one that will teach them some bad habits, and then they have to re-learn everything from scratch when they just start thinking of themselves as multiplayer-ready. In fact, people may think they play well after fighting a poor AI 1x5 continously for some 10 years, but then dying in 5 minutes in their first multiplayer matches (:

Grouping units also has the probem that there is not enough place in many maps to group units in many places and this will cause more trouble. This is something Glest typical, so this might be different for other games.

I had no problems with that so far. Just increase the cluster radius limit if necessary; it'd be still a huge improvement compared to ungrouped armies.

For example a human will send 5 airplanes to attack the enemy making the AI build anti-air units and so on. But hen he attacks him with ground units and wins....

If our human has learned to do that, then ... mission accomplished, the AI is good enough. This can be worked around by not letting adaptation go too far (anyway make sure we have at least 20% anti-ground stuff). The AI will also anyway see units at the enemy base whenever he himself attacks.

But in fact such behaviour of a human is much less of a problem than it might seem: if the human is using up half of his income to create units that don't ever shoot, then he's either already dead, or our problem is elsewhere. You can't normally do such things in a competitive match.

[MoLAoS]

If you are really, really into doing AI, you could do an AI for 0 AD. They use Javascript iirc for mod APIs. You can even force AI to fight each other and see which AIs do better. Maybe you already know that, but just in case. There is a semi decent group of people working on AI there.

[softcoder]

In case you didn't know, Molas contributes nothing to megaglest and continuously points people away from using our game. He also continuously talks about a game (Majesty) that he rarely shows any actual screenshots of work that he has accomplished let alone actually releasing anything to the public. He is mostly a troll.

</end of reality check>

[MoLAoS]

Quite the contrary. I tell people to play MG if they want multiplayer. I mentioned 0 AD which I don't play and have no association with because he says he writes AI in Javascript which is how their system works. None of the Glest derivatives have any sort of moddable AI, unless you could a few XML attributes.

MG is actually better at multiplayer currently, compared to 0AD, and 0 AD has some lag issues and its gameplay and balance are lacking because they still don't even have a beta. But for AI scripting it is indeed better.

I recommend Spring to people too, although generally not here, if Spring would serve their interests better than other foss projects. There is no need to make everything so personal.

[softcoder]

I've formed my opinions purely from the material you have posted, not trying to be personal as much as honest.

[MoLAoS]

You can say what you like about my other posting, but you can hardly argue that MG is more appropriate for a JS proficient AI scripter than MG.

And as you well know I did release my work to the public as you saw me trying to help John get it to compile on the irc.

I find your honestly claim dubious.

Someone might want to split this thread also, since you've dragged it off topic. I suspect NoQ doesn't want to be dragged into the Glest  codebase fragmentation mine field.

[NoQ]

Please don't quarrel, i don't like it when people start quarreling around me
Also, it's pretty hard to point me away, since i'm not quite inside yet ...

I can decide what i enjoy, don't worry about me (: Glest is enjoyable, so i'm a bit worried about it. Haven't yet tried 0 A.D. yet, but wanted to have a look anyway; and spring games never worked for me on my low-end ATIs (i even accidentally tried to run it on windows lol). The fact that they use JS doesn't make things much easier; their API will most likely be completely different, and also one can't make a good AI without being a pro mp player; that was nice to know though, thanks.

[softcoder]

Back on topic, to control AI behavior you may modify XML, for more specifics see this forum posting:

https://forum.megaglest.org/index.php?topic=8202.msg81414#msg81414

[MoLAoS]

Please don't quarrel, i don't like it when people start quarreling around me
Also, it's pretty hard to point me away, since i'm not quite inside yet ...

I can decide what i enjoy, don't worry about me (: Glest is enjoyable, so i'm a bit worried about it. Haven't yet tried 0 A.D. yet, but wanted to have a look anyway; and spring games never worked for me on my low-end ATIs (i even accidentally tried to run it on windows lol). The fact that they use JS doesn't make things much easier; their API will most likely be completely different, and also one can't make a good AI without being a pro mp player; that was nice to know though, thanks.

Well this is perfectly on topic. You can absolutely make good AI without being a pro player. Almost no AI programmers are pro MP players because it takes so long to become a pro, most people make a career out of it in popular games. Also the standard RTS is so focused on execution whereas AI doesn't care about execution because its not using a GUI, its just activating functions directly. In fact I suspect that most AI programmers would make terrible pro RTS players.

[Omega]

Well this is perfectly on topic. You can absolutely make good AI without being a pro player. Almost no AI programmers are pro MP players because it takes so long to become a pro, most people make a career out of it in popular games. Also the standard RTS is so focused on execution whereas AI doesn't care about execution because its not using a GUI, its just activating functions directly. In fact I suspect that most AI programmers would make terrible pro RTS players.

I don't know, using an interface alone doesn't mean much. For most games, the strategy is most important. Consider Civilization V, where strategy is far more complex than MegaGlest. Most of the best AI ideas come from "pro" players on the forums; the people who have the most experience with playing the game. Myself, I'd love to get into AI in the future, and it seems that a strong understanding of how the AI should act matters as much as how it should be implemented.

[MoLAoS]

Well this is perfectly on topic. You can absolutely make good AI without being a pro player. Almost no AI programmers are pro MP players because it takes so long to become a pro, most people make a career out of it in popular games. Also the standard RTS is so focused on execution whereas AI doesn't care about execution because its not using a GUI, its just activating functions directly. In fact I suspect that most AI programmers would make terrible pro RTS players.

I don't know, using an interface alone doesn't mean much. For most games, the strategy is most important. Consider Civilization V, where strategy is far more complex than MegaGlest. Most of the best AI ideas come from "pro" players on the forums; the people who have the most experience with playing the game. Myself, I'd love to get into AI in the future, and it seems that a strong understanding of how the AI should act matters as much as how it should be implemented.

That's a TBS game. The interface could be awful, and frequently is and it doesn't matter. We are talking about RTS games. Also TBS AI is different because you don't care about execution time, whereas in an RTS it needs to make its moves at least every 5 seconds.

It might be more accurate to say that the computer has multiple ways to be better. You could make it do a few simple tactics with execution and speed a human couldn't possibly match which is easier. You could also try to make it smarter. But that's more work. Humans have a whole separate super powerful computer highly optimized for strategy whereas a computer can only do what the programmer tells it. How can it compete?

Also, how do you know the pro players have the best AI ideas? Have they made several implementations of the AI with ideas from non pro players, pro player, and AI programmers and compared them?

What do you mean by ideas anyways? Just a paragraph description? Pseudo code? Actual implementation? One of those is not like the others.

[NoQ]

Also, how do you know the pro players have the best AI ideas?

When i'm saying "pro", i don't mean it as in starcraft-like notion of a pro. It should be at least a player who learned what it takes to win a game, who can, in most human or AI games, easily identify why they were won or lost (and make corrections). That's what can be identified as AI ideas. Then, if they are actually working on the AI code, they can observe AI games and keep tweaking its behaviour until the flaw they found is removed, or give up on it.

It seems that whoever you are, you can't make the AI play better than yourself: if you fail to realise a certain aspect of gameplay, the AI you make will fail here as well.

Opensource games that follow the "release early release often" paradigm and stay around for a while seem to have better chance of having a good AI inside them, compared to most commercial games where people good enough to work on an AI appear much after the game is released.

whereas in an RTS it needs to make its moves at least every 5 seconds.

Well, in my case, i had to make decisions in under 20 milliseconds. Because the API was implemented in such a way that the game just stalls when the AI is thinking >_<

You could make it do a few simple tactics with execution and speed a human couldn't possibly match which is easier.

Macro > Micro.

Brute force should win, in a usual game, against an improved micro. Moreover, providing a better macro is often surprisingly easy: it does much less to do with our intuition than tactics and micro, since the latter relies on our visual terrain geography and topology analysis. That's one of the common failures of AI developers, i think, to fall into improving micro, which is both hard and pointless. That's why i started speaking in the first place: to identify a few directions of easy and effective improvements.

[MoLAoS]

Also, how do you know the pro players have the best AI ideas?

When i'm saying "pro", i don't mean it as in starcraft-like notion of a pro. It should be at least a player who learned what it takes to win a game, who can, in most human or AI games, easily identify why they were won or lost (and make corrections). That's what can be identified as AI ideas. Then, if they are actually working on the AI code, they can observe AI games and keep tweaking its behaviour until the flaw they found is removed, or give up on it.

You are aware that you are responding to a post directed at Omega?

It seems that whoever you are, you can't make the AI play better than yourself: if you fail to realise a certain aspect of gameplay, the AI you make will fail here as well.

Opensource games that follow the "release early release often" paradigm and stay around for a while seem to have better chance of having a good AI inside them, compared to most commercial games where people good enough to work on an AI appear much after the game is released.

Being a good player doesn't necessarily mean you know why certain things work. And if you don't know why you can't tell the computer what to do. Also human minds short cut a lot, your average person doesn't really know why they can throw a ball perfectly, they just know they can. A task that is incredibly difficult mathematically in some ways. But that information is below the level of conscious thought.

And further even if you can articulate why you win, that doesn't mean you can do it on the level of a programmer.

whereas in an RTS it needs to make its moves at least every 5 seconds.

Well, in my case, i had to make decisions in under 20 milliseconds. Because the API was implemented in such a way that the game just stalls when the AI is thinking >_<

I was referring to the high level decision making. Humans don't reevaluate every decision every 20 milliseconds. The response time to alter your medium level game plan is not the same as microing units for instance. Also "every 5 seconds" is not grammatically the same as "in 5 seconds".

You could make it do a few simple tactics with execution and speed a human couldn't possibly match which is easier.

Macro > Micro.

Its not that simple. As a human you need to divide your attention micro wise across multiple battles. Computers don't have to do this. That is because the amount of time it takes a computer to issue an order is measure in milliseconds or less. It takes a human with 600 APM, which is incredibly high, ~100 times longer, 1/10 of a second vs 1/1000 to make the same decision. Actually the disparity is probably larger depending on how many instructions the code the programmer wrote takes to process.

You need both micro and macro to win a game. And the game space contains fewer options than the real world. Also you didn't define macro. For instance SC players define macro as dumb crap like keeping each barracks making 1 and only 1 unit at a time.

Suppose we assign a value of 40% to micro and 60% to macro. If the computer micro score is 1000 and the player score is 10 and the computer macro score is 10 and the player score is 500, even though macro matters more and the player is 50x better the computer still wins. In fact the value is 4600 vs 3400. That's a 30% bonus to the computer.

Brute force should win, in a usual game, against an improved micro. Moreover, providing a better macro is often surprisingly easy: it does much less to do with our intuition than tactics and micro, since the latter relies on our visual terrain geography and topology analysis. That's one of the common failures of AI developers, i think, to fall into improving micro, which is both hard and pointless. That's why i started speaking in the first place: to identify a few directions of easy and effective improvements.

I cannot follow what you said at all. It would probably be easier if you define micro and macro in your opinion so we know we are talking about the same thing.

[NoQ]

It would probably be easier if you define micro and macro in your opinion

Ok, lets try the following.

Strategy = where to move out, what to protect, what enemy to target first, at what timing. This is something quite hard for an AI, but certain approximations to good behaviour can be made. Lets put the expand fix in the first post there.

Macro = what to produce, what to upgrade, what to build and when. Not only make sure your barracks build swordsmen, but also choose whether to build swordsmen or archers. Depending on strategy decisions. This is fairly easy to program and improve, as i described above.

Tactics = formation movement, army placement, using terrain to gain an advantage in a single battle, surrounding enemy, placing units concave-ly during combat. This is fantastically hard for an AI, for it requires a human eye to recognize terrain pecularities.

Micro = management of single units during combat: concentrate fire, assign different targets to different units based on their roles, move damaged units behind and cover them with healthy units, make ranged units stay out of enemy range. This might seem easy to program to a certain extent, but doesn't have much effect.

You are aware that you are responding to a post directed at Omega?

Sure, i just keep saying what i think of it.

Being a good player doesn't necessarily mean you know why certain things work.

Hard for me to imagine. Provide an example?

And further even if you can articulate why you win, that doesn't mean you can do it on the level of a programmer.

I never said that you don't need to be a programmer to write AIs. That is obviously wrong. I also never said that if you know how to win, then it's a one-line tweak in the existing AI code. It may require a full code refactoring sometimes.

Its not that simple. As a human you need to divide your attention micro wise across multiple battles.

This is almost never relevant. Hardly ever more than one or two battles happen simultaneously, simply because a packed up army usually wins against an army split in two uncooperating parts. That's why the AI will most likely fail his micromanagement against a human, despite being able to make decisions much quicker. Unless an insane amount of efforts were put into the micromanagement code to make sure most of a human's micromanagement ideas (imagine an AI that has a code to do a mine drag in starcraft) are actually implemented.

One of the realms where AI can actually make use of his CPU power is harassing multiple defenseless targets at once. But in this game such skill doesn't seem to be very important.