Unit Learning Algorithms

[AF]

well you have something like:

Code: Select all

voidCGlobalAI::UnitFinished(int unit){
    const UnitDef* ud = cb->gtunitdef(unit);
    if(ud == 0) return;
    if(ud->name == string("ARMPW")) // it's a peewee!!!!!
    {
         units.insert(unit); // untis is a set<int> to be defined in the header in CGlobalAI class
          float3 Gatheringpoint;
          // put a location in gathering point somehow
          Command c;
          c.id = CMD_MOVE;
          c.params.push_back(gatheringpoint.x);
          c.params.push_back(gatheringpoint.y);
          c.params.push_back(gatheringpoint.z);
          cb->GiveOrder(unit,&c);
          if(units.size() == 4){
               Command c;
               c.id = CMD_ATTACK;
               c.params.push_back(/*whatever itneger variable is holding the enemy commander ID*/);
               cb->GiveOrder(units[0],&c);
               cb->GiveOrder(units[1],&c);
               cb->GiveOrder(units[2],&c);
               cb->GiveOrder(units[3],&c);
          }
     }
}

However that has no command caching, doesnt check the return values on GiveOrder() to see if it was succesful, and is limited to handling 4 peewees, instead it should have a for loop using tierators to issue the commands...

All you need do is ask if you dunno howto do something and wait till you get a reply like that in actual code.

Anyways now I have that example out of the way I have a few solutions to remedy that and put a few basics into simpler easier more understandable terms....

[Veylon]

Very interesting topic.
I'll put my two cents in:

Context is everything. Figuring out how something happened is the biggest barrier to AI learning. What is an "event" is much harder than interpreting it once you have it.

If 20 peewees, 10 Hammers, a Jethro, and a flea are ordered to attack a LLT position and there are two mexxes and two HLTs nearby that wipes them all out, while a couple AKs and a storm die two, how would that get boiled down? What happened? Would the AI say that attacking LLTs with those units was a mistake? That AKs should be feared? That mexxes were the deciding factor?

A human can say that the couple HLTs were all important, and that the few enemy kbots were irrelevant, as were the mexxes, but an AI has trouble with this, as well as figuring out how similiar, but differently composed groups might have handled it. What about 15 peewees and 15 hammers? Or two more Jethros? What if a Bulldog was added to the mix?

Before any serious learning can be done, the AI's have to have a way of figuring out what happened, how to understand what went wrong. That might be by seeing which types of units inflicted the most damage, and targeting those kind first next time.

I'd say some more comprehensive form of unit value is needed. Something like:

Code: Select all

Value = (Damage + D) / (TimePerShot) * (Speed + S) / (Cost + C) * (Health + H) / (BuildTime + BT)

And then additional values for workertime, flight, weapon range, etc. could be added to it.

D, S, C, H, and BT would be set to decrease the impact of certain stats. We might put S at 10 if we wanted a unit with 20 Speed to be twice as valuable as a unit with only 5 Speed, all else being equal.

Of course, health and damage are subject to changes, via armor.txt, so they might have to be taken into consideration on a case-by-case basis.

Anyway, we can then create an aggregate value for a group of units. Something like this:

Code: Select all

for each unit
  TotalValue += UnitValue
TotalValue *= 1.00 - (NumUnits) // Or something better

TotalValue is reduced to compensate for the inherently lower efficiency of a swarm of units that all get in each other's way.

Then, we would have to have the AI track the life and death of this squad of units as it is built, organized, deployed, and destroyed and remember how all of these things happened so that it will do better next time.

Assuming all of that is possible, the AI will have to rate the squad versus all of the groups it faced and grade the encounter. Absurd ones would have to be ignored.

Code: Select all

If(EnemyValue < MyValue / 10)
  Ignore
else
  Grade = EnemyLosses/(MyLosses + EnemyLosses)

20 Peewees kill 1 AK, little damage: (Ignore)
20 Peewees kill 1 Mex: (Ignore)
20 Peewees kill 1 LLT, lose two peewees: B
etc, etc.

When the squad's gone, all of it's grades are tallied up and reified. If the squad did poorly vs. air units, it's likelyhood of being built in response to air attacks would be reduced. If it did well, it would be increased. A log of all recent grades would be kept and averaged for each encounter type. The oldest grades would be tossed out to prevent overtraining.

Most of the groundwork for this would have to be laid by the programmer and/or modmaker.

Also, squads could be formed into armies to simplify things. If air units are expected, an AA squad could be attached to it. If defenses are, artillery could be added. Scouts could be added, as well, though rating how good they are at scouting would be difficult. Attempts could be made to hold formation, but clogging is always a problem.

Anyway, that's what I think would need to be done before any serious AI learning is possible.

[AF]

hmm, AI learning is also a problem in that what is a valid value for one game and one map and one player is totally inadequate against another player on another map etc....

[Dragon45]

A solid AI learning algorithm on TA's is very possible...

but you'd need a small supercomputr to get it working solidly with minimal lag on a good-sized map.
------------------------------

The best way again is to fake it, or really really limit what an AI can learn, so that it doesnt stray too far...

Multi-user agents ftw...

Now im just waiting for summer so ican put my ideas into practice...

[bamb]

You could possibly also use an expert system to ask questions from veteran players and then compile the data from that.
"how good is this unit against that" etc. What kind of units would you use against a heavy laser tower?

It's also clear that beginner - intermediate humans can learn a lot from watching other people play, it could be potentially very useful if there was some way to make an AI spectate a human player and take note which units he used to say, take out an annihilator. (On the dumbest level)

I also guess that one can only get so far with learning number values for units from past fights - the next step would be mental models and simulation ahead of action, like people playing do. Instead of a huge number of pre-calculated statistics, one can simulate in one's mind what would happen if I attacked these units with these. It can help in unit building and targeting too and could be a very universal tool, although computationally expensive. But that's probably still far in the future.

[Triaxx2]

Part of the problem with that last suggestion, is what's good in one mod, isn't always in another one. For example, in one mod, a Peewee might have a special bonus versus LLT's, while in another the LLT has the advantage.

What's needed, is a more powerful graphing system. Bear with me a moment, I'm working this out as I go. Start with a clean slate, all units being equal. Peewee versus Peewee, is a fairly even match up. Peewee vs. an AK, is not. One to one, whoever shoots first wins PWvPW. One to one a PW always defeats an AK. However, Two PW's, beat one handily, while two AK's, only do more damage. Now, I think it's what 5 or so AK's before a Peewee goes down? And it still takes four with it. So that's a five to one to win ratio.

You can run these calculations with all units, and go exponentially upwards, though twenty is probably a good number to stop at, because you can multiply to get the actual number from any of the other nineteen.

So your grid runs in three dimensions. X is the attackers. Y is the defenders, and Z is the number of units. (Z should obviously never be a negative number.) To save processor power, these grids should be generated and sent with the AI. This gives it the ability to reference these lists, instead of generating them as it goes. It doesn't have to learn, because it already has.

Thoughts?

[AF]

Thats also flawed.

A peewee moving into your base has a value, but that value is ideally different at different points in time and in different situations.

Also the actual unit affects, health, experience, has ti just fired or can ti fire immediatly? etc

Context is everything and there are too many different contexts where a value has to be countered in to use a single value.

Player A attacks you with lots and lots of peewees, this artificially raises the peewee value.

So AI builds something thats known to be good against peewees. Right action? Depends on context

Possibility A: Player sends a second horde of peewees and is utterly defeated and AI send sin backup and destroys player

Possibility B: Information on the peewee is innacurate and a stalemate is achieved

Possibility C: Peewees are overestimated and the AI is left with units it doesnt need and wasted resources

Possibility D: Player purposely sent in a horde of peewees and the AI has now fallen into a trap, player send sin a horde of units he knows will coutner tha peeweee coutner and wins the game.

Possibility E: The game continues in another possibility and a future game is affected by the context of the current game, making the AI's algorithms innefficient and the AI misjudges the situation, but the mistake cotninues in further games and takes too long to correct.

Also there are elements of randomness in simulating, and ti doesnt account the fact the player may be micromanaging or have given a list of command, really you need to know the enemies command queue, which you cant know.

The values alone arent enough, humans see things by differences, not by statistical meddling, and how big we percieve that difference changes over time depending on the situation, the expected situation, and the prior situation, aswell as our attention and feelings.....

I reccomend you read the NTAI X thread as that may give a few clues.

[bamb]

This is getting out of hand, but I'll continue this time.
One dumb way to get context is, if the AI is going to attack, say we will pause spring, take most of the data the AI sees (and has seen), open up another instance, place that data there and simulate attacks against it with various units and tactics (use a genetic algorithm or sth). This way, context is automatically taken into account, you can see that if you move vehicles, they can't get up that hill and are killed by the laser tower, but if you go kbots, they devastate the tower. Then when a good way has been found (ok it took an hour), we save the data as a plan for the next ten minutes of play, close this instance, go back to the original and start moving according to the plan. Until again, a few minutes later, we again have to simulate, starting with some (random?) variations to the current plan.

Maybe the simulation wouldn't even have to be done in a complete spring instance, just some simpler format, but not one that reduces to a single line equation, rather something that can take terrain and time into account too. I think you need both some coarse simulation and number-level quantifiable assumptions to make it play well.

The plan would consist of build orders and waypoints and so such, maybe not anything too complicated, since that would screw up at the tiniest unexpected thing. Timing would be tricky, maybe use some triggers like "after the 20th flash is ready".

Of course the AI would have to do a priori assumptions about the enemy positions it does not see, these could be just pretty simple things at beginning, like that the enemy has some factories and mexxes and a commander at least, and we can simulate if we could kill those too..
In the endgame when it knows the most data and there is little of it, it could simulate the surest/fastest way to victory.
One couldn't anticipate the opponent's tactics, it should be simulated by just some fairly stupid AI.

It becomes a bit like chess programs that solve stuff by brute force, although they also score positions on board as absolute, and have intermediate goals. (I'm not very familiar with them.) Anyway, they use simulation up to many moves ahead.

[AF]

The problem is a unti has a near infinite given distributuion fo possible futures.

Say the llt your launchign an atatck againsta dn you generate a plan the way you describe, your units reach the poitn and start atatckign when suddenly a large army appears that you couldnt see previously due to LOS that wa as unepected.

Or say there's a set of defences behind that tower.

Maybe the tower has since been reclaimed.

Also the very choice to go after th tower requires cotnext,a dn to gain cotnext the wya you've put ti would require the game be simulated across the entire map which then gets the problem of where does it matter and what todo adn what to change each time, it becoems too much.

And if your simulation yielded results for a situation that turns out to be onyl half the story adn you're gonna fail, thn you've got a good few minutes of AI being massacred till your units are resimulated and the best options is once again chosen.

Simulating thigns is good, but only for certain things, such as predicting when a player is micromanaging an AK and the AI is doing the same against ti, foresight is a good idea, in that case you'd best rely mroe on probabilities than hard accurate simulation, and have a very fuzzy fast simulation that re-evaluated every second or two.

However it cant be sued to place unit values in context like that, it's relying upon the basic concept which I've already stated as flawed.

Unit values wether you use them are not, ti isnt enough to use them solely in that way, looking at what killed/damaged what and using ti to make efficiencys which then dictate what's built. You need to spread the values so that there are more ways of changing a value, and more ways that those values affect the AI's play, that in itself counters in partial context because the context itself afefcts the values over time rather than the values needing a context to eb assesed and generated then applied to the value which just wotn work.

[bamb]

fair enough, I think you're mostly right, that context can not be only simulated in (top down), it should start from the bottom up too...
Regards to your example: If unexpected stuff happens, simulate again. :) Just like a human player has to rethink their tactics or strategy when unexpected things pop up. There could even be parallel coarse long-term simulation and finer-grained short term simulation (not necessarily even global). This all is just gibberish though if I'm not picking up stuff and coding, it's probably quite hard to translate this into a working program.

Anyway, here's a paper I just a minute ago read about using short-term (units moving less than their LOS) coarse (divide to map into tiles) planning with Monte Carlo simulation in a simple CTF strategy game:
http://www.cs.ualberta.ca/~mburo/ps/mcplan.pdf
It works somewhat with tuned abstraction coefficients and such.
I wish they tried that with a resource-gathering game.

[Triaxx2]

Except you aren't taking scouting into account. An AI that has these basic value rules is going to scout out the opponents base and see what he's building. If it see's lots of Peewee's, it's going to shift into production of counters, while maintaining scouting. If the first wave is sent in as a trap, scouting will report that the next group is a Peewee counter-counter. The simplest move is to charge with the counter, and begin construction of the anti-unit.

If you take those into account, it's far more plausible. But what I'm thinking of are simply basic values that don't change from game to game, but will modify for each game. Sort of an all things equal list. Commander vs. Commander is always a one to one kill ratio.

[AF]

interesting, though be aware the complete simulation isn't required, instead a fuzzy simulation (for speed purposes) based more on probable actions than running through a virtual spring engine, especially since there are factors the AI doesn't have knowledge of, such as the direction the unit is facing, when the unit last fired etc....

That and the whole thing should be made quicker by extrapolating things such as where the enemy unit is moving too, and other data values that are dependent on the current status and aren't quite cumulative (such as a threat matrix)

Also be aware of bayesian networks

[bamb]

yeah, it's probably hard to tune the simulation... if you make it too precise, it's noisy and also slow, if you make it too general, it loses context. I would hunch you need terrain and time steps in it at least.

[Argh]

...

I will just come back to this when I do not need to sleep, wake up and then put in a full day doing RL crap. Maybe Sunday.

Short version, though, is this:

Context is everything. It is not a minor adjunct to statistical gooeyness. Stat comparisions are a complete waste of time! I shall begin making fun of (or logic-slicing, if it comes to that) every attempt to arrive at useful results by comparing stats from here on out. It's completely inadequate, and will never arrive at good results in a realtime setting.



Let's do a very simple logic problem, shall we?

We have to kill a tank. It moves at a speed of 1, but may be at any position XYZ within 0.5 units of its predicted position. The tank has a radius of 2 units.

The tank has 1500 hitpoints.

Which kills the tank faster?

1. A laser cannon that has a rate of fire of 1 per second, can do 1000 damage, has 1000 range, and is sitting at the bottom of a crater 200 units across, with rims 100 units high...

2. Or a laser cannon that can do 100 damage, fires 7 times per second, has 500 range, and is placed on top of a hill 300 units high, 500 units around, all other factors being equal?

Which is more powerful in absolute, straight-line comparision terms? If the laser beams do not travel instaneously, does balance shift? Which laser is now more powerful?

In a practical Spring game design, where shots will never travel instaneously (for visual purposes, if nothing else), what are the practical implications of this? If we reverse the geometric positions of these two objects, are there any changes in their overall balance?

Now, chew on that for a few minutes, and come up with a defendable system that relies in any way, shape or form on kill/death ratios or raw unit stats to deterministically shape AI behavior

[Argh]

...

...

...

When you're done chewing on the first part, let's add one... tiny factor.

If the theoretical tank gets within 500 units of the laser cannon, it can fire a weapon that always hits the target, and will kill the laser cannon in two hits.

What is the statistical probability that the tank will survive this encounter?

[krogothe]

And how do you expect someone to come up with a scripting system that will account for all that all while not forcing you to code millions if not billions of situations?

Code: Select all

for{every type of unit}
..
.
..
tank
  for{Every possible tactic}
..
..
..
..
   Attacking
   for{every possible unit you will attack}
...
...
...
   Laser cannon X
   for{every possible arrangement of enemy troops}
..
..
..
...
      Just the laser cannon
      for{Every possible terrain conditions in the encounter}
...
...
...
...
...
..
       Cannon in crater
       for{all different heights and sizes of craters}
...
...
..
..
..
..
         A crater with lip 500 units high, and 400 units wide
         Do Not attack
}}}}}}}}

Do you think the rockets that send people to space, the computer youre using right now and the house you live in were designted and calculated with precise stats? Its all about models and apporximation.

[submarine]

thank you so much krog :)

[unpossible]

I think you're going to have to wait a while for this...computers don't have billions of neurons and massively parallel processing capabilities at the moment!

Perhaps in a few years time we can get one of those Argh inc. AI processing cards...so long as we have the 2MW power supply and squashcourt-expansion slot availible....

Until computers have brains they won't learn...and hard coding responses seems a little much effort! Where is the error correction in a hard coded ten billion different combinations of attack and defense given different circumstances/times of day/colours each team has chosen?

The comp can't sit back and say "wait up I've balls'd this up royally, lets start again". There isn't even some easy (automatic) check to make sure that 'thought' processes are coherent and error free (or backups in case they aren't).

Ten billion if and for loops intelligently designed won't hold a candle to a genuine brain...something'll always go wrong and the error will take a lifetime to solve.

Can't there be a few concessions regarding craters? :D

p.s. Can we set up some global SETI-like spring simulation to genetically breed he perfect AI?

p.p.s. why is everyone bickering?

[bamb]

argh, there is room for mod-wise scripting in tuning the abstraction parameters at least if you have a simulating ai. There has to be some abstraction since simulation becomes too slow if you take all the data. After all, people play like that too, the amount of data is just too overwhelming and they're concentrating on small areas (microing) or approximate forces or something like that most of the time. Maybe only at the very early game a human can calculate game happenings 90% accurately deterministically forward for quite a long time, set the build queue etc..

[AF]

*_*

THIS SI GAME AI NOT SCIENCE AI

The aim of a skirmish AI is to beat the opponent, not to be capable of doing things in such a way it can philosophise.

All this unti learnign stuff is allll wrooong, your very concept of how ti should work doesnt fit in with what you think it leads to.

raw unti stats arent going to be useful without context. Choosing untis based on those stats is a logical falalcy, even the values themselves are flawed as none of you can even define what they stand for, onyl how you got them, and a vague effect they have.

Another problem here is you lto are all saying either do advanced statistical arrangements on data you've gathered and then call it learning which ti isnt, or hardcode everything.

You're both wrong. Statistical meddling isnt enough. For oen your not taking into account accuracy and error, nor allowing the data to be fully colelctedand represented in a meaningful way. You're not visualising it properly. The bridge designer will get a lot further along when he starts seeing the bridge instead of thinking of the two sides that need joining.

Probability is your problem. Arghs approach works. But it would work better if ti was guided by probabilities and the values(stress the guided part). However the probabilities themselves dont give a good answer.

The scripts the data the user gives is what gives the values the meaning as does the probability it represents. The raw statistic is useless here.

An example is the scouting in JCAI. It uses a grid of values that tell JCAI when they where last seen. JCAI runs the surrounding values of a scouter to gt a new scout position. The values themselves dont have context, it's the algorithm that gives them context, and thus ti is the coder that gives th values their context, there is a direct structured link where every single variable is explainable and you know exactly what eahc possibility means.

To be able to learn you need to be able to recognise the situation and the context ti is in. The unti learning algorithms you have discussed are not doing this. They dont even learn, or infer, they dont know why ('why' is an itnegral part of learning).

I think the title of this thread should be changed from Unit learning algorithms to kills based construction selection.

Also your algorithms if they carry on like this become useless once units are put together in a group. And they dont take into account the situation they're in or will be put in.

If AAI learns that tanks are good and pwn kbots on flat maps it'll draw that experience into a hilly map adn get owned by kbots and aircraft. Which it then takes into a flatmap and uses and gets pawned again, and end sup usign an even mix because it doesnt know anymore and the statistics have averaged out.