Page 1 of 1

Ideas/references on getting an ai to learn by itself?

Posted: 26 Nov 2011, 10:43
by hughperkins
Ideas/references on getting an ai to learn by itself?

I'm thinking it could be interesting to just get the computer to learn to play all by itself, from first principles.

Any ideas/references/papers that might help with this?

Re: Ideas/references on getting an ai to learn by itself?

Posted: 26 Nov 2011, 14:33
by jK
1. Change the fac buildqueue with an Artificial Neural Networks (ANN) or a Genetic Algorithm (GA).
2. Balance between expansion, rushing, porking & eco with an ANN.
3. Change the frontline tower defense buildqueue with an ANN.
4. Change the attack squad size/strength with a GA.
5. Parse the UnitDefs with ANN+GA, so the AI sorts the unitdefs itself into classes like: eco, fac, worker, defense, passive defense (shields), heavy combat, long range, ...

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Nov 2011, 12:13
by knorke
just get the computer to learn to play all by itself,
what game?

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Nov 2011, 14:51
by Tobi
In my experience playing all by itself from first principles will take way too much generations (thus, time) when using GAs/ANNs, if it will even converge to something sane at all.

(It already took a quite a while to train simple food-searching-ants in a trivial world, and training time didn't scale up nicely when I made the problem more complicated.)

It might be possible when you use backpropagation to pre-train the ANNs to do something relatively sane, or by setting extremely simple objectives at first (e.g., build 1 solar), and only making the objective progressively harder as the AI masters the previous objective.

But then you aren't letting them learn from first principles of course, you are just training it exactly to do whatever you would hardcode in a non learning AI :-P

EDIT:

If you try it anyway you're probably going to have to write some quite complicated fitness function, so that even building 1 solar and doing nothing else is considered closer to a winning condition than doing nothing at all. Similarly, building 1 solar and 1 mex should be even closer, while building 10 solars and then stalling might need to be considered further from winning.

Then again, the shape of the fitness function will train the AI in a specific direction. Actually, most probably it will simply exploit a bug in your fitness function to get "infinitely" close to winning, while not doing anything sane at all :-P

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Nov 2011, 15:42
by hughperkins
[quote="Tobi"]It might be possible when you use backpropagation to pre-train the ANNs to do something relatively sane, or by setting extremely simple objectives at first (e.g., build 1 solar), and only making the objective progressively harder as the AI masters the previous objective./quote]

Yeah, that was kind of my plan.

Basically, I don't expect the computer to do any better than a baby, or a human who's never done *anything* *ever* at all.

So I'm happy with encouraging it to do simple things to start with.

Still, it might be nice if it had some natural curiosity, sort of like a child playing with toys. "ooh look I can build a solar panel!" "ooh! another solar panel!" "oooh! I made lots and lots of solar panels!!!"

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Nov 2011, 18:55
by jK
Tobi wrote:In my experience playing all by itself from first principles will take way too much generations (thus, time) when using GAs/ANNs, if it will even converge to something sane at all.
I know of a StarCraft modification that detected the ideal start buildqueue, and it worked fine there.
It depends a _lot_ on the input & the way you use the output. So it's unlikely that there is any sane ANN that is able to define the buildqueue from the start to the end of a 1h match. But having an ANN that is able to check if it's running out of metal or energy and then gives the correct orders (build mex, reclaim wreckages, build windgen, build fusion, ..) is very very likely.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Nov 2011, 23:41
by Tobi
But having an ANN that is able to check if it's running out of metal or energy and then gives the correct orders (build mex, reclaim wreckages, build windgen, build fusion, ..) is very very likely.
Indeed, making an ANN that chooses one of 2-20 options based on 2-5 inputs (e.g., metal + energy [+ dm/dt + de/dt maybe]) is quite possible (it is similar to the size of the ant simulation I once made), but one of the questions that remains is how you train that ANN quickly. Or rather: how you train all those small ANNs you have quickly so that the performance of the whole AI improves, and so that you aren't just modeling a piece of procedural code using an ANN. (which is bound to happen if you pre-train on a simple model IMHO, unless you use real data from players to train the ANN maybe.)
I know of a StarCraft modification that detected the ideal start buildqueue, and it worked fine there.
Detecting an ideal start build queue is a relatively 'simple' problem IMHO. Any sane pathfinding algorithm on a properly designed graph of the the available choices should be able to solve that. (e.g., pathfinding in (metal,energy,time[,x,z])-space, in the case of *A, towards a goal of e.g. shortest time to 5 flash tanks and/or highest metal income at a fixed time.)

A planning/scheduling/path finding approach may be interesting too.
E.g. AI starts with high-level goal 'win'. The goal 'win' can be subdivided in a number of smaller goals, such as 'kill player 1' and 'kill player 2', which can be subdivided in 'kill unit X of player 1', etc.

I think that if you can generate a nice set of such tasks, with heuristics as to how much closer a certain choice the AI brings to fulfillment of one of those tasks / how much worth each task is (e.g., killing an expensive unit is better than killing a cheap unit, killing a player that hurt us a lot in the past is better than killing a passive player), then running a planning/path finding algorithm over this graph of tasks might give some interesting results.

Hard parts here, of course, are that the decision space is huge, and changes rapidly over time, and that you'll need to code manually how each tasks subdivides into smaller tasks down to the level of single unit orders.

Another interesting approach may be agent based (maybe combined with such a task planner based approach).
Still, it might be nice if it had some natural curiosity, sort of like a child playing with toys. "ooh look I can build a solar panel!" "ooh! another solar panel!" "oooh! I made lots and lots of solar panels!!!"
Lol, yeah, that are fun things to see if you didn't hardcode it :-)


Sidenote: as was probably readable between the lines I personally don't believe in succesful ANN/GA-based RTS AI, although these techniques may solve tiny subproblems pretty well.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 13 Dec 2011, 01:29
by Error323
Hi,

I agree with Tobi on this. Cracked my insignificant nut on this quite some time when I was hyped about GA's and ANN's. There is one project that I know of which implemented ANN's successfully in determining which enemies to attack for group 1 vs group 2. I don't remember the details unfortunately. But as I heard from the interview the training of the networks was painfull...

Re: Ideas/references on getting an ai to learn by itself?

Posted: 24 Jan 2012, 06:05
by hughperkins
Tobi wrote:Another interesting approach may be agent based (maybe combined with such a task planner based approach).
Interesting idea. So maybe give each unit it's own simple AI? Get it to learn to hang out with other units on its team? Reward it every time it kills an enemy unit, something like that?

Re: Ideas/references on getting an ai to learn by itself?

Posted: 24 Jan 2012, 06:25
by Petah
Create a modification of a game (BA) which has a small subset of game play.

E.g.
On a small flat map, 1 AI is given 5 flash tanks, and 1 AI is given a commander.

Now train them. Each time one loses their units. Kill all remaining units, and re-spawn them.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 24 Jan 2012, 13:12
by hughperkins
Petah wrote:Create a modification of a game (BA) which has a small subset of game play.

E.g.
On a small flat map, 1 AI is given 5 flash tanks, and 1 AI is given a commander.

Now train them. Each time one loses their units. Kill all remaining units, and re-spawn them.
Not a bad idea!

Re: Ideas/references on getting an ai to learn by itself?

Posted: 24 Jan 2012, 13:38
by gajop
you may want to check zerok mission editor for that (not entirely sure if it's capable to do spawns yet or not though)

Re: Ideas/references on getting an ai to learn by itself?

Posted: 24 Jan 2012, 20:53
by hoijui
killing units if one unit dies must be a very easy thing in lua. no need to use a whole mission editor for sure.

i also remember that there is a minimal version of... not sure if it was XTA or BA, but it also does not matter much. i think it was only one faction, with commadner, kbot lab, radar, LLT, constructor, AK, Thud. i also remember having it cleaned up once. in case you wont find it on springfiles.com, you might also make your own one. it can be done in a few hours, by just deleting lots of stuff out of BA, for example. i also did it without any prior knowledge of modding.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 24 Jan 2012, 22:08
by Petah
And of course, once the AI is trained significantly, you replace one of the teams, and see if you can beat the AI.

Fun fun.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 25 Jan 2012, 06:16
by knorke
hoijui wrote:i also remember that there is a minimal version of... not sure if it was XTA or BA, but it also does not matter much. i think it was only one faction, with commadner, kbot lab, radar, LLT, constructor, AK, Thud. i also remember having it cleaned up once. in case you wont find it on springfiles.com, you might also make your own one. it can be done in a few hours, by just deleting lots of stuff out of BA, for example. i also did it without any prior knowledge of modding.
No need to delete lots of stuff, just modify the buildoptions of all construction units and factories to only include the stuff you want.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 25 Jan 2012, 12:36
by PicassoCT
make a nice little sideeffect proudFatherOfAKillingMaschine:
If pewee killz all the AKs then
kbotlab is proud (worthy of protection money in form of defense towers) and reproduction.

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Jan 2012, 09:56
by hughperkins
PicassoCT wrote:make a nice little sideeffect proudFatherOfAKillingMaschine:
If pewee killz all the AKs then
kbotlab is proud (worthy of protection money in form of defense towers) and reproduction.
Haha :-) I think the images you describe are awesome :-)

Re: Ideas/references on getting an ai to learn by itself?

Posted: 27 Jan 2012, 09:58
by hughperkins
Found a paper on hierarchical reinforcement learning ("feudal reinforcement learning"). Sounds quite interesting:

http://www.gatsby.ucl.ac.uk/~dayan/papers/dh93.html