Further AI development

[wraitii]

I'm pretty sure this is always the same old issue.

[gameboy]

This is an annoying old problem, but it never can be resolved, perhaps the problem is really very difficult to solve!

Perhaps this September will be resolved!

BTW: The old problem so I kept the report, because it always appears on the game screen! Please forgive me always to report the problem, thank you!

[RedFox]

I made some measurements concerning the topic we discussed today.

We really need a better solution for applying entities delta.

This was a 2vs2 AI game that ran for about 15000 turns.

Looks like there's some O(nlogn) action going around, so it seems to iterate over all entities and does something on a binary-tree structure (totally shooting in the dark here based on the graph alone).

Is the entity-delta code entirely in JS?

[Yves]

Looks like there's some O(nlogn) action going around, so it seems to iterate over all entities and does something on a binary-tree structure (totally shooting in the dark here based on the graph alone).

Is the entity-delta code entirely in JS?

Currently it's entirely in JS. Check binaries/data/mods/public/simulation/ai/common-api-v3/shared.js somewhere around line 230.

One reason why it takes longer is that at some point the AIs start spamming masses of soldiers.

This function basically updates all entity collections for each changed prop in each entity using a slow for .. in loop.

Edited September 3, 2013 by Yves
added "for each change prop"

[RedFox]

Alright, looks like most of the logic is in entitycollection.js

Isn't this bad?: entitycollection.js : 10

    Object.defineProperty(this, "length", {
        get: function () {
            if (this._length === undefined)
            {
                this._length = 0;
                for (var id in entities)
                    ++this._length;
            }
            return this._length;
        }
    });

Why doesn't it use entities.length() ? If there are deleted entities in the entities array, then that might explain the gradual degradation of overall performance.

[Yves]

I'm sorry it looks like the big performance problem in Shared Apply Entities Delta was caused by replacing a for .. in loop with an array.foreach.

This loops through all the "undefined" indices between entity ids. If you have one entity with id 3000, it will loop through 3000 indices.

Now it's between 3 and 5 ms which actually is still too much for a finished game but probably not an issue for us right now.

The AI Script section still uses way too much time though.

Why doesn't it use entities.length() ? If there are deleted entities in the entities array, then that might explain the gradual degradation of overall performance.

Entities isn't an array, it's an object. the entities are indexed by the id which will become non-consecutive as soon as an entity gets destroyed.

Deleting entities can actually be a real performance problem because the JIT compiler can't apply certain optimizations and the function calling delete won't be JIT compiled.

[wraitii]

RedFox: that doesn't exist because it's an associative array. But performance is generally horrible. I've got a few ideas on how to improve on that, but it might be worth considering moving it to C++.

[RedFox]

Yves, wraitii: I think a quick fix can be to add a member "length" to the entitites object. We can increase the counter as needed.

At any rate, it looks like a mess. We should consider moving it to C++ definitely.

[Yves]

According to the comment this is already meant to be a performance improvement.

It just avoids looping through all entities when creating the collection.

I didn't measure if it makes a difference in practice.

It will look like a mess in C++ too.

We should only move things to C++ if we can prove that it makes an important difference.

If we have entity collections in C++ we still need to query them from JS and we have to create temporary objects etc...

If this transition from JS to C++ happens too often we could also end up with lower performance.

[RedFox]

It will only look like a mess in C++ if we do a direct port.

However, if we put our heads together with all the people who have been working on the AI, procure some actual design requirements and structure, we can design something elegant and readable.

It really depends on how much effort we put into it; though, at least in C++ it won't be such a performance hog

[gameboy]

This will be a very great project, quantumstate may provide help in this regard!

[wraitii]

RedFox/Yves: porting the existing stuff to C++ is a little bit like shooting a bullet in our heads.

BTW Redfox Length is never recomputed, it's actually done only once and the counter is incremented/decremtned. The check for "this.length === undefined" checks if the object has ever been initialized.

Anyway as I've said the whole architecture needs to be rethought. Currently entity collections are a bit like std::map, only less efficient. We loop over then entities a lot (for filtering, with "ForEach" and we actually very rarely need to call a particular entity in those at all (for that we use a call to the "big" std::map which stores all entities). So an std::map is probably the worst thing you could do.

Secondly, the use made of those is dumb: most entity collections are created by filtering from another one. We could thus see them as some sort of tree, which would help "ApplyENtitiesDelta" because we could, with much less work, eliminate entity collections that won't accept this entity.

I don't think this last point is 100% clear, but I'll get back to it later (with some graphs and all), I don't have the time right now.

[wraitii]

Okay, self-replying for a more detailed explanation about how entity collections work.

First, this all happens in shared.js, which is the core of the shared component.

Shared.js stores a list of all entities in an associative array [key] = stuff, which is like an even more flexible and slower version of an std::map. There is also an entity collections of those entities.

It also stores entity collections in 2 ways: as an array (somewhat similar to an std::vector), under the name _entityCollections, and as an associative array of arrays ([Key] = [vector]), under the name _EntityCollectionByDynProp.

Now what happens when we run ApplyEntitiesDelta()? There are 2 cases:

-If the message is "Create" or "Destroy", ie if an entity has been created or destroyed, we will loop over all entity collections (using _EntityCollections) and either add it if it fits, or remove it if it was present.

-If we are dealing with a state change, we will loop over all entity collections that have registered for this state change. If for example the change is a change in position, we will access _EntityCollectionByDynProp[position] and we will loop over the array of entity collections. Same deal, we'll check if we need to add/remove.

Now this doesn't sound too bad. However whenever we check if we need to remove an entity, we will have to check if the entity is listed in the collection. And the collections store their entities as an associative array. Thus we need to do something pretty similar to a "find" for an std::map. And we do this a lot. Same for state changes, as we need to know if we need to check wether to remove or add then entity. Put together, this gets way too slow.

To complicate things further, we often iterate over entities of an entity collection. And iterating over an associative array in JS is really slow.

Now the proper way to deal with this would be to realize that entity collections are reaaaally often created by filtering other entity collections. Thus there is a "natural" tree here, and we could use this property to speed things up.

Something to keep in mind though is that an entity collection would not be fully defined by its children.

At the most basic level, we have all entities. THen we have entities for each players, including gaia. Gaia is special-case, since it's basically mostly resources.

However for players the enxt level of division is generally structures and units. And in units, support and the rest (which ban de further divided in infantry/cav/siege…)

With a tree, when we receive a "Create" message, we'd start from the top and see if the entity can be added to that collection. However if we check starting with the "all entities" collection, that's always a yes. We should probably start at a lower level, like which player.

Then we'll check children of that collection. Thus we would only check a little more than what we need, and not all entity collections.

When we get a destroy message, the procedure would be somewhat similar. if the parent doesn't have it, the children won't either.

State changes are a little trickier. The best guess is probably to register the first collection in a branch that needs this state change, and check its children if an update for the parent was required.

This would also help with making Filters more hierarchical, because obviously it's better to check if the entity belongs to the right player first then do some more complex calculation than the opposite.

I think this would help improve the efficiency of entity collection filtering in JS. It might not be much faster though, because JS sucks for looping over associative arrays and arrays in general. Needs some thinking. And it definitely needs a C++ architecture to be efficient, in my opinion.

(if only because the entity collections themselves are inefficient).

Edit: some more notes. ApplyEntitiesDelta also changes the entity in the _entities associative array. Which is also a fairly slow operation. This is about 100% similar to the issue with the range manager and its entity maps.

[gameboy]

Maybe it takes a few days to complete it, and hope you will soon come back together to solve this problem!

[Don]

I'd be interested in playing around with the AI, but without docs on the API I'm struggling to come up with the right question. Probably neither of these is the right question:

• Is there a skeletal do-nothing AI example in the code base, one that does nothing useful but contains the most basic components?
  
• I'd like to create a new AI implementation, and watch it fight AegisBot (and lose). Is it possible to create a new AI in one C++ module, or must I write JavaScript?
  

[wraitii]

Hi Don, those questions are actually perfectly valid and are some things that I should improve someday.

• There is a do-nothing AI, which is the "base" in the common-api folders. In the common-api-v3, this is made slightly more complicated by the presence of a "shared script", ie something that does computations for all AIs (and which is basically compulsory at this point). Another "do nothing" AI is scaredybot, which you can check in the AI folder (it's declared as hidden in its data.json though), it uses the common-api-v1.
  
• I don't think you can write on in C++ now, so you have to do it in Javascript. However we're planning to move some things to C++ for performance, so there might be a day when this is possible.
  

[historic_bruno]

Played several A14 multiplayer games today with a friend against Aegis. I think he was impressed by how hard the AI is now even on default settings, and overall how much it has improved from last time he played

But we ran into a few problems. The OOS error is still there, and at least on our setup it happens practically every game The other thing we noticed was on certain maps, ally AIs will build their expansion CCs very close to our bases, and even surround them. This has the consequence of towers, storehouses, and other things we build on the edges of our territory falling into their territory and becoming damaged. That's really a flaw in our territory logic (it should do something different with allies IMO, allies shouldn't inadvertently damage eachother), but maybe Aegis could stay a bit farther away from its allies? I mean placing 2-3 CCs near my base is a bit crazy

[historic_bruno]

Dropsite placement logic causes extreme lag in certain conditions. My friend was playing A14 on a single player random map, after opening the saved game and using profiler2 I see "Build new dropsites" takes about 2 seconds, and it happens almost constantly. That really shouldn't happen, even if the algorithm is slow, I would expect it to place a dropsite or two and then be finished. Maybe it's due to loading a saved game or some other known problem, but I'm attaching the saved game in case it helps troubleshooting (rename .zip to .0adsave).

savegame-0002.zip

[gameboy]

How do we use it?

[wraitii]

Sounds like it's getting stuck on something... I'm afraid this is a "wont fix", I've changed this logic in my repo already so the error is about 100% non-reproducible.

[gameboy]

@wraitii: My God, this error can fix it? What about the new AI when released? Thank you!

[wraitii]

I think it will be released in a few weeks from now.

Historic_bruno, just to be clear, are your issues with the SVN AI or my beta above?

[gameboy]

@wraitii: About the next beta release at what time will you? Thank you!

BTW:I tested you at the forum released a beta version of AI, I have reported errors you will in the next release of the beta version Fix it?

Edited September 7, 2013 by gameboy

[Josh]

@wraitii: About the next beta release at what time will you? Thank you!

BTW:I tested you at the forum released a beta version of AI, I have reported errors you will in the next release of the beta version Fix it?

Unfortunately because we have limited time and resources, it might take awhile to fix the issues you're encountering. The best way you can help would be by promoting our fundraiser. If we can make $300,000 we would be able to not only fix all these errors but make massive improvements to the game. So, if you really want these errors fixed, promote our fundraiser as much as you can.

[Sonarpulse]

You guys should consider something besides C++ and Javascript. Haskell, Rust maybe.