Split the AI system for better MP performance

[Zakalwe]

My observation is that the goal of the current AI is to give the player a good fight in single player campaigns, NOT to give them a good fight in one-off battles on MP maps.

There is a simple reason for this - in the single player campaigns the AI is often given more gold and/or starting units/villages and basically acts by attacking the player with everything they have to do as much damage as possible and delay them from finishing before the turn limit is up.

This somewhat suicidal behaviour (never retreating, not bothering to heal or properly use leadership, being EXTREMELY cavalier with lvl2 and lvl3 units) is fine for single player campaigns, in fact, they probably wouldn't be as much fun if you weren't facing down the hordes of bad guys with your loyal cadre of battle hardened veterans (recalled from a previous scenario).
However the skills that are useful for the campaign AI are not necessarily useful for the MP AI and vice versa.
There is a tug of war between the motivations of developers - a change that makes the AI better at SP might make it worse at MP and vice versa.

Therefore I suggest that the AI be forked/cloned/split from it's current design into two diverging 'development streams'. One can be the 'campaign AI' and the other one can be the 'battle AI'.

The campaign AI can stick with it's current traits such as non-stop attack and deliberately killing player units about to level (even to it's own strategic detriment). etc. etc.

The battle AI can now be given priorities that would have hindered the campaign AI.
A short list of skills/priorities would be:
* Capturing all of the villages on its own side of the map at the start of games.
* Being careful with lvl 2 and lvl 3 units and retreating them when severely damaged.
* Using healers to support it's own units.
* Paying attention to ToD and actually retreating when the odds are against it, rather than continuing to attack.
* Concentrating/grouping it's units around good/key pieces of terrain when appropriate.
* Forming plans. (sorry, yes that's vague)

I'm sure people can come up with other ideas for how to improve the battle AI and I am even willing to make pseudocode suggestions (although I'm a economist, not a programmer). But I think a useful first step would be to split off the AI's. That would not be hard, just copy/paste the code for the AI and slap a label (campaign/MP) on each 'stream'. The trickier part might be to code in something that allows you to choose between different AI's, although if I remember correctly that would already implemented back in/before 1.4.x?

If I'm wrong then the counter argument is that any change that improves AI performance in campaign must also improve performance in multiplayer (and vice versa), which I am not sure is true and may indeed limit the possibility frontier for improvements in BOTH categories, so long as they are chained to each other as they are currently.

EDIT: This idea is for mainline. I am ignorant of any application/use/relevance towards UMC.

Also, just to clarify the my idea:
the 'campaign AI' would be used to control the opponents in the single player campaign game and you would be able to choose the 'battle AI' to control the opponents in multiplayer games.

[thespaceinvader]

WhyWritingAWesnothAIIsHard

It's easy to suggest improvements. It's difficult to make them. Any improvements to the AI will inevitably improve its performance in both campaigns and multiplayer.

I'm not a programmer, so I can't say what effect your proposed splitting of the AI would have. But it's my understanding that the problems you mentioned with its strategy are just that - they are mistakes the AI makes due to its not working properly, not intentional behaviours. Fixing them would improve both play methods. Whilst the playstyle for players differs fairly radically in MP and campaigns, for the AI, the whole campaign consists of single, multiplayer-like scenarios - they don't have a recall list or gold management to contend with, as the player does. The major difference is that they have to cope with unusual win conditions. But let's face it, making them able to do so would make some campaigns impossible. Imagine if the AI knew that it just had to sit a powerful unit on that signpost to stop you winning - you'd be stuffed...

Hopefully someone with better knowledge of AI programming will be able to help out further.

[Daxion]

You can have a look in New AI Design for Wesnoth 1.7 - a post by Dave

* Capturing all of the villages on its own side of the map at the start of games.

I'm not sure about that. For me it usually starts village capturing right from the start. In MP as well as in Campaigns

* Being careful with lvl 2 and lvl 3 units and retreating them when severely damaged.

Yes, that's true. But mostly this point is that: currently the AI has no real (or little) concept of looking one round ahead (see WhyWritingAWesnothAIIsHard)

* Using healers to support it's own units.

According to Dave this is something really hard to get right. Same goes for Leadership, and the aura ability.

* Paying attention to ToD and actually retreating when the odds are against it, rather than continuing to attack.

I think the big point is again: retreating is something that needs a bit foresight. One problem for the AI. However this is a point I feel, might be possible to improve

* Concentrating/grouping it's units around good/key pieces of terrain when appropriate.

Foresight again. Only makes sense if the enemy will be going for that position (how do you know it's a key position, without looking "into the future"?).

* Forming plans. (sorry, yes that's vague)

I'm not sure what you mean with that. Having specific goals?

[Max]

you may want to read this:
http://www.wesnoth.org/wiki/SummerOfCod ... ement_Crab

[Yoyobuae]

It is just too easy to underestimate the stupidity of computers in general. I mean, how long have programmers been trying to do "smart" things with computers, voice/image/etc recognition, complex systems control (ie. robot walking), etc.

But it is hard, VERY hard. You have to thank God (or evolution, depending on your beliefs) that there is some unbelievably efficient, flexible and powerful "software" working in your brain.

Now, I don't think the need for a challenging AI will ever go away. The AI may possibly improve until it becomes a challenge to at least some lower level players. Or perhaps even a challenge against better players by giving it an advantage. But that will surely take time.

The only way I see we could take a "shortcut" is to make an AI that plays a single scenario as good as possible, that will at least reduce some of the complexity. It could be a nice way to explore what works.

[DEATH_is_undead]

Now, I don't think the need for a challenging AI will ever go away. The AI may possibly improve until it becomes a challenge to at least some lower level players. Or perhaps even a challenge against better players by giving it an advantage. But that will surely take time.

It all depends on the map. I think, since the AI must be remade, humans should give it harder advantage... More gold/income, or give it a partner with a human side for regular players, coders give it units at prestart and such.

EDIT: I mean to make an AI harder, not actually remade. I, personally, think the AI is fairly fine the way it is.

[Zakalwe]

The post below is a copy paste of the post I just made in the wesnoth 1.7 new AI design thread (which I did read in it's entirety)

btw I did like the squads idea - I just think that there should be a strategic master planning phase.


I've got a lot of ideas for how to give the AI an ability to think and make decisions 'strategically'.

EXAMPLE Multiplayer AI

for this example we will assume the AI ignores fog of war and that there are only two players on the map.

STEP 1.
AI does this process ONCE at the beginning of each game (maybe a once-off recalculation if the leader moves to a different keep):
Firstly, creates an array with a value (set at zero) for each hex on the map.
Then it simulates the path that each of it's race units would take from it's starting castle to each
i) keep
ii) village
on the map
during each pathfinding simulation every hex that is crossed is incremented +1 in the array.
Then it does the same thing with the opponent, starting from the opponent's starting castle and decrementing -1 on the array all the hexes crossed during those simulations of the opponent's race units.
Finally run some sort of algorithim that smears out the data in the array so that adjacent hexes will share values (think of it as a mathematical 'blur tool') - this may have to be done more than once (potentially)

Now you've got a sort of numeric topographic map that overlays the actual map in the AI's mind, it has the following features:
1. Hexes with positive values are on the AI's "side" of the map
2. The higher the value the deeper within the AI's territory that hex is. The higher the value the stronger the AI is to it's military 'center of gravity' or the shorter it's 'supply lines' are. This means that theoretically it will find it easiest to concentrate it's forces around those hexes.
3. The AI now has an easy way to identify which villages 'belong' to it - any that have a positive value should be captured because they are closer to the AI than to the opponent (or the AI is between the village and the opponent).
4. Hexes that have a value close to zero are the ones where paths between the AI and it's opponent cross - these are the areas of conflict. In fact, if you colour in all the hexes with a value close to zero you'd probably get what can be termed a 'border zone' or 'no man's land'. This is a concept that is easy for a human to grasp but difficult for a computer the handle.

Now this is part of the basic information the AI can use for later decision making.
For example if it wanted to prioritise some 'village stealing' with some scout units - it would just make a list of villages starting from the one with the most positive value to the one with the most negative value, then it will exclude any village with more than 1 or 2 enemy units within 1 turn's movement range. Leftover is a list of villages suitable for stealing.
Another example is if it does a ToD calculation (I will elaborate on this later) and decides to retreat, which way to go? towards hexes with a more positive value and away from ones with a lower value.

#######
I'm going to bed now but I will try to get back and type up more of my ideas about how the AI could perform strategic analysis and decision making.

If people really like my ideas I will try and come up with some pseudo-code to help figure out implementation.

Preview of other ideas:
* Terrain type analysis (I get the feeling the AI already does this for picking troop mix?)
* Force mix analysis - based on averaging out all damage types on one side against the resistance types on the other side. (using weighted averages)
* Fighting strength analysis (including ToD analysis) (calculating a number for each side based on the aggregate of all of one side's unit's best attacks against a weighted average of the opponent's defense and resistances (taking into account ToD) and then comparing the two
* Wholistic comparison analysis - AI compares each player's
i) villages/income/gold reserves (if known, otherwise smart guesstimate)
ii) unit count and strength (see strength analysis above)
iii) experience (totals of player's unit's exp.)
iv) other factors? (as people come up with them.

--- The AI will then formulate the 'grand strategy' for the turn based on the result of the Wholistic comparison.
Ripping off Lionel's translation of Sun Tzu's Art of War:

8. It is the rule in war, if our forces are ten
to the enemy's one, to surround him; if five to one,
to attack him; if twice as numerous, to divide our army
into two.

9. If equally matched, we can offer battle;
if slightly inferior in numbers, we can avoid the enemy;
if quite unequal in every way, we can flee from him.

the AI will use some sort of heurustic rule similar to the above to figure out it's grand strategy for each turn.

Okay, I'm going to bed now. Good night all.

Please let me know what you guys think.

[Yogibear]

The current way of developing the AI further concentrates not on splitting it for different tasks, but instead to make it customizable through parameterization. That was actually the main goal when developing the formula AI, to be able to customize the AI's behaviour much better.

Also, there is more than fighting an opponent best. You could probably imagine for certain scenarios other tasks, the AI should fulfill, for example:
- escort and protect a unit on its way through a map
- hold and defend a certain terrain on the map but not push beyond it

The key to this is to have basic actions, that can be prioritized differently, according to rules that are set up and customizable via WML.

If you stop by on IRC (freenode, #wesnoth-dev) Dragonking (deekay), Dave (Sirp), Crab and boucman can tell you a lot more about that.

[Zakalwe]

Yogibear:

I think I might not have explained my idea very clearly - I understand and agree that there will be situations where the AI will need to do things other than win multiplayer games, in fact that is one of the reasons for my idea.

I'd just like to point out I'm only talking about improving multiplayer performance - better singleplayer/scenario AI is outside the scope of this thread.

Whilst I think that having a programmable AI that can be programmed through WML is a good idea and will enable campaign writers etc. to improve their scenarios I would like to point out that one of the weaknesses of the current AI is computation time/efficiency - i.e. if the AI is confronted with more than a few dozen units it tends to make people's computers chug away. This is not to mention the fact that everyone agrees that the multiplayer AI is a weak opponent.

What I'm suggesting is that there should be two DEVELOPMENT strands for the AI - one to make it better at multiplayer and one to make it programmable/customisable for singleplayer/campaign.

If I understand you correctly you are saying that if the AI was sufficiently customisable you would be able to use a set of WML settings to program a strong multiplayer AI opponent. I don't think I can really agree with this. Whilst in theory you would be able to make a 'custom' AI that is just as strong as a purpose-built multiplayer AI I think in practice the 'custom' AI will either be weaker, run slower or both slower and weaker. Whilst I know there are not that many players (that participate in the community anyway) that play a lot against the AI (or at least they play more against humans or in campaigns) I think this might partly be because the AI is weak, rather than because good multiplayer AI is not of interest to the players.

I know there are also multiplayer scenarios that have different goals and requirements than a 'deathmatch' AI. No problems - I just think the player & scenario creators should be able to choose which AI's they use and which to play against.

As for another practical considerations of having a custom multiplayer AI:
Would each player be expected to have to program the AI in WML themselves in order to get a decent MP opponent? Otherwise they would have to download a specialised multiplayer AI from the server (or it might be included with the game download). If this is the case then you have basically got a case where the AI is split, which is what I am proposing in the first place. I am proposing that we develop a specialised multiplayer AI that players can PICK/CHOOSE to play against in multiplayer games on standard maps.

[Yogibear]

Ok, i understand better now what you are heading for. And i agree with much of what you said. However, i don't see the need to split the AI, at least not at this point.

There is basically two areas of AI improving, that are very different to be dealt with and i think they are important both for campaigns and multiplayer.

1. Micromanagement (tactics)
Which unit to kill, which unit to choose for attack, finding best terrain to do so etc. The AI is already pretty good at this. At the moment, we are working in this area by improving the recruitment and teaching the AI specials like how to use poison best.
These abilities are useful both for campaigns and mp.

2. Macromanagement (strategy)
Attack or defend, finding strategic places, building battle fronts etc. This is what the AI seriously lacks. However, improving this area is worthwhile for mp and campaigns as well, too.
Let's have an example: There are already parameters to customize the strategy of the AI, though admittedly rather unspecific ones. You can set the level of aggressiveness via a simple WML number parameter. You could use that for campaigns to force an all-out-don't-care-for-casualties attack. You could use it also to teach the AI to better care for the day-night cycle, as it works by comparing the strength of the AI and its enemies. It would certainly have to be improved, but you see what i am heading for.

Can you give an example, that would not benefit campaigns and mp both? The only one i could imagine is to give the AI map dependent hints, if it is not smart enough to see by itself. For example chokepoints, strategic terrain spots, things like that. In fact there has been an idea in the past to write a map specific AI, but it has never been tried on.

[Zakalwe]

I thought about what you are saying and I think you might have a good point.

Now the arguments I had were basically that in MP the AI cannot afford to be reckless because it (ideally) has to compete on even terms with the human and therefore must conserve its resources and use its units intelligently - this was in contrast with SP/Campaign where the AI can (and currently does) tend to play very recklessly and aggresively, throwing itself at the human knowing that it probably has higher starting resources, higher income, is able to recruit lvl2/lvl3 units at will and/or is going to be given free units or new allies during the course of the battle. Of course a counter argument is that the human player is often given units etc. etc. as well.

But I started thinking - what if the SP/campaign AI started behaving like a good MP AI/intermediate human opponent?
If the AI would retreat when appropriate, take care of it's units, sometimes hold ground instead of attacking, try to gain an income advantage etc. etc. it might even try to run down the clock by forcing the player to attack its units on high-defense terrain.

I'm not necessarily sure it would be a good thing, it would certainly change the flavour of campaign games!

Nevertheless you might be right that any change that makes the MP AI stronger probably makes the SP AI stronger as well. the only proviso is you might need to customise the SP AI for each scenario to make it behave appropriately.

There would be a lot of scenarios in the campaigns where the best strategy for the AI side is not to attack the player straight away but to spend all it's gold first to build a huge army and then just hold its part of the map (with the majority of villages) and try to build an overwhelming force advantage - never attacking but just holding the high defense terrain. Such an AI would be better but I'm not certain if it would be fun.

And that's what I'm talking about - the limitation is not a purely technical one but rather a tug of war between wanting to make the MP AI performance better and wanting to keep the campaigns fun. But maybe having smarter campaign AI would BE more fun and I just happen to be wrong about this. I am open to hearing other's opinions on this.