PDA

View Full Version : Towards a Factions AI: Part B -- What is the strongest move?



Aleonymous
09-09-2013, 03:53 PM
TL;DR = This long and tedious read is the course of my thoughts towards designing an AI. I've skipped a lot of the programming details and tried to present only the reasoning behind my approach. Theorizing on how to optimize and AI can help bring us closer to answering the true question: "what is the best move?".

Introduction -- What is an AI?

In the scope of this post, an AI is a set of rules used to identify an optimum "action-set" within a large number of valid action-sets. As "action-set" we define the set of orders we give to a unit through our mouse-clicks, i.e. the path picked, the destination tile, the attack-target and type, the willpower spent etc. The set of rules that makes up the AI is basically just "mathematics", i.e. weighting/evaluating/assessing the relative impact of each valid action-set and picking the one that is most beneficial (or less harmful) to the acting unit and his team.

The next --and probably more important-- question that comes along the fundamental question that the AI must provide an answer for, i.e. "what is the best move?", is this: "how do you define the best move?". What do you seek to optimize? What criteria do you use? What data do you analyze? The answers to all these lie within what I define as the "Level" of the AI. This roughly denotes how smart is the rule-set or, equivalently, the person who defined it :)

Level 0 AI -- Complete Randomness!

This is the simplest form of "AI", where each unit picks a random valid action-set and executes it. For instance, the unit randomly rests/acts, moves on a random valid tile, terminates his turn or attacks an enemy for STR/ARM spending a random amount of WP on a the attack. Evidently, there's not much use in this Elo=1 "AI", except to have an easy to beat opponent. Imagine this opponent as a monkey or a cat playing with your mouse :cool:

One could implement a slightly more advanced AI, e.g. Level 0.x, where some obviously moronic action-sets are not considered at all. For instance, in this AI, the unit always moves to a tile where it can attack an enemy, whichever, and then does an STR attack if STR>ARM or else an ARM attack. I think that this kind of AI is pretty close to the Elo of 800-900, meaning that it "knows" the basic STR>ARM principle.

Level 1.0 AI -- Seek MAX: (STR+ARM+WP)ally - (STR+ARM+WP)enemy

This is next level of AI (notice the absence of the quote-marks, compared to the Level 0 AI :)) where each unit evaluates its options based only on the change of stats (for both the enemy and the ally units) brought upon by its actions. This level of AI completely ignores the units' turn-order and relative positions, and only seeks to maximize its own contribution to victory in a purely stat-counting manner. In this "static" (in contrast to "dynamic") AI Level, all units are considered equal, i.e. they do not have any particular roles/tasks in the team, meaning that their best move is chosen based only on their own stats. In practice, what a unit commanded by this AI tries to do, is:


Avoid spending WP on EXerted movement and/or moving thru burning-coals
Stand next to a Raider, in order to increase his ARM
Pick a position & target where he can do max HP damage on the enemy team (prioritizing ARM-over-STR and excluding chance-shots)
Spend as much WP as EX-possible on this attack (avoiding overkills)
Use as much Horn-WP as is available & usable in his turn


An AI-commanded unit must first list all his valid choices, evaluate them and select & execute the best one. So, having defined what the general criteria this AI uses, lets take a look at the math that can be used to quantify the impact, i.e. "evaluate" the action-sets. To do this, some simple "factors" can be used to measure the "cost" of each sub-action of each action-set. The Level 1.0 AI uses the following set of factors


F0 (Rest) == +1 or 0, from the 1WP gained from resting (zero if already at full WP)
F1 (Movement/Exertion) == -1 for each WP spent on EXerted movement, to get to the target tile
F2 (Movement/Coals) == -X-1, where X is the coals-damage to be suffered, to reach the target tile (-1 if the unit stands on a coals-tile)
F3 (Position/Shieldwall) == +Y1-Y2, where Y1 & Y2 are the ARM bonuses from Shieldwalls, when standing at the target & starting tile, respectively
F4 (Attack/Damage) == +Z, where Z=max{ STR, ARM }-damage to be done to a unit, from a given tile (chance-STR-attacks are omitted and overkills/breaks are truncated)
F5 (Attack/Kills) == +W, where W is the number of units killed with this attack (Heavy-Impact included), corresponding to the Horn-WP gained.
F6 (Attack/Side-Effects) == -V, where V is the RtF you get if hitting a SB (HI-induced RtF included)


Having calculated the above factors F0-F6 for a given action-set, we weight them (using a weight of 1 for all factors) and sum the result in order to get a final "score". The "Score" is a single number telling us how good is this action-set; of course, the scores are relative and should only be considered as such. Comparing the scores of all valid action-sets, the AI selects the highest-scoring action-set and executes it. Equal scores are sorted in descending order based on the priority of the factions F0-F6; if the scores are still equal, one of the action-sets is randomly chosen. WP and Horn are factored in during the listing of the possible movement-tiles (e.g. for F1) as well as the damage output of the attack (be it STR or ARM)

So, how do we implement this AI? The procedure has the following steps:


Consider ALL valid action-sets, in the 3D "space" of [Valid-Tiles]x[Targets-from-tile]x[ARM/STR-damage-on-Target]
Evaluate factors F0-F6 for each of the above action-sets
Calculate the final "Score" of each action-set, where Score{ Action-Set } = SUM_i( wi*Fi ) and wi==1 (for Level 1.0 AI)
Order the action-sets based on the Score they got
Resolving situation where highly scoring action-sets are tied
Select and execute the highest-scoring action set


Notes on Level 1.0 AI

Evidently, all the factors listed above (F0-F6) are linked DIRECTLY and PROPORTIONALLY to the STATS of the team's units, gains and losses of them. All the vital depleteable stats (ARM/STR/WP) are treated with equal importance, if the weights (wi) are equal.

Note that some factors have a positive sign, while others a negative one. That are the "good" and "bad" results of the unit's actions, respectively, considering only it's own welfare and the opponent's malaise.

The valid action sets for archers are expected to be much more numerous than the melee units' ones, since they can attack multiple targets from many different tiles.

Seemingly wrong action-sets like "move but don't attack" are likely to arise as good options, in the case where: (1) SW bonus to be gained is high, (2) valid tiles for attacks are too far away costing WP and/or fire-damage, (3) too low STR and/or AB on the acting unit. This choice seems likely to arise as a good action-set for archers in the early game, where they follow up behind the raiders' advance.

In order to make an AI based on such "scoring" more unpredictable (and thus fun to play against, emulating the human-error-factor) we can apply a random "noise" on the scores of each action-set. So, adding a random number (RNG! :p), in the range of -5 to +5, to each score can "force" the AI into selecting a sub-optimal choice. Who knows? Perhaps our criteria were not so good, and this choice proves out to be a stronger move :)

Epilogue -- What about Promoted-Classes & Active Abilities?

Introducing promoted classes into the above formalism makes the number of criteria used to EXPLODE, due to wild variety of abilities. Some offensive abilities (e.g. Tempest, SI, BoP, RT, BF, SnB) can be directly introduced in the Level-1.0 AI above, because their impact can be directly calculated & measured. However, other not-directly aggressive abilities (e.g. SW, FA, RoA, PK, BtP, BR) are a little or quite a bit more complicated to introduce. In principle, we can start by "scripting" these units/abilities, that is "teaching" the AI to identify particular situations where the profit of using the ability is deemed higher than selecting an action-set based only on the Level 1.0 AI described above.

Lets give some classic examples:


Classic-example #1: A low-STR/high-ARM PK acts before a menacing high-STR enemy, that can kill an ally archer in one blow. The PK can do a 3+1 break on the enemy at maximum. But, the potential loss of stats if the enemy kills the archer is -10 or worse. What if the PK malices this unit? If you compare the two choices (AB or Malice the enemy), I think there's no question as to which one you'd pick. However, in order to "teach" the AI this criterion, you'll need to either implement the "look-ahead" feature and weight its impact too, or just script the unit's AI.


Classic-example #2: A TH with low STR, 1AB and no WP can be used to do just 1AB on a relatively healthy enemy. But, if he rests and regain 1WP he can do a BF with a 3-4 guaranteed damage output. So, in two turns he does 3-4 damage, whereas if he doesn't rest he does just 1+1=2AB. This kind of "smart decision making" also demands for the "look-ahead" feature and/or scripting such "armor-bypass" damaging abilities/units.


Classic-example #3: You control a SS. Unfortunately, she is arrayed alongside two more ally units for a triple-Tempest by a full WH acting up next. The path the WH has to pick in order to do the Tempest is very narrow. What do you do? No need to answer that.

Let me just point out that to "teach" an AI (i.e. write a computer program) to consistently identify situations like the ones described above is a complicated task indeed.

Aleonymous
09-09-2013, 03:54 PM
*** Reserved for what's next ***

Yeah, there's more... :o

Slimsy Platypus
09-25-2013, 11:52 PM
Holy cow Aleonymous! This is beastly! From the glimpses of the AI we have seen in the Let's Play videos, at first glance it looks like your AI may be even more complex than the one Stoic has developed!

In the single player AI that we've have seen, it appears that the Dredge favor Iver as a target over the majority of the others. This should add an interesting twist to the team building, because in Factions our opponnents typically aren't going to burn through our defensive Varl as a primary target first. If this remains true as we are exposed to more of the AI Stoic has built, the way we build our teams could be very different in Factions and the single player.

Aleonymous
09-26-2013, 04:14 AM
Thanks for you reply, Slimsy :) I was fearing that nobody would bother --even-- replying to these posts (much less actually reading them), due to their size and/or the complex way they were written :( I have some more "interesting" things to add, but I don't have time to clearly shape them now. The most interesting thing is a way to measure the Turn-Advantage vs Stat-Advantage. This, I believe will also apply to the Saga, where it is very common to have Turn-Advantage.

Concerning the Saga's AI, I believe that the units are "scripted". That means they

tend to follow specific patterns in their behavior, e.g. they attack the closest enemy,
don't necessarily work towards winning the battle, in the altruistic way we are so accustomed in Factions,
are oblivious to several "buffs" like traps, stone-walls, fire/coals etc

I believe this AI is much more lore-friendly than the AI I am trying to outline. The former gives character to the units (e.g. the Dredge hate their ancient enemies, the Varl, and always focus on them first) while the latter just looks at the mathematics and tries to have the last man standing in order to win the fight.

Having different AI "modules" for different kinds of battles or units is highly desirable, because it will make the fights diverse and unpredictable. Especially if (a) character's death/knock-outs matter and/or (b) more complex objectives exist, for instance you need to maim a specific character to "capture him alive" or you need to get to a specific --well protected-- tile of the map to unlock something etc.

Slimsy Platypus
09-26-2013, 05:04 PM
Concerning the Saga's AI, I believe that the units are "scripted". That means they

tend to follow specific patterns in their behavior, e.g. they attack the closest enemy,


That's what I originally thought as well, because we saw the dredge move up and attack Egil (a shieldmaster) in Let's Play 2 when in range of a Stone Walled Egil and Rook (a hunter). (1:38 here (http://www.youtube.com/watch?v=-E0rhoN1Eog))

Later in that same video (at 3:45) we see a dredge favor Iver (a strongarm) over Rook and Egil, which made me think that perhaps they favored Iver because he was a defensive Varl.

The preference of Iver as a target is later confirmed in Let's Play 5 (1:59 here (http://www.youtube.com/watch?v=eZlnawT9FWs)), when a dredge favors Iver as a target over Oddleif, a Skystriker.

Then this theory gets blown away when we see a dredge peel off Iver, and go for Alette (a sharpshooter) at 3:49 here (https://www.youtube.com/watch?v=gy0Raj1QC3M)



So... there is something we are still missing about how the AI choosing it's target. Perhaps different encounters have the AI going after different characters for lore reasons? Perhaps there is an intentional designed randomness in their targeting? Or perhaps there is some element that we haven't thought of that makes the data above make sense. Who knows!

Aleonymous
09-26-2013, 05:34 PM
So... there is something we are still missing about how the AI choosing it's target. Perhaps different encounters have the AI going after different characters for lore reasons? Perhaps there is an intentional designed randomness in their targeting? Or perhaps there is some element that we haven't thought of that makes the data above make sense. Who knows!

Indeed. However, the data we have are too few to make any conclusions. Also, it's not like the Dredge had a chance to do massive damage or kill; in all these instances its options were 1-2 ARM/STR damages. So, it's not unlikely that they have implemented some sort of randomizer between equal moves (i.e. moves that do the same amount of damage), so that the AI seems more unpredictable. Arnie (or Alex?) has said that they designed the AI to be "know-able", so I guess that with a little experience most of these things will be revealed...

raven2134
09-27-2013, 06:46 AM
Reserved (until I get to assimilate the information)

Slimsy Platypus
09-27-2013, 03:14 PM
I have some more "interesting" things to add, but I don't have time to clearly shape them now. The most interesting thing is a way to measure the Turn-Advantage vs Stat-Advantage. This, I believe will also apply to the Saga, where it is very common to have Turn-Advantage.



Not to derail the current conversation, as I'm very interested to see what Raven is going to add, but one way to quantify turn advantage is converting it to STR per cycle. A cycle is defined as 6 turns.

As an example, let's say I'm facing an opponent and we both start with 6 units that are all 10 ARM 10 STR.


We both start out with 60 STR/cycle:
Half way through the battle I've maimed 4 of his units to 4 STR, but he has killed 3 of mine and left the remaining 3 intact. He has 36 STR/cycle, but I still have 60 STR/cycle. That IS turn advantage!
I have the opportunity to gain serious advantage over my opponent, as I may be able to kill units that have armor remaining while they will have to break my armor down to kill mine
Now the complex part is getting an AI to understand this. Because usually it's not the existing STR/cycle that matters, but the resulting STR/cycle AFTER taking your move. The STR/cycle evaluation really needs to take place like several turns in advance. Perhaps there are inherent STR/cycle guidelines that we could use (like never let ours deter more than 10, 15, 20 etc. from our opponent), but quantifying the right one might be a challenge in itself. And even further complicating it is adding ARM to the mix. We don't want to AI ignoring ARM break to get an advantage in STR/cycle early that isn't sustainable when they have to remove armor in the end game to continue getting value hits in. Like you mentioned in the original post as well, considering passives and active abilities shakes this up as well, especially abilities like Bloody Flail, Puncture, and Heavy Impact that can all be effective at low strength.

Just thought I'd throw my brain power in there. There could be much better ways to quantify turn advantage - this is just have I've tackled it in my head in the past :)

Aleonymous
09-28-2013, 04:28 AM
[...] one way to quantify turn advantage is converting it to STR per cycle. A cycle is defined as 6 turns.

That is exactly what I came up with too! It seems I'll have to get my scraps of text together and complete that second post :rolleyes:

For the moment, I'll just say here that I tried to relate Turn-Adv vs. Stat-Adv to the fundamental physics principle of

Energy = Power * Time,
where Energy and Power is a measure of Turn-Adv and Stat-Adv, respectfully. Naturally, Time is measure by the number of turns that each unit takes, before the cycle starts over. Of course, Energy & Power are always relative to the opponents, i.e. they mean nothing by themselves, and are calculated at the specific instant before the unit's actions. The "eye" of the experienced Factions player can quantify the above by just a quick glance at the units banners and the turn-queue, so it isn't so hard to teach a program to do it. What is difficult, is bringing in complicated aspects like relative-order, distancing etc. Finally, I've also tried to bring ARM, WP, EX & AB in a coherent framework, although there is still a lot of small "holes" here and there...

To wrap it up, I'll hint that the best move is the one that maximizes what I dub the Energy-Difference Gain (EDG) and is defined as

EDG = ( EA - EB )@postmove - ( EA - EB )@premove ,
where E is the Energy, subscripts A&B are for the two teams and pre/post-move designate the "instants" right-before and right-after the unit's actions/orders are executed.