Little Query Language

[agentx]

Was in need to query the templates more often than acceptable and code got littered with ifs, switches and very long condition lines. So I've spend my bot a triple store and its own query language. This is how it loads:

 : reading 1188 templates :  65/1188 nodes for athen : 139/1188 nodes for gaia : ignored: Brit(1), brit(59), cart(84), celt(69), gaul(55), hele(93), ..... : loaded 0/0 nodes from Hannibal.Data.RootNodes : created   79/  79 nodes for classes : created   41/  41 nodes for technologies : created   14/  14 nodes for resources : created    4/   4 nodes for resourcetypes : created  613 edges on     member (entities membering classes) : created  613 edges on    contain (classes contain entities) : created  111 edges on    provide (entities providing resources) : created  165 edges on     gather (entities gathering resources) : created  274 edges on      build (entities build entities) : created   26 edges on      train (entities train entities) : created   46 edges on       hold (entities holding class) : created    3 edges on       heal (healer heal classes) : created   39 edges on   research (entity researches technology) : created   57 edges on    require (entities require technology) : created   57 edges on     enable (technology enables entities) : created   12 edges on     accept (entities accepting resourcetype (dropsites)) : created  156 edges on      carry (entities carrying resourcetype (ships, trader, gatherer)) : have 2 civs, 13 verbs, 342 nodes, 2172 edges: : have [accept, build, carry, contain, enable, gather, heal, hold, member, provide, require, research, train]

The database has nodes and edges, edges represent a verb and have a direction. Nodes have a unique name. So you start a query with some nodes. Here are a few sessions, 'i' denotes the query (a plain string), 'o:' the parse tree and R a result line:

Parser: i 'healer, hero'      : o: ["healer, hero"]     Q: executed: msecs: 0, records: 2     R: node: healer     R: node: hero

Queries always return nodes and obviously two classes return two class nodes

Parser: i 'healer, hero CONTAIN'      : o: ["healer, hero",["CONTAIN"]]     Q: executed: msecs: 0, records: 6     R: node: units.athen.support.healer.a     R: node: units.athen.support.healer.b     R: node: units.athen.support.healer.e     R: node: units.athen.hero.iphicrates     R: node: units.athen.hero.pericles     R: node: units.athen.hero.themistocles

Here I added a verb after and now the query has a direction, it points from classes to entities. All verbs are keywords and uppercase. LIMIT, SORT, RAND, WITH are keywords too.

Parser: i 'infantry, hero CONTAIN SORT > costs.metal'      : o: ["infantry, hero",["CONTAIN"],["SORT","> costs.metal"]]     Q: executed: msecs: 3, records: 21     R: node: units.athen.hero.pericles,             metal: 200     R: node: units.athen.hero.themistocles,         metal: 200     R: node: units.athen.hero.pericles,             metal: 200     R: node: units.athen.hero.themistocles,         metal: 200     R: node: units.athen.champion.infantry,         metal: 80     R: node: units.athen.champion.marine,           metal: 80     R: node: units.athen.champion.ranged,           metal: 50     R: node: units.athen.infantry.archer.a,         metal: 50     R: node: units.athen.infantry.archer.b,         metal: 50     R: node: units.athen.infantry.archer.e,         metal: 50     R: node: units.athen.infantry.javelinist.a,     metal: 50     R: node: units.athen.infantry.javelinist.b,     metal: 50     R: node: units.athen.infantry.javelinist.e,     metal: 50     R: node: units.athen.hero.iphicrates,           metal: 0     R: node: units.athen.infantry.slinger.a,        metal: 0     R: node: units.athen.infantry.slinger.b,        metal: 0     R: node: units.athen.infantry.slinger.e,        metal: 0     R: node: units.athen.infantry.spearman.a,       metal: 0     R: node: units.athen.infantry.spearman.b,       metal: 0     R: node: units.athen.infantry.spearman.e,       metal: 0     R: node: units.athen.hero.iphicrates,           metal: 0

The syntax is simple, it starts either with nodes or a verb clause. Then you may put one verb clause after another verb clause to traverse the mesh.

[ nodes | VERB [prop [, prop, [...]]]          [WITH prop op value [, prop op value, [...]]]          [SORT op prop [, op prop, [...]]]          [LIMIT value]          [RAND value]          [VERB [...]]]

The idea is the DB represents the involved civilisations, it's a knowledge base of their capabilities. Who can do what, what does it cost and how long does it take. Next step is to retrieve not only templates but real game units, buildings, etc. and in the far future queries written in SPARQL. Currently the code is not optimized and I don't know what happens when 8 bots load their own triple store each with 8 civilisations.

You start the whole thing like this:

civs = new Hannibal.Civilisations(this, ["athen", "gaia"], this.settings.templates);HCQ = Hannibal.Civilisations.Queryquery = new HCQ(civs , "infantry, hero CONTAIN SORT > costs.metal");nodes = query.execute();

Code (still hot, but working) is attached, comments welcome!

querylanguage.zip

Edited February 24, 2014 by agentx

[Radagast.]

Well done and thanks for sharing. It's really hard currently to follow all these actions around. So I'm haven't seen this until now-

You will probably get angry because of my question:

infantry, hero CONTAIN SORT > costs.metal

Does this match all infantry hero units that are filtered by > costs.metal? Or is it really SORTing instead of filtering. Then I think all would be CONTAINed in the result, no?

The parser/query language will surely have benefits other than look if compared to writing MACROs or functions for that directly, e.g. get('infantry,hero', filter_callback)?

Where filter callback would be just like SORT ... ah I get it, the ultimate benefit is the chaining as you stated in the excellent nodes call description!

Is your AI called Hannibal? Your work is motivating me a lot. One I have time I will dive deeply into the AI to finally get my AI (TauCeti) to work ... hopefully we then can include all your improvements into the common_api.

[niektb]

Any numbers on code speed? (So actually: will it cause the game to lag more and if yes, how much?)

Even though it might slow down the game, keep up your work! It is good to create a easier way to access game resources for AI's (It might even encourage me to write a little AI, even though Hephaestion already picked up my idea and started working on (decision tree)).

[agentx]

The language keeps evolving, in game entities are now linked too. Speed-wise, I figure, it is enough to load the bot's own civilisation only. Critical loops now run as while(){}, and most queries are below 1 msec, which is fine. And as long as in game entities are not involved queries are perfectly cachable.

There are two other advantages of the query language: It moves domain knowledge from code to config and since it is based on a triple store it opens door to run a backward chaining inference engine, where the bot designer sets goals and the bot tries to achieve them. But that will take some time to implement. Currently I'm working on the autonomous groups, the grain-picker use these resources:

units:  [5, "food.grain GATHEREDBY WITH costs.metal = 0, costs.stone = 0, costs.wood = 0 SORT < costs.food"],field:  [1, "food.grain PROVIDEDBY"], refuge: [1, "<units> HOLDBY CONTAIN distance < 100"],

Works quite nice so far, I think I make a video once garrison looks a bit more coordinated.

[niektb]

Works quite nice so far, I think I make a video once garrison looks a bit more coordinated.

Looking forward to it!

[sanderd17]

I'm wondering, if you do a lot of querying, maybe it would be beneficial to have a real database. Something like an SQLite DB in the RAM. Working on the native side could make it a lot faster. And to avoid transforming everything to JS vals every time (which takes time), it could return iterators as query result, and only convert the values when they're needed.

[agentx]

@sander

A culture DB on the native side would be great. Usually the result sets are not that huge, just a few records. Let me expand the example of grain picker above:

units:  [5, "food.grain GATHEREDBY WITH costs.metal = 0, costs.stone = 0, costs.wood = 0 SORT < costs.food"],

From the point of the group it only cares whether the units CAN gather food.grain. It doesn't care if they are soldiers, females, slaves, what ever. It is up to the economy to find out what is currently cheapest. First it has to find out how to deliver what the group requested. So it runs the query and gets a list of templates, then it checks whether there are entities in the game not occupied by other groups matching these templates. Let's say the result is: "units.athen.support.female.citizen", checking in game is easy, just append verb + filter and run again: "units.athen.support.female.citizen INGAME WITH metadata.group = ''". If there are results, then the unit IDs are included and all left is assigning the units to the group.

In the case of no in game units, the economy first has to check requirements (technology) the query is "units.athen.support.female.citizen REQUIRE". If that returns nothing next step is to find out how to produce the requested resource. The economy doesn't know a thing at this point whether these are units, technologies or structures. So it runs 3 queries:

units.athen.support.female.citizen TRAINEDBY INGAMEunits.athen.support.female.citizen BUILDBY INGAMEunits.athen.support.female.citizen RESEARCHEDBY INGAME

to find out structures.athen.civil.centre is a candidate, is in the game and the engine command to produce them is "train".

Basically the economy reads every tick its list of requests and checks what can be done using the query language and fires the according engine commands. It is an easy process and just requires to build proper queries using string operations.

A query like : "units.athen.support.female.citizen TRAINEDBY INGAME" runs in virtually no time, because it starts with one node only and checks just a handful edges. If "TRAINEDBY" returns nothing, "INGAME" doesn't even need to run.

So, yes there are probably are a lot of queries per tick. The crucial thing is whether they query in game objects or only the template space. Don't know how this could be done on native side. Also the query would need translation into SQL, which may open another can of worms because fast and simple triple store queries may lead to heavy SQL queries.

More obstacles come to my mind, I think, I can make a better proposal once the bot knows a bit more than cropping.

[agentx]

> make a video

How do you guys make youtube videos?

[niektb]

> make a video

How do you guys make youtube videos?

Upload a video to YouTube and paste the link in your post, the site itself will do the rest.

[agentx]

Which tool is good for capturing on Windows XP?

[niektb]

Which tool is good for capturing on Windows XP?

What is your system looking like? I've used Fraps but didn't liked it too much but that depended heavily on my system. Enormous file sizes and the additional CPU usage made 0 A.D. running very bad on my Windows XP system (Which had an old AMD Phenom 2,2GHz x4). But it's definitely worth trying out.

[baoxiaotian]

Consequently in most nations where internet betting is forbidden the game might even become prohibited.This may usually outcome in discontent and several people obtained forbidden through messing around with Diablo 3 Gold their balances forever shut down.

[Radagast.]

... if you do a lot of querying, maybe it would be beneficial to have a real database. Something like an SQLite DB in the RAM. Working on the native side could make it a lot faster. And to avoid transforming everything to JS vals every time (which takes time), it could return iterators as query result, and only convert the values when they're needed.

Couldn't we use UnQLite (from the same devs like SQLite) instead? It's self-contained in one (1) C-file - without dependency. Has a C API and is object, JSON storage. (key => value pairs).

[query sets are] not that huge, just a few records. Let me expand the example of grain picker above:

Thanks for the expansion on grain picker example. Gives some interesting insights.

Is your AI called Hannibal? So perhaps soon we have Aegis, Hannibal, TauCet & Fides and the one of Teiresias ... (essentially myself is working on two variants hence Fides & TauCeti as one is quite specific for the Roman Republic Mod in a hybrid-human-AI mode and with splitting and joining capabilities.)

It might even encourage me to write a little AI, even though Hephaestion already picked up my idea and started working on (decision tree).

I didn't want to discredit anyone. Surely Teiresias must have spakred the splitting and joining idea. You brought in the self-learning comment and agentx the state machine. My humble self only forged both into the hybrid version of state machine and the variant weighted decision making tree.

[...] since I arrived here, I have seen no-one start serious work on AIs.

0 A.D. is also limiting because it requires extreme flexibility [as it might change heavily in the future?].

See we need your AI ... okay, I also recall:

1 working bot and one sub-par experimental bot are not interesting compared to having one really good bot, I believe.

So decide yourself, it doesn't matter. If you think our efforts are enough already (though we have not yet a working alternate AI) you don't have to start your own - but are always allowed to!

[niektb]

@Hephaeistion

Hi guys,

I've just returned from my holiday and I've got a bunch of idea's for my upcoming AI.

I decided to name it Brennus, derivated from the Galic leader who attacked Rome and almost conquered it.

It relies heavily on scouting, so scouting is the key. Futhermore I'm going to make a dynamic strategic-tree.

Using the information from the scouts, it detects key information about strength, troop types and so on, and then the AI determines (using the tree) the best way to behave.

I decided to use APIv2 at startup, and later on I'll upgrade. (as soon as v3 is really, really stable)

Roadmap:

- Startup:

First I want an AI that works in every aspect of the game. This one won't be released.

- Scouting programming

First the basic scouting routine.

Second the ability to detect information about the enemy.

- Tree design startup

I start with some simple decisions and then work to advanced strategic battle-level.

- Micromanagment

After I've set up a simple AI, I'm going to implement all buildable / trainable stuff, getting a defence set up and some extra tree-decisions concerning balance of units.

- Advanced functionality

When all this works, I'm going to implement advanced functionality like all civs, more than 2 players, naval support and (vs human) psychological warfare based on Sun Tzu's Art of War.

- Bugfixing.

Note: This list is of course subject to changes.

I would love to get some tips / suggestions / something else. If someone wants to coöperate just PM me. (I could use some help to finish it before alpha ∞. http://www.wildfiregames.com/forum/public/style_emoticons/#EMO_DIR#/lol2.gif )

Greets,

Niek

Basically I did nothing more than putting ideas on paper, since I couldn't get any simple stuff working. So no blame to you!

[Radagast.]

Interesting! Another useful list.

So did I, basically just a collection of ideas thrown into our thinkfarm . Finally we will make it happen jointly. As a single one it does not make sense any way as we stated before, because if there is noone to show your work or ideas to... well then it's all useless.

So thanks for sharing! (currently I'm thinking about if it's useful to make enemy attacks being coordinated from an right-angle as seen from the frontiers to the attack target or if the units should try to reach their targets straight through enemy territory... probably yet another decision the general should make and learn from it.)

Thanks for the suplply work, too!

Have to get into the query language next month when I start my AI tests 'in the fields'.

Edit: of if --> or if, Unother --> Another, on the field --> in the fields?

Edited March 9, 2014 by Hephaestion

[niektb]

Thanks for the suplply work, too!

There is no supply work yet, only some code in the engine to get a message when the entity's territory has changed. I got a bit of headache on really implementing the supply itself (I know some kind of a way to implement it, but don't know how to really start, had a few stucked trials and paused work for a while ) I'm now trying some Random Map Scripting. See if I can create some fun maps!

[Radagast.]

Thought the random maps were random ... so how do you plan to influence the random?

Supply will work.. I have a decision tree somewhere for this functionality .. so the general staff will manage the logistics.

[agentx]

The 'Little Query Language' now has a web interface at http://noiv.pythonanywhere.com/agentx/0ad/explorer/hannibal.html To start click HCQ in the menu, choose an interesting node from the list and click 'analyse'. From there you can browse the triple store via the blue links.

Also the planner makes progress: I've ported the python sources to JavaScript. Two tests are ready to try out. It seems a blocks world is the Hello World in terms of planning, so the examples define 3 blocks (a,b,c) and a table. The planner tries to find a list of actions moving the blocks from state to goal, see test2.

The new JS module system has the advantage sources run in the web AND in 0 A.D. Very useful, this way I can use the browser to debug!!!! However, above site is only tested with FF30, don't tell me it doesn't run with IE , even Chrome doesn't support all ES6 features.

I've started to document more of Hannibal in the wiki: http://trac.wildfiregames.com/wiki/HannibalBot check it out! Comments are welcome.

Hannibal is making first baby steps, it can launch groups maintaining a field. Groups are coded with a high level bot language:

// message queue snifferlistener: {  // game started, something launched this group  onLaunch: function(){    // turn res definitions into res objects    this.register("dropsite", "units", "field");     // assuming a CC exists    this.economy.request(1, this.dropsite);            },  // a request was succesful  onAssign: function(resource){        if (this.dropsite.match(resource)){      this.location = resource;      this.economy.request(5, this.units);    } else if (this.field.match(resource)){      this.location = resource;      if (resource.isFoundation){this.units.repair(resource);}      if (resource.isStructure){this.units.gather(resource);}    } else if (this.units.match(resource)){      if (this.units.first(resource)){  // not sharp enough        this.economy.request(1, this.field, this.dropsite);      } else if (this.field.isFoundation){        resource.repair(this.field);      } else if (this.field.isStructure){        resource.gather(this.field);      }    }  },  // resource lost  onDestroy: function(resource){    if (this.field.match(resource)){      this.economy.request(1, this.field, this.dropsite);    } else if (this.units.match(resource)){      this.economy.request(1, this.units);    }  },  // there are enemies and gaia  onAttack: function(resource, enemy, type, damage){    if (this.field.match(resource)){      this.units.repair(resource);    } else if (this.units.match(resource)){      deb("     G: %s health: %s", resource.name, this.units.health);      if (this.units.health < 50) {         this.units.garisson(this.refuge);      }    }  }}

I hope the semantics are self explaining. It really took some effort to make things that simple, well, now I understand why it takes a village to raise a child In case you're wondering, the idea is all other features are much faster and easier implemented using this (sigh) language. I have plenty of time this WE and hope I can finalize it with a video showing above code in action.

Edit: this is a very interesting Google search: https://encrypted.google.com/search?num=100&q=site%3Ajsperf.com+%27use+asm%27 lots of asm.js code to checkout, some are very clever and fast.

Edit2: links

Edited April 19, 2014 by agentx

[niektb]

Curious to see the first gameplay shots!

[agentx]

First try:

Team blue, game starts with 2 building and 2 units. At tick 1 and 2 a grain-picker group is launched requesting a dropsite first. Economy picks existing CC and assigns it. Having that the groups request 5 units. For the first group the economy picks the two idle, as they match the request, and trains 3 other. The second group gets 5 freshly trained units. With the first unit assigned, the groups request a field and start repairing once it was assigned. Gathering happens automatically by the units' AI. The video shows also how the groups auto-request new resources, when destroyed.

I want the groups as self-sustaining as possible, what ever happens their mission is to gather. Next step is make them shelter from violence.

How can I adjust width and height of video in the post's code?

[niektb]

Looks cool!

I guess you can't change the width and height in the post? (Don't know actually, why do you want to?)

Edit: how is decided where to place the farm?

Edited April 21, 2014 by niektb

[feneur]

How can I adjust width and height of video in the post's code?

Not sure it's possible. Should be no real reason though, anyone who wants to see it larger can just click through to Youtube

[agentx]

That's right, just wanted to get rid of the black borders, at least here.

[agentx]

> farm position.

The groups keep track of their position. So far I use Aegis' findGoodPosition() feeded with that position.

Keeping track depends on what's known, if there is a dropsite that pos has priority, otherwise the center of the units is taken. Missing is a logic which chooses a new position, if the foundation is destroyed immediately and repeatedly. But that's part of a more general problem. I want groups making claims on the map without actually building something. Think of a place for the army to exercise, where healers do their job, jobless units demonstrate , etc.

Ontop that allows to structure the village a bit by claiming upfront good places for later defense towers or like I've seen recently in a MP with 4 fortresses close to a CC.