the AI discussion

[nonickch]

So then the first way to evaluate is to award favourable points to any place on the map as an end point.
1. Do I know of any enemy in view (of that alien or a teammate, to include some cooperation)?
2. Can I go somewhere that has views in other directions that I or my teammates currently have? (what places are not in line of sight?)
3. What places (within my TU range) have cover on many sides (NSEW)?

Last night I was having a discussion with arakis on irc about the AI and I realized that the AI actually cheats major-style in the visibility department. FighterBestAction checks for visibility on the target before considering to shoot him, which tricked me into thinking that it's all kosher. What I did forget though is that it sets the aliens ent->origin at the spot it's considering. This means that all the aliens get futuro-vision and know what they can see from any spot they can move to before actually going there. I previously assumed the autopsy reports are to blame for behaviour indicative of that (they all say they have perma-IR vision), but it may just turn out to be this one.
This little trick actually makes away with all the visibility considerations that the AI ever needed to ever make. Should we ever decide to drop this AI shortcut, we will need to make up for it with some heavy visibility calculations. This is definitely a way to improve the 'feeling' of the AI that adds a penalty to it's effectiveness lest we do vis checks much better. A pragmatist I am not, this is definitely something I'd like to try out, but when other areas are finished first (everything set @todo already in my posts, quite a few).
For the pragmatists that will definitely ask 'why should we nerf the AI and then augment it again instead of just keeping the cheat in place?', here's a couple of reasons why we should:
* Ever managed to sneak up on an alien? Me neither.
* You can actually employ tactics like distraction much more effectively. Your rabbit down there is getting the alien behind the window on the 1st floor to try and shoot at him rather than checking if someone is sneaking up on him. As it is right now (since I've tried this tactic), the minute your backstabbing guy gets anywhere close to the sniper, the sniper lets the rabbit go. Ofc your tactic still works when the sniper promptly gets stuck behind the corner.
* The aliens will look much more active. They will actively patrol areas (the vis maximization score) trying to find targets.
* I suspect that this will make them <3 their sniping positions. As it is right now, mappers place perched aliens to godly positions, only for the CLOSE_IN metric to kick in and leave their position in turn 1.

All your listed metrics sound quite proper for this task. Say, are you interested in some coding-fu?

Now if an enemy is in view, you get additional considerations:
4. What places are closer to visible enemies than my current position?
5. Where are the (three?) nearest visible enemies (average into a 'centre of gravity')
6. Where are the (three?) nearest friendlies (average into a 'centre of gravity')
7. What is the main line of fire (vector between centres of gravity), in what places could I get line of sight to an enemy from a different/cross angle? (more teamwork)
8. What places are available where the known enemies cannot see me?
9. What places are available where the known enemies have trouble hitting me?

Calculating clusters of enemies/friendlies! Excellent idea!
At least for the enemies, I can see this getting in asap is for the close_in metric. Try and approach the centroids of clusters (mmmm, clustering algo's here I come) instead of individual targets. I'll be doing the changes in the close_in right after the guete's and the wiki, so let's see what we can get here
As for clusters/centres of friendlies, hmmm. I don't think we could use this as a bonus metric since that would make aliens slowly pack in tight spots, but as a penalty metric (don't wander off X tiles away from your local group unless you have a good reason), it sounds really nice.
(7) is an interesting point. I was thinking something along this lines when trying to imagine how we could possibly define our&enemy lines. Cluster us, cluster them, sketch line between centroids, draw perpendicular line on either side (length varies with dispersion) and voila! A basic definition of a combat front for either side. Sweet part is that it can work the other way around, so if a chosen tactic requires moving your front, you can just add bonuses to spots that move centroid&dispersion accordingly (that goes to the decomposition to primitives mentioned in the theorycrafting of machine learning).
( and (9) are already calculated, well it's more of a gradient of visibility.

Now all the places that are interesting to be are already known. Some are safe places and some are not at all safe (if you can see them, they can usually see you). But for attacking, some of the squares with LOS to an enemy need to be evaluated further.
10. What weapons do I have in my hand? Can it/these hit from there?
11. In case I go there and shoot, what is the safest place I can end up in?
12. What other weapons I have in my inventory? Can they hit from there?
13. In case I go there and change weapon and shoot, what is the safest place I can end up in?
Thinning out some more squares in this way comes the attack calculation
14. What damage can I expect from shooting with any of my weapons from that square?

10&11 is already properly evaluated. So is 12&14, I think, but there are some obvious shortcomings. 13 is implied because of the search tree and the fact that we count the remaining TU's.

In this system, each place could be evaluated essentially by five variables: VIEW (how much lookout do I have), SAFE (cover/hiding), HIT (can I attack), DAMAGE (how much can I inflict) and TIME (how long will I spend there). You would want to plot a route within the maximum total TIME from where the alien is now to somewhere with high SAFE, while stopping somewhere with high HIT and DAMAGE and shoot, as well as passing through as many places as possible with high VIEW.

Barring the VIEW metric (which is totally ignored because of god-o-vision), the rest are the basis of the current AI: SAFE is definitely in there and HIT&DAMAGE are merged into one multiplicative metric (named damage). The plotting of move-shoot-hide is exactly what the search tree is currently doing. With emphasis on the exact move-shoot-hide.

Excellent ideas all around

[Hertzila]

10&11 is already properly evaluated. So is 12&14, I think, but there are some obvious shortcomings. 13 is implied because of the search tree and the fact that we count the remaining TU's.

I'm not so sure that 10 is correctly evaluated. In couple of cases there has been a window between me and an alien. For some reason the alien doesn't realise that and tries to shoot through it, even though my Line-Of-Fire line gets red when I try to do so (so obviously the game knows you can't shoot through a window).

[nonickch]

I'm not so sure that 10 is correctly evaluated. In couple of cases there has been a window between me and an alien. For some reason the alien doesn't realise that and tries to shoot through it, even though my Line-Of-Fire line gets red when I try to do so (so obviously the game knows you can't shoot through a window).

You are correct in that aspect. But afaik you can shoot through a window, I've done it multiple times (does the first bullet get wasted on the window?).
The whole shoot/can't shoot thing seems to be the one producing the 'aliens shoot through walls'. I was about to make comments on that, then I realized I have a very fuzzy knowledge of that part of the code.
I'm finishing off the new diagrams, creating the wiki page, have a go at the 'stuck behind hulls' issue and then the wall-shooting and all the los/lof things are next.


EDIT:
Upon remaking the charts, I run again on the AND/OR notice I have about the AI_FighterBestAction. This is the code for awarding being hidden:
if (AI_HideNeeded(ent) || !(G_TestVis(hidingTeam, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES)) {
         /* is a hiding spot */
         //bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
         bestActionPoints += guete_hide->integer + (aia->target ? guete_close_in->integer : 0); //AI TESTING MODIFICATION FROM NONICKCH
      }

What does that tell you? AI_HideNeeded checks for our visibility and compare it to our bravery (brave can still stay exposed).
The Vis functions did get me quite confused. Some new and old functions geting |'d together and a long trail of functions. If I'm not mistaken that whole expr simply returns true if we're visible to any of the hostiles or not.
Doesn't that mean there should definitely be an && there instead of ||? I need someone to take a look at that as if it is as I think, that would have a serious negative impact on the AI and all the behavior caused by GUETE_HIDE is skewed.
SOLUTION: It seems that the AI_HideNeeded is used for moral checking vs enemies in a way that produces chicken-out moves. It is not enough by itself to allow aliens to seriously consider hiding. So all is fine. Dodon's post explaining stuff bleow.

What is the 'old' visibility system that's implied in the G_VIS functions, and why is it still working with both systems?

wiki page is up: http://ufoai.ninex.info/wiki/index.php/Combat_AI
Can someone force the .zargo file in it's place in the page? Original file is on the 1st post of this thread.

[shaunc311]

Thanks for the cool graphs and wiki page with the summary of the stuff above. 

Looking at them and the g_ai.c file, it looks like the current AI works the same no matter what difficulty level you are playing at.  That will be good to know when I play some harder campaigns later.

[ovvldc]

This little trick actually makes away with all the visibility considerations that the AI ever needed to ever make.

Very unfortunate. Having a tactical (sub)game is so much less enjoyable if you can't do any tactics..

All your listed metrics sound quite proper for this task. Say, are you interested in some coding-fu?

I wrote this all down as an approximation of my own decision-making process and to help the discussion about heuristics to clip the search trees. You'll note that my own emphasis is on moving, not on shooting, because my XCom soldiers carry at most two weapons (short and long range) so that the question of what weapon to use when I get where I want to be is pretty obvious. And since none of my soldiers were ever good enough to hit a cow's rear end at point blank range, I do lots of advancing from cover to cover with squadmates ready to provide suppressive fire.

Other people may have different lines of thinking.

Interested, yes. Flattered, certainly. But I am only a humble scientist and I couldn't do proper coding to save my life. And I haven't the time to learn proper C++ or something like that. I can read C++ equations (I wrote some 2300 lines including extensive comments) but I cannot write code that interacts with anything else. Besides, I'll probably have to learn R or Java for work and Finnish for my girlfriend, and those are enough foreign languages for now .

Calculating clusters of enemies/friendlies! Excellent idea!

Why, thank you . It popped into my head as I was writing the rest. Though I didn't even think about clustering aliens in groups. Then again, if I were an alien stranded on a hostile world and cut off from my hivemind, it would seem like the instinctive thing to do. If you do use it, the choice on whether or not to wander off could also depend on bravery.

It is interesting that you thought of group fronts, whereas I thought of individual flanking actions .

Barring the VIEW metric (which is totally ignored because of god-o-vision), the rest are the basis of the current AI: SAFE is definitely in there and HIT&DAMAGE are merged into one multiplicative metric (named damage). The plotting of move-shoot-hide is exactly what the search tree is currently doing. With emphasis on the exact move-shoot-hide.

Excellent ideas all around

Thanks again . My personal instinct would be to hold off the aggregation of SAFE and DAMAGE for as long as possible in the AI code, because they are such different sides to the battlefield coin. And having such different criteria (and other metrics) disaggregated probably lends itself better to discrete heuristic choice mechanisms, refactoring primitives, and caching results (to cut on calculations). But you seem to be a better coder than me, so feel free to tell me that my instincts are off the mark.

Best wishes,
 Oscar

EDIT: Having said that I have no time, I would still read and comment on this stuff with pleasure .

[Hertzila]

You are correct in that aspect. But afaik you can shoot through a window, I've done it multiple times (does the first bullet get wasted on the window?).
The whole shoot/can't shoot thing seems to be the one producing the 'aliens shoot through walls'. I was about to make comments on that, then I realized I have a very fuzzy knowledge of that part of the code.
I'm finishing off the new diagrams, creating the wiki page, have a go at the 'stuck behind hulls' issue and then the wall-shooting and all the los/lof things are next.

I don't think you can shoot through windows that have actual glass in them (as opposed to empty space as they usually have). UFO:AI doesn't support destructible stuff in maps and I've understood that this extends to glass too.
I haven't looked at the code and I think would have been resolved very quickly if this is the case but just to be sure I think you should check that the game does a line-of-fire check instead of a line-of-sight when deciding whether to shoot. AFAIK a mix between these two would explain it. (This is coming from a person who doesn't understand practically anything from code so take it for what it's worth.)

[dodon]

if (AI_HideNeeded(ent) || !(G_TestVis(hidingTeam, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES)) {
         /* is a hiding spot */
         //bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
         bestActionPoints += guete_hide->integer + (aia->target ? guete_close_in->integer : 0); //AI TESTING MODIFICATION FROM NONICKCH
      }

I dug through the archive and i figured out whats wrong.


first occurence is ok

Code: [Select]

/* hide */
if (!(G_TestVis(-ent->team, ent, VT_PERISH | VT_NOFRUSTOM) & VIS_YES)) {
/* is a hiding spot */
guete += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
} else if (aia->target && tu >= 2) {


then a todo was added:

Code: [Select]

/* hide */
/** @todo Only hide if the visible actors have long range weapons in their hands
* otherwise make it depended on the mood (or some skill) of the alien whether
* it tries to attack by trying to get as close as possible or to try to hide */
if (!(G_TestVis(-ent->team, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES)) {
/* is a hiding spot */
bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
/** @todo What is this 2? */
} else if (aia->target && tu >= 2) {


the next step is an implementon of the todo:

Code: [Select]

/* hide */
/** @todo Only hide if the visible actors have long range weapons in their hands
* otherwise make it depended on the mood (or some skill) of the alien whether
* it tries to attack by trying to get as close as possible or to try to hide */
if (!(G_TestVis(-ent->team, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES) || AI_NoHideNeeded(ent)) {
/* is a hiding spot */
bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
} else if (aia->target && tu >= TU_MOVE_STRAIGHT) {
this code is ok,


but if you look at the AI_NoHideNeeded

Code: [Select]

/**
 * @param ent The alien edict that checks whether it should hide
 * @return true if hide is needed or false if the alien thinks that it is not needed
 */
static qboolean AI_NoHideNeeded (edict_t *ent)
you realize that the description of the @return and the function name don't match. So AI_NoHideNeeded changed to

Code: [Select]

/**
 * @brief Checks whether the given alien should try to hide because there are enemies close
 * enough to shoot the alien.
 * @param ent The alien edict that should (maybe) hide
 * @return @c true if hide is needed or @c false if the alien thinks that it is not needed
 */
static qboolean AI_HideNeeded (edict_t *ent)
and our hiding code now is:

Code: [Select]

/* hide */
if (AI_HideNeeded(ent) || !(G_TestVis(-ent->team, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES)) {
/* is a hiding spot */
bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
} else if (aia->target && tu >= TU_MOVE_STRAIGHT) {
and that is error, the name of the function in this context was right. So now there is a "!" missing. The code realy should look like:

Code: [Select]

/* hide */
if (!AI_HideNeeded(ent) || !(G_TestVis(-ent->team, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES)) {
/* is a hiding spot */
bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
} else if (aia->target && tu >= TU_MOVE_STRAIGHT) {


the last change has no problems so the code should be

Code: [Select]

/* hide */
if (!AI_HideNeeded(ent) || !(G_TestVis(hidingTeam, ent, VT_PERISH | VT_NOFRUSTUM) & VIS_YES)) {
/* is a hiding spot */
bestActionPoints += GUETE_HIDE + (aia->target ? GUETE_CLOSE_IN : 0);
} else if (aia->target && tu >= TU_MOVE_STRAIGHT) {

---------------------------------------------------------------------------------------------------------------------------


Now let's take a closer look at AI_HideNeeded

Code: [Select]

/**
 * @brief Checks whether the given alien should try to hide because there are enemies close
 * enough to shoot the alien.
 * @param ent The alien edict that should (maybe) hide
 * @return @c true if hide is needed or @c false if the alien thinks that it is not needed
 */
static qboolean AI_HideNeeded (edict_t *ent)
{
/* only brave aliens are trying to stay on the field if no dangerous actor is visible */
if (ent->morale > mor_brave->integer) {
edict_t *from = NULL;
/* test if check is visible */
while ((from = G_EdictsGetNextLivingActor(from))) {
if (from->team == ent->team)
continue;

if (G_IsCivilian(from))
continue;

if (G_IsVisibleForTeam(from, ent->team)) {
const invList_t *invlist = RIGHT(from);
const fireDef_t *fd = NULL;
if (invlist && invlist->item.t) {
fd = FIRESH_FiredefForWeapon(&invlist->item);
} else {
invlist = LEFT(from);
if (invlist && invlist->item.t)
fd = FIRESH_FiredefForWeapon(&invlist->item);
}
/* search the (visible) inventory (by just checking the weapon in the hands of the enemy */
if (fd != NULL && fd->range * fd->range >= VectorDistSqr(ent->origin, from->origin)) {
const int damage = max(0, fd->damage[0] + (fd->damage[1] * crand()));
if (damage >= ent->HP / 3) {
const int hidingTeam = AI_GetHidingTeam(ent);
/* now check whether this enemy is visible for this alien */
if (G_Vis(hidingTeam, ent, from, VT_NOFRUSTUM))
return qtrue;
}
}
}
}
}
return qfalse;
}


If I am right only brave aliens (when they are threatened by enemy fire) ever feel the urge to hide.
It looks like the code is stuck somewhere between the implementation of AI_HideNeeded and AI_NoHideNeeded.


This code should work fine.

Code: [Select]

/**
 * @brief Checks whether the given alien should try to hide because there are enemies close
 * enough to shoot the alien.
 * @param ent The alien edict that should (maybe) hide
 * @return @c true if hide is needed or @c false if the alien thinks that it is not needed
 */
static qboolean AI_HideNeeded (edict_t *ent)
{
/* only brave aliens are trying to stay on the field if no dangerous actor is visible */
if (ent->morale > mor_brave->integer) {
edict_t *from = NULL;
/* test if check is visible */
while ((from = G_EdictsGetNextLivingActor(from))) {
if (from->team == ent->team)
continue;

if (G_IsCivilian(from))
continue;

if (G_IsVisibleForTeam(from, ent->team)) {
const invList_t *invlist = RIGHT(from);
const fireDef_t *fd = NULL;
if (invlist && invlist->item.t) {
fd = FIRESH_FiredefForWeapon(&invlist->item);
} else {
invlist = LEFT(from);
if (invlist && invlist->item.t)
fd = FIRESH_FiredefForWeapon(&invlist->item);
}
/* search the (visible) inventory (by just checking the weapon in the hands of the enemy */
if (fd != NULL && fd->range * fd->range >= VectorDistSqr(ent->origin, from->origin)) {
const int damage = max(0, fd->damage[0] + (fd->damage[1] * crand()));
if (damage >= ent->HP / 3) {
const int hidingTeam = AI_GetHidingTeam(ent);
/* now check whether this enemy is visible for this alien */
if (G_Vis(hidingTeam, ent, from, VT_NOFRUSTUM))
return qtrue;
}
}
}
}
return qfalse;
}
return qtrue;
}

What do you think?
It's quite late and I hope there are not too many errors in this post.

[Mattn]

attached the above change as a diff

[Mattn]

I don't think you can shoot through windows that have actual glass in them (as opposed to empty space as they usually have). UFO:AI doesn't support destructible stuff in maps and I've understood that this extends to glass too.

windows can be destroyed - but only if the mapper wanted them to be destroyable - see http://ufoai.ninex.info/wiki/index.php/Mapping/Entities/func_breakable

[Mattn]

@dodon - thanks, applied to trunk http://sourceforge.net/apps/trac/ufoai/changeset/30780

[nonickch]

coding high-5 dodon 

So, now: we give the hiding bonus to spots that don't cause our aliens to shit_pants (according to the morale/brave comparison) and spots that have caused our actor to dissapear from enemy view. Try out a standoff landing, the results will be quite different than what you expected.

I tried a couple of skirmishes and oh boy does this slight change totally change the alien behavior. You guys need to check for yourselves, they're pretty much all over the place not always hiding (even with the original 60 GUETE value).
If this 'error'/'new behavior'  was introduced into a patch, how come nobody went 'omg aliens are cowards now'?
Somehow the aliens think that hiding right behind a soldiers back (after stabbing him) is a good place to hide (when they actually dissapear it's ok, they also do it when they don't). Todo I guess.
Getting stabbed is now quite popular, aliens will not cower in a bungalow close to you never to come out again.

We should remember that whatever makes sense to us and looks logical in code does not directly lead to better alien behavior in the game. That's why we need of testing with even slight changes to see if we turned them into zombies.

I'm trying to figure out a way to visualise the search tree to a developer. Is it possible to:
a) Draw those 'move-to' lines (that appear if I click a soldier of mine to move during the aliens turn)
b) Freeze the execution of the ai until some external event somehow arrives from the console/client (I can smell the mutex&threaded client/ServerFrame being thrown here, is there something simpler?)

This way you can examine some debugging output as the alien examines each tile separately (and visualized by the move-to lines). Type something in the console to consider the next tile.
Once we start using performance cutoffs this will be sorely needed since we will actually be able to see them kick in without going through thousands of debug lines.
I was trying to switch the close-in bonus to pathing last night, not much of a success (working on it). This is to fix the hull-hugging behavior.
While fixing that, I spotted another quite influencing parameter for the AI: #def CLOSE_IN_DIST 1200. Now this one was very subtle and was overshadowed my the puzzling OR in the hiding calcs.
As it stands, this 1200 value is the vector distance at which the aliens will start gravitating towards your soldiers. As long as you're further away from that (to be precise: further away from a tile an alien is considering to move to), the CLOSE_IN bonus is effectively nullified. While trying out the pathing distance metric, I'll be using something similar, like 50 TU's. That'd make an alien start gravitating towards you when he can get next to you within the next ~2.7 moves.
Ahhh, that's why my tests failed and the aliens looked stupid. They needed a larger value to get out of the ship. This complicates things, as the needed 80+ values to get aliens out of the ship are very large when no obstacles are involved (they can gravitate from other side of the map). I'll also be testing a weighted average of both vector and pathing to see if it's better.
Hey, can I somehow remove the fog of war?

[shaunc311]

Hey, can I somehow remove the fog of war?

I'm at work right now so I can't play to test it, but I think this:

#define G_IsVisibleForTeam(ent, team) ((ent)->visflags & G_TeamToVisMask(team))

line in g_local.h (line 187) can be changed to true.

[nonickch]

That would eat into the AI calculations. You could check and see if it's the player teams' vision, but then again the AI does exactly the same calc to see if it's being seen.
If there's no standard way to do that, no biggie, I can just kill the AI and walk around instead.

[shaunc311]

I'm not any type of authority   I just saw that while browsing through some of the files and figured I'd try and help.

[dodon]

If this 'error'/'new behavior'  was introduced into a patch, how come nobody went 'omg aliens are cowards now'?

The "hiding is good" part was always there. And the second part was added to make the aliens more visible.

Getting stabbed is now quite popular, aliens will not cower in a bungalow close to you never to come out again.

As the new behaviour needs high morale the aliens will hide again, when the casualties rise.

attached the above change as a diff

Ugh, missed that step yesterday