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.

Moderator: Forum Moderators

Post Reply
User avatar
Simons Mith
Posts: 784
Joined: January 27th, 2005, 10:46 pm
Location: Twickenham
Contact:

Re: Exercises in Formula and Lua AI

Post by Simons Mith »

That seems happy now. Unit behaviour is the same, and the error message has gone. Cheers.

Edit: Here's a new question - What's the cleanest way to turn stationed_guardian and coward behaviour off again?

I've got some escorts taking an NPC to her escape point, but after that I'd like them to go back to just fighting normally. I'm currently doing it by setting a guard radius of 50 and guard and stationed_at point of their original keep.
 
User avatar
Elvish_Hunter
Forum Moderator
Posts: 1444
Joined: September 4th, 2009, 2:39 pm
Location: Lintanir Forest...

Re: Exercises in Formula and Lua AI

Post by Elvish_Hunter »

So, finally I found some time to take a deep look to ai_helper.lua. :oops: I was reading it when I noticed this line: local dstsrc = ai.get_dstsrc() . At http://wiki.wesnoth.org/Customizing_AI_ ... _AI_syntax there is written that...
when writing functions of my_ai, you have access to ai table, which contains the following functions
  • ai.side
  • ai.move
  • ai.move_full
  • ai.attack
  • ai.recruit
  • ai.recall
At this point, I asked myself, "There are any undocumented functions?" So, I added this line:

Code: Select all

for key, value in pairs( ai ) do print( key, value ) end
to the first scenario of ARL, and that was my output:
Spoiler:
Well, it looks like that most Lua AI functions aren't yet documented... Or the documentation is simply placed in a page that I didn't yet find? :hmm:
Current maintainer of these add-ons:
1.14: The Sojournings of Grog, A Rough Life, The White Troll (co-author), Wesnoth Lua Pack
1.12: Children of Dragons
Anonymissimus
Inactive Developer
Posts: 2460
Joined: August 15th, 2008, 8:46 pm
Location: Germany

Re: Exercises in Formula and Lua AI

Post by Anonymissimus »

Well, it looks like that most Lua AI functions aren't yet documented... Or the documentation is simply placed in a page that I didn't yet find?
To find out about them you apparently have to read ai/lua/core.cpp. The according names in the C++ code are in the luaL_reg array from line 579 on, then jump to the function's implementation above.

Documenting this should have been part of Nephro's GSoC project!!!
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: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

This is exactly the way how I found out about the available functions also, and then I've done a lot of trial and error (and a little bit of looking into the C++ code). I do want to work on the documentation of the LuaAI pages also, I simply haven't gotten around to it yet. I think it should be separated from the Customizing AI ... page and put onto LuaAI, so it's a bit more work than just adding a few lines. So far I have only gone through those pages and fixed a few things that were not correct any more (because they describe an earlier version of the AI). I've also bolded the available functions (or my understanding thereof) at LuaAI Functions. I haven't had time for adding stuff yet, but I'll get to it soon. (Btw, links to all these pages are available on my "Practical Guide" page.)

Now, having said that, most of the information is actually on the wiki (just not in one place). The majority of those functions are the 'get_aspect()' type, which is described in the first section of LuaAI. The 4 'get_dstsrc()' variations are not ready to be documented yet, IMHO, because they are buggy. They hang Wesnoth under certain circumstances. I know they hang Wesnoth when there are no units with moves left on the side being queried, but they seem to hang it under other circumstances also that I have not understood yet. So there are only a few undocumented functions overall, I think. I'll work on documenting those soon.
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Simons Mith wrote:Edit: Here's a new question - What's the cleanest way to turn stationed_guardian and coward behaviour off again?

I've got some escorts taking an NPC to her escape point, but after that I'd like them to go back to just fighting normally. I'm currently doing it by setting a guard radius of 50 and guard and stationed_at point of their original keep.
Simons: Sorry, didn't see that question until now (I need to change how I check the forums for new posts!). Hopefully you didn't post it too long ago. And let me know if there's something else I missed.

Umm, that is a good question. The best way of doing it is to remove the candidate action using the method described here. However, you need to know the CA's id for that, which gets set automatically by [add_ai_behavior]. It is possible to extract that information from the side configuration, but if you save/reload in between, the bug I mentioned before with the 'ca_counter' variable might give several CAs the same id, wreaking havoc with that.

So, unless somebody has a better idea, I suggest the following:
- I write an alternative [add_ai_behavior] tag which takes an (optional?) 'id' key, that can later be used for removal of the CA.
- While I am doing that, I can also try to fix the 'ca_counter' bug (and make that variable unnecessary in the first place).
- I then modify the COWARD and STATIONED_GUARDIAN macros to provide that id information, and add REMOVE_... macros.

Comments, anyone?? Thanks.

EDIT: Of course, since all [add_ai_behavior] does is call [modify_ai] with a bunch of keys, I don't actually need to fix the former in order to change the macros . :doh: So I'll update the macros to use the [modify_ai] tag and add the REMOVE_... macros.
I still think that [add_ai_behavior] should be changed because the save/load problem should be fixed. I'll submit a bug report for that with the suggested change.
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Simons: I updated the coward, return guardian and stationed guardian macros. Internal (=invisible to the user) changes were made to the preload and unit macros. The latter were also renamed following your usage from a few posts ago.

The biggest change is that there is now an UNDO_... macro for each kind of AI special that can be put into an event (or any ActionWML) to turn the behaviour off again for a unit. They are one-line calls to another macro (so it's really pretty bad style), but I added them anyway so that the scenario designer does not have to look into the macros in order to find the candidate action id.

The new macros are up at the Lua AI Code Library. I hope this works for what you had in mind.


Oh... I just thought of something. I think the new macros will currently only work if the unit id does not have spaces in it. This can easily be changed by placing some "" or '' in the right places, but I don't have time to test that right now. If you want to use the new macros today, please use units with space-less ids. I'll make that modification tonight or tomorrow and add an edit to this post when it is done.

EDIT: No, I was wrong. It works without modification with unit ids that contain spaces.
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Lua question: is it possible to calculate the hexes Unit 1 at (x1,x2) could reach if enemy Unit 2 were at (xh,yh), rather than at (x2,y2) where it currently is? I would like this done taking ZoC into account and without a visible change on the map.

This would be useful for questions like: where do I have to move my units in order to block the enemy from getting to my leader? I think this is equivalent to asking whether it is possible to work on a virtual map. The C++ AI code does something like that, but I haven't found a way to do this with Lua.
Anonymissimus
Inactive Developer
Posts: 2460
Joined: August 15th, 2008, 8:46 pm
Location: Germany

Re: Exercises in Formula and Lua AI

Post by Anonymissimus »

mattsc wrote:Lua question: is it possible to calculate the hexes Unit 1 at (x1,x2) could reach if enemy Unit 2 were at (xh,yh), rather than at (x2,y2) where it currently is? I would like this done taking ZoC into account and without a visible change on the map.
I don't think so.

However, I digged a bit in the commit history. Obviously the pathfinder lua functions were coded at a time the private lua proxy units were not yet available so your problems of "on-map unit overwrites a private one at the same location" simply weren't taken into account. I was afraid silene might have had a particular reason for such limitation...

For 1.11 I can imagine that lua coders would be allowed to set up sort of a private unit map with private lua proxy units which can then be passed to the pathfinder. And none of the units currently on the game map would matter any more. From what I can tell the whiteboard is doing something similar.
There could be a userdata type with metatable unit_map (a C++ unit_map hold by the lua intderface), which can be created, addded units to, removed units from and passed to the pathfinder functions.
Of course that has great potential of introducing bugs since the pathfinder is called from everywhere in the engine and we need to discuss such an idea with Crab.

As for 1.10 I suggest adding/removing on-map units. Perhaps some fake units which are hard to see (Fog Clearer, no ellipses, no hp bar etc or hiders) are your friends.
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: 1171
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:[snip]
As for 1.10 I suggest adding/removing on-map units. Perhaps some fake units which are hard to see (Fog Clearer, no ellipses, no hp bar etc or hiders) are your friends.
Thanks, that's what I thought. I am wondering how much slower it is to put units on the map than simply doing it in memory, but then, I have a lot of very basic testing to do for which this really doesn't matter. Even just changing the coordinates in the proxy tables of existing on-map units and watching them jump around erratically is fine for that, as most of it will be done with only a few units on the map. Being allowed to do what you suggest by 1.11 is probably good timing for me anyway.

EDIT: To answer my own question, this code snippet:

Code: Select all

for n = 1, 10000 do
    for x = 1, w do
        for y = 1, h do
          wesnoth.put_unit(x, y, unit) 
        end
    end
end
placing a unit 10,000 times on each hex of a map takes just over 2 seconds, as the graphics are not updated until afterward. It's a very small map, granted, only 24x12, but still, it looks like computation time won't be problem for the testing I want to do.
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

I could use some help. I've been on and off working on a "defensive unit placement" algorithm: placing units in as strong a formation as possible, taking terrain into account, without the intent of attacking on this turn, but preparing for an attack of the opponent on the next turn. I've made some progress with this, I can identify lines (straight and somewhat bending) of strong terrain for my units next to weak terrain for the enemy, but I am kind of stuck on how to proceed.

So, I could use some help with ideas, references, brainstorming etc. on how to develop algorithms that do this. I've searched around a bit and found some information on influence, tension and vulnerability maps, but most of the references I found are along the lines of "you set up some position evaluation algorithm and then you use our new and improved and world-changing method to improve the AI by another 5%". Nobody ever seems to talk about how those position evaluation algorithms work, at least not for turn-based strategy games like Wesnoth. (There seems to be a lot more info on real-time strategy games.)

Any pointers on what to read would be great. Any offers to discuss ideas with me would be fantastic.

It would also be helpful if somebody were willing to test the algorithms under different conditions, and/or tweak and change them as needed, but what I have so far might still be too basic for that to be fun...
User avatar
Simons Mith
Posts: 784
Joined: January 27th, 2005, 10:46 pm
Location: Twickenham
Contact:

Re: Exercises in Formula and Lua AI

Post by Simons Mith »

Interesting question. I can't give you any specific pointers, but here's what my general approach would be. I doubt I'll be suggesting anything particularly novel, but here goes anyway:

If I was going to try to code such a thing for myself, my first priority would be the same as yours - identifying lines of good terrain for your side next to bad terrain for your opponent. After that, I think I'd start looking at the following things:

Which parts of the line are most and least crucial? Which parts of the line are the most and least vulnerable? What areas are special, in that they are weaker or stronger than the average for the line?

The usual priorities for 'crucial' parts of the line are the ends and the centre. The ends because enemies can wrap around them, the centre because if the centre breaks you risk your forces becoming split and being defeated in detail. So if an end can be 'lapped round' it gets a higher priority, if it can't its priority is lowered slightly. If there are vulnerable units nearby behind the centre, the centre gets higher priority. What needs to be done about 'higher priority' areas is discussed shortly.

Another area that needs a priority boost is sticky-out hexes (when you've got a not-quite-straight line and a hex can be attacked by three or more opponents. Areas where your units are weaker may need extra attention. Areas where your terrain is slightly less favorable than elsewhere, or the enemy's is better are also possible weak points.

So anyway, one way or another you're going to have a list of hexes that are flagged as higher or lower priority than the average. What factors you cover may vary, but the end result should be a rough list of priority scores for your line, maybe something like this for an eight-unit line. Imagine this is dwarves vs mermen, to make things more concrete:

Terrain: 1-1-1-1-2-1-1-2 (line of mountains, but a couple of hexes which are hills)
Enemy terrain: 1-1-1-2-1-1-1-1 (mostly plains, but one shallow water hex)
Exposure: 0-1-1-1-2-1-1-2 (left side pretty safe, center has some vulnerable units, right side 'lappable')
Available units: 0-1-1-1-2-1-1-1 (strong third level unit available for left hand side; available centre units all wounded)
Available enemies: 2-2-2-2-1-1-1-2 (enemy has skirmishers available on left side, unit with magic attacks on right)

Tot up the scores and you get 4-6-6-7-8-5-5-8

From which you conclude you need the toughest possible right-hand anchor unit, two tough units in the center, you can put anything you want on the far left, and provided you have a strong centre and RH anchor, you can afford to use slightly weaker units on the right side than on the left. So now you have qualitative answers to basic operational questions like 'should I send the quick units left or right?' 'Where would a leader help?'

You can also grade your units once you've placed them, according to their hitpoints, level, experience, abilities or whatever else matters to you, and anywhere there's a mismatch between what you have and what you want, you know you're using too weak or too powerful a unit. This is partly a dynamic process; sometimes you do want the strongest possible units to do a particular job, whereas other times all you need is strong enough, and knowing you can withdraw some over-powerful units, or not waste time sending too many weak units could also be useful.

You can add grading for anything you can think of in this way - time of day, leadership, illuminates, healers on either side. You could grade things in terms of number of hits to kill, number of points of damage expected, and so forth. You can also identify spots where the odds are so heavily stacked against the unit that anything sent there could die. In which case you could either send a tough unit about to level, or an expendable.

An approach like this has the advantage that you can 'plumb in' evaluation functions one at a time as you write them, and then all you have to do is worry about tuning the weightings. You can also use different functions in different circumstances.

Note how the way I've scored the skirmishers has pushed a 'demand' for stronger units to the left flank. One might think that against skirmishers, quick units might actually rate higher, but the algorithm given here prioritises using tougher units that would presumably have a better chance of surviving being swarmed. That might not be the right thing to do, but at least it's now clear where the decision is coming from.

Putting my thoughts down like this does lead me to think a single one size fits all algorithm would be terribly complicated. Lots of little algorithms, each evaluating one aspect of the contest and then adding a weighting to the final score would indivdually be simpler. If they all disagree, then they'll more or less cancel out and you'd spread the forces more or less equally. If they all agree that one or two hexes are particularly important or dangerous, then you're got some useful information to determine where you send which units. What's more, even though the basic principle is the same, I would expect different deployment behaviour for a force of horsemen, say, compared to a force of dwarves, and you could hopefully achieve this by applying different weightings depending on your force composition. It also seems to me that this is one of those open-ended projects which can become as complicated as you care to make it. Picking the best factors to score on and discarding the less important ones is going to be important to avoid getting a needlessly slow solution.
 
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Thank you very much for writing all of this down, Simons! It will take me some time to digest all of this and think about how to implement it in practice. For example, one of the things that are unclear to me is how to do things like
"Available units: 0-1-1-1-2-1-1-1 (strong third level unit available for left hand side; available centre units all wounded)"
and
"Available enemies: 2-2-2-2-1-1-1-2 (enemy has skirmishers available on left side, unit with magic attacks on right)"
since often most units can reach many spots along the line (especially skirmishers).

In one of my functions I have done this by simply taking the average of all units that can reach a certain hex (since you won't know exactly what the enemy will do); or one could use the worst-case scenario for each hex (a min-max sort of approach). But the latter would be unrealistic if, for example, the enemy had one really strong unit and a lot of weak units. Even if the strong unit could reach all 8 spots along the example line above, it would be grossly overrating the enemy forces if we assumed that this unit would, in fact, be the enemy faced at each of those hexes. These are the kinds of things I am playing with right now.

I agree with a lot of the things you are saying, in particular that individual evaluation functions should be used that then get added (or multiplied) with weighting functions that can be adjusted etc. That's the approach I have taken so far. I also think that the first examples should be very simple. For example, currently I am doing all my tests with L1 saurians only (both for my own units and the enemy). That way I can use the same terrain rating, unit weighting etc. for all of them. Once I have understood what the important factors for equal-unit positioning are, the extension to different unit types will make the code more complicated, but will (hopefully) be reasonably straight forward. I'm trying to follow the Wesnoth KISS philosophy as much as possible.

And just to give you an idea what I am doing to find the lines of strong terrain. I first calculate several types of influence (and tension and vulnerability) maps. See the first attached file which shows a combined influence map of my units and enemy units. The higher the number at the bottom of each hex, the stronger the "influence" of my units. The lower the number, the stronger the enemy. You need this as you want to set up your lines of defense (roughly) perpendicular to the direction in which this value decreases the most (largest gradient).

To get the terrain rating of a hex, I then add several evaluation functions, together with certain weights:
  • Strongest weight for defense rating of the hex itself
  • About half that weight for enemy defense rating on the two hexes on the "enemy side" (on the left for most hexes in this example); also, this weight coefficient is negative, as strong defense rating for the enemy is bad
  • Also about half that weight for my own units on hexes "on either side" (top and bottom in this example)
  • I also add in the influence function itself, multiplied by a very small number (0.01 or so). This is meant both as a tie breaker and to set offensive vs. defensive behavior. If the number is positive, positions away from the enemy are favored, the opposite for negative values
All of the weights are variables that can be adjusted easily to experiment with the effect of the individual functions.

If you do that, you get something like the ratings in the second attached file. You can see that you don't want to go to the hexes that have the individually strongest rating, but areas that have a number of strong hexes roughly equal to the number of units you want to position. Thus, in this example, you can see that this is the swamp area just below and to the right of the center - which is probably also what I would choose if I were to place the units myself.

You can also immediately see a weakness of this approach: the hex below the ice hex does not get a particularly high rating, although it might be quite a useful position to take, especially if the enemy does not have skirmishers.

Anyways, this is very interesting stuff, IMHO. Thanks again for writing down your thoughts! I'll think about what I can do with that. If you have more comments, or anybody else, please keep them coming. The more people chime in on this, the better.
Attachments
Influence map
Influence map
Terrain rating
Terrain rating
User avatar
Elvish_Hunter
Forum Moderator
Posts: 1444
Joined: September 4th, 2009, 2:39 pm
Location: Lintanir Forest...

Re: Exercises in Formula and Lua AI

Post by Elvish_Hunter »

mattsc: recently I had to fix a bug in LoW, Ka'lian Under Attack, and this required me to modify the Lua AI code for that scenario. You may be interested in updating your Lua AI Code Library page then. :)
Current maintainer of these add-ons:
1.14: The Sojournings of Grog, A Rough Life, The White Troll (co-author), Wesnoth Lua Pack
1.12: Children of Dragons
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Will do. Thanks.
EDIT: Done
mattsc
Developer
Posts: 1171
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Hey All, dumb Lua question: I am trying to test whether a unit has a certain ability. When I use

Code: Select all

wesnoth.unit_ability(u, "teleport")
on a Silver Mage, I get 'true', as is described here. When I try the same with either "cures" or "curing" (the name and id of the ability) on a White Mage, or "leadership" on a Sergeant, I always get 'false'.

I found somewhere in the forums that it supposedly doesn't work for healing/curing, but I did not understand the reason. And I did not see anything about leadership. Is there any way to make this work? I guess I could manually dig into the saved unit's table, but since the function exist, I'd rather use that, if possible.

Thanks!
Post Reply