the AI discussion

[Mattn]

console command "sv debug_showall"

[nonickch]

Right.

Regarding dodon's patch, I've had conflicting reports from 2 people on irc.
One says it's much more challenging now, the other one says they're just plain suicidal/silly. Probably need to finetune values there and augment HideNeeded because it only checks for threat from single individuals and doesn't care if it's surrounded by 1000 lemmings (only cares if one of them can 1-shot 1/3 of it's hp). Also checks for visibility ofr that specific actor instead of shoot-ability, so I guess that's why the AI now hides behind your back more than often.

Found a new bug today while spamming debug messages around the code:
in AI_FighterCalcBestAction, there are cases where there is a target added to the action and no maxDmg set:

Code: [Select]

if (aia->target) {
bestActionPoints += maxDmg;
        assert(maxDmg>0);
assert(bestTime > 0);
tu -= bestTime;
}The assert(maxDmg>0) is there to prove the point.
Perpetrator is the ungodly large set of nested statements before it (we should really break em down asap) that calculate damage:

Code: [Select]

maxDmg = 0.0;
for (shootType = ST_RIGHT; shootType < ST_NUM_SHOOT_TYPES; shootType++) {
See the maxDmg being reset? That shouldn't be there as it holds the current max dmg. I commented that out.
Also, dmg may end up having a value when a target is not even remotely shootable, that's because of the continue;'s, so the fix I got is:

Code: [Select]

for (fdIdx = 0; fdIdx < item->m->numFiredefs[fdArray->weapFdsIdx]; fdIdx++) {
   dmg=0.0;

Here's the .diff
Can someone refactor the entire set of firing calculations into nice little functions? It's kinda chaotic to read and bug such as this can creep up. I tried to, but I still don't feel comfortable enough with C code.
It'd be nice to especially have the calculations for the base damage as one function, as I can use this in the AI_HideNeeded in order for the aliens to properly evaluate the threat level (don't run headlong into my machine-gunner you idiotic tammie).

console command "sv debug_showall"

Many thnx for that one


Dammit, maybe I'll finally manage to get to the part where I can test the pathing close_in metric tommorow.

[nonickch]

Right, todays work ended up being the AI_HideNeeded while trying to tone down suicidal tendencies introduced from fixing the hiding checks.
There's quite a few things wrong with this function:

a) Checking if we take too much damage is very poor. Only considers one shot (probably the simpled firetype) from an enemy and doesn't add up the damage when many enemies can see you (death by pistol firing squad, dmg expected from a flamer is 7!!). I kinda fixed the many-enemies issue in my working copy (by just adding up and having a % of HP threshold) but then I found the rest of the bugs:
b) Before we consider the damage we take from an enemy, we first check if our team can see him: "if (G_IsVisibleForTeam(from, ent->team)) {". BUT, this function doesn't take into account that we're actually considering going places where we still have no vision on. So aliens tend up to rush to a firing squad as long as they had no vision on them. Testing fix of thinking we're always visible still stumbles upon:
c) Damage expectation from:  a rocketlauncher is always 0, 0-range shotgun is 11, grenade launcher 0. This essentially turns AI_HideNeeded into just a morale check as I have never seen it evaluate true because of the damage. This is where I'd need the function-ized damage calculations mentioned in the previous post.

EDIT: I'm rewriting the damage calcs and HideNeeded atm. No need for someone else to go at it at the same time
The current state is this: The basic damage calculations are so simplistic you can say they are totally wrong. Attempts to use the core server shooting algorithm is not going anywhere since the G_IsVisibleForTeam(ent) is used all over the place, and this function does not take into account that we are considering an alternate positioning of our alien.
Anyone got ideas how to fix this without messing up the server code? If not, I guess I'll have to start ripping large portions of the G_* code

[Valaska]

 I dunno, the AI needs more aggression. Some maps, it feels like some wild goose hunt and gets extremely boring and randomly they will get a lucky kill in and I restart. Then there's maps where they are just stunned and its straight forward and easy.

 Then there's maps.. Riverside Town. It's virtually impossible because you have to go to the aliens.. These are apparently some super aggressive, dominating force.. They already have massive technology over you and equipment, even more health better reaction fire than you can even dream of getting etc..

 They need to push, come to you, be aggressive or do SOMETHING other than ducking in and out of cover, it's sickening especially now reaction fire is effed up beyond all recognition. They broke the game for me when they broke reaction fire.. Sure you can use the exact same weapons as everyone else does now adays and play the game like some breeze fest but come on I want a challenge or something different, surprises etc.

[nonickch]

GOOD NEWS EVERYBODY

Futurama is back!
Errr, I mean I solved many AI shooting-related problems. I think... eh, what? Oooh, but I do have my jammies on.

On related news the damage calculations have been fixed & the AI_HideNeeded was brought in line with the dodon patch (no more suicide, mkay?).
Kinda... I used proof-of-concept sampling of real shots via mock calls to G_ClientShoot, and, um, I broke my CPU (a turn takes 15 mins atm and crashes are frequent). I didn't check memory usage, but I expect that to skyrocket aswell.
Remember the fan-out term and tree size theorycrafting? Good, here's how it all ties into this post, along with the performance cost estimations & the necessary optimizations. We consider each function separately:

GAH, upon reviewing, my complexity calculations are WAY off. Too bothered to fix tm

AI_FighterCalcBestAction
All damage considerations for a given target are now moved to AI_GetDamagePotential. All notes on AI_GetDamagePotential are in reference to the code that existed i AI_FighterCalcBestAction
AI_GetDamagePotential now drops visibility checks against the target because:
* (fix) Visibility checks were counter-productive. G_VisTeam was used which incorrectly (yet efficiently) checks the vis flags. BUT, a few lines above we moved our critter to a new position which makes those flags obsolete (and G_Vis a terrible liar).
* (fix) We don't need to see someone if we yield an indirect-fire weapon like a grenade/grenadelauncher.
This removes the visibility cut-off and produces a possible fanout between 0(seeing all targets) to enemies+civilians(16?). So, worst case scenario is 16x more leafs.
Obvious performance optimizations are to re-introduce visibility checks for non-indirect weapons.

AI_GetDamagePotential now has all it's damage calculations replaced with the avg of 10 G_ClientShoot mock-up calls. This means that the damage expectation we have is the best there can be (even better from the UI estimations imho).
* (fix) Aliens properly pick shoot types and shooting spots. The difference in their dmg output is quite dramatic.
* (fix) Aliens no longer try and shoot through walls. LOF is properly calculated in G_ClientShoot.
* (fix) Aliens now know the destructive power of grenades & launchers. I did not test this, but it is most probable that they will strongly prefer crowded places for their splash weapons.
* (fix) Aliens properly evaluate friendly fire/self-harm chances (they currently subtract FF damage from damage to enemies in order to get to a final expected dmg).
The penalty we take on performance is quite significant. The fan-out may be only 10 (ontop of the previous one, for a total 160x number of leaves compared to 2.3 AI), but the tracing calculations needed here are a heavy factor.
Performance optimizations needed: An obvious proper bridge to the G_ClientShoot (no reason to try 10x, instead it can give us a base dmg+deviation), OR a complete copy of the damage calculations inside the AI code (bad, code replication&heavy maintenance). Best solution is a mathematical equation that can give us comparable results with minimal CPU.
For people wanting to try and extract the math equations, have a look at g_combat.c. Entry point is G_ClientShoot. HELP APPRECIATED, I SUCK AT MATH

AI_HideNeeded
This function became an issue as soon as the dodon patch fixed a hiding issue which moved quite some weight onto this function. Right, over here we need to perform a basic morale check (if morale < brave, then we need to hide), but most of all we evaluate what kind of damage we can expect in the next round (given the tile we stand on). The old style was very simplistic and quite mistaken in the damage expectations. So, we change these with a call to our new AI_GetDamagePotential for every enemy soldier out there. Simple isn't it? That should fix:
* (fix) Aliens now exactly know how much damage they can take the next round (not taking enemies moving into consideration). This means that they will not wander in range of large guns for no reason (reason enough is ofc slamming a grenade in your cluster of soldiers )
Now, this function is what cause the MAJOR fan-out disaster of doom. If you exclude the changes in this function, the AI is fast enough to play, but here we fan-out again, ontop of our 160x worst case scenario. For every of those leaves we check the damage possible for every enemy. Yes, that's another set of the same fan-outs we had up to this point (we just have num_enemies, not num_enemies+civilians). So that's a worst-case scenario of 8, bringing our fanout up to 8x10=80. Since this is in sequence with the damage calculations, this is multiplicative bringing the total amount of leaves to 160x80=12.800 for a worst case scenario. Yes, this is the point where the CPU just shrieks and tries to liftoff. And don't forget, the shooting calculations are a whole lot heavier than any other calculation we ever do.
Obviously, this would need to be another place were we need to improve quite a bit if we still intend to perform full-tree non-heuristic searches. Only checking only vs enemies that have a direct line of sight would be a first step (but that would make us oblivious to indirect-fire nades/launchers). Other than that, I can't see many ways to keep this functionality and still preserve a full-tree searching. The performance of this function is mainly influenced from the AI_GetDamagePotential function, so any performance gain (in fan-outs) there affects this function in a sqrt kinda of way (8x8 vs (8-Y)x(8-Y)).

So there it is, a nice step forward. Woah, the aliens in the background game are giving me a REALLY hard time :}
You may wanna test this out, if only for a turn or two to get a general idea of what's really changing. You may also want to skip the changes that happen in the AI_HideNeeded  function if you only want to see the AI gains in the damage output department.
Oh and I did change the g_ai.h #def GUETE_CIV_FACTOR to 0.20 (from 0.25) because it seemed right (I liked 0.15, but babysteps...). I also created a "#def GUETE_DAMAGE_AVOID 0.5" which is the % of current HP that an alien considers 'acceptable losses' (if not, this tile does not get the GUETE_HIDE bonus). Obvious possible change to this is to flip it from a binary value (run | not_run) to a gradient of score penalty.
Here's the svn diff vs the latest-ish trunk. (DO NOT GET COMMIT-HAPPY WITH THIS)

P.S: Sweet jesus, my squad got mauled in the last turn, and I did position them nicely...

[Mattn]

i've updated the patch a little bit and fixed some compilation errors as well as applied coding guidelines

http://pastebin.com/63PBDkyn

[MCR]

Hey Nonickch !

Great to see someone taking on the fight with the AI & already having some major successes !
Gratulations !!! (although I was not able to test latest improvements yet)

Ofc. I would not be MCR, if I wouldn't have some opinions & suggestions regarding this subject also

So here they come:

1.) The idea to have a different AI for the specific races, which is ideally not hardcoded, but scriptable via .ufo scripts is something I strongly support & something I would really wish to see in some future version of the AI.

2.) Please do not forget that we already have some excellent & detailed descriptions of the various alien races, their capablities, their behaviour &weaknesses & following those descriptions would automatically mean having a substancially different AI behaviour for each race as already suggested in this thread (YEAH, TOP IDEA - A MUST-HAVE FEATURE FOR THIS GAME !!!) 

Here some behaviour I would suggest:

Bloodspider:
Robot which should never hide & never panic, but strictly use all the time-units for approaching & killing the next enemy target. The Bloodspider should maybe strictly attack the enemy & ignore civilians, which would mean that eventual bloodspiders on the battlefield would be the first to attack our landing crew & would be a threat that would have to be dealt with as quickly as possible to survive...
The bloodspider's AI would not need much CPU-Power

Taman:
Those are described as being the most intelligent species, which also leads the other races when on the battlefield (group tactics ?).
They should naturally get the most advanced AI, but to avoid making them over-powerful as they will get 'Psionics' in later stages also, I would suggest massive cuts in their god-o-vision

Ortnok:
I would like to see those heavy, tough Ortnoks behave as brutal as possible, but I also would like to see them using dumb tactics & brute force by simply attacking the nearest target without making any damage calculation or without consideration if the next target is a civilian or enemy
I do not know, if I want to see the Ortnoks take cover, maybe we should make them just a little bit tougher, but more self-confident & straight-forward ?! I also do not know if Ortnoks should ever panic ?!

Shevaar:
This is the race with the best (infrared) visual abilities (they could imho keep their god-o-vision), they are described as moving fast (we should reflect this somehow visually on the battlescape also) & as being quite intelligent & tough, but still those are the ones taking orders from the Taman, when fighting together on the battlefield...

Here the link to the descriptions of the various races for your inspiration:

http://ufoai.ninex.info/wiki/index.php/Aliens

Thanx again to all folks making our aliens behave wiser & even more challenging , especially to nonickch or his late-night-twin nonickch-drinkin for investing all this brain- & workforce here !!! GREAT !!!

[shaunc311]

Just as a preface, I'm not that great at C, but it looks like if G_ClientShoot returns false, you don't have to call it 9 more times.  The only time it returns false is when no shot is generated.  If it wasn't a mock shot then it could return false if the reaction fire kills you, but since this is mock, that isn't going to execute.  I doubt that saves much CPU though since all the hard math comes after those checks. 

You might want to experiment with breaking out of the if(shots) if it returns false since 0 shots should land.  That might not be valid though since the AI actor could run out of ammo.

I hope that helps a little.  I tried building trunk last night and it hung on the loading screen.  Going to try again tonight.

[nonickch]

mattn's edition on the original diff includes the removal of a NULL player_t * being passed into G_ClientShoot. This would happen when HideNeeded requested GetDamagePotential. The null was my solution to G_ClientShoot returning false because G_ActionCheck reports 'this is not your turn'. This is logical ofc because we are mock-shooting for the humans in the aliens' turn.
ActionCheck though returns default true if "!player". We also need to skip ActionCheck because the TU's left on the human soldiers is next to 0 (we simulate the shots by checking vs 30 TU's worth of shots with the appropriate GetDamagePotential param).

Now, I found what caused all of my crashes, it's a visibility check that uses the (NULL) player_t when we are considering the humans tossing grenades. I took the liberty of enclosing that check in a "if (!mock)" check that seems to be covering all other visChecks in the code. If that's not viable for some reason, do tell me.
Now, for optimization in search trees, the higher-up you optimize (see: prune) the tree, the greater the overall gain. I did notice that the AI_Run is called on ServerFrame events, and only 1/10 of them is utilized. ActorThink is called way more than 8 times in the aliens turn, so that's the first place to start.
What are serverframes, when is AI_Run really called and why do we have to call ActorThink more than once for any alien is the issues I will solve... tomorrow, because today nonickch is hitting the bars.

Shaunc311: Yes that's one of the things we should see more into. I do indeed depend on the fact that ClientShoot will quickly return false. I will debug a few to see if there is any chance of G_ClientShoot returning anything but false after returning it one (you should be right with this one, but I just wanna make sure).
Update, the returning qfalse is "typedef enum {qfalse, qtrue} qboolean;", so we can't really make between 0-dmg because of a miss and qfalse because we can't take the shot.

MCR: I do love the customized alien behaviour aswell. Up to now I've seen 2 possible ways of doing that:
a) Behaviour: Move/tie GUETE values (or some of them) to a race/weapon-outfit. That can parameterize the aliens. If it needs to be LUA, I guess we could make LUA alter the GUETE's, then call AI_ActorThink. But aren't the alien stats scriptable?
b) Intelligence: If we ever incompletely search trees, the ordering of the candidate nodes decides the apparent 'intelligence'. Divert from best-to-worst to dumb-down.
I don't believe we're currently in any position to consider the extent of infra-vision. Maybe if we play with the CLOSE_IN metric... not sure. But in overall, aliens have the same amount of god-o-vision because we really have 0 visibility considerations in the AI (The last few we had I snuffed because of the vis flags). Once this cheating AI is top notch, then we can go from there.

For anyone thinking on running tests like these: Get CDT-Eclipse or go mental with any of your debuggers. I was slowly inching through the code untill I got my trusty eclipse up and everything sped along nicely. dcom_printf's are NOT to be trusted when you spam 100's of em.

[shaunc311]

I did notice that the AI_Run is called on ServerFrame events, and only 1/10 of them is utilized. ActorThink is called way more than 8 times in the aliens turn, so that's the first place to start.
What are serverframes, when is AI_Run really called and why do we have to call ActorThink more than once for any alien is the issues I will solve...

Just to save you a few minutes, I threw in some breakpoints and this is what I found:

ServerFrame is called every second no matter if it is the alien, civilian, or players turn.  90% of the time, it just returns (as you already noted).    The other 10%, it figures out if it's an AI players turn to move and then moves 1 player and then returns.  So one AI player every 10 seconds.

From what I could tell, ActorThink is called for every alien and every civilian.  That may be why you are getting more than 8 calls per turn.  The good news is that with the new super smart aliens, the civilians die in the first turn so there are less of them to calculate.

I was getting a lot of assertion errors in dbuffer.c so I could never finish an alien turn completely so this might not be 100% accurate.  When I get home I'll update from svn and see if that issue has been resolved.

[dodon]

I was getting a lot of assertion errors in dbuffer.c

I investigated this. Have no time now, will post later.

When I get home I'll update from svn and see if that issue has been resolved.

not likely

EDIT:
Assertions in dbuffer.c

[shaunc311]

AI_GetDamagePotential
...

The penalty we take on performance is quite significant. The fan-out may be only 10 (ontop of the previous one, for a total 160x number of leaves compared to 2.3 AI), but the tracing calculations needed here are a heavy factor.
Performance optimizations needed: An obvious proper bridge to the G_ClientShoot (no reason to try 10x, instead it can give us a base dmg+deviation), OR a complete copy of the damage calculations inside the AI code (bad, code replication&heavy maintenance). Best solution is a mathematical equation that can give us comparable results with minimal CPU.
For people wanting to try and extract the math equations, have a look at g_combat.c. Entry point is G_ClientShoot. HELP APPRECIATED, I SUCK AT MATH

Been looking at this at work today.  I have a couple ideas:

1.  Instead of 10x, what if we set up a delta value.  We run it once to get a base value and if the 2nd run is within the deltaof the first value we just return the average of the two.  If it isn't, we keep running up to 10x until the average is within the delta. 

For example:
delta = 10
run 1: damage = 100
run 2: damage = 94 (avg 97)
returns 97

or
run 1: damage = 100
run 2: damage = 25 (avg 62.5)
run 3: damage = 44 (avg 56.3)
return 56.3

2.  Personally, I like the project management time estimation formula ( (worst case + best case + 4x most likely) /6 ) So we'd run it at least three times.  Take the best, worst, and average.  Then put it through the formula.  The 2nd example above would return 58.3.

AI_HideNeeded
...
Now, this function is what cause the MAJOR fan-out disaster of doom. If you exclude the changes in this function, the AI is fast enough to play, but here we fan-out again, ontop of our 160x worst case scenario. For every of those leaves we check the damage possible for every enemy. Yes, that's another set of the same fan-outs we had up to this point (we just have num_enemies, not num_enemies+civilians). So that's a worst-case scenario of 8, bringing our fanout up to 8x10=80. Since this is in sequence with the damage calculations, this is multiplicative bringing the total amount of leaves to 160x80=12.800 for a worst case scenario. Yes, this is the point where the CPU just shrieks and tries to liftoff. And don't forget, the shooting calculations are a whole lot heavier than any other calculation we ever do.
Obviously, this would need to be another place were we need to improve quite a bit if we still intend to perform full-tree non-heuristic searches. Only checking only vs enemies that have a direct line of sight would be a first step (but that would make us oblivious to indirect-fire nades/launchers). Other than that, I can't see many ways to keep this functionality and still preserve a full-tree searching. The performance of this function is mainly influenced from the AI_GetDamagePotential function, so any performance gain (in fan-outs) there affects this function in a sqrt kinda of way (8x8 vs (8-Y)x(8-Y)).

And a couple for this as well:

1.  Still go through every actor, but only do the calculation if the actor is visible or has a grenade/launcher weapon.

2.  Maybe if one of the 10 calls to G_ClientShoot returned a value higher than the  HP * GUETE_DAMAGE_AVOID_FACTOR, that would be enough for them to hide.  So stop looping if that happens and just make them hide. 

[nonickch]

Shawnc311:
I don't use the 10 shots to get an avg damage, that is going to be pretty stable because the rand variations on damage are pretty miniscule. I run it so it can take into consideration a good amount of the hit probability. This is especially true with low-accuracy explosive weapons. So essentially I'm taking back the old dmg*hit-% metric. The more I think about it, the more I'm convinced we just have to duplicate the hit mechanics employed in the G_Shot functions:
a)Calculate the shooting origin of the weapon
b)Calculate a line that intersects the point we want to shoot
c)Apply rand&accuracy deviations on each axis with some gaussian rands.
d) Trace the modified line and find the first object that it intersects.
That wouldn't be that difficult to replicate, and the damage calculations are even easier. The real problem is the explosive weapons.
Mattn/other people that work on g_combat.c: What's the real use of the mock shots? Can we ninja-in the mock structure (and the shooting code) values that would stop us from having to sample shots?
It's not so much as the base dmg (we could easily estimate that) nor the % to hit (we could use the UI estimation function). It's the LOF issue which we cannot substitute with LOS. And remember, we don't deal with only one LOF, we deal with a 'window' to the target, since we don't always hit spot on and that's where the partial cover really comes into play (I guess we could skip the window calculations in favor of speed without sacrificing a lot).

1. Filtering by vis before taking shots: That's a very logical thing to do, and doesn't seem to be that hard (UNLESS that ent-to-ent visibility function uses the visflags, then I'm fked).
2. Aborting on shot > maxDmg. Sheesh! I can't believe I made such a nubbish mistake. I'm moving the entire if statement inside the loop to constantly keep checking the total mock damage vs the dmg_avoid_factor

I scaled the sampling down to 5 checks and now 4x4 is quite playable (still weeding out a bug that makes aliens try to take more shots than they can).

I also have a confession to make: I think I was mistaken in my assumptions (at least partly) about god-o-vision and the vis flags. If I'm not mistaken what I thought as a 'bug' was actually what was holding the AI back in terms of unlimited vision (quite crafty too). So, I worked under the assumption of that and amptly handed out vision to the aliens in my current code. Nonetheless, I do believe we should first see the results of the pending changes, then contrast them vs the 2.3 AI behaviour (with the augmented dmg calcs included). We could also slap on bestAia re-calculation every time a visibility event is thrown (at which point visflags should get recalculated) for some extra spice (for the 2.3 because the current work sees all).

Also, there are no performance issues with multiple calls to the AI_ActorThink() as I thought there would be. Oh well, good ole optimization needed then.

[shaunc311]

So are you looking for a cheap version of G_ClientShoot that does the following(going down the lines in G_ClientShoot):

*ignores the if statements in the beginning that make sure you aren't shooting yourself and you have ammo(ammo check is done in ActorThink)
*probably keep the range check
*ignore the ammo check for multiple fire shots?  Or keep that?
*still calculates the visibility
*call G_GetShotOrigin (part A)
*fires the shots
*does the else part of the last if

Is there anything in shootGrenade or shootSingle that you'd also want to remove?  I think those methods will do B, C and D for you.

We could probably call those shoot methods a couple times to get a window of LOFs if that is more what you are looking for.  Not sure how expensive that is though.

[dodon]

Mattn/other people that work on g_combat.c: What's the real use of the mock shots? Can we ninja-in the mock structure (and the shooting code) values that would stop us from having to sample shots?
It's not so much as the base dmg (we could easily estimate that) nor the % to hit (we could use the UI estimation function). It's the LOF issue which we cannot substitute with LOS. And remember, we don't deal with only one LOF, we deal with a 'window' to the target, since we don't always hit spot on and that's where the partial cover really comes into play (I guess we could skip the window calculations in favor of speed without sacrificing a lot).

I encountered the mock shots in reaction fire. 100 of them are used to calculate the chances to hit and the chances of friendly fire. I think there is also a formula to calculate partial visibility.