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

Re: Exercises in Formula and Lua AI

Post by mattsc »

Thanks, guys! Unfortunately, I seem to be a bit slow this morning ...
Sapient wrote:function(self) ... end -- this isn't so bad is it?
Do you mean that what I have there isn't so bad? If so, yeah, I am quite happy with it, given my still tenuous grasp of the language. Thanks. :)
Sapient wrote:Also, you may want to use
filtered_table=v
instead of
table.insert(filtered_table, v)

Is that for performance reasons? The reason why I didn't do that is because 'i' refers to the index of the original table, and I want the one of the new one to be consecutive numerical integers starting at 1. Of course, that's easily done by adding another iteration variable.

Anonymissimus wrote:You should probably not use "self" as the name of a variable or parameter, since self is a special keyword in lua, it is very much like the "this" in object-oriented java and C++, see the usage in data/lua/location_set.lua.

Ok, thanks, I'll check that out. I thought that it refers to the object that holds a method if referred to by that method - which is originally what I thought I was heading for with the code. So I set it up that way to make it clear to myself where I was going with it. But it would still be wrong in that place.

Anonymissimus wrote:Unfortunately, it's not clear enough to me what you want and what the FAI code does for I could post some untested code.

The code I posted inside the spoiler tags already does what I want, I'm just wondering if there's a shorter syntax to call a function like that. I want the filter() function to take a table (any table) containing a number of fields (consecutively numbered by integers), each of which is an table with identical keys. One example would be a table of units. Or the table of src-dst move coordinates that I have in my code. As an example, currently I could select all the injured units of Side 2 with my code by doing this (untested):

Code: Select all

    local s2_units = get_units { side = 2 }
    local injured_units = filter(s2_units, function(tmp) return tmp.hitpoints < tmp.max_hitpoints end)
What I am trying to figure out is if I can define the function so that I can safe the 20 or so key strokes to put the function() ... end into the call. Ideally, I'd like this:

Code: Select all

    local s2_units = get_units { side = 2 }
    local injured_units = filter(s2_units, hitpoints < max_hitpoints)
but this would be good too:

Code: Select all

    local s2_units = get_units { side = 2 }
    local injured_units = filter(s2_units, tmp.hitpoints < tmp.max_hitpoints)
As I said, this isn't all that important (the function doesn't save that much programming anyway), it's mostly interesting to me for figuring out what can be done. Thanks again.
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:The reason why I didn't do that is because 'i' refers to the index of the original table, and I want the one of the new one to be consecutive numerical integers starting at 1.
That's a good reason an Sapient apparently overlooked it...
I thought that it refers to the object that holds a method if referred to by that method - which is originally what I thought I was heading for with the code.
That is afaik exactly what it does if you look at location_set.lua and check out its methods.

Look at the function table.sort which is an "official" lua function, it takes a function as an argument to describe the sorting condition, not a conditional expression. So afaik there is no way to make this shorter.
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
User avatar
Sapient
Inactive Developer
Posts: 4453
Joined: November 26th, 2005, 7:41 am
Contact:

Re: Exercises in Formula and Lua AI

Post by Sapient »

Yes, I was aware that filtering that way would remove numbers from the sequence. Tables are not always simple lists and they may be associative maps a.k.a. dictionaries. So if you are creating a library and provide a generic "filter" function, it may be more desirable to preserve dictionary keys than to return unbroken numeric sequence of keys. You could re-key them with a separate function call. Just a thought.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
mattsc
Developer
Posts: 1174
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:Look at the function table.sort which is an "official" lua function, it takes a function as an argument to describe the sorting condition, not a conditional expression. So afaik there is no way to make this shorter.
Ah, yes. If the built-in library functions do it that way, that's probably how it should be done. Good, looks like I've done it "right" then.
Sapient wrote:Yes, I was aware that filtering that way would remove numbers from the sequence.
I didn't mean to imply that you weren't, sorry, just saying why I had done it that way. And I was wondering if there was a different reason that I wasn't aware of.
Sapient wrote:Tables are not always simple lists and they may be associative maps a.k.a. dictionaries. So if you are creating a library and provide a generic "filter" function, it may be more desirable to preserve dictionary keys than to return unbroken numeric sequence of keys. You could re-key them with a separate function call. Just a thought.
Good point. I guess (so far) I was only looking at this for a very specific reason, to use it for candidate action move evaluation in Lua AI (and that's really what I meant the "library" to be for, an optional set of functions for 'ai': 'ai.ai_helper' or something). I guess I assumed that something I can write that easily would have been done many times over already and be way too trivial to be of general interest. ;)

Thanks again, to both of you.

PS: I have now confirmed that the 'injured_units' code works, just that it needs to be 'wesnoth.get_units', of course.
mattsc
Developer
Posts: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Lua AI: use of location_set

Post by mattsc »

I am ready to dive deeper into Lua AI and am trying to wrap my head around the intended use of location_set. If I understand this right, I could implement my example of the Swamp Lurker moves using such sets. As a reminder, lurkers are dumb, impulse-drive creatures that move as follows:
- They can move across most terrain, but only stop on swamp
- All lurkers move individually, there is no strategy
- If there are enemies within reach (next to swamp terrain), a lurker will attack the unit with the fewest hitpoints
- If no unit is in reach, it will move to a random reachable swamp hex.

So, I think I could implement that using location set as follows:
- Create a set of all hexes a lurker can reach (with wesnoth.find_reach)
- Create a set of all empty swamp hexes next to enemies (using a location filter), and assign the hitpoints of the adjacent enemy unit (well, minimum of all adjacent units; which, I guess, could be done by the union of sets of adjacent hexes around individual enemy units) as data to the set
- Find the intersection of those two
- If intersection ~= nil: find lowest data (=hitpoints) value, move and attack there
- if intersection == nil: draw random location from first set and move there

This seems easy enough, but there are also a bunch of other ways to implement this. My questions:

1. Is something along those lines what location sets were created for?

2. Is this an efficient way of doing this? This is a pretty trivial example, but one could easily imagine to, for example, assign certain values to all locations on the map to tell the AI how much it should try to move there for attack/defense/retreat purposes.


EDIT: Out of curiosity, I coded the above using location sets. (Well, I implemented it slightly differently, but the principle is the same.) As expected, it works just fine, but my question as to whether this is an appropriate use of location sets remains.
Spoiler:
mattsc
Developer
Posts: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Next question: I seem to be missing something, somewhere... The following sample code:

Code: Select all

    local my_reach = {}
    for x = 1,2 do
        for y = 1,2 do
            my_reach[x*10 + y] = x*10 + y
            print(my_reach[x*10+y])
        end
    end
gives the expected output:

Code: Select all

11
12
21
22
However, when I am trying to use a table as key (which I thought I am allowed to do), I can make the assignment, but cannot pull the information back out. Code (this uses debug_utils from WLP):

Code: Select all

    local my_reach2 = {}
    for x = 1,2 do
        for y = 1,2 do
            my_reach2[{x=x,y=y}] = x*10 + y
            print(my_reach2[{x=x,y=y}])
        end
    end
    --debug_utils.dbms(my_reach2,false,"variable",false)

    for k,v in pairs(my_reach2) do
        debug_utils.dbms(k,false,"variable",false)
        print(v,"\n")
    end
produces:

Code: Select all

nil
nil
nil
nil
variable is of type WML table, value table: 0x2754d400, length 0:
{
    y = 2,
    x = 2
}
22	

variable is of type WML table, value table: 0x27553840, length 0:
{
    y = 2,
    x = 1
}
12	

variable is of type WML table, value table: 0x27557fc0, length 0:
{
    y = 1,
    x = 1
}
11	

variable is of type WML table, value table: 0x27551980, length 0:
{
    y = 1,
    x = 2
}
21
[Note: I also tried print(my_reach2[{x=1,y=1}]) (hardcoded 1's) with same result.]

So, it looks to me that table my_reach2 is populated correctly, but that I cannot access the values except by iterating over the array with pairs(). What I would like to do eventually is something like

Code: Select all

my_reach[{x=x1,y=y1}] = my_reach[{x=x1,y=y1}] + some_function(x1,y1)
inside a loop that iterates over a different array (which does not seem to work). I could accomplish this through the first method above, but that would always involve calculating a single index from the x and y coordinates. Not a big deal if that is the only way to do it, I am just wondering if I am doing something wrong with the other method. Thanks.
User avatar
8680
Moderator Emeritus
Posts: 742
Joined: March 20th, 2011, 11:45 pm
Location: The past

Re: Exercises in Formula and Lua AI

Post by 8680 »

{...} isn't a table literal, it's a table constructor. Each {...} expression creates a new table somewhere in memory, and returns a pointer to that table (which is the hexadecimal number you get by printing a table). When you pass tables to functions or assign them to variables, you're actually passing/assigning pointers to tables (tables use call-by-reference semantics). When you compare tables (including using them as keys), you're actually comparing pointers to tables (tables use physical equality). (See also TablesTutorial, especially the third subsection from the bottom.)
Last edited by 8680 on December 2nd, 2012, 5:50 pm, edited 2 times in total.
mattsc
Developer
Posts: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Oh, right... I remember that now. Thanks a lot!
Anonymissimus
Inactive Developer
Posts: 2460
Joined: August 15th, 2008, 8:46 pm
Location: Germany

Re: Exercises in Formula and Lua AI

Post by Anonymissimus »

This code snippet visualizes it, explanation see 8680.

Code: Select all

	dbms({x=1,y=1}, false)
	dbms({x=1,y=1}, false)

	local my_reach2 = {}
	for x = 1,2 do
		for y = 1,2 do
			local index = {x=x,y=y}
			my_reach2[index] = x*10 + y
			dbms(my_reach2[index], false)
		end
	end
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: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Yeah... Thanks! That's not practical for what I want to do, so I'll go back to the single numerical index (which isn't a problem).
mattsc
Developer
Posts: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Requesting help with ideas for alternative AI actions/behavior

I'm in contact with Crab about testing/debuging Lua AI. I figure that the best way of doing that is to actually write some AI candidate actions of my own, beyond the toy examples I have dealt with so far. Rather than simply replicating what the default Wesnoth AI does already, I would prefer to write something different. What I would like to hear are ideas for:

1. What alternative AI behavior would be interesting to people -- the more specific the better; I can do the coding, but if the idea could be expressed in a set of clear instruction, ideally even in equations or pseudo code, that would be much preferable over vague directives like "avoid enemy as much as possible" or "move units to favorable terrain". [No guarantees that I will act on any of the suggestions, in part because I might be to dumb to implement them, but I'd like to hear what others are thinking.]

2. Defensive unit placement: Thinking about why I can usually easily beat a significantly stronger (richer) AI under otherwise equal conditions, I believe the main difference is unit placement (in combination with the decision when it is advantageous not to attack), in particular when it comes to placing groups of units in formation (lines, hedgehogs, ...) on favorable (or the least unfavorable) terrain. So this is what I have started to look into. I'd like to come up with a "defensive unit placement" candidate action that complements or replaces combat under certain conditions (tbd), in which the AI doesn't attack, but places units within range of enemy units in as strong a formation as possible. (This is similar to the retreat CA, but not quite the same.)

I'd like to stick with the KISS approach here: I have neither the experience nor the time to come up with a full pattern recognition solution (or whatever is best here), and the brute-force try-all-combinations approach is not possible because of the sheer number of possible moves. What I am trying to come up with is a somewhat "intelligent", but still reasonably simple and quick (in terms of computation time) method of placing groups of units that gives a somewhat better solution than placing each unit individually. (And some of that is already done in the default AI, but I am not sure yet to what extent.) I will make a separate post in a little while about what I have done to that effect so far. Any comments on that or different ideas would be much appreciated (or pointers as to where this has been done already).


PS: I've read all (well, at least a lot of) the documentation on 'modifying AI', 'why writing an AI for Wesnoth is difficult' etc., including this thread. I have also looked at the C++ code used by the default AI, although I have not digested all of that yet. I am not suggesting that anything coming out of this will be better than what the Wesnoth AI does already -- I think it really does a great job, especially for an AI that has to deal with such a varied set of conditions. But ideally this would result in a set of alternative candidate actions that scenario designers could use to invoke special non-standard AI behavior under more specific circumstances (which is my interpretation of why Formula AI and Lua AI were created in the first place). That's much more ambitious than what I want to accomplish at this time though...
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 have one scenario in my campaign where the AI is supposed to perform a "moveto-goal". Basically what the player does with Konrad in HttT scenario 1.
I'm currently doing it with complicated wml.
-If you're free to move, move towards the goal hex.
-If you're wounded, heal until full health in one of some defined villages, then move again.
-If you're trapped, don't do anything.
That's about the minimum requirements.
If possible, things like
-Don't move too quickly away from friendly units into the direction of many enemies.
-If possible and this doesn't slow down moving towards the target hex, attack with no retaliation.
could be done.
Actually I've always wanted to try coding this but shied away from it due to the lua ai being supposedly buggy and needing to learn something new.

If you use the lua AI I'm sure Crab will be happy about your bug reports. ^_^
Also, I you code the above then I will probably be motivated enough to take it on after your pre-work. ^_^

EDIT
Also, the heal aspect could be extended:
For certain units (specified by a SUF), in case they are wounded (dangerously wounded ?), move them to a (save, predefined ?) village until they have full health again.
This is useful for scenarios where certain units on AI side should or have to stay alive (and there are many of such scenarios).
I'm also doing this with complicated WML currently.
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: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

Taking this somewhat out of order:
Anonymissimus wrote:If you use the lua AI I'm sure Crab will be happy about your bug reports. ^_^
I switched from FAI to Lua AI based on Crab's comments a few weeks ago, among other things for that reason. :)
Anonymissimus wrote:Actually I've always wanted to try coding this but shied away from it due to the lua ai being supposedly buggy and needing to learn something new.
Lua AI still has some bugs and a few missing pieces, but a lot of it is working already and for most of the rest there are easy workarounds for the time being. So I think a lot of what you write could be done in its current state. In fact, the first 4 points should not be too hard at all. The combat action might or might not be easy (with the current state of lua ai), depending on what exactly you need.

In any case, this sounds like an interesting problem to look into. I'd need a bit more details to be certain though. Is this a scenraio that's on the add-ons server? If you have it coded in WML already, the easiest is probably for me to look at that.
Anonymissimus wrote:Also, I you code the above then I will probably be motivated enough to take it on after your pre-work. ^_^
Nice. :)
mattsc
Developer
Posts: 1174
Joined: October 13th, 2010, 6:14 pm
Location: Hidden on the hex behind Fred

Re: Exercises in Formula and Lua AI

Post by mattsc »

More details on my dilettante attempts to code defensive unit placement:

To recap, I would like something where units are placed as a group in as strong a defensive position as possible (and hopefully in a stronger position than what would result from placing each unit on its individually preferred terrain). As an example, if playing a saurian side, the AI could decide not to attack a lawful faction during the day, but for some reason retreat is not an option or not desired. Instead, we want to position the units in reach of the enemy, but so that they will suffer the least possible damage on the next enemy turn.

Also, at least for the time being, I am looking for something reasonably simple. A quick and dirty approximate approach that does most of the job is preferable from my point of view over the "ideal" solution. So, here's where I am at with that so far. One could start by analyzing the map at the beginning of the scenario for favorable areas, mark them, and make them goals for later. I'm not really sure how to do that in practice (the identifying favorable areas part, in "real code" terms), so I skipped this. For now. Instead, I am looking at each turn individually, with 2 different (and so far rather primitive) evaluation algorithms.

1. Trying to form lines (approximately) following strong terrain. [Clarification: what one really wants is strong terrain (for our side) next to weak terrain (for the enemy)] In pseudo code, this looks roughly like this:

Code: Select all

- Identify defense of both our units and the enemy for each hex that can be reached by our units, and for the 6 surrounding hexes
- If we want to form a N-S line with the enemy in the west, good target hexes have the following characteristics:
  - Defense is strong on the hex itself
  - Defense is strong on the hexes north and south of it and they each can be reached by at least one other unit of our side
  - Defense is weak for the enemy on the two adjacent hexes to the west
- In terms of an evaluation function, this could look like ('def' being the defense percentage on the given hex):
    value = def_hex + C1 * (def_n * N_n + def_s * N_s) + C2 * [(def_hex - def_enemy_nw) + (def_hex - def_enemy_sw)]
         where N_n, N_s are the number of our units that can reach the hexes in the north and south

- This could be done for all 6 possible orientations of lines, then picking the maximum/minimum/average - which might be useful in scenarios with lots of skirmishers around
- Or one could figure out the main direction in which the enemy forces are located (that's easy) and set up the line perpendicular to it
Anyways, that's just the very beginning, taking only the terrain itself into account. In the end one would want to add additional weighting functions taking into account which of our own and enemy units (how many, how strong, how hurt, ...) could reach those hexes, etc.

2. Trying to form strong clusters of units, again on terrain as strong as possible:

Code: Select all

- For each unit and each hex the unit can reach, add up the following numbers:
  - Defense percentage of the hex itself
  - Defense percentage of all the adjacent hexes that can be reached by other units on our side (times some number btw 0 and 1)
  - Defense percentage of the hex minus def. perc. of any remaining adjacent hexes that can be reached by enemies (times some number).  This means that having enemy units reach the adjacent hexes is actually desirable if they have weaker defense there than our unit on its hex, undesirable if the enemy defense is higher.  In practice, I actually did (def_hex - def_adj_enemy - 20), such that it only becomes an advantage when our unit has at least a 20% better defense stat than the adjacent enemy.

Do this for all units, move unit to highest-rated hex, then repeat analysis.  
This will tend to cluster units together on strong terrain, including also the own castle, which needs to be discouraged, unless it's the desired effect. The same disclaimers of primitivity apply at this time as for the previous method. In this case (or both?), it might be desirable to do a downselect of the highest-rated positions and then do an actual combat simulation for the few apparently best formations for the final decision. In the end, this would ideally also include things like placing healers or units with leadership in protected but effective locations, etc., but one step at a time.

Anyways, those are just a few first ideas (yes, I have coded both of them and they do work - to some extent). If anybody has suggestions on how to improve this, or good reason why it is all nonsense and not worth trying, I'd like to hear that.
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 »

Can I make some reasonably simple requests: First, a guardian-like AI that returns to its post after attacking rather than allowing itself to be lured further and further away.

I'm proposing something that could be called with {GUARDIAN stationed_at_x, stationed_at_y, guarding_x, guarding_y}

Behaviour would be, if anything moves close enough to guarding_x,guarding_y, attack it. If there's nothing close enough to attack, go back to stationed_at_x,stationed_at_y. If there is something, but attacking it would mean you were more than one turn's movement from stationed_at_x,stationed_at_y, then return to stationed_at_x,stationed_at_y instead of attacking. (This is an expansion on the basic idea where stationed_at_ and guarding_ are the same location.)

I'd also like a 'coward' AI special; a unit which tries to move away from any threat(s) to come within a certain range. Basically as close as possible to the opposite of the current Guardian behaviour. This would be useful for things like 'chase' scenarios, animals, neutral observers watching a battle and fleeing if approached, unarmed civilians fleeing at the approach of marauding monsters, and indeed AI soldiers fleeing from a powerful foe.

Rough behavioural algorithm:

For Guardian, as I understand it, guardians remain stationary until one or more units move into their movement range. Then they attack the best of those targets, using the standard AI attack criteria to determine which to choose. Then they sit there at that point until another unit comes in range; they don't return to their posts. So you can lure them across the map by offering them targets to attack.

By comparison, for coward, I suggest using {COWARD seek_x, seek_y, avoid_x, avoid_y, radius}.
When a unit comes within radius hexes of the coward, it moves away from the unit, and if it has a choice of 'away' directions it prefers the ones towards seek_x,seek_y. If it has several movement options, it also chooses the one that keeps it furthest from avoid_x,avoid_y. Any of seek_x,seek_y, avoid_x and avoid_y may be set to invalid values, which means either don't seek or don't avoid any particular hexes.

This gives various behaviour possibilities:

Code: Select all

seek    avoid   behaviour
-----   ------  ----------
on-map  undef   unit flees to the on-map seek location - a village, a keep, the exit hex etc.
undef   on-map  unit moves away from the on-map location towards the map edges and finishes up cowering in a map corner, presumably
on-map  on-map  unit flees to the on-map seek location, by a route that avoids the avoid location as far as possible
undef   undef   unit just moves away from anything that comes in range, without having any directional preference
If you set x but not y or vice versa, you can herd the unit towards or away from a map edge rather than a precise point.

If more than one unit comes in range at the same time, then the unit does its best to move away from all of them, with the seek and avoid hexes (if defined) helping to provide tie-break information.

If a unit overshoots its seek location, it keeps going in a straight line for that turn, but will then try to circle round.

If you set seek and avoid to the same place, seek takes precedence, and you'd get the unit spiralling slowly in, probably a hex a turn.

The seek and avoid hexes are refinements. A basic implementation would just be {COWARD radius}, giving a unit which moves away from anything that comes in range, without having any directional preference.

So there, several requests of varying difficulty for some more refined single-unit behaviour.

Edit: Further behaviour clarification: As for guardian, if there aren't any units in-range, a cowardly unit should just sit there. This is because if you did want a cowardly unit to keep moving, all you have to do is give it a very large threshhold radius, possibly map-sized if you like; the bigger the radius, the sooner it will start to move and the longer it will keep moving.

Edits 2: table tidying
Last edited by Simons Mith on November 14th, 2011, 1:31 am, edited 3 times in total.
 
Post Reply