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

Discussion of all aspects of the game engine, including development of new and existing features.

Moderators: Forum Moderators, Developers

Post Reply
mattsc
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Alarantalara wrote:
mattsc wrote: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.
Alarantalara wrote: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.
Alarantalara wrote: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 ...
Alarantalara wrote: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.
Alarantalara wrote: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
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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
User avatar
Alarantalara
Art Contributor
Posts: 784
Joined: April 23rd, 2010, 8:17 pm
Location: Canada

Re: Exercises in Formula and Lua AI

Post by 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
Attachments
AI-demos-Messenger_Esc..._replay.gz
(9.04 KiB) Downloaded 109 times
mattsc
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Alarantalara wrote:I've tried it out a few times now and I'm very impressed.
Thanks. :D 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.
Alarantalara wrote: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.
Alarantalara wrote: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.
Alarantalara wrote: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.
Alarantalara wrote: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!
User avatar
Rigor
Posts: 941
Joined: September 27th, 2007, 1:40 am

Re: Exercises in Formula and Lua AI

Post by 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:


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
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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. :oops: :lol2:

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
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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. :)
Last edited by mattsc on April 20th, 2012, 1:52 pm, edited 1 time in total.
Anonymissimus
Inactive Developer
Posts: 2460
Joined: August 15th, 2008, 8:46 pm
Location: Germany

Re: Exercises in Formula and Lua AI

Post by 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.
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml startersPlan Your Advancements: mp mod
The Earth's Gut: sp campaignSettlers of Wesnoth: mp scenarioWesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
mattsc
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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. :D 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
Inactive Developer
Posts: 2460
Joined: August 15th, 2008, 8:46 pm
Location: Germany

Re: Exercises in Formula and Lua AI

Post by 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. :)
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml startersPlan Your Advancements: mp mod
The Earth's Gut: sp campaignSettlers of Wesnoth: mp scenarioWesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
mattsc
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Anonymissimus wrote: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
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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
Developer
Posts: 1166
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by 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
Inactive Developer
Posts: 2460
Joined: August 15th, 2008, 8:46 pm
Location: Germany

Re: Exercises in Formula and Lua AI

Post by Anonymissimus »

Posting a replay in which the custom AI is using its melee attack against skeletons.
engine r54124 (win MinGw build)
Attachments
AI-demos-Prune_Cart_replay.zip
(23.3 KiB) Downloaded 75 times
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml startersPlan Your Advancements: mp mod
The Earth's Gut: sp campaignSettlers of Wesnoth: mp scenarioWesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
Post Reply