Topics

1

Coding / the AI discussion

« on: June 28, 2010, 03:44:53 pm »

UPDATES:
1/July/2010: Updated diagrams (minor fixes and refactoring) and ArgoUML project file.

Morning everyone.

As you can guess by my postcount, I'm new in here.
So I decided to take a peek in this project. Models I can't do, I've got the artistic touch of a baboon, so what's left?
Coding!  

So, yesterday I grabbed my cold pizza leftovers and started scouring through the code. First place I went and checked was the AI. There were quite a few things that I found annoying at my playtime (24-hr sessions over a week on 2.3):
a) Aliens stupidly home in towards the closest phalanx member. They will promptly get stuck in a corner only 2-3 steps away from plasmablade-stabbing my squaddie in the face. This gets worse when there are aliens in their spaceship where they will clump on the other side of the hull where a squaddie is taking cover.
b) The AI is really predictable. Uncover, shoot, cover, endturn.
c) I have never been on the receiving end of the armageddon called a plasma grenade. No wonder I tend to place them in southpark-esque manpiles for maximum firepower. Only once have I been stabbed with a plasblade (thrown too!) by an alien, which promptly made me restart the mission. Why doesn't this happen more often? Even though carrying blades/nades is good for the loot, I doubt the aliens do it out of courtesy.
e) Let's face it, with the alien weapons, stats, positioning and perma-infra you should get have a REALLY hard time defeating any engagement, let alone the starting ones. Instead, this feels like a breeze every single time.

So, for my understanding considerations and for sparking a discussion on the AI, I made some half-*cough* diagrams. Bear in mind It's been ages since I've done any kind of standardized diagram, so I've just drawn circles and spammed chars all over the place. Bear with me and do fix the style if you'd like (here's the ArgoUML project file).

For starters, a brief overview and a disclaimer:
I've only reviewed the code for about 10 hours, I'm bound to be mistaken and have quite a few misconceptions. Please correct me whenever possible. I will probably be updating this first post if this thing ever catches up.
The AI is a score maximization algorithm that performs a (kinda) depth-first complete search over the tree of possible actions. There's a catch here ofc, it doesn't calculate the entire set of possible gamestates (that'd be a whole lot larger than the chess tree), it just takes turns for each of it's actors and creates/searches/executes a tree for all possible moves. Given that the outcome of a shot is non-deterministic and we can't know it's result prior to taking it, the scoring algorithm evaluates damage dealt with some human-like metrics: 'is it worth it?' etc. A whole series of other metrics like 'did I get to hide well enough?' are also added ontop of the possible damage metric to give us the final score for each of the tree's leafs.
It's also worth to mention that in no point does the AI cheat, it plays like a normal player, sees what you see. The AI cheats in the visibility sector, it will know if it can see a target from a spot before it goes there. Another minor exception to this that I've noticed is to not consider moving to a spot where one of the enemy (and yet unseen) actors stand on.

The main AI-centric file (the C AI, not the LUA) which I've examined is the src/game/g_ai.c one. Most of the interesting things in there are included in the following diagrams, with some notices about them:
* overall flow of AI
* Missing trivial/'inconsequential' things like 'exclude occupied spaces when calculating all possible move destinations'
* Only investigating sane aliens, crazed/angered aliens and civvies are ignored
* I didn't look into the gi object area, so pathing is not in there. (import_t object, I'm guessing it comes from the .bsp maps)
* You can spot the keyword 'IMMEDIATE' in some parts of the AI. This is done to differentiate between the thinking part and the execution part of the algorithm. Usually this wouldn't have been an issue but it does look like someone patched the code and ninja'ed in a hack or two (see AI_ActorThink early steps)
* You can spot some obvious function names in the diagram, it's there for your ease of referring to the code really fast.
* You will see me often pointing some 'shortcomings' whose implementation would be impossible or hard to do. I'm just theorycrafting in most cases and I do like to nitpick everything.
* I've split the AI into 3 diagrams (and more should be in there). They are presented in the sequence of execution and shouldn't confuse you too much.


Let's start with the main AI loop, AI_ActorThink.
When it's the AI's turn, this should (didn't check it and I have no idea what serverFrames are) be executed once for every actor in a particular ordering.
The diagram for this is quite simple:


Does everyone understand my diagram style? Good, neither do I from time to time.
The main reason of existence for this function appears to be the execution of the highest-scored action found (after requesting one).
I did mention before some hacks in the code. This seems to be the place. See the reloading and checking hands part? That shouldn't (normally) be there, it should part of the searching algorithm. We do flatten our tree quite a bit and we can end up doing silly things like:
-> If bestAction wants us to run far FAR away, reloading/equipping a gun first is a  bad idea jeans.
-> If bestaction wants us to stab someone, equipping that pistol from the holster instead of that knife from the backpack is counter-productive.
Also notice that we are executing only the shooting part of the best action here, prep does the walking for us. Oh well, fine with me
Now, some theorycrafting: Do you notice that each actor moves&shoots in sequence? That's limiting the tactical abilities quite a bit. I think this is quite obvious in the landing standoffs where you and the aliens are facing each other. Instead of thinning out your numbers before trying to get cover, each of the aliens shits it's pants individually and runs for cover. It would be nice to at least get a scheme for aliens to spend some of their TU's to try and see if the situation improves (remember, non-deterministic, so we can't/shouldn't make one common huge tree for all the actors).

Right, onto the AI_PrepBestAction part that's already been referenced:
This part of the code calculates all the possible moving positions for the actor and requests the scoring of what can happen from that position. It finds the best (by score) spot to move to with it's resulting actionSet (like move there, shoot that, then move over there) and executes only the moving part.

Pretty clear-cut I believe.
Notice the dual-path of scoring. I believe the right one is the traditional one and the left one was added for supporting mission targets. Do we even have mission targets in the game? At least we got support for those
I assume this is the part that will make the aliens dash for your alien containment/command center of your base once such a thing is in. Again, there shouldn't be a branch here, target evaluation should be part of the scoring code, but it's not bad enough to warrant a change (yet). This is the stuff that spaghetti code is made of

Well, that was pretty easy up to here, now for the hard part.

Welcome to the AI_FighterCalcBestAction
This function is called once for every possible spot each actor can move to. At the search tree we're at the last level of nodes before the leaves start. The whole goal of this function is to find what's best to do from a position. This usually entails shooting someone, but it may end up being just a nice hiding spot. All of the action completion and scoring happens here aswell.

This is where it gets kinda complicated.
Don't get confused at the 2nd level of cute baloons. I didn't know how to depict this properly without creating a huge diagram. I'm only trying to depict a set of nested while's there. It essentially says foreach_possible_target{foreach_possibly_firestyle{calculate_damage}} to find the maximum damage possible.
So, we can see that the basis and first hint at the scoring system is the possible damage dealt. After applying some of the bonii/malus to the damage expected, we have a semi-complete action (up to now it only had a moving part from prepBestAction) and it's basic scoring. I say semi-complete because we may end up adding more moving to it by the end of this function.
After this we start adding/subtracting scores according to some principles we make our fluffy little aliens like: hide, hide, hide and then try to close in the distance. Oh, and hide some more. The bonuses to the current score for things like hiding are #def's in the file and they start at about line 39 of g_ai.c. I have to notice here that there is a considerable impact on the AI by using absolute dmg balues as part of the score. At least this should (and I think it does in practice) make early aliens a bit timid, but when they get nice weapons they get a bit more aggressive. Then again if you add more armour it makes the pistol-wielders cry like babies :}
I got kinda lost in the fire calculations part. Especially with the LEFT/RIGHT & firing types. I might be missing something important in there (it's only abstract in the diagrams). There's a good chance the 'aliens try to shoot through walls' bug is in there because of the visChecked var. Not sure. Notable omission (of what should be another diagram): AI_HideNeeded
Also note the huge values of the bonuses like hide. 60! I'd make some guesses here on the behaviour this cause, but I'd refrain since it downed upon me that the search space is quite large for me to digest at this time. At least I would suggest some toying around with those #defs to see if we can get some nicer behaviour.

Do you remember my gripe about the aliens sticking to the other side of the hull of the ship when my squaddie is right next to it? I believe we can trace this behaviour down to the closing distance scoring. Notice that I do mention in the diagram that the distance used is the Vector, not the pathing distance. Combine this with the fact that the AI cannot possibly plan for more than one turn (we only ever check where we can go only this turn) and the scoring ends maximizing behind the wall because it is close by absolute distance and no other reachable spots produce anything with a better score (we're already hidden and can't reach to shoot someone). Obvious solution to this is to factor in the path distance aswell. Replacing vector with just path *might* be counter-productive since it usually also means firing distance when no walls are involced. This is probably worth checking in the immediate future.
A nice testing idea: Try expanding the searchspace of the PrepBestAction to spots reachable by twice the tu's of the unit (prefferably currentTU's+maxTU's since we might have reloaded. See why we shouldn't add actions outside the evaluator?). Ofc since the code is written for 1-move, we might have to double-triple check that nowhere does the AI try to move the entire length if tha'ts exceeding max TU's (does the server even allow us to do that?). That should at least broaden the horizon of our lovely critters and may bring an end to the hull-hugging and breath some air of longer-term planning to them. It could also end up unleashing the hell of mordor upon unsuspecting kittens across your window, you never know what will actually happen in such situations unless you try it. Performance might be an issue here aswell, we're not doubling the size of the search space, we're doing much more (running complexity calcs right now is out of the question, I need to get over with this post).

Also, look for the place where the actor needs to hide from danger. If I'm reading this right there's an OR where an AND should be. Am I reading this right? Input needed

It's generally great to hide/take cover, but I think this is where the 'aliens stick behind corners'. Like when raiding a house with a closecombat/flamer guy. If you stay like ~15 tu's away from him just around a corner next to a door, he will opt for closing in (CLOSE_IN bonus) and still staying out of your direct sight (HIDE bonus) instead of trying to get to a safer position or take a chunk of of your HP (better yet, introduce me to mr. plasblade). Do you know what spot seems to produce that max score? Yup, it's the other side of that wall, 3 steps away from me


OVERALL
It's not as bad as I thought it would be from my experience. Maybe we can get some quick and painless boost by expanding the search tree by extra moves-worth of tu's. Also, finetuning the score-bonus #def's? That's a lot of tinkering requiring recompiles and game restarts
Notice the full-tree searching (with limited performance cutoffs) that exponentially grows with all_moves->all_targets->all_shootTypes. This tree can quickly grow enormous and will probably create issues if teamsizes/numbers are ever scaled (hmmm, can I put like 10 AI teams+me in a map and watch the lagfest?). Then again for our limited usual cases this guarantees the best solution given our metrics.
There is absolutely NO battleplan and zero actor cooperation. We could do something like baiting without too much hassle? That's like a mini-battleplan. "Hey look, there's a smartass with a firebreather that can candle me, how about I bait him towards me past the corner where I'll the reaction-fire welcomming committee is waiting Hmm, that would require cooperation, pretty hard to do this in the current design. Maybe just coming to the aid of another cornered alien?

I hope this thread gets some discussion started about the AI, and who knows, some patching and a general housecleaning if that's not enough.

So here's some questions-notes I didn't compile into the wall-o-text but don't want to skip:
a) What's going on with LUA? Is it coming in sometime in the future as the standard higher-function AI handler? I heard something about a slowdown in pathing, what's the issue? Exporting the base AI functions to lua and working from there would tremendously help any development/testing. I don't even know if this AI is mirrored in the LUA so I can just opt it in at compiletime
b) Game balance is done with AI in mind. If the AI suddenly gets a whole lot nastier, how quick can the rest rebalance? (alien numbers/stats/weapons/numbers/introduction to missions etc)
d) Getting ufoai as coursework = influx of geeks. Given that the primitives to use are quite straightforward, I bet lecturers may consider using ufoai as a basis of teaching via real examples. You can't believe how crappy and boring enviroments are used even these days at the universities.
e) Actor limitations are hardcoded and not configurable (eg bloodspiders can't pickup things). That's going to hamper development quite a bit. Maybe we should be grabbing those from the creature defs (which I have no idea where they reside)
f) Official Performance limitations? X/sec/actor on Y cpu? How fat can we make our search tree and still get away with it?
z) Holy (academic) grail/solution for the AI: Machine learning (yea, I can kick your ass after I learn how you play) coupled with agent (ewh, I hate this term) system of planning and coordinating. Can I/will I try to do this?

HELL NO!

I may not have a life atm, but damn, I'm trying to get one, not permanently snuff it out.
Middle ground anyone? Only patching? Rewriting parts/whole of the code?

Oh well, this is what happens when the game locks up and eats my X a couple of times.
This is your punishment: Read this wall-o-text because I had nothing better to do