Fun with Planning

[agentx]

At game start or load a bot is thrown into cold water. He might discover a very hostile environment in terms of resources, units, buildings and enemies. Interestingly game start and end can be very similar, meaning eveything is low, if the human opponnent has victory within his grasp. But a bot doesn't give up, as long there is a small chance of success - he takes it, right?

What is the worst case? Let's say no civic centers. That's close to ground zero in 0 A.D., because without CC you lack the territory to build any other structure. So, naturally the very first questions in this case are: Can I build a CC? And if not, what can I do at all? It turns out, these are very complex questions.

Let's start with some simple conditions:

  has only resources        -> whiteflag  has only buildings        -> whiteflag  has only units        -> whiteflag or fight like hell

Ok, that's not so difficult. And it looks translatable into straight forward JavaScript, too. Here comes the next level:

  has buildings, units, no resources    has no CC      has no CC builder        can not train CC builder          -> whiteflag or fight like hell        can train CC builder          -> gather resources          -> train CC builder          -> construct CC      has CC builder        -> gather resources        -> construct CC

Actually that's only the surface. It assumes the units are not champions and the needed resources are available. Here are a few more:

  has buildings, resources, no units    has no CC      can train CC builder        -> train CC builder        -> construct CC      can not train CC builder        -> whiteflag  has units, resources, no buildings    has no CC      has no CC builder        -> whiteflag or fight like hell      has CC builder        -> construct CC

and finally:

  has units, resources, buildings    has no CC      has CC builder        -> construct CC      has no CC builder        can train CC builder          -> train builder          -> construct CC        can not train CC builder          -> whiteflag or fight like hell

Can you imagine how many conditions the bot has to check just to find out he has definetly lost? Now add more edge cases, mixin technologies, multiply with all buildings and all factions and you'll end up with tens of thousands lines of code, hard to read, difficult to maintain and taking months to write.

That's where planners jump in. They know which conditions to check and how to answer them. Ontop they come up with a list of actions leading to your goal or none if your goal is unreachable.

HTN (hierarchical task network) planners are conceptually fairly simple, but extremely powerful. They define a state, that's the starting point, a goal and operators and methods, the latter are just functions. Operators can change the state and methods result in more methods or operators.

So, you initialize a planner with a state, your goal and then call the first method. From there it tries to decompose the problem until only an ordered list of operators is left - that's your plan.

0 A.D example:

state = {  resources: {food: 300, wood: 300},  entities: {    structures.athen.civil.centre: 1    },  technologies: [phase.village]};

goal = {  resources: {},  entities: {    structures.athen.field: 1},  technologies: [gather.wicker.baskets]}

The goal basically says: I don't care about resources and the civic centre, but in any case I want a field and foragers better equipped. Do you see the two traps?

Here's the plan:

HTN: SUCCESS, actions: 8, 1 msecs  op:   1, train_units ( units.athen.support.female.citizen, 1 )  op:   2, wait_secs ( 10 )  op:   3, build_structures ( structures.athen.farmstead, 1 )  op:   4, wait_secs ( 45 )  op:   5, build_structures ( structures.athen.field, 1 )  op:   6, wait_secs ( 100 )  op:   7, research_tech ( gather.wicker.baskets, 1 )  op:   8, wait_secs ( 40 )

See how the planner automatically found out he needs a builder for the field and the farmstead for the technology.

And the final state:

resources: { food: 250, wood: 150, time: 195, metal: 0, stone: 0, pop: 1, popmax: 300, popcap: 20 }entities: {  structures.athen.civil.centre: 1  units.athen.support.female.citizen: 1  structures.athen.farmstead: 1  structures.athen.field: 1}technologies: [phase.village, gather.wicker.baskets]

... which can be used for your next goal. HTN Planners are well used in RTS games. The link finds a a few interesting presentations. Some games have highly optimized ones, checking hundreds of plans each tick, looking for the optimal strategy to keep the human opponent entertained.

So far Hannibal's planner lacks a few features, he needs a better awareness of time e.g. calculate how long it takes to get a given amount of resources and more challenging learns the concept of parallel tasks.

I'll continue when it produces heros.

PS: Did I mention that's probably the first JS planner ever written for an RTS?

Edited May 1, 2014 by agentx

[Yves]

Impressive, how you are combining these concepts such as the triple store, the query language and the HTN approach for planning actions based on the data and goals.

It seems to be as generic as it can be and seems to be a good approach to make the AI more flexible, more configurable and easier to understand.

I hope it works out as planned.

Do you have a working version somewhere where these concepts could be tested in 0 A.D. directly?

Even if it has just basic functionality as shown in the video, it would be interesting so experiment with that and figure out how it works.

Using a git repository for your work would probably be the best way for sharing it and it's also very helpful for managing your own versioning and keeping track of changes in the development version of 0 A.D..

[agentx]

https://github.com/noiv/Hannibal

[Radagast.]

My respect. Yet another milestone reached. In real life, I don't really want to meet Hannibal. Here in 0AD I can't wait seeing it in action. And then, when I see it .. I will probably hopelessly be on the run with my civilisation. Thank you man.

Edit: I saw the Github. Really _asm.js. All that far evolved? Oh dear, we have to put into SVN. As you use mercurial locally, this might not even be a big problem to switch for you. Or evven as it is now, it is a real mod. You must have made giant progress the last months.

If you build walls, tell me please. I think this Hannibal is even much more promising than I ever dreamt of.

So now we have Aegis in two variants, Hannibal & Tereisias is working on a bot too if I'm not wrong.

  has units, resources, no buildings    has no CC      has no CC builder        -> whiteflag or fight like hell      has CC builder        -> construct CC

I assume you already check each unit if it could construct a civil center capable builder to finally build a civil center. Or rather you're planning algorithm does so. Edited May 2, 2014 by Hephaestion

[Teiresias]

@agentx, are you studying planning techniques as a pro? :-) I'm very interested to see how your planner comes up. I've already toyed around with the idea of a planning AI but without satisfying results. I faced two mental problems (have not experiments by now):

1. Combinatoric explosion. As your state considers more and more game variables, maybe even including the entity layout on the map, i presume it will take more and more computing power to simulate the gameplay into the future? When driven at max, would the planner have to run a de-facto copy of the current game with the examined action taken, to find how it would work out?
2. How do you set up the various operations for the planner - by hand or do you plan on parsing the entity templates (more or less) automatically?

Do you plan to give the planner a rough route e.g. to reach city stage and a group of troups or, in the final version, will the planner start with the "simple" goal { isVictorious : true } to figure out everything on its own?

@Hephaestion: Yes, i'm fiddling with a bot as well, but currently it's more a puzzle than a real bot :-( Still, made some progress in optimizing the gathering process. Still going slow, as i can just spend an hour or so per day on it, and tend to suffer a bit from analysis paralysis...

[agentx]

My respect. Yet another milestone reached. In real life, I don't really want to meet Hannibal. Here in 0AD I can't wait seeing it in action. And then, when I see it .. I will probably hopelessly be on the run with my civilisation. Thank you man.

Thank you for your inspiration.

> asm.js

tldr: forget it.

Funny story. If I test in browser 0AD's handwritten cos function is as fast as the JS internal!!, cos with asm is 10 times slower AND interestingly if I remove the 'use asm' line the cos is comparable. Ontop there is a huge lag, if one calls into or out of ASM, so you are forced to write all your code in the asm module. However, then it is like writing assembler and a lot of JS feature are gone. So the only way seems to be writing Hannibal in usual JS and transpile it into asm.js. I postponed that until Alpha 517.

> walls

A must. Have you ever survived a MP without walls? Well, don't mean your 4 years old sister. Look here: http://www.cse.lehigh.edu/~munoz/CSE497/classes/Patrick2.ppt I think the challenge is not building the wall, but finding/logging a path through a map full of trees.

[Yves]

> asm.js

tldr: forget it.

Funny story. If I test in browser 0AD's handwritten cos function is as fast as the JS internal!!, cos with asm is 10 times slower AND interestingly if I remove the 'use asm' line the cos is comparable.

I'm not a fan of asm.js yet, but you should not draw conclusions too early.

A quote from this article:

The astute reader may at this point be wondering what happened to the plain Javascript scores. Did regular Javascript do so badly that I ignored them? Is there something fishy going on here?

To be frank, I didn’t include the regular Javascript scores in the results because regular Javascript did far too well, and I felt that including those scores would actually confuse the analysis instead of help it.

The somewhat sad fact is that SunSpider scores have been “benchmarketed” beyond reason. All Javascript engines, including SpiderMonkey, use optimizations like transcendental math caches (a cache for operations such as sine, cosine, tangent, etc.) to improve their SunSpider scores. These SunSpider-specific optimizations, ironically, make SunSpider a poor benchmark for talking about plain Javascript performance.

Ontop there is a huge lag, if one calls into or out of ASM, so you are forced to write all your code in the asm module.

A quote from this article:

Second: one performance fault that we already know trips up people trying to benchmark asm.js is that calling from non-asm.js into asm.js and vice versa is much slower than normal calls due to general-purpose enter/exit routines. We plan to fix this in the next few months but, in the meantime, for benchmarking purposes, try to keep the whole computation happening inside a single asm.js module, not calling in and out.

You might want to test with ESR31 again. I haven't tested ASM.JS yet and I don't know if/how much they improved this in the meantime.

[agentx]

@Teiresias

{ isVictorious : true }, that's the plan to become a pro. No seriously, can't run this goal every second.In a RTS a bot has to re-evaluate plans after any incident, e.g. the building needed to advance to phase.town was destroyed in the meantime.

I'll use the planner to feed the economy and advance from phase to phase. Attack plans are the holy grail of planning, but during combat only a few msecs can be spared for the planner. I don't know how far I get this. Current state of thinking looks like this:

I'll give you some numbers about combinatoric explosion when planning heroes works. Athen uses about 70 templates and 40 techs/pairs. Going from zero to hero, may involve max 10 levels, not that bad. The triple store searches 500,000 node/edge combinations in less than 1 msec. The trick with JS is finding the sweet spot, where IonMonkey kicks in and compiles very fast code. Then you can do amazing things.

> How do you set up the various operations for the planner - by hand or do you plan on parsing the entity templates (more or less) automatically?

At game start all knowledge (template, techs) goes into the triple store, here is an example where I check and resolve the requirements for a phase, name === 'phase.town', buildings stores countable buildings and entities the ents in the state.

if (tech.requires && tech.requires.class){  // check for enough buildings  klass     = tech.requires.class;  amount    = tech.requires.number;  buildings = H.QRY(klass + " CONTAIN")                .map(node => node.name)                .filter(name => (                    !name.contains("palisade") ||                     !name.contains("field")    ||                    !name.contains("wall")     ||                    !name.contains("civil.centre")                ));  entities  = H.attribs(state.ents);  inter     = H.intersect(buildings, entities);  have      = inter.reduce((a,  => state.ents[a] + state.ents[b], 0);  diff      = amount - have;  if (diff > 0){    if (name.contains('phase.town'){      house = H.QRY("house CONTAIN").first().name;    } else (name.contains'phase.city'){      house = H.QRY("defensetower CONTAIN").first().name;    }    return [['produce', house, diff]];  }}

A H.QRY with CONTAIN retrieves templates from a given class. If buildings are missing, this section composes and returns a new task for the planner, I'm sure you get the idea if you look how the produce function works: https://github.com/noiv/Hannibal/blob/master/htn-methods.js#L145

Edited May 2, 2014 by agentx

[sanderd17]

I tested one of those math functions I made with asm.js before, but my differences were way smaller. The asm.js version was slower than the original, but when ran enough, the difference became very small (certainly not over 10% difference).

Comparing with the engine function is not fair though. Our cos contains some variables to make it faster, but less precise. Currently, it's precise enough for our purposes, but the native function is way more precise.

[agentx]

You might want to test with ESR31 again. I haven't tested ASM.JS yet and I don't know if/how much they improved this in the meantime.

Actually, if I put 'use asm' into a module I get this: JavaScript warning: asm.js type error: Disabled by javascript.options.asmjs in about:config

I've read these articles, because I couldn't believe the results I got. I wish I could you asm for the map analysis, that would be really great. But the way it currently looks, I can only image it as part of the API where bots request dozens of paths and get them back next tick.

[Yves]

Actually, if I put 'use asm' into a module I get this: JavaScript warning: asm.js type error: Disabled by javascript.options.asmjs in about:config

It's not enabled in our engine currently, but I think this should be enough to enable it:

Index: source/scriptinterface/ScriptInterface.cpp===================================================================--- source/scriptinterface/ScriptInterface.cpp	(Revision 15092)+++ source/scriptinterface/ScriptInterface.cpp	(Arbeitskopie)@@ -652,6 +652,7 @@ 		options |= JSOPTION_ION; 		options |= JSOPTION_TYPE_INFERENCE; 		options |= JSOPTION_COMPILE_N_GO;+		options |= JSOPTION_ASMJS;  		// Some other JIT flags to experiment with: 		//options |= JSOPTION_METHODJIT_ALWAYS;

[agentx]

I have just planned a hero:

// state"ress": {},"ents": {"structures.athen.civil.centre": 1},"tech": ["phase.village"]// goal"ress": {},"ents": {"units.athen.hero.iphicrates":1},"tech": []

HTN: SUCCESS actions: 35, 33 msecs, iter: 247, depth: 155  op:   1, inc_resource ( wood, 50 )  op:   2, inc_resource ( food, 50 )  op:   3, inc_resource ( population, 1 )  op:   4, wait_secs ( 10 )  op:   5, train_units ( units.athen.infantry.spearman.b, 1 )  op:   6, wait_secs ( 10 )  op:   7, inc_resource ( metal, 200 )  op:   8, inc_resource ( stone, 100 )  op:   9, wait_secs ( 200 )  op:  10, inc_resource ( stone, 300 )  op:  11, inc_resource ( wood, 400 )  op:  12, wait_secs ( 600 )  op:  13, inc_resource ( wood, 350 )  op:  14, build_structures ( structures.athen.house, 5 )  op:  15, wait_secs ( 265 )  op:  16, inc_resource ( wood, 400 )  op:  17, inc_resource ( wood, 400 )  op:  18, inc_resource ( food, 800 )  op:  19, research_tech ( phase.town.athen )  op:  20, inc_resource ( wood, 400 )  op:  21, build_structures ( structures.athen.defense.tower, 4 )  op:  22, wait_secs ( 600 )  op:  23, inc_resource ( stone, 100 )  op:  24, inc_resource ( metal, 800 )  op:  25, inc_resource ( stone, 900 )  op:  26, research_tech ( phase.city.athen )  op:  27, inc_resource ( metal, 200 )  op:  28, inc_resource ( stone, 100 )  op:  29, build_structures ( structures.athen.prytaneion, 1 )  op:  30, wait_secs ( 200 )  op:  31, inc_resource ( wood, 200 )  op:  32, inc_resource ( food, 50 )  op:  33, inc_resource ( population, 1 )  op:  34, train_units ( units.athen.hero.iphicrates, 1 )  op:  35, wait_secs ( 35 )

op 3 + 33 look strange. The planner called about 250 methods and tree search depth was 155. I think, I rewrite some recursive parts where tail optimization doesn't work, 33 msecs are too much. Check it out: http://noiv.pythonanywhere.com/agentx/0ad/explorer/hannibal.html (FF30 mandatory, click GO)

Edit: if you click stress with 10 loops, it shows stats from the triple store cache. Now, after clicking more often it takes only 13 msecs, much better.

Edited May 2, 2014 by agentx

[agentx]

I could make the planner somewhat faster, but the main function is still a recursive one. So, I still have to convert it into a while loop, because FF's profiler doesn't help with recursive calls. However, now it is ready to optimize for either cost or time and it is more robust now. I have tested it on all units and structures of athen, hele and mace found in the triple store, which gives a cost report like this:

depth iter msec ops Name                    time  food  wood  stone metal   78   79   13  20 units.hele.ship.trireme  535  850   1900          150  108  109   14  24 structures.mace.wonder  2035  850   3000   2400  2000

The costs are total, as if you start with a CC only. Time is the minimum with one unit building and excludes gathering resources. I didn't manage to make nice tables here, shots are attached. The report generator is also online. If someone has a machine planning a units.athen.champion.marine in less than 5 msecs, I'd like to know...

[niektb]

[...]

If someone has a machine planning a units.athen.champion.marine in less than 5 msecs, I'd like to know...

My rig doesn't (i5-3230M @ 2.6Ghz, 6 GB RAM, latest FF)

It takes 14.1 msecs on average when looping here.

[Lion.Kanzen]

You can survive with a dock. For me the Ai can use this tactic to try survive in late game.

[Stan`]

Will a I7 3770 do the trick ?

[niektb]

Will a I7 3770 do the trick ?

If one needs a i7 to do the trick than it is obvious that there is some optimization to be done I guess.

[agentx]

> My rig doesn't (i5-3230M @ 2.6Ghz, 6 GB RAM, latest FF)

Mmmh, I have a CoreDuo @ 3GHZ and switched now from WXP to Linux and the average dropped from 30 to 12 msecs (FF31). Is 0AD on Linux considered faster?

[Loki1950]

Almost any app is faster under Linux the kernel is more efficient and there is less OS overhead which translates into faster apps.

Enjoy the Choice

[agentx]

Wow, without that recursive stuff the planner is down to 0.16 msecs and there is still some room for improvement. That teaches me something about JavaScript. Now I can really go and make it search for the best male/female ratio to achieve city phase fast by checking all possible alternatives or whatever optimization problem come up.

Achievement unlocked!

grr, profiler error.

Edited June 6, 2014 by agentx