project-navigation
Personal tools

Author Topic: the AI discussion  (Read 60764 times)

Offline nonickch

  • Rookie
  • ***
  • Posts: 36
    • View Profile
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 :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  ::)
« Last Edit: July 02, 2010, 10:17:14 am by Mattn »

Offline Mattn

  • Administrator
  • PHALANX Commander
  • *****
  • Posts: 4831
  • https://github.com/mgerhardy/vengi
    • View Profile
    • Vengi Voxel Tools
Re: the AI discussion
« Reply #1 on: June 28, 2010, 06:55:43 pm »
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

Offline dodon

  • Rookie
  • ***
  • Posts: 48
    • View Profile
Re: the AI discussion
« Reply #2 on: June 28, 2010, 10:30:05 pm »
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?


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.
After I noticed this, my successrate went up :)


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.
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


Also note the huge values of the bonuses like hide. 60!
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?


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.
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.

Offline Marte

  • Rookie
  • ***
  • Posts: 46
    • View Profile
Re: the AI discussion
« Reply #3 on: June 29, 2010, 09:12:49 am »
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

Offline nonickch

  • Rookie
  • ***
  • Posts: 36
    • View Profile
Re: the AI discussion
« Reply #4 on: June 29, 2010, 02:39:17 pm »
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)

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).
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
« Last Edit: June 29, 2010, 03:18:04 pm by nonickch »

Offline Hertzila

  • Sergeant
  • *****
  • Posts: 469
    • View Profile
Re: the AI discussion
« Reply #5 on: June 29, 2010, 04:59:31 pm »
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).

This nearly happened to me once: 6 aliens, all who had only grenades as weapons (one had kerrblade but that's it). I had a laserguy on RF some distance away from the door, crouching. In their turn, every single one of them just walked out of the door and lobbed a grenade at that guy. I had my men behind the corner too so one bad bounce and nearly all my agents would be dead. Luckily, since they are just as good throwers as your agents (that is, even worse than an armless guy), the grenades missed by a good margin, no one turned up dead and only one guy suffered damage. My next turn was storming their "safehouse" where all of them were neatly packed in one corner.

Offline Mattn

  • Administrator
  • PHALANX Commander
  • *****
  • Posts: 4831
  • https://github.com/mgerhardy/vengi
    • View Profile
    • Vengi Voxel Tools
Re: the AI discussion
« Reply #6 on: June 29, 2010, 06:55:33 pm »
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)

make cvars out of them.

Offline arakis

  • Cannon Fodder
  • **
  • Posts: 6
    • View Profile
Re: the AI discussion
« Reply #7 on: June 29, 2010, 10:35:59 pm »
if this is a squad based game, how come the ai  is hamperd with every alien is for himself? I think it should be a priority to rehaul the ai so it thinks like a player, one entety controling all aliens and geting inputs from all aliens.  MO only, should not be  taken to seriusy

Offline Duke

  • Administrator
  • PHALANX veteran
  • *****
  • Posts: 1037
    • View Profile
Re: the AI discussion
« Reply #8 on: June 30, 2010, 01:35:25 am »
@nonickch:
First off, welcome to these forums :)

Secondly, kudos for your (almost)precise analysis of what the AI code does. It took me much longer to figure that out. And thanks for writing it down ;)

1. Would you mind to transform your first post into a wiki article about the 'as-is AI' ? Somewhere in the vicinity of the BSP and pathfinding articles would be suitable imho.

2. Fiddling with the GUETE_* values is fine. I bet you can heavily influence the AI behaviour. But imho those values should NOT be made cvars unless restricted to debug mode (think: bug reports!).

3. Imho LUA is NOT the way to go yet. AI mostly has a performance problem. LUA will certainly not speed up AI.

4. We should define a limit for the duration of the alien turn on a contemporary machine. Afaik this has not been done yet. I'd suggest 2 min.

5. Having #4 in mind, a two-turn look-ahead is currently not really doable. btw to get the crew out of the harvester cockpit, you'd need a three- or four-turn look-ahead !

6. Sure enough I'd like to see a team-behaviour. Do you happen to know about any concepts for that ?

7. Always keep in mind that it doesn't help us to have a perfect (slow) AI that forces us to downgrade the firepower of the aliens. What we want is playabilty without too much NS (=natural stupidity, pun intended).

Imho your analysis of the AI code justifies immediate commit access to the svn, but that's up to Mattn (the rule is: send a patch that we accept).
Also let me express the wish to make a person with your skills a *permanent* member of the UFO dev team (provided you keep on discussing before committing).
I know AI is every programmer's darling, but there are several even more important places where your skill could help...

Offline Mattn

  • Administrator
  • PHALANX Commander
  • *****
  • Posts: 4831
  • https://github.com/mgerhardy/vengi
    • View Profile
    • Vengi Voxel Tools
Re: the AI discussion
« Reply #9 on: June 30, 2010, 06:48:12 am »
@Duke: Keep in mind that the game frame (and thus the ai frame) is threaded now - the ui would not interrupt when the ai round is running.

Offline bayo

  • Professional loser
  • Project Coder
  • Captain
  • ***
  • Posts: 733
    • View Profile
Re: the AI discussion
« Reply #10 on: June 30, 2010, 11:22:08 am »
Quote
3. Imho LUA is NOT the way to go yet. AI mostly has a performance problem. LUA will certainly not speed up AI.

AI is something need tweek and rework.. All computation need resources like paththinding, bsp access... is/will only be a C binding. Scripting should be the way, and one day if we found the final AI, we can speed up it with C. Before that, working with C will only need a harder work without a sure result.

Quote
Keep in mind that the game frame (and thus the ai frame) is threaded now - the ui would not interrupt when the ai round is running.
Is everything is already protected by mutex? For UI at least the main game frame should be pretected avoiding thread accessing resources (for example if AI need to read/edit cvar or thing like that).

Offline nonickch

  • Rookie
  • ***
  • Posts: 36
    • View Profile
Re: the AI discussion
« Reply #11 on: June 30, 2010, 04:41:04 pm »
This nearly happened to me once: 6 aliens, all who had only grenades as weapons (one had kerrblade but that's it). I had a laserguy on RF some distance away from the door, crouching. In their turn, every single one of them just walked out of the door and lobbed a grenade at that guy. I had my men behind the corner too so one bad bounce and nearly all my agents would be dead. Luckily, since they are just as good throwers as your agents (that is, even worse than an armless guy), the grenades missed by a good margin, no one turned up dead and only one guy suffered damage. My next turn was storming their "safehouse" where all of them were neatly packed in one corner.

Hmm, interesting, I was under the impression that the AI couldn't lob grenades. That should teach me to read the code better. Which leaves me to go figure out what the nades @todo is all about.

make cvars out of them.
I got wind of that some time yesterday. I've now made a modded g_ai.c file that utilizes cvars. That's only for finetuning the AI and as duke says there's no reason/point to ever commiting that. This will be my main focus later on in the post, trying to gauge the actual effect of the GUETE values (and not just assume as I did up to now). Here's the modified file. Essentially FighterThink utilizes cvars (with the same name as the GUETE #defs, only in lowercase) with exactly the same names. Also there's an g_ai_kill (in AI_Tun) option that disables the AI so you can maneuver your guys at peace and test specific scenarios.

if this is a squad based game, how come the ai  is hamperd with every alien is for himself? I think it should be a priority to rehaul the ai so it thinks like a player, one entety controling all aliens and geting inputs from all aliens.  MO only, should not be  taken to seriusy
'thinks like a player' is not something even theoretically reached, given that we don't really know how any player thinks. What we try to do is make it look like it thinks like a player. Depending on the situation, this can be harder than others. Look at the chat Turing tests, there's not much AI behind that, just games with words and proper grammatical analysis. In a squad-based game like this, one would expect at least some form of plan discovery and execution. Baiting is the simplest of cases, fire&maneuver is another one. The problem here is that planning lands us spot-on in the machine learning parts of AI, where brainsuckers lie (I'll rumble about this a bit later). Even though fire&maneuver requires us to define and translate to gameterms higher semantics (squads, maneuver directions, and above all 'situational awareness' concepts like controlling parts of the map), baiting we could probably get away without all those stuff by adding some smart metrics to the algorithm (check enemy weapon, check if using it on us in his next turn reveals him to one of our teammembers with RF on). Although even in this simple case we'd now have to search trees for possible enemy moves and suddenly have some kind of cooperation between the 2 (or more) participants of the trap (you could just check if the executioner has finished his turn and has RF, but this will be unlikely to ever happen).

1. Would you mind to transform your first post into a wiki article about the 'as-is AI' ? Somewhere in the vicinity of the BSP and pathfinding articles would be suitable imho.
Since reformatting the AI diagrams is definitely on the todo list, I can do that at the same time. I just need to read up on the parts I really didn't understand so I don't have any gross mistakes (see part where I thought nades are never used).
Imho LUA is NOT the way to go yet. AI mostly has a performance problem. LUA will certainly not speed up AI.
Pretty much with you on that, but I do have to note down that LUA does not have to ever touch the processor-heavy parts like the trees. Simple primitives like the ones offered atm by the C interface would require the LUA to perform the entire tree searching, which is probably a no-no. But if instead we provide only/also higher-primitives like the entire FighterGetBestAction, then the LUA has limited cpu impact, but also limited AI impact aswell. Maybe sometime in the future it'd be nice to have that so lua-modders can do simple things like ignoring the result and/or executing it differently. Conga-line mod it is!

5. Having #4 in mind, a two-turn look-ahead is currently not really doable. btw to get the crew out of the harvester cockpit, you'd need a three- or four-turn look-ahead !
2 minutes is a whole lot of time, and kind of excessive. I don't think I've seen a turn take much more than 30 secs on my amd 2500+ cpu.
If we go after the extra lookahead and if it does prove to be very slow, there are quite a few things that we can do to drastically cut down on the searching time, depending on the concessions we make:
a) If we don't want to sacrifice ANY of the perfection a full-search algorithm provides, we can place strict searching cutoffs. A classic cutoff is the following: We are sitting in front of an enemy, we have a plasblade in our hands. We know that the damage we can deal is 100HP, plus the GUETE_KILL bonus of 30), and we can easily hide after the kill while still being close-ish to the enemies (hah, now that I think of it the AI probably considers in the distance-checking the enemy that's about to die. Minor issue tbh). So that's another ~70 pts amounting us to the ungodly amount of 200. At this point we should stop searching as this is the theoretical maximum. This is an extreme case ofc, but we can adjust for other cases: if 200 is the max, and we can achieve 150, we should never consider any tiles from which we cannot hide, since the max of those would be 140 tops. Now, if you order the checked tiles by path distance from the current spot (instead of foreach_h{foreach_y{foreach_x}}, you should be reaching some high-valued scores early enough (since you have more tu's to shoot&hide). This means that the cutoffs will kick in sooner.
b) Apply heuristic cutoffs. These are unproven 'human intuition' rules, which are already employed in the AI (see the damage calculations where there are cutoffs based on expected dmg and target visibility). An example could be: 'If your current max score is 100, do not consider tiles that are further away from the closest target'. Or: 'The most score deviation you can get from two adjacent tiles with the same visibility is 20, calculate the center tile and check the neighbors with the current max to see if it's actually worth calculating the full score'. Depending on the quality of the heuristics, you can easily prune the tree really fast without loosing many cases where the score would be higher. You could even order the nodes according to the likelihood they will produce better results and process them in some ad-hoc sequence while having a timer ticking that tells us when to stop. Iterate best-to-worst for the max possible results, other ordering for adjusting the AI strength according to a game setting and/or an alien intellingence stat. Holy crap, I really liked this idea.
c) Full tree searching is something rarely done. There' a whole lot of other algorithms for incompletely searching a tree that may produce 'good enough' results. A classic example is a greedy algorithm where it will simply try to maximize the score at each step and ignore all the rest of the tree's nodes (can search insanely large trees, has obvious shortcomings: in chess, it would never sacrifice even a pawn, eve if the next turn could produce a certain check-mate). I'd need to refresh my theory a bit more on this scenario, as the choice of algorithm is heavily dependent on the application and a bad pick will easily produce poor results. This case really is more or less like (b).

WARNING: Theorycrafting mostly
Finally you can (mostly) forget about the search tree and have a machine learning aided algorithms to be your daddy. My understanding on the applicability of these algorithms in our case is on a totally different level regarding how they discover the proposed action:
At the current tree-searching AI, we go bottom-up: given all the primitives, we try to combine them into a set that maximizes a score. The machine learning would go about doing the inverse, given a set of of integer-based(usually) semantics that describe the current situation (like 'control' and 'firepower'), find an abstract tactic to employ by discovering what happened in similar situations in other games. (one could say that the edict_t's could be enough, but we do need a limited amount of variables or risk getting absurd results). Like 'retreat to X', 'entrench to Y', 'flank Z' etc. Then you properly decompose these to the basic primitives (with search trees like the current one if you like).
You may ask yourself, 'if you assume we can easily decompose the tactics to primitives' why on earth can't I just skip the machine-learning algo's and find some other simple way of deciding which play to enforce? Well, I'd love to see the person that can do that. It may seem obvious to a human to observe the battle and decide which tactic is proper, but try to put that in code while generalizing enough to have a play for every possible gamestate. What the machine learning offers us here is the automatic discovery of this algorithm if given enough examples. Some machine learning algorithms can even produce a human-readable result, but from what I've seen they generally suck for complex situations such as this (rule-producing algo's).

So, off the top of my head, here's the things that would need be done in order to try (and I do mean try, nothing says this will guarantee better results than the current AI):
* First of all, we need metrics of 'success' in order to evaluate the result of a fight. Doesn't have to be formally defined if we employ strict supervised learning where some people go through the results of hundreds (or thousands?) of tests and assign a score to the result. Unsupervised metric could be simply the % of HP dmg we have caused to the enemy. Finally we can even have the algorithms learn-as-they-go (part supervised, part unsupervised), where they will augment their home-made knowledge with the results of every battle they take (this also leads to adaptation and countering a certain gamers playstyle). This last one is pretty ninja-looking stuff and does produce a totally different experience for every player.
Here's a set of notes that I'm just too bored to translate in the wall-o-text:
* Learning algo's need to define a situation in a small subset (say, max 12) numeric NON-CODEPENDENT (can't stress this enough) values that define the current battle situation. How on earth can you do that? I can imagine defining 'control' the % of space that is visible, 'firepower' the avg dmg you can apply on the visible tiles etc. Finding the proper set of descriptors can easily surpass in importance of the selection of a proper algorithm in terms of success. PCA can help a lot here.
* Depending on the selected algorithm, it would be helpful to have a simulator for gaming on it's own to gain experience. I guess it's possible if you make the AI to talk to a stub instead of the server.
* Needs a large (the larger the better, say well over a 100) of multiplayer games (maybe not entire games, but just a few turns) where the tactics are employed (and properly annotated somehow) by humans so it can actually get a starting 'knowledge' from somewhere. This could instead be just playing against the AI yourself and then evaluating. You could even ask the general public to do that, although I'm guessing the results will not be that reliable because of the different skill of the players.
* Some of these algo's are lightning fast (really, next to 0 execution time, see SVM's), but those are the ones that require most of the work done in the learning part.
* Since we're dealing with plans and not individual moves, we're transcending the confines of a single, or even, a couple of moves. The decisions are made in a way that are more likely to provide us a favorable outcome for the entire battle, not just a particular move. Every time the battle changes (every shot, every new visibility etc), we rethink our strategy and keep on going.
*The list of algorithms and their modded counterparts is quite extensive, and can range from a simple&straightforward Bayes-theorem application to dark-magic neural networks (which are silly-easy to code, yet picking the correct parameters seems more like a game of chance). If these last few paragraphs gave you a hard-on, try reading some wikipedia and then you can go from there.
Steven Fry is more likely to get out of suspended animation before I can manage to (convincingly) solo-code these things in my spare time.

Offline nonickch

  • Rookie
  • ***
  • Posts: 36
    • View Profile
Re: the AI discussion
« Reply #12 on: June 30, 2010, 04:41:39 pm »
Next up: actually doing some work rather than babbling: Observing the behaviour of aliens according to the GUETE_* #defs
For these, I employed the modified g_ai.c file attached at the start of this thread, and start playing with the numbers.
One of the things to notice, is that you cannot really assign a distinct GUETE value to a type of 'behaviour'. This is a direct result from the fact that the values are adding/multiplying ontop of each other, so the actual behaviour is the sum of all the values. Some initial testing verified this, so instead I decided to try and get some general idea about what happens for extreme values of each of the defs. So I keep the standard values for all but one in each test. Then the next step is to find a 'best' value for each of them and combine them.
Then re-optimize each value with that new set of starting values etc,etc (which can be a work in progress forever).
The list of GUETE defs toyed with are:
GUETE_HIDE: default 60, the bonus(additive) score for being hidden at the end of the move. Double the bonus if there was no target.
GUETE_CLOSE_IN: default 20, the bonus(additive) score for closing in on any of the enemy soldiers. This is used as a 'don't dash to the enemy before shooting him' (bonus=GUETE_CLOSE_IN-move) and also as a bonus for ending up closer to the enemy soldiers at the end of your turn: score+= guete_close_in->integer * (1.0 - minDist / CLOSE_IN_DIST) (absolute distance as in 'it doesn't matter if it's 1000 steps away in pathing distance'. Also AI cheats here as it checks all entities, not just visible ones). close-in dist is set to 1200 in the defs and I didn't really touch that, minDist is the distance from the closest opponent.
GUETE_KILL: default 30, the bonus (additive)  score for expecting to kill an entity with the shot you are considering to make.
GUETE_RANDOM: default 10, the randomizing bonus to an action. This is set to zero on all the tests in order to avoid skewed results.
GUETE_CIV_FACTOR: default 0.25 (or 25 in the cvar version), the (multiplicative) malus for shooting a civilian. This nerfs the base damage score because we're shooting a civilian.
even though I've cvar'ed other GUETE things, they are mostly about the civvies and the LUA AI, so ignore them.
I will be using 4 thresholds on each test: -1000, 0, default, 1000. This should tell us what behaviours are influenced from this tests. Observations are mainly a comparison between these 4 values.
My test map is the first one that pops-up in the skirmish: +africa small.
I observe the first 4 turns of the game without moving my units. Deviations from this only where otherwise mentioned

So, without further ado:
GUETE_HIDE (WARNING: if you're using trunk >=30780 or just dodon's patch in the following page, this observation goes out the window)
Right, default value is 60. This means that given a  choice of expecting to deal less than 60 dmg OR hiding, the alien will opt to hide. That's a pretty harsh value I believe.

default(60): Well, the classic behaviour you all know. Aliens almost always opt to end up hidden. Bloodspiders don't dare attack me in fear of staying visible at the end of the turn (which ends up with them perma-hiding in a bungalow next to me). After 4 turns only one of my exposed squaddies is dead and about 4 civvies. Quite depressing.
-1000: madness! The aliens simply refuse to stay hidden. In the first turn 7 of them become visible, the 8th just didn't have enough TU's and appears at the 2nd turn. Since they don't seem so preoccupied with hiding behind a basket, their itchy trigger fingers produce (in the first 4 turns) 4 dead civvies and 6 of my squad members. A 7th is running around rumbling and the 8th is slightly injured. And that's with the 3 bloodspiders dashing from the other side of the map and one alien having no weapons on him after turn 2.
0: Splatter. 6 civvies dead and my whole squad at turn 4 (at turn 3 all were mad). I'd attribute the better killratios to the fact that the -1000 was hampering the alien movement by forcing them to end their turn in visible spots. The aliens don't seem to have any prefference to staying hidden or not (makes sense, bonus no longer applies).
1000: Aliens really love their hiding, as expected. This ofc has a drastic effect on their damage. 4 civvies dead, only one of my soldiers slightly injured. The pop-shoot-hide occassions are next to non-existent (compared to the default value). I'm guessing the aliens were so afraid of getting seen that they couldn't even get to a pop-shoot-cover position.  Only in turns 3-4 one alien found a far-away cover that could produce a shooting spot next to it. Result: 2 hits with a pistol. All of the dead civvies are in areas I don't have vis on. Strange flukes: An alien is staying still and visible behind a fence, I guess he considers it hiding even though I have a 20% shot on him. I guess this implies hide may refer to (possibly exclusively) to cover. Need to revisit the code for that. Also: A bloodspider parked 2 tiles away from a soldier of mine (while visibleofc ) while dashing towards an empty bungalow next to the soldier (spider hid in there and staid there till end of test). I don't really know how this could've produce a max score, as it could've hidden on the other side of the bungalow. Maybe the hiding doesn't only refer to my team, but the civvies aswell (contrary to what I remember from the code).

Some general thoughts/notes:
*map design prolly affects aggressiveness penalty caused by the hiding bonus value.
*possibly nice heuristic because of the preference of aliens for pop-shoot-hide spots: explore such branches of the search tree first(prepBestAction checks these first against FighterBestAction), since they are likely to produce high-scores (so cutoffs prune the tree faster).
* aliens-shoot-through-walls happens a lot in this map, interesting.
* General observations: >0 values increasingly lower the lethality of the engagement. It does expose them to coutnerfire though. Values <0 increase the lethality, although in a much lower pace and are also counter-productive to the survivability of the alien. Stands to reason to ignore negative values.
*I suspect the best value is somewhere between 0 and 60, possibly around the 30's area. Needs real combat testing to really evaluate and it's really a matter of personal choice which battle style is preferred.

GUETE_CLOSE_IN
As mentioned before, this value is both used for:
* Take shorter paths to the shooting spot (as the comments mention: don't run around the target before stabbing him)
* Force the aliens to get closer to the enemies (in cheat-o-vision) so the engagement can happen sooner or later (also should avoid searching for forgotten aliens in rooms with little vision).

default value (20): At round 4, the aliens have killed 4 civilians, slightly injured one of my soldiers. Most of the aliens have only crossed about half of the map, cept for spiders which are now hiding in the closeby bungalow
<ah... defeatfear theme kicks in. Taking 5 mins to headbang to it>
-1000:
The Ballad of Brave Sir Robin
Bravely bold Sir Robin rode forth from Camelot.
He was not afraid to die, O brave Sir Robin!
He was not at all afraid to be killed in nasty ways,
Brave, brave, brave, brave Sir Robin!

He was not in the least bit scared to be mashed into a pulp,
Or to have his eyes gouged out, and his elbows broken;
To have his kneecaps split, and his body burned away;
And his limbs all hacked and mangled, brave Sir Robin!

His head smashed in and his heart cut out
And his liver removed and his bowels unplugged
And his nostrils raped and his bottom burned off
And his pen--
Right, 4 rounds of the aliens running away to the furthest possible spot, blocking each other en route. 0 shots fired, funny to behold. Hiding was not affected as much (couldn't see many of em at end of turns), but that has probably something to do with the fact that the furthest edge of the map had a my line of vision almost completely covered with bungalows. I'd definitely expect them to totally ignore cover (or anything else for that matter) in favor to running away. Another thing I noticed is that reaction fire has nothing to do with the AI, from the looks of it, all leftover TU's on aliens are automatically used for RF (either that or they can always RF, don't know which).
0: 5 civilians dead, 1 squad member. Interesting things to point out is that this happened from pretty much 2-3 aliens, all ranged. After disabling ai with g_ai_kill, I took a strawl and found that the rest of the aliens were hidden in spots that could produce any shots within walking distance (this causes the BestfighterAction to return 0 and force PrepBestAction to stand still). Blood spiders seem to be completely useless at this value as they will never enter a range where they could reach their target. The aliens would also refuse to take a diagonal step ahead which would produce the same hiding spot, yet a closer range to shoot from. Apparently the hit % bonus is not strong enough to force this on it's own (rounding issue? this was observed on a pistol wielder).
1000: 7 civvies dead and all of my squad on round 4. Hiding feature seems non-existent too. I did see aliens move away from my soldiers which probably means they were getting closer to a civvie. Ah, that's the perp, the code rewards total distance closing in AFTER shooting, and the distance is to any non-member (so civvies were the case). That'd explain most of the civvies dying first.

Some general thoughts/notes:
* positive values definitely help agression&map completion by bringing the enemies closer to you, which also helps them explore more of the map. Negative values could be used only in strange cases (hunts) or a simplistic civvie behaviour (I believe civvie AI uses a similar method, not sure since I've only glanced at it 3 days ago). Also this value does influence the hiding behaviour since at high enough values it can overshadow it. I don't believe though we should ever investigate such high values. From this simplistic check I found that the default value looks ok. It's high enough to progressively bring the enemies towards you, but it's not large enough to overshadow shooting stuff or hiding. If someone wants to further experiment with this value, I'd suggest the 20-60 range (at 60 we interfere with hiding a lot) with a focus on the 20-30 range (remember, we're cutting in the agression by preferring a dash instead of a shot). Bear in mind that the large close_in bonus happens AFTER the shot, before that it works as a malus:
Before: max(guete_close_in->integer - move, 0)
After: guete_close_in->integer * (1.0 - minDist / CLOSE_IN_DIST)
Bear in mind that I intend to modify the 2nd part by factoring in the path distance (try to avoid having them stuck behind the hull of ships)

GUETE_KILL
A simple additive score boost that rewards killing a target. Default value of 30, which gets an additional bonus if the target was in reaction-fire mode (GUETE_REACTION_ELIMINATION). The extra bonus should make agression to RF'ers prefferable, but would make this test a lot harder (aliens dying), so I don't put RF on, and as such I take the reaction_elimination out of the picture.
default(30): Using the 4 civvies dead & 1 squad member that seems to be the result of the previous tests
-1000: 3 civilians dead and one injured squaddie. Interesting to mention that the alienn that landed the hit on my squaddie immediatelly switched fire to a harder target. One would expect that there should be 0 deaths with this value (I did), but then I remembered that the dmg score also factors in the hit %. So those deaths were probably the 'lucky' hits.
0: Interesting results. Only 2 civilian kills and one heavily injured soldier. I can't really explain the result, someone care to repeat this test and see what he finds? Supposedly this value would make the aliens ignore whether they'd kill someone or not and make them go for raw dps. Instead, I get minimal dps&deaths. Will have to repeat myself sometime.
1000: 2 civvie deaths and some melee enemies sitting next to my soldiers visible, doing nothing. This gets weirder by the moment. Redid the test, same results. Maybe I need to see this with a cleared head at a later time.

*Bloodspiders/melle heavily influenced by this metric, at least in the negative values where they just freeze up.
*Initially i thought that this could be used in order to make snipers prefer larger distances. Then I realized that this would make them useless at close-range, unless the value is somehow tied to the weapon (so we could theoretically force a weapon change?)
* due to the probabilistic nature of when this metric is applied, it's not that easy to weigh it without repeated tests. I can only go as far as to say that this *should* affect how flims a shot the aliens are allowed to take when a possible kill is involved (might partly explain why aliens somtimes prefer to take shots to civvies further away, despite the civ-target nerf. The other reason ofc being the large base dmg because of the lack of armor).


GUETE_CIV_FACTOR
This is a multiplicative malus that is directly applied to the damage expected, right before it becomes the base score for this action: dmg *= (guete_civ_factor->integer)/100.0
Please note that the original value is a float, but I switched it to an integer and added the "/100" part. I'll still consider -1000 and +1000 (rather than -100 and +100) since it still makes sense to check for extreme ranges first.
default(25): Copy/pasta from previous examples, 4 civvies dead and one squaddie
-1000: 2 civvies dead (??!!) and one squaddie. The 2nd civ death was a collateral from a grenade launcher, the first one I believe was because the civ was in the line of fire. Other than that there were civs sitting right next to the aliens and were completely ignored.
0: 0 civvies and 3 squaddies dead (damn that alien with that plasma grenade launcher). This time no civvies were in the line of fire. Despite the difference of the results, I'd say this was a fluke. Both this and the previous example should be identical, since it's multiplicative and makes the aliens totally avoid targeting civvies
1000: lots of kills, that guy with the bazooka got a monsterkill. Only behavior worth to mention here is that at no occasion would an alien pick try and shoot a squaddie of mine instead of me. There was an occasion where I received direct fire, and that was from an alien that closed-in, and from his hiding spot he could only reach my squaddie.

notes:
*This is a pretty clear-cut case. It handles how willing are the aliens to shoot at civilians. This indirectly affects other behaviour by letting civ-shooting get in the way of doing other things (like shooting your squad).
* I believe the original value of 25 (0.25 in #defs) is too large. I'd reccomend looking to something closer to 0.15, maybe less. Remember, most civ hits are kills, so the dmg (how many hp's do civvies have?) will usually get the kill bonus (I don't know if the auto-RF makes civvies flagged as RF. That'd also add the RF eradication bonus ontop). So, if a civvie has 50 health, that's 80 base score for certain hits, which can easily overshadow aggression towards your team in many occasions.

OVERALL & NOTES:
* From those simple tests, it's obvious that the GUETE values don't just affect dramatically the efficiency&behaviour of the aliens as a combat group, but also the bloodspider/melee as a race/outfit. Values that may look nice for ranged units will probably be not so much for the melee ones, and vice-versa. One more reason for creating individual/race-specific sets of GUETE values (apart from the 'nice feature' aspect of it). I suspect that the various degrees of long-ranged and short-ranged weapon wielders have a similar, yet not so dramatic, effect. Example: there's no reason for a sniper to get any positive bonus from the close_in at the absolute-distance calculation. Maybe we could go as far as to say this should be a malus for him.
* Fine tuning these values to perfection is probably going to have an inverse square relationship of time spent and performance boost. Still, it should be considered an ongoing sport, even past the initial large-gain period. Should be especially honored when something significant changes in the game (new races/weapons and combat mechanics).
* Changing the numeric values the one way examined here. Another way to go about it is to transform the additive effect of most of the to multiplicative. This will create another interesting set of values that can easily be better or worse.
* Changing the base dmg weight to the score (apply some kind of multiplication at the end) can be of equal importance as the GUETE values. This needs to be tested and tuned accordingly (TODO).
* Noticed that aliens will toss the sole (melee) weapon they have. We should get them to avoid doing that in general, and/or take into account that in the next turn they will have to spend TU's to re-equip a weapon. If we force them to make sure they re-equip a weapon at the same turn (or stop considering a weapon if they an't), we don't need to do the avoiding part.


If someone wants to help, I'd appreciate:
*people to repeat those tests and evaluate/comment.
* Maybe some kind of a fixed small/med map where spawnlocations&numbers&equipment are also fixed. That way we can compare the results without needing many repetitions and deviations due to the randomness of the skirmish.

On a semi-relevant notice (aliens-shoot through walls):
"dmg = vis * (fd->damage[0] + fd->spldmg[0]) * fd->shots * shots;". This is the base dmg calculation. See the vis variable? that's a G_ActorVis() returns 0.0-1.0. I have also noticed that the shoot-through-walls happens a lot more often in maps with objects that for some reason you can see through at some point (the huts of africa for example). The huts is also the example where the aliens tend to futily shoot up. Maybe there is a disparity between visibility and shooting lines that confuses the AI and makes it shoot through ubreakable & semi-transparent objects? Glass for example work fine here, but hut walls don't. Maybe it's an issue with the definition of the wall itself? I can't really say much since I have no idea what happens outside of g_ai.c. I could start printing out the vis&dmg values and wait to see the results when a wall-shooting occurs.

Finally, I have to add, that I'll probably need someone to review any/all the code I write. I've been java-spoiled for the past decade or so, and I'm really terribad with having 'free()' in my mind ;) I also have forgotten every single performance coding tip I ever knew.
I'm also terribad with handling svn access. So me playing with commit without someone holding my hand can be a bad idea.
« Last Edit: July 02, 2010, 01:39:06 pm by nonickch »

Offline shaunc311

  • Rookie
  • ***
  • Posts: 17
    • View Profile
Re: the AI discussion
« Reply #13 on: June 30, 2010, 09:23:24 pm »
I would love to help you test this out.  It sounds like a lot of fun actually.  Is there a certain build I need to get to start messing around?  Also, is there a way to either save a video or another build that stores the movements of all the players and enemies?  That seems like it would help a lot with testing this.

One question I have about the GUETE_ metrics.  Would it be possible for the aliens to modify them as the game progresses?  I have absolutely no AI programming knowledge but here is what I'm thinking: 

Let's say that the very first mission all the aliens start at the default setting and the game keeps track of all the damage they do to players and civs.  They keep it like that for a few missions to get a good average damage.  Then maybe the game bumps up GUETE_KILL (or another stat) for a few missions and see if the average damage increases.  If so then they change the default to that and start modifying another attribute.  If it decreases then they drop it back down but remembers that the particular combination of values didn't work so it knows not to try again. 

Offline ovvldc

  • Rookie
  • ***
  • Posts: 59
    • View Profile
Re: the AI discussion
« Reply #14 on: June 30, 2010, 10:04:25 pm »
I've done some agent-based modelling for my PhD, and I fully agree that finding salient criteria is much more important than the exact computation. Also, heuristics will be less computationally intensive than calculating everything.

All in all, I would suggest making a diagram, even simpler than the one that nonickch did, that lays out the basic line of thinking. What variables comes into when?

For example, I play patiently. When I play, I always think about where my guys end up at the end of the turn, especially if the aliens are far away and not always visible..

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

Until an XCom soldier comes into view, you could just have the alien walk via places with new views to places with high cover. Interrupt as soon as an XCom soldier comes into view.

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?

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?

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.

The result is like superimposed landscapes with hills and valleys. VIEW landscape needs to be updated whenever your side moves. SAFE and HIT needs to be updated when their side moves or when enemies get discovered during your turn. DAMAGE need to be updated a lot, but only in places where the HIT has a sufficiently high value and that are in walking distance.

Using this kind of thinking you can install cutoffs that keep you from doing all of the calculations for everywhere. Obviously, this was extremely lightweight in the time of UFO:Enemy Unknown when you only had a thousands or so squares. Now the maps are more fine-grained, so some location sampling and interpolation may be needed.

Good luck,
 Oscar