Development > Coding

the AI discussion

(1/19) > >>

nonickch:
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 :P

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  ::)

Mattn:
wow - that sounds like it's not the first time you look into ai coding ;)

i've commited your flowcharts to the svn - they are quite handy.

the lua ai should (someday in the future) replace the c-ai - but the c-ai is currently still more advanced (even if you find a lot of flaws in it).

i'm sorry, but i don't have 9 hours to write an answer ;) - and don't remember all the questions you asked in your post so if you would like to know something particular, please ask - i will try to answer some stuff.

the server will allow you to check above your TU boundaries - but there is a max step width in the server to limit the cpu time that would be needed to calculate this (see Grid_MoveCalc).

about "Actor limitations are hardcoded and not configurable": this is (or should be) in teamDef_t and in base/ufos/team_*.ufo

"Game balance is done with AI in mind" - i think if the AI would get smarter that would not have a direct impact on the weapon balance or something like that - "only" on e.g. the map layout - but this should be fast to fix in cases where this would be needed.

"Getting ufoai as coursework" - that would be quite cool - but to be honest i don't have an idea how to push something like that.

if you would like to improve or tweak the ai and would send patches we would include them with pleasure.

hope to hear more from your side

regards
martin

dodon:
The AI is quite weak and we should improve it.
So here are some random thoughts


I have not noticed MedPacs in your description. Are they missing?



--- Quote from: nonickch on June 28, 2010, 03:44:53 pm ---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.

--- End quote ---
After I noticed this, my successrate went up :)



--- Quote from: nonickch on June 28, 2010, 03:44:53 pm ---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.

--- End quote ---
I think the aliens go for the civilians (easy to hit/kill (no armor) + good place to hide(won't fight back if not killed))
So this might need some rebalancing



--- Quote from: nonickch on June 28, 2010, 03:44:53 pm ---Also note the huge values of the bonuses like hide. 60!

--- End quote ---
I would judge the hidingplace by these questions:

* can a Human kill me in the next turn?
* can a Human hurt me in the next turn?
* am I able to attack a Human in the next turn?


--- Quote from: nonickch on June 28, 2010, 03:44:53 pm ---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.

--- End quote ---
I would describe this action as go near a place where I can use my wappons in the next turn. And different wappons call for different actions:

* meelwappon: shortest path to a square adjacent to a human (never tried it, but I thought about stabbing through a window)
* direct fire: shortest path to a square with line of sight to a human
* indirect fire: ?

If I had do improve the AI I'd

* fix the fire through wall bug
* improve the "pathfinding"
* refacture the bad code (reload, equipt wappon, ...)and then check the new behaviour.

Marte:
nonickch = 1 titanic post to read, interesting too!
I like idea of pluggable (or something else) AI into game, could be really cool and join new people to project

nonickch:
Since people tend to skim the first few lines, some requests first:
* Right now I'm just fiddling with the #defs in g_ai.h, (the GUETE ones). Anyone can whip up a quick way so I could tinker with them from something like the console? I see some set commands in there, so I guess if I could use that functionality and replace all the uses of the GUETE defs in the g_ai.c? Things would go a lot faster as atm I'm just recompiling for each tested value :/
Help appreciated with some playtesting. I'm always on irc and typing my name there bleeps my client (I'm on GMT+2 tz)


--- Quote from: Mattn on June 28, 2010, 06:55:43 pm ---the server will allow you to check above your TU boundaries - but there is a max step width in the server to limit the cpu time that would be needed to calculate this (see Grid_MoveCalc).

--- End quote ---
What do you mean 'check'? If I accidentally ask the server to move the alien past it's available TU's, is it going to let me? Spit an error? Silently discard?
I bet I'm going to find out sooner than later, but just asking in case you remember off the top of your head
Also, you mentioned a couple of neat startup tricks like +set developer 1 and +map in irc. Is there a wiki page/thread detailing those?
Since you did put the graphs/project in the contrib/, I'd rather go make it prettier and more formal. I saw the LUA civvie graph there which I'll use as an example (oh, and if you look closely at that, the two levels of the graph are identical apart from a child node. So you can compact them by merging them and just sticking a conditional at the differentiating point. Remember my nitpicking comment? ;))

dodon:
Yes, medipacks are nowhere to be seen in the AI. And I have never seen medipacks as part of the loot, so I guess the aliens never carry them.
The civilian targets are already penalized by something like *0.6. I guess that's still not enough as I have seen a lot of cases where the aliens shoot them first even though I'm clearly visible and shootable. That will be part of the value tinkering.
The 'next turn' metrics you propose can only be implemented if we expand the search tree to another turn. That's one of the things to do after playing around with the #def's, as this will probably be not easy as it sounds. I do remember a comment about limited searching and the need to rewrite other parts of the code. Can be hairy.
Indirect fire seems to be totally out of the picture in the current AI. Grenades are a todo in a place where it shouldn't be that hard, but that's only for visible targets. Lobbing grenades above fences is not the same though since the AI does not consider targets that are not visible to the current actor. Finally, there's the part about calculating splash damage, since the hit percentage of a nade is small, yet the damage cause is still way above significant. Given the TU's needed to fire alien weapons, and a working grnade tossing AI, I wouldn't be surprised if they would insist on chucking all their grenades at the first opportunity (I'd laugh so hard if this happens, half your squad gone on round one in the close-quarter spawns).
As for the 'aliens shoot through walls', I'll have to read a whole lot more (or at least make the console start raining msg's). I haven't been able to reliable reproduce it yet, so fidling with something and then play 5 hours waiting for it to happen is not that feasible. That, and I can't really say I have a solid theory on why that happens. Maybe it's the same as the 'bug' the player gets: The target line is green (no obstacles), the hit % is good, yet all the shots strike an obstacle.
Refactoring the code and moving the snippets from actorThink and missionTargets from PrepBestAction shouldn't be that hard. It's probably the next thing to do since I do like to find things where they should be.

Marte:
The pluggable part is all about the LUA. I'm ambivalent at this point for that issue since I have absolutely no experience with that language. I also heard that someone recently implemented that, is he still around?
It's going to be hard(er) for me to get in touch with LUA than to get back to my olde C days. Then again if I get to use it, things will definitely go a whole lot faster. Plus it will make people much more interested in playing with it as it will be easier for them.
I do believe the middle road is much better. The primitives exposed to LUA by the C code could expand to encapsulate the more process-heavy, long-winded and least likely to change things like the damage calculations. Then all that's left to the LUA script is to deal with higher-level intelligence.

Right, my compile is done (why the hell did it recompress all the pk3's?). Going back to playing.

edit: bingo. Halved the hide bonus and the little critters started getting way more aggressive, at least in the spaceship scenario where most of them marched out and started shooting stuff. It was easier to shoot them, only after they shot to pieces every visible civvie in sight from the door. Clearly there's a lot to be gained here, time to go nerf the civvie shooting score. In the end, it will boil down to a collective descision on what the balance should be.
Hmm, can anyone say distinctive alien behaviours? If the scoring #defs are moved to the critter stats you can get per alien, or even better - per race, behaviours! Say tammies are more careful/hide-prone, where ortnoks tend to be more gun-ho. Maybe use the moral here aswell. Shot-up ortnoks are not that prone to leeroying.
Mmmmm, I smell nice things  ;D

Navigation

[0] Message Index

[#] Next page