Questions and Ideas for AI

[onomastikon]

Hello! I hope this is the correct place to post this.

I'll have one question and 3-4 suggestions (constructive criticism). First, the context. I love BfW -- and particularly enjoy playing BfW as a single-player experience when underway (I commute a lot). I understand that most people here play BfW multiplayer, and that's fine; I enjoy the SP aspects. I'm particularly keen on practicing with the default factions on premade maps.
I guess that because most people are interested in MP, I do not see the AI discussed much.
This is the most recent information I could find about improving the AI in BfW: this http://forums.wesnoth.org/viewtopic.php?f=6&t=36512from March.
In it, I gather that at least some people (but I do not know who) are possibly interested in possibly improving the RCA AI in BfW sometime this summer. Hence my questions...

QUESTIONS
- Is that still the case? That some people (who?) are working on the "RCA" AI for BfW this summer? Where can I find more information on that?
- Is this the right place to make comments about that? If not, where must I go?

SUGGESTIONS / IDEAS / CONSTRUCTIVE CRITICISM
The AI in 1.10 does what seems to be a good job in picking targets and attempting to surround these, or at least attack the target from two different sides, hindering its ability to escape. It also seems to evaluate fairly well when it will lose a fight and not attack with a unit which will probably only die without inflicting damage. Additionally, with the exception of the Rebels, the AI recruits what appears to be acceptable troops (the Rebels seem to choose Woses too often and, sadly, they use them suboptimally, s. below). Finally, if the AI has the choice of terrain, it will choose better terrain in which to place its units, all other things being equal.

But the AI seems to need help in some other fields. Here are some humble remarks which, hopefully, may help

- In default games, the game is over when the opposing leaders are killed. The AI will, however, frequently move its own leader out attack enemies within its range. In doing so, the AI may succeed in inflicting damage on one enemy unit -- but frequently, not nearly enough to kill the unit; yet simultaneously, the AI will almost unerringly suffer the following: the leader is injured, the leader is on poor terrain, and, which is the worst, the leader may become surrounded on the next turn, unable to escape. So while the AI may succeed in injuring one or even many units by using its own leader as an attacking force outside of its own cidadel, it almost invariably means its downfall, because it endangers its own victory conditions. Moreover, the AI leader in many of these cases will also exhibit additional suboptimal behavior as mentioned below.
Suggestions: Greatly increase the weight to which the AI evaluates danger to its leader; never allow the leader to exit its citadel to attack units if there is a chance >10% that 2 or more enemy units may surround the leader on the next turn, even if an enemy unit may be eliminated.

- While the AI will choose good terrain to place its units in when all other factors are equal, the AI will rarely choose optimal or even good terrain to place its units in if the AI has a chance of attacking an enemy unit. The AI will go to great lengths to attack at what appears are almost all costs. Frequently, the AI will do some or even all of the following at once: place its units in suboptimal terrain for the chance to attack a unit rather than not attack, prefer to attack during a suboptimal time of day rather than not attack, place a unit directly next to a village (so that an enemy unit on the next turn may move into the village and attack it from relative safety), place a unit deep into enemy territory in order to attack without having recon of possible counterattackers, prefer to attack even with wounded units which gain benefits from defense, and prefer to attack rather than capture a village and heal.
Suggestions: significantly increase the weight which the AI would give to placing units in >suboptimal defensive terrain; increase this weight significantly if there are very few or no units within range with magical attacks or marksman abilities; increase this weight greatly if there are very few units within range with magical attacks or marksman abilities. Increase the weight which the AI applies to retreating and healing its units. Decrease the weight which the AI gives to attacking with support units (particularly healers).

Thank you for your time.

[Elvish_Hunter]

Moved to Coder's Corner, where AI improvements are discussed.

[Crab]

Hello!
Thanks. Some notes about your remarks:
1) yes, control of leaders and other not-to-be-lost units should be handled differently, but there's no work done about this at the moment.
2) AI (with default aggression of 0.4) would attack at approximately 2:1 disadvantage, and might not consider next-turn counter-attacks properly. This is by design, since current AI has trouble with defense - so, we just make it attack instead. Lower the aggression to 0 (where AI would attack only where it has advantage) and see what happens - only units with good attacks would attack, but other units won't support them properly. This can be fixed by improving the defence strategies of the AI. There's no work done about this at the moment.

What is done in context of GSoC :
1) improving of recruitment code (rewriting it almost from scratch, actually)
2) improving our support for usage of Lua to write AIs.

You're welcome to ask questions and contribute ideas. However, since one of the major constraints is the lack of time, many good ideas sit unimplemented. However, we'll try our best to answer questions and point to places in the code, if necessary.

[Guest]

.

[mattsc]

onomastikon: thanks for posting your comments! As Crab said, the main thing is that none of the developers has much time to work on the base AI code and that modifications to it are, for the most part, quite involved. It is certainly not for lack of interest. Just to give you an idea about some of the complications:

Concerning your first point, having the leader attack only when it is safe also during the next enemy turn means not only predicting what might happen on the AI's own turn, but also on the next enemy turn. Since the computer cannot argue logically in the same way as we can, it essentially has to play through all the possibilities, incl. what happens when one or more of the AI's units that currently block the enemy die.

As for your second point, having the AI only attack from "favorable terrain" without the rest of the units supporting the attackers (setting up defensive lines) is actually a weaker strategy than always attacking without compromise. (I have tried that, and the AI I set up doing that just got butchered by the RCA AI.) It is also amazing how difficult it is to tell a computer things like: "set up a line along edges of favorable terrain perpendicular to the direction toward the enemy"...

So, it's not that your ideas are bad, quite the contrary, but it's not as simple as changing a few parameters or lines in the code. Now, having said that, I have been working on modifying AI behavior for some time (and the first thing I learned is actually just how good that RCA AI is in fact). It's still all work in progress, but if you want to have a look, check out add-on 'AI Modification Demos'. In particular, I'd point you to scenarios:
- 'Protect the Wizard' and 'HttT: The Elves Besieged': These are set up to have the AI protect one or two valuable units. As part of that, those units attack only when the AI perceives that they cannot be killed by retalliation attacks on the next enemy turn. It does, however, not take into account what would happen if one of the AI units blocking enemies would die.
- 'Prune Cart': This scenario is very much unfinished and has a lot of known (to me) weaknesses and does some outright stupid things, but it is my first attempt of setting up an AI that works with defensive formations and attacking mostly from favorable terrain. It's probably not even half done yet, but ... well, if you look at the code, you'll see what I mean.

If you have a look at those scenarios and could give me some feedback on what you think the strengths and weaknesses of those AI's are, that would be much appreciated and help me a lot. But just to add this: I am not a Wesnoth developer and it's unlikely that any if this will end up in the default AI (most of it is way too specialized for this and would not stand a chance against the RCA AI in a general setting), but maybe it demonstrates a little what we as the users can do with the tools that already exist.

PS: I don't know if any of this makes sense. I'm really tired at the moment, so I might only be babbling nonsense. If so, I'll try again tomorrow.

[Dugi]

I would like to request a feature as well. It should not be anything overcomplicated.

The problem is that in some cases, the AI needs massive amounts of time to make a single decision, and this problem can arrive even if you just set a few extreme values to a random scenario. I had this problem when AI had to attack a strong unit (with tons of damage and hp), mattsc made a workaround for me to add a candidate action of attacking the unit with a greater value than attacking anything else, but it is not a perfect solution. I decided to his hp, but that would be a massive change an would need a lot of rebalancing, and I am leaving it on my to-do list as too time-consuming to be done at the moment.

The solution I suggest is that if the matrix of all possible actions grows too large, the AI just makes the best decision out from those that are already there. Or just uses a simple way to choose to attack, just takes the strongest unit available and attacks the weakest unit in its range, or something else (as Sapient wrote like 5 months ago, that there used to be a simpler way the AI decided what the attack would be, and that one never had those problems).
For short, if after a certain number of considered actions the AI does not come to a solution, it makes the decision in a certain primitive way, because this is better than leaving the players watch the AI's ages long zen meditations.

[Crab]

for making attacks simpler, it should be possible to do by decreasing the attach depth (if the feature is currently broken, it should be trivial to fix); Also, there's a constant in the code which can be changed to limit the amount of attacks considered and evaluated (but this shouldn't matter much if the problem is slow evaluation of the attack probability distributions)

[onomastikon]

Thank you very much.
I wasn't able to understand all of what was said here, but I think I get the general gist. Sadly, I know nothing about programming
I would like to see if some form of moderate aggression reduction might help the AI to place units in better terrain. Maybe this would also help: The AI tends to move its units the maximum amount that unit can move towards the front line; this makes for suboptimal unit placement and is also bad for recon / scouting; in other words, the AI appears not to pause and reevaluate along the same lines that human users are promted to (the gigantic red warning by default: movement stopped because of "enemy unit(s) sighted!").
Surely I am in the minority, but I do not believe the AI takes a long time to evaluate it options. In 1vs1 setup (human vs RCA) on applicable maps, the AI seems to take less than a tenth of a second. I wouldn't mind waiting 10x that length and much more if it meant that the AI could evaluate its options better (e.g. extreme care with its leader as sole carrier of victory conditions, less wanton aggression and more attention to terrain / time of day).
Thank you so very much

[taptap]

Often bad AI behaviour could be avoided with the available means. Less aggressive play etc. but it isn't used often enough.

Micromanagement of a battle line is a particular weakness of the AI (it does much better in the open). If you have some slow available and the AI has a unit mix of high and low damage units, you can very efficiently limit exposure of your units and make their high damage dealers attack where it suits you. The reason is, I believe, that the AI is considering units individually not collectively. If it would start to retreat low damage dealers 1 hex to get better attacks on the crucial spots with the high damage dealers and then cover the achieved break with the low damage but resilient units many campaigns would suddenly be very hard

[mattsc]

Micromanagement of a battle line is a particular weakness of the AI (it does much better in the open). If you have some slow available and the AI has a unit mix of high and low damage units, you can very efficiently limit exposure of your units and make their high damage dealers attack where it suits you. The reason is, I believe, that the AI is considering units individually not collectively. If it would start to retreat low damage dealers 1 hex to get better attacks on the crucial spots with the high damage dealers and then cover the achieved break with the low damage but resilient units many campaigns would suddenly be very hard

Hey taptap, thanks for the comments. You're right about all that. Unfortunately, doing anything but moving units individually is quite hard to program. Pattern recognition is so easy for our brains, and so hard for a computer... I've been struggling with that for months and still think I have barely made half a step forward. If you have the time and interest, you could check out the above-mentioned 'Prune Cart' scenario, which is an attempt to deal with units in groups rather than individually. Any comments on how to improve on that would be much appreciated.
Caveat: the code is very much incomplete and also still contains a few bugs, so a unit suddenly jumping in front of the line into the middle of a bunch of enemies is likely not an intended feature. It's the overall strategy that I am more interested in at this time.

Also, I don't know if you've seen the recent discussion on MP AIs in my thread here in the Coder's Corner forum. Any advice on that from a good player like yourself would be really, really helpful. I've started to get some great advice from people who are much, much better than I am, but every bit helps!

[taptap]

That "Prune cart" scenario from Grnk the Almighty? I thought it worked very well already when I played it, but I was running from the sheer mass of undead, although the undead backed off when I posed a reasonable threat to their vanguard.

I guess the issue is really complex, but maybe even "simple" shortcuts help. I don't believe putting work into increasingly complex evaluation functions of individual units is a good investment as in my experience the more educated and "specialized" the AI behaviour the easier it is exploited, I would work on interaction or shortcuts that feel like interaction while not actually being it. 1) like unit A movement suggests hex H, now compare all my units that can reach this spot whether anyone is better suited for it. Or 2) add sth. like consider even hexes as movement targets where units with remaining MP stand, if selected move sitting unit one hex away (not into ZoC) and move in the other unit. The AI is basically still moving units individually but they feel a little as if they interact. 3) Consider some spots as targets (villages, next to healer who made his move,spot where you killed a unit) and look for idle suitable units to move there, i.e. look the other way round not the unit to move and then write a complicated evaluation function, but make it sometimes in the other direction. Or 4) shuffle the order units are considered each turn (i got the impression it does not, but i might be wrong).

[mattsc]

That "Prune cart" scenario from Grnk the Almighty?

He's been upgraded to Almighty now? Well, who knows what happens in Part 2 ... But seriously, sorry, I forgot that that scenario has almost the same name (and not coincidentally). No, I mean scenario 'Prune Cart' in 'AI Modification Demos'. Some of the things you suggest are (kind of) done in there.

[csdidier]

Thanks for the comments here.

I finally got around to attaching the eclipse/gdb combo to wesnoth, today, and started stepping through 'stage_rca.cpp', 'ca.cpp', and 'ai.cpp'. There is definitely a lot to it, but I have the basic idea.

My first impression was that the weighted candidate actions was a primitive idea, but on further thought, it really isn't such a bad idea, and in fact I'm amazed at how well the RCA AI performs.

Another thought I had is that one might want to try to combine the movement, attack, and get_villages phases, as it would be more effective to have these actions coordinated (i.e. after attack move these units here so our unit has only one hex exposed to the enemy ... etc) and such that the attacks are in line with acquiring a village.

It would seem to me that a truly effective AI would need to have a 'book' much like chess-playing programs have, meaning an AI library would be map specific, and would have reactions to specific scenarios "hard-coded". In fact this isn't that different from the way a human thinks. I know it took me a long time to figure out how to use Fishes with the water village in Isar's Cross. Now after several games, I have a winning routine, that could easily fit into a switch(){case 1: , case 2:} loop.

mattsc, I downloaded the scenarios, ... quite impressive. Are you doing all of your development using LUA (haven't researched that one yet), or have you done any examination of the cpp code?

Actually, I can answer that question myself, by looking at the files that came with the add-on download.

Regards,

csdidier

onomastikon: thanks for posting your comments! As Crab said, the main thing is that none of the developers has much time to work on the base AI code and that modifications to it are, for the most part, quite involved. It is certainly not for lack of interest. Just to give you an idea about some of the complications:

Concerning your first point, having the leader attack only when it is safe also during the next enemy turn means not only predicting what might happen on the AI's own turn, but also on the next enemy turn. Since the computer cannot argue logically in the same way as we can, it essentially has to play through all the possibilities, incl. what happens when one or more of the AI's units that currently block the enemy die.

As for your second point, having the AI only attack from "favorable terrain" without the rest of the units supporting the attackers (setting up defensive lines) is actually a weaker strategy than always attacking without compromise. (I have tried that, and the AI I set up doing that just got butchered by the RCA AI.) It is also amazing how difficult it is to tell a computer things like: "set up a line along edges of favorable terrain perpendicular to the direction toward the enemy"...

So, it's not that your ideas are bad, quite the contrary, but it's not as simple as changing a few parameters or lines in the code. Now, having said that, I have been working on modifying AI behavior for some time (and the first thing I learned is actually just how good that RCA AI is in fact). It's still all work in progress, but if you want to have a look, check out add-on 'AI Modification Demos'. In particular, I'd point you to scenarios:
- 'Protect the Wizard' and 'HttT: The Elves Besieged': These are set up to have the AI protect one or two valuable units. As part of that, those units attack only when the AI perceives that they cannot be killed by retalliation attacks on the next enemy turn. It does, however, not take into account what would happen if one of the AI units blocking enemies would die.
- 'Prune Cart': This scenario is very much unfinished and has a lot of known (to me) weaknesses and does some outright stupid things, but it is my first attempt of setting up an AI that works with defensive formations and attacking mostly from favorable terrain. It's probably not even half done yet, but ... well, if you look at the code, you'll see what I mean.

If you have a look at those scenarios and could give me some feedback on what you think the strengths and weaknesses of those AI's are, that would be much appreciated and help me a lot. But just to add this: I am not a Wesnoth developer and it's unlikely that any if this will end up in the default AI (most of it is way too specialized for this and would not stand a chance against the RCA AI in a general setting), but maybe it demonstrates a little what we as the users can do with the tools that already exist.

PS: I don't know if any of this makes sense. I'm really tired at the moment, so I might only be babbling nonsense. If so, I'll try again tomorrow.

[mattsc]

mattsc, I downloaded the scenarios, ... quite impressive. Are you doing all of your development using LUA (haven't researched that one yet), or have you done any examination of the cpp code?

I have looked through a lot of the C++ AI code, so I know what's there and how it works for the most part. But I have never programmed in C++ myself (I know C, so I can read C++ code just fine, with a little help from Google), so all my coding is done in Lua and Formula AI.

Actually, I can answer that question myself, by looking at the files that came with the add-on download.

I hope it's ok that I answered it anyway.

Another thought I had is that one might want to try to combine the movement, attack, and get_villages phases, as it would be more effective to have these actions coordinated (i.e. after attack move these units here so our unit has only one hex exposed to the enemy ... etc) and such that the attacks are in line with acquiring a village.

That's a pretty big task, but I've been trying to do things along those lines to some extent in my custom AIs. Another thing you can do with the candidate action formalism is to vary the evaluation scores. For example, the default AI always recruits first (if possible), before doing anything else. In my grunt rush AI, I always recruit last, so that the recruited unit type can be adapted to what happened during the turn -- except when the leader is about to move off the keep for an attack. In that case, the recruitment evaluation score is set very high, so that recruitment is done first. The CA method is really very flexible with things like that.

It would seem to me that a truly effective AI would need to have a 'book' much like chess-playing programs have, meaning an AI library would be map specific, and would have reactions to specific scenarios "hard-coded". In fact this isn't that different from the way a human thinks. I know it took me a long time to figure out how to use Fishes with the water village in Isar's Cross. Now after several games, I have a winning routine, that could easily fit into a switch(){case 1: , case 2:} loop.

Well, we're trying this at the moment, by implementing a grunt rush AI, for the Freelands map, for Side 1, for Northerners only. But even that's not so easy, as it turns out. My personal goal with this is to figure out what works under these specific circumstances, and then to use some of it in general, and set up other things that can be adapted on a map by map basis, if desired. I've discussed the idea of adding new tags that let the scenario designer "dial in" and customize certain AI behaviors in a scenario specific way with some of the developers. My custom AI's aren't ready for this yet, but doing this in principle is quite easy (this could even be done entirely in Lua).

Btw, to test out the grunt rush, go to the MP lobby, choose 'default + experimental AI' as era, then select the Freelands map, Northerners for Side 1, and the respective AI for the computer player for that side. Disclaimer: the current version does not play very well, but hopefully I'll get back to that again soon. [I really need to add some instructions about this to the add-on...]