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

[mattsc]

In other words, I want all units that can attack him to do so, even if there is a more attractive target available (by the default evaluation algorithm), before considering other enemies. How do I do that?

Is the "leader_value=" key from the old [ai] tag supported by the new AI? Maybe try assuming "leader_value" is a simple aspect and give it a value of 100 or something?

It is, I believe, and that does work to some extent, but it isn't quite what I want. First, I want to be able to use this on non-leader units as well, and also on entire groups of units (such as one specific enemy side over all others, or all the undead out of a mixed orc-undead army). Second, if the AI has the choice of making an easy kill on a different unit (incl. thru attack combinations) vs. attacking the leader with no chance to kill, it will often do the former (no matter how high leader_value is). So it won't always attack the leader, which is what I want (in this case; there are other cases where the other behavior would be preferable). Thanks for the suggestion though, I hadn't considered that (recently).

[mattsc]

Is the "leader_value=" key from the old [ai] tag supported by the new AI? Maybe try assuming "leader_value" is a simple aspect and give it a value of 100 or something?

I looked into this some more and I got very confused. These aspect values seem to be still valid in the new AI, however, when one uses the latest version (10710), it appears that they are not set correctly if simply included in the side definition. For example, look at this very simple side AI definition:

Code: Select all

        [ai]
            version=10710
            aggression=0.222
            caution=0.111
        [/ai]

This, if placed inside the side definition, results in 'aggression' and 'caution' being set to the defaults, not the values assigned here. By contrast, if the version line is commented out, it works as expected.

On the other hand, setting 'aggression' and 'caution' inside a [modify_side] tag in an event works just fine even with version 10710. As does using the [aspect] tag inside the side definition with the "lua" engine (I couldn't get it to work with the "fai" or "cpp" engines).

Does anybody understand this? Is it the desired behavior and if so, why? Wouldn't it be advantageous to be able to set the aspects as in the old version, by simply including them in the side definition?

EDIT: PS: ... but if I define the aspects for the lua engine, they do not apply to the cpp engine and the normal candidate actions. Thus, I conclude (so far?) that it is not possible to define simple aspects inside the side definition if version 10710 of the AI is used. It has to be done separately in an event. Is that correct?

[JaMiT]

Second, if the AI has the choice of making an easy kill on a different unit (incl. thru attack combinations) vs. attacking the leader with no chance to kill, it will often do the former (no matter how high leader_value is).

Well, as a general principle (applicable to strategy games as a whole, not just Wesnoth), taking out a lesser unit is usually a better long-term plan than merely injuring the true goal. There are, though, cases when this does not apply (weakening the leader to the point where it might be killable next turn -- i.e. long-term is not a consideration -- comes to mind), so... I would not be surprised if the default AI puts too much weight on kills. I can understand the extra weight to some extent, but it might be too much for custom AIs. Just how high did you try setting leader_value?

Of course, there is still your question about targeting a unit that is not the leader. I wonder if the behavior you saw with the [goal] tag is a bug? It seems a bit strange to have the movement phase devote a bunch of resources to pursuing a unit, only to have those resources distracted at the last moment. If the [goal] tag were to affect attack selection as well as movement, maybe it could be given a key that could offset the weight given to kills? I suppose the value= key could be used, but I see two distinct situations here -- first, preferential targeting, where killing non-preferred units is still desirable for long-term strategy; second, near-exclusive targeting, where killing preferred units should be considered akin to a victory condition. Could a high enough value= sufficiently offset the bias towards kills to give the second situation? Is the second situation common/fun enough to warrant special consideration? (I'm thinking in terms of bug/feature request. As an exercise in AI, I find it to be an interesting enough situation.)

I guess this post is more thoughts and questions than answers, but hopefully it still manages to be useful.
I wonder how easily I could locate the weight the AI gives to kills...

Edit: I scanned what might be the right source code (so don't take this as even moderately reliable), but it looks like 100 is way too low a value to offset the preference for kills. As a rule of thumb, 20 times the cost of the easily-killed unit might be in the ballpark. So for the wizard-protecting scenario, setting leader_value=280 might be high enough to ignore potential kills of spearmen and bowmen, while 700 might be needed to ignore killing the lieutenant. But it's a floating point value, with a maximum of what, over 10300? If it's just to see what can happen, why not 10,000 or a million or something even higher? Then again, maybe you tried that? You did say "no matter how high"; I'm just naturally skeptical in the absence of specifics.

Edit 2: It might be nice to have a guideline like this pinned down. This would be like an "effective maximum", which might help people pick an initial value for their scenarios. (That's "initial" in the sense of "before balance testing" -- not totally necessary, but it could reduce the balance testing involved.)

[mattsc]

Taking things a bit out of order:

I guess this post is more thoughts and questions than answers, but hopefully it still manages to be useful.

Yes, absolutely. Thanks!

Let me start with a disclaimer: I did not write any of the AI C++ code, nor was I involved in its development. So most of what I know comes from some sort of secondary information (wiki, questions on the forums, ...) or reverse engineering (trial and error, inexpert checking of the source code, ...). There's still lots that I don't know and I frequently (easily?) get confused. As I was in part in my reply to you yesterday...

One of the things that often causes confusion (it definitely did for me) is what goals and targets mean: they only affect the move-to-targets phase, and have no effect whatsoever on the attack or combat phase. Everything you set with the [target] and [goal] tags only has an influence on where units are going to go if they cannot attack on that move. It's that way by design and supposed to be like this -- although it's an interesting question whether such a capability should exist for the combat phase as well.

The part I was confused about yesterday: 'leader_value' also applies only to the value of an enemy leader as a goal for the move-to-targets phase. So unfortunately we cannot use it for what I want to accomplish in 'Protect the Wizard' (even if I'd just want to apply it to leader units).

Well, as a general principle (applicable to strategy games as a whole, not just Wesnoth), taking out a lesser unit is usually a better long-term plan than merely injuring the true goal. There are, though, cases when this does not apply

Agreed.. This is not an attempt to create an overall strategy that does better on average than the normal AI. It's more of an exercise in how can I make it do this.

Just how high did you try setting leader_value?

You did say "no matter how high"; I'm just naturally skeptical in the absence of specifics.

Yeah, well, I guess I was exaggerating a little. I didn't go to 10300, but I tried it with 10,000. But then, for the reasons described above that was pointless anyway.

It might be nice to have a guideline like this pinned down. This would be like an "effective maximum", which might help people pick an initial value for their scenarios. (That's "initial" in the sense of "before balance testing" -- not totally necessary, but it could reduce the balance testing involved.)

That's a good idea. I will add it to the roughly 10300 things I want to add to the wiki. Sometime. When I get bored...

So having said all this, I figure I should also explain how I did implement this option in 'Protect the Wizard'. I'll put that in spoiler tags though, as this post is already long enough.

Spoiler:

The thing you can do with the 'attacks' aspect is to specifically include/exclude units from the combat phase. I am using this in order to make the wizard the only target when there are units left to attack him, and impose no attack restrictions when no attacks on him are possible.

In practice, I do this with an additional Lua CA with the following properties:

• It always returns score 0 which means two things: 1. It will never be executed, 2. It will never be blacklisted.
• During the evaluation, it checks whether any of the AI's units can still attack the wizard. If so, it sets 'attacks' so that only he is a permissible target. If not, the 'attacks' aspect is deleted making all enemy units attack targets. This is not a change of the gamestate, only of the parameters used to evaluate the potential moves and is therefore legal. (But it is what I referred to as somewhat perverted - in the sense of 'deviating from its intended use')
• Then, after this evaluation, if the combat phase has the highest score, it will be executed with those settings of the 'attacks' aspect.
• The downside is that this only works for sure if we set 'aggression=1' and 'caution=0', at least during attacks on the wizard. And that part is not quite working in v0.4.6 yet because of the problem described in my post from earlier today. I'll upload a new version after I've done a few more tests.

EDIT: v0.4.6a now includes the workaround for the apparent bug(?) in how 'aggression' and 'caution' are (not) set. It now works as I imagined (for the 'priority attacks' on the wizard, that is; the 'protect the wizard' part is still rather primitive -- but amazingly effective for something that simple)

[JaMiT]

One of the things that often causes confusion (it definitely did for me) is what goals and targets mean: they only affect the move-to-targets phase, and have no effect whatsoever on the attack or combat phase.

Looking at AI goals in the wiki again, I think I see where some of this confusion comes from. That article currently states "All the markers from different goals are added together and used by certain parts of the ai (in particular, by movement and targeting phase and by grouping code)"; the underlined part is grammatically incomplete. I believe when I read this, I mentally chose the simplest fix by sticking an 's' at the end of "phase", making it plural and allowing the indefinite article to be implied. This also created the implication that "movement" and "targeting" are different phases. I guess the correct fix is adding the definite article ("the"). Even better may be to describe the phase as "the move-to-targets phase" since then there is nothing suggesting there might be more than one phase being talked about.

I'll go ahead with this change, as even if it is not yet accurate, it would seem to be more accurate than what is currently there.

[mattsc]

I'll go ahead with this change, as even if it is not yet accurate, it would seem to be more accurate than what is currently there.

Thanks much for doing that! I had a look over the existing AI wiki pages and maybe the main issue is that a lot of it was written when the RCA AI was not yet the default. Thus, a lot of it really needs to be updated, and some of it would benefit from reorganizing. I assume nobody'll object if I give that a shot? (Slowly, over the next weeks, maybe months.)

I think I'll start with AiWML, as that is likely the first goto page for most scenario coders (and it's not in too bad a shape). After that, I'd probably organize the rest under my Practical Guide pages, simply because that's set up in a way that makes sense to me. I'd keep existing pages as they are, just copy content from them into the new pages, and mark the old ones as out of date when I am done.

Anyway, if anybody has specific suggestions, let me know. Otherwise I'll just slowly plug away at this.

[mattsc]

A good and useful thing to have would be a way to teach the AI to 'protect' certain unit (which might not be a leader), while moving the unit to location B and doing attacks-of-opportunity (where the unit can't be easily hurt). For example, in HttT 1, Delfador should not die, but it's useful to attack with him; so, if we want the AI to play HttT 1, we must teach it how to use Delfador to help move Konrad to the target location, yet to avoid getting him killed.

For example:
0) this is for unit with ID=id
1) do not attack with that unit in normal attach phase
2) do not move this unit in normal strategic move-to-targets phase
3) just-after-combat, if there's good attack available which can be done without exposing this unit to heavy this-turn or next-turn retaliation, do it.
4) if the unit is threatened, retreat or cover him with other units.
5) otherwise, try to move closer to a target hex/unit, but not on exposed locations.

Hi Crab: After a short Wesbreak of sorts, I got back to this and have a first version working (on a very simple, boring map). You can check it out in the latest version (0.4.7) of "AI Modification Demos". Go to scenario "Protect the Wizard", let the AI's fight each other and choose all the default options in the dialog.

The way it works:
- The wizard Rossauba does not take part in the normal combat phase
- Right after combat of all other units, if there is a good attack available (meaning: he will definitely not die during the attack and the next round of enemy attacks) he does this attack.
- Otherwise, move to a good location. 'Good' is prioritized as:
1. Most important: it's safe from enemies
2. Second: Move toward goal signpost
3. Stay close to own units
4. Tiebreaker: move closer to or farther away from enemies, depending on 'bearing' variable
- After that, units that can still move do their moves
- To spice it up a little, the enemy attacks Rossauba whenever there is a chance, even if a better target is available (by the standard combat phase criteria)
- I've given Rossauba's side slightly more gold than the enemy so that he wins more often than not.

I believe that covers all the points you raised. I stayed with the KISS principle as much as possible. Any comments, suggestions and observations would be most helpful, to figure out if any of it is too simplistic.

I will set this up for Scenario 1 of HttT next. It won't work quite the way it is for that one yet (for example, it needs to be adapted to work with 2 units).

[mattsc]

I apologize for double posting, but IMHO this is worth its own post: I applied the code from "Protect the Wizard" to scenario "The Elves Besieged" of "Heir to the Throne" and it works right out of the box! I've watched it play through more than a half dozen times now, and Konrad made it to the signpost each time, with Delfador surviving as well. So, I have written my first AI algorithm that can win a (not-just-battle) mainline campaign scenario.

See v0.4.8 of "AI Modification Demos"

A few technical details:
- I chose the 'easy' difficulty setting and removed the time limit (although it usually finishes within the original time limit)
- For simplicity, I used core units and images for Konrad and Delfador
- A few weaknesses become apparent immediately (such as: don't attack units with poison!), but since, so far, the AI has won every time, I'll deal with this later.

[Crab]

great:)
I'll try to patch it into my code for last scenario of Two Brothers to see if it would help the AI win it

[mattsc]

great:)
I'll try to patch it into my code for last scenario of Two Brothers to see if it would help the AI win it

Great, thanks. Let me know if you have suggestions for improvements. I'll keep working on it too. The code's still a bit "rough around the edges" and in watching it play HttT-TEB a few more times, I already found a couple (minor) things that I want to change.

[mattsc]

Question of speed/efficiency: I need an 'attack map', that is, a table that lists how many enemies can attack each hex. Same as what is displayed on the map with "show enemy moves", only for attackable hexes rather than moves. I currently do that by going through [store_reachable_locations] with 'range=attack' and it works just fine. (See code below.)

The problem is that this is slow when there are lots of enemies on the map (not super slow, but somewhat sluggish), such as in the Elves Besieged scenario. wesnoth.find_reach() is much faster, but as far as I can tell, it does not have the 'range=attacks' equivalent option. Is there a different, faster way to do this in Lua? TIA.

Code: Select all

function ai_helper.mind(x,y)
    -- Calculate 1-dim map index
    return x*1000 + y
end

function ai_helper.get_reachable_attack(unit, moves)
    -- Get all hexes that a unit can attack
    -- Returned array is of form { x = ..., y = ... }
    -- moves: if set, use this for 'moves' key, otherwise use "current"

    W.store_reachable_locations { { "filter", { id = unit.id } },
        range = "attack",
        moves = moves or "current",
        variable = "tmp_locs"
    }
    local reach = H.get_variable_array("tmp_locs")
    W.clear_variable { name = "tmp_locs" }

    return reach
end

function ai_helper.attack_map(units, moves)
    -- Attack map: number of units which can attack each hex

    local AM = {}  -- attack map
    for i,u in ipairs(units) do
        local reach = ai_helper.get_reachable_attack(u, moves)
        for j,r in ipairs(reach) do
            AM[ai_helper.mind(r.x, r.y)] = (AM[ai_helper.mind(r.x, r.y)] or 0) + 1
        end
    end
    --ai_helper.put_labels(AM)
    --W.message {speaker="narrator", message="Attack map" }

    return AM
end

[Alarantalara]

Here is a different way. I don't know if it's faster since I have yet to set up a timing test, but it might suggest something to you.

Code: Select all

function ai_helper.get_reachable_attack(unit, moves)
    local location_set = wesnoth.require "lua/location_set.lua"
    local reach = location_set.create()

    local initial_reach = wesnoth.find_reach(unit)
    for i,loc in ipairs(initial_reach) do
        for x, y in H.adjacent_tiles(loc[1], loc[2]) do
            reach:insert(x,y)
        end
    end

    return reach:to_pairs()
end

function ai_helper.attack_map(units, moves)
    -- Attack map: number of units which can attack each hex

    local AM = {}  -- attack map
    for i,u in ipairs(units) do

        local reach = ai_helper.get_reachable_attack(u, moves)
        for j,r in ipairs(reach) do
            AM[ai_helper.mind(r[1], r[2])] = (AM[ai_helper.mind(r[1], r[2])] or 0) + 1
        end
    end

    ai_helper.put_labels(AM)
    W.message {speaker="narrator", message="Attack map" }

    return AM
end

Edit: Timing test is now done. Average for the first 3 turns of 1.3 seconds for new code and over 6 for old code for the first turn and much more once more than just the leaders are present (I killed Wesnoth first due to impatience), so it's noticeably faster on HttT at the start. Test was 1000 calculations of the enemy map.

[mattsc]

Edit: Timing test is now done. Average for the first 3 turns of 1.3 seconds for new code and over 6 for old code for the first turn and much more (I killed Wesntoh first due to impatience), so it's noticeably faster on HttT at the start. Test was 1000 calculations of the enemy map.

Wow, great, thanks! I've been wondering whether I should be working with location sets anyway, but so far hadn't come up with a convincing reason yet. I guess I have one now! 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.

Thanks !!

[mattsc]

Alarantalara: I did some more tests, and the code needs a small modification. wesnoth.find_reach() by default uses the current movement of a side (which for the enemies is 0 for most units during the AI turn), while I need the enemy moves during their next turn. So I also need to pass '{additional_turns = 1}' for the enemy attack map (which is what the 'moves = max' did in the previous version). This greatly increases the number of hexes in the attack map. With that, I get the following times for 100 reps of the enemy map calculation:

Code: Select all

Turn   old      new
1      0.8s     0.5s
2      9.3s     2.0s
3      15.2 s   2.9s

Still a good improvement, but not by as much as before.

There might still be ways of speeding this up a little. For example, the current algorithm adds almost all hexes 6 times to the location set. Maybe there's a smart way of avoiding this? I'll think about that later, for now this is pretty good the way it is (30ms delay is not so bad). Thanks again.

[Alarantalara]

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.

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?

I did some more tests, and the code needs a small modification. wesnoth.find_reach() by default uses the current movement of a side (which for the enemies is 0 for most units during the AI turn), while I need the enemy moves during their next turn. So I also need to pass '{additional_turns = 1}' for the enemy attack map (which is what the 'moves = max' did in the previous version).

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.

Why not set the unit's current moves to the maximum before calling the function. Would slow need to be taken into account as well here?