Exercises in Formula and Lua AI and AI-demos add-on feedback

[mattsc]

I might change my whole map index (ai_helper.mind()) setup, since it's essentially the same thing anyway, but without all those convenient functions.

That should give you a bit of extra speed since it's currently converting from one index form to a list and back again.You could also rewrite it to use your current index functions for the same effect.

I could, but locations sets already have all those nice methods (union, union_merge, iter, ...), so I think I'll just put in the effort once to make the change and then have all of that at my disposal.

Also, I notice that for the Heir to the Throne scenario, the map is calculated twice. Would it be possible to store it so it doesn't need to be recalculated or do the effects of allied units moving matter here?

They don't for the version that is on the server ( 0.4.8 ), but in my current working version, there is a difference if any of the 'protected units' have moved already. So unfortunately I will need to calculate it for each move.

That shouldn't work either if a unit could keep moving for some reason (passive leaders, move to village for healing, human control, moving backwards along path), but in the opposite direction.

Damn, you catch all the caveats! Yes, I had noticed that already and ...

Why not set the unit's current moves to the maximum before calling the function.

... that is what I had come up with as well (only for the enemy map though; for my own units I want to use the current movement status). In the meantime, I figured that '{additional_turns=1}' will give me a slightly conservative behavior.

Would slow need to be taken into account as well here?

Good point. I don't know how that is handled. I'll check it out.

Thanks!

Oh, and before you find that problem also, the 'distance map' is currently being calculated very inefficiently and slowly (I really don't need it for the entire map, but only for the hexes the protected unit can move to). I'm already on that.


EDIT: Umm, here's another stupid question. So, now I am using location sets and end up with an LS index for the target of the best move. I need to convert that index back into x,y coordinates so that I can use ai.move(). What's the most elegant way to do this? The only things I can come up with so far are:

• Create a LS with only this element, then use this_set:to_pairs (or :filter or :iter or whatever). Disadvantage: need to create a separate LS with only one element
• Use the formula given in 'revindex(p) in file location_set.lua. Disadvantage: if that formula ever changes, the code breaks (and probably without producing an error message).

Shouldn't there be an easy way to do this?

[mattsc]

v0.4.9 is out, which contains many improvements (both in behavior and speed) in scenarios Protect the Wizard and The Elves Besieged. Among the highlights:

• Movement calculation now also takes terrain into account. 5 different configuration parameters can be set at the beginning of the scenario
• Attack calculation avoids attacks against enemies with posion & slow defense; all enemy weapons are taken into account. [The decision to attack with one of the protected units is made very conservatively. You might have to watch The Elves Besieged a couple times to witness that, but they really do attack occasionally]
• Only one candidate action is needed even for several protected units now - that has algorithm/behavior advantages in addition to the obvious added convenience
• Added a condition that avoids the AI to be "stuck" in place in rare cases if all enemy units have been defeated
• The full changelog is included with the distribution

If anybody wants to test this in another scenario, I strongly recommend using the code from version 0.4.9.

[mattsc]

v0.5.10 of 'Ai Modification Demos' is out, with a new scenario. In 'Messenger Escort' a small number of riders (controlled by the AI) is trying to outrun an orcish horde (controlled by the player). The idea (and map geometry) comes from UtBS, on a suggestion made by Alarantalara. I could really use some play testing help with this, and ideas what to improve in the AI algorithm. It plays reasonably well, but there's clearly room for improvement.

There are currently 3 separate candidate actions:
1) If an enemy unit is in the way of the messenger, attack that unit, or attack other units to get to it
2) If no unit is in the way, or all attacks are done, move the messenger as far as possible toward the signpost (the messenger never attacks)
3) If any units have movement left, move them as close to the messenger as possible, for his protection

[Alarantalara]

I've tried it out a few times now and I'm very impressed.
It took about 10 tries before I could figure out how to beat the AI at all, and even then, I would have lost if the messenger was willing to attack when it gets pinned (even if only with ranged attacks vs grunts).

There is one noticeable difference from UtBS: the player doesn't have any units that are fast enough to keep up with the messenger once he starts running. I suspect adding wolf riders to the recruit list (since you wouldn't know you need them ahead of time) may make the scenario easier for the player.

Once they appear, I wonder if the third candidate action should be trying to place themselves between the messenger and enemy units, while staying close to the messenger.
Also, I noticed that for me to catch the messenger I had to initially block the opponent by moving a space away from the unit I was trying to stop, not adjacent to it. This might imply that the units with movement left should be doing something similar, i.e. move as close as possible but not move adjacent to the leader. I don't know if it would improve things though.

Edit: included replay of successful run

[mattsc]

I've tried it out a few times now and I'm very impressed.

Thanks. I have to admit though that this is an extremely carefully balanced setup. I even prescribe which units get the quick trait and which don't. Using this in a "real" scenario would be much harder to do.

I would have lost if the messenger was willing to attack when it gets pinned (even if only with ranged attacks vs grunts).

I should probably do that. At the very least the no retaliation version, or when there's only a small chance of taking significant damage.

There is one noticeable difference from UtBS: the player doesn't have any units that are fast enough to keep up with the messenger once he starts running. I suspect adding wolf riders to the recruit list (since you wouldn't know you need them ahead of time) may make the scenario easier for the player.

Hmm, good point. Maybe I'll add one wolf rider to the map by default, far enough away that he can catch up on Turn 3 or so, in addition to adding them to the recruit list.

Once they appear, I wonder if the third candidate action should be trying to place themselves between the messenger and enemy units, while staying close to the messenger.

I agree, it should. I've thought of that too, but haven't had time to figure out how to do that yet. Adding distance to enemy units as another weighting function will probably do the trick.

Also, I noticed that for me to catch the messenger I had to initially block the opponent by moving a space away from the unit I was trying to stop, not adjacent to it. This might imply that the units with movement left should be doing something similar, i.e. move as close as possible but not move adjacent to the leader. I don't know if it would improve things though.

Interesting. I'll play with that idea a bit.

Thanks much for the comments, I'll let you know when I have made those changes!

[Rigor]

hi,

im glad you are still motivated and industrious and because you are what you are, i have to ask you this: did you consider applying for the Google Summer of Code 2012 http://wiki.wesnoth.org/SummerOfCodeIdeas and the second news line on http://www.wesnoth.org/ ? applicants are people like you who work on some project on their own. i mean, you just have to apply. check this one out, some ideas are dedicated to teach the AI, look here (its a hand-copy/pasted list and might not be complete):

Spoiler:

4.2 AI: Implement a 'total defense' strategy [12]

4.2.1 Andriy Andriychuk - "Total defence" strategy
4.2.2 James Heath - AI: Implement a 'total defense' strategy
4.2.3 Sanka Darshana - "Implement a 'total defense' strategy"
4.2.4 Christopher Conway - Defensive AI
4.2.5 Conor Nevin - Implementing a Total Defense AI
4.2.6 Nikolay Agafonov - Line Defence Strategy
4.2.7 Ed Kim - Total Defense AI
4.2.8 Geoffrey Hart - Maximizing Utility

4.3 AI: Make lua AI development and usage easier [2]

4.3.1 Dmitry Kovalenko(Nephro) - Further Lua

4.3 AI: Make lua AI development and usage easier [2]

4.3.1 Dmitry Kovalenko(Nephro) - Further Lua
4.3.2 Tyrannodogg - Make lua AI development and usage easier


4.4 AI: Refactor recruitment algorithm [5]

4.4.1 Aline Riss Recruitment Proposal
4.4.2 Talbot Pierre - Refactor Recruitment Algorithm
4.4.3 Paolo De Luca - Refactoring recruitment algorithm
4.4.4 Kseniya Buraya - Refactoring AI Recruitment


4.5 AI: teach the AI to play Wesnoth's mainline campaigns [3]

4.5.1 Yigit Demirag : Development of AI to Play Mainline Campaigns in Battle For Wesnoth
4.5.2 Kevin Wyckmans - Teach That AI!
4.5.3 Thomas Martinet - AI: teach the AI to play Wesnoth's mainline campaigns
4.5.4 Philipp Battenberg - AI: teach the AI to play Wesnoth's mainline campaigns

the bottom line is, i think your ideas are equally worth to be recognized by a broader community and you should really apply. and you could not only exchange your ideas with others but polish them in a fruitful environment.

[mattsc]

Hi Rigor, thanks for the nice words. Unfortunately, there's this line in the GSoC FAQs:
"In order to participate in the program, you must be a student"
and, well, I'm not a student. Haven't been for a bit, in fact. I'm one of those people who probably shouldn't waste their time with silly computer games, but hey, it's so much fun.

I've been following the GSoC proposals quite closely and have communicated with some of the students. There is some really interesting stuff being suggested and already being done. And don't worry, I'll keep working on this, I just don't always have as much time for it as I would like.

[mattsc]

v0.6.0 of 'AI Demos' is out with a new scenario. This is the first scenario that might go in the direction of a general-use AI of a somewhat defensive orientation. Scenario 'Prune Cart' has the AI protect a (very slow) unit as it makes its way toward a signpost. It features forming defensive lines along favorable terrain and moving units in squads.

EDIT: To be clear: this code is still in an early stage and the custom AI will lose the scenario more often than not. What I am looking for at the moment are comments what the biggest weaknesses appear to be to you (such as those by Anonymissimus below), so that I can tackle those first. There's a long way to go...

The scenario is still incomplete (and the AI behavior kind of falls apart when unit numbers get low), but I think it shows promise. Comments on weaknesses would be extremely helpful at this time. Below follows a long (and incomplete) list of things that are still missing. However, this is the first scenario in 'AI Demos' that is adaptable enough that all of those things can be included (they'll just take a bit of time and thought).

Among the many things that need to be added/improved:

• AI spreads out a bit too much
• There's no rotating of injured units toward the back, or moving them toward villages
• It doesn't use "broken lines", bridging unfavorable hexes by using ZoC.
• It should specifically target enemies that have broken into a formation
• It should specifically target units that are about to attack the cart
• AI doesn't make use of leadership/healing. Well, there aren't any healers (yet) and the one leadership unit is entirely uncontrolled

Those are things that I am already planning to work on and (kind of) know how to deal with. But this is big enough that any play testing by others would help me a lot. Oh, and don't look too closely at the code, it's kind of a mess atm.

[Anonymissimus]

I watched the RCA beat your custom AI easily.
The custom AI should attack before moving if he can make an attack without "exposing the attacker too much" and without putting him on bad terrain. I imagine the first condition is hard to specify. Also perhaps the fact that not all units should attack but only some which are in range of good positions and which have good health.

[mattsc]

Anonymissimus: yeah, my AI is just not ready yet to pull it out. I usually don't post code this incomplete, I was just so happy yesterday that I had finally figured out this "place units along edges of favorable terrain" thing, that I got carried away. I guess it's easier for me to see what this new code does well (since I know exactly what to look for), and ignore all the bad things it does. This really isn't meant to be a fully working AI yet, but I think I have cleared the biggest road block (for me, so far) on the way to getting there.

Thanks for the feedback, it helps me a lot to know what others think are the biggest weaknesses atm. I agree that figuring out when to attack vs. when to form lines is crucial (and non-trivial). I'll keep working on it.

[Anonymissimus]

And I forgot to mention: It should also consider whether and by how many enemies an attacker can be attacked during the enemy's next turn. If his own unit could die that way, don't attack. But do it if it is safe provided that the unit it plans to kill does actually die. Meaning that now the killers can not be reached by sufficiently many units to kill one of them.

[mattsc]

It should also consider whether and by how many enemies an attacker can be attacked during the enemy's next turn. If his own unit could die that way, don't attack. But do it if it is safe provided that the unit it plans to kill does actually die. Meaning that now the killers can not be reached by sufficiently many units to kill one of them.

It's funny how you can describe this clearly in few words and how we can look at a map and see how to do this immediately, compared to how many lines of code are needed to teach this to a computer. But this one's "easy" compared to "find edges of good terrain" and I've actually done (something like) this in one of the other scenarios.

I'll add it to the list, thanks.

[mattsc]

Anonymissimus: I have not coded the attack features you suggested yet, but I have made significant improvements to the way the orcs form their lines and to hunting down units that get too close to the cart. Watching the AI, it's obvious that many things still need to be improved, but apparently this is good enough already that it now usually wins the scenario.

I don't know if you want to check out every incremental improvement, but if you do, it's out there (v0.6.1).

EDIT: I just put v0.6.4 onto the server. AI play is much improved and now also includes healers and leaders backing up the formations. It still does not do 'active attacks' (and there seem to be a couple bugs that I have not found yet), but it does some pretty decent playing in between those.

[mattsc]

Finally !! I now have a version of a defensive AI that does some semi-decent gameplay (I think). Scenario 'Prune Cart' in 'AI Demos v0.6.6' now has 400 gold worth of orcish archers protect the prune cart against 500 gold of skeletons and skeleton archers. It now wins it almost all the time, often with an overwhelming advantage in units at the end.

I am not saying that it is perfect yet, far from it (see some of the issues mention in the opening dialog), but at least in this scenario it seems to be standing up to the standard AI quite well. Note that (unlike 'Pass Defense', where I hard-coded locations on the map as being good for defensive positioning) I am giving the AI no added information about the map. It decides by itself where to set up defensive lines. (But I should point out that I disabled cart movements for the time being, to have a slightly easier problem to begin with. EDIT: In v0.6.7 the player now has a choice of playing with a stationary or with a moving cart.)

I would be very interested in comments as to where the AI seems to fail or behave stupidly. It does get itself into trouble occasionally, but I am not quite sure yet whether that's the strategy itself or bugs in the implementation.

And just in case anybody cares , the AI currently has the following features:
- Setting up defensive lines along favorable terrain to protect the cart, healers, leaders and injured units (when possible)
- Attacking and intercepting enemy units that get too close to the cart
- Positioning healers and leaders strategically behind the front line
- Placing injured units next to healers or on villages (and/or keeping them away from enemies if needed)
- Level-up attacks
- It does not yet have an offensive element that takes over when the battle is won by numbers, so watching it trying (or rather not trying) to get rid of the last few enemies can be a bit frustrating. EDIT: v0.6.7 includes an "end game mode", which takes over when the AI side is much stronger than the enemy.

[Anonymissimus]

Posting a replay in which the custom AI is using its melee attack against skeletons.
engine r54124 (win MinGw build)