McGuireAI (Threaded Lua AI Experiment)

[kmcguire]

http://www.kmcguire.org/spring.McGuireAI.git/

The actual AI is not finished. Only, about ninety percent or more of the support infrastructure. I have just started to work on the actual code for the AI.

One of the more interesting abilities which makes it different from other AI is that it executes on separate thread from game engine. When I first started I had no reason to use a separate thread since the normal processing done, as with other AIs, is hardly worth moving it into a separate thread. What happened was that as I was working with some path finding algorithms and some normal enumeration of data from the game I noticed that my load time was getting rather long. This created a noticeable pause before the game started. To keep from using threads I implemented a cache for this data, but this did not solve the first time loading. Also, my goal is to write as much as possible in Lua to make it easy for people to experiment and fix problems. Since Lua can be edited with any text editor and requires no compilation this makes it perfect. The down side is that it is magnitudes slower in some areas. So my only option left was to move the code in C which I did not and still will not due, unless I always have a equivalent function in Lua that someone can switch too.

So, I decided to try using co-routines in Lua. These worked very nicely except now I had the headache of having to maintain all these yield commands in just the right places and then end up with later on scaling problems where a slow machine might notice the points between the yields more. In Lua a co-routine is cooperative multi-tasking. Each thread yields it's execution. This caused me to put some time and effort in creating a separate AI thread that could run Lua and use co-routines for multiple AI, but not block the main game engine thread. Oh, and I disliked the co-routine approach too because the more yields you inserted to smooth out the heavy loading computations the more overhead and the less efficient everything became.

My results so far as very good. I use ring buffers for communication between the AI thread and the game engine thread. A implementation of asynchronous callbacks is implemented, and also (which I use in my code at some points) the equivalent synchronous calls. I do not plan at the moment to support a individual thread for each instance of my AI -- although in the future this would be nice to simply match the number of cores (maybe minus one) on someone's machine -- if the processing need even existed but it requires some additional work for data shared between Lua instances. Plenty of tricks to do it with out lots of overhead.

The code is written for win32 systems. I will have to take some time to add in the ability for it to compile on unix machines, but this is only a minor annoyance at the moment. The problem is the thread creation and synchronization calls being win32 specific. I tried to keep everything so that it would compile in plain C, although I might have accidentally slipped in a C++ keyword somewhere which needs removal.

At the moment it just loads. Drives the AI commander to the 0,0 position on the map and handles most of the events including tracking units on the fields and their properties for their definition and current real time properties like health and such.

I thought it was to a point that other people might find it useful or helpful in the event that they were planning to do something similar and wanted some insight into how someone else did it. You know since my AI is not actually playable.

Oh, and just in case someone missed it. The only reason I made a separate thread was not because the AI needed the extra computation power on a multi-core system -- but it was to keep the game running smooth no matter how deep the AI got into thinking about it's next move or generating any type of data structure to make the game more challenging. <-- This makes it a lot easy on me which is important in the sum of things.

If you are wondering about my actual AI. This is a overview and you can find a bare minimum of the code for it implemented.

Code: Select all

	Overlord
		1- handling contracts to build certain units
		2- manages the contracts for building structures and units that collect resources
		3- manages the accept/deny of contracts to build units and structures from 
		   the scout, defense, and offense masters
		4- manages goals which entail contracts with defense, offense, and scout master

	ScoutMaster
		1- manages groups(singe/multi) of units
		2- determines need to build radar towers
		3- determines need to build radar jammers
		4- keeps track of targets (by scouting or radar)
		5- determines enemy movement destinations, ect.
		6- requests building of units and structures to the overlord

	BuildMaster
		1- manages groups(single/multi) of construction units
		2- builds structures and units
		3- manages the building queue and balances with resource needs
		4- tells overlord about resource needs
		5- tracks unmanaged units

	DefenseMaster
		1- requests structures to the overlord (not units -- OffensiveMaster does this)
		2- requests guard or patrol contracts from the offensive master

	OffenseMaster
		1- manages groups(single/multi) of offensive units
		2- manages contracts for attacking and guarding
		3- requests units (not structures) from the overlord
		4- manages need for bigger, specialized, ect units by talking to the scout master

The interesting part is that the masters (and overlord) all run in a software thread (Lua co-routines). This is not for speed but rather to allow them to think independently. They communicate using contracts. So they work together while each performs a specific function. The overlord adjusts and pokes them. And, the contracts also keep each headed towards the ultimate game goal.. Total Annihilation!!!

You will not find any of that code implemented, but it will not take much code to do it. It is all mostly abstract thinking.

[imbaczek]

the architecture sounds very nice. your "masters" are what other AI people usually call planners, and i'd suggest implementing vertical planners - on group and unit level - so your master planner can think about what and lower level planners get to think about how.

[hoijui]

yeah... then the higher level planners say: "win the game already!!"
and the lower level ones say: "with what my lord, with what?"
and.. you get it

what i did not really get.. are you using the C AI Interface or the Lua AI (interface)? also.. you start talking and it sounds like everything is written in Lua, but somewhen you start talking about C stuff ...
and ultimately: does it make sense to keep stuff like pathfinder and such in Lua, for the reasons you mentioned? because... usually people unable to understand C algorithms, and unable to compile stuff, will neither be able to fix a pathfinder algorithm in Lua anyway.

and last.. is there a repo already? :D

[kmcguire]

I get confused sometimes between wrapper and interface. I think you are talking about the interfaces that wrap the game interface. I can not directly answer the question, but I can hopefully answer it by saying that I simply call the functions passed to me in the callback structure.

I say-- I wanted everything in Lua. But, I can not always get what I want. The code that bonds the Lua and the game engine together using two separate threads is in C. Then these functions are implemented in C that Lua can call (they could be wrote in Lua):
ExecuteScript, Debug, SerializeToFile, DeserializeFromFile, StructPack, StructUnpack, BitAnd, BitOr, BitNot, SendCallsToEngine, FreeMemory, ConvertArrayToTableAndFree

If performance is the goal then it makes no sense to keep the path finding algorithm in Lua. As for what is the best way to do stuff I have no idea.

I can see a connection between people unable to compile C code and not being able to understand a path finding algorithm. But, how much of a connection I do not know. This is a very good question!

But, I have this feeling deep down inside that it would be easier for people to poke on the path finding from Lua rather than trying to setup a build environment. There are a lot of really smart scientist that would rather pull their teeth out then try to get a build environment setup for compiling C code. Which, is why I think you see a lot of them write code in something easier. So they can spend their headaches on the problem at hand and not something that is completely irrelevant.

I have even seen people build stuff to make writing code in C more like writing it in Fortran. Which was horribly inefficient. But, apparently it was worth it because they had fewer headaches.

So I think that is it worthy as a experiment at the least.

I made this GIT repository. I do not know if it works. But, it is located here: http://www.kmcguire.org/spring.McGuireAI.git/

But, you raise very valid argument! Yes, I love to hear from people. I know how tough it is to raise a question with out sounding like you are trying to beat something down. I also have a hard time trying reply with out sounding like I am trying to tell someone they were wrong.

But, you know we do this like a experiment. And, in the next few weeks maybe we can see a working AI that gives at least a medium challenge to players. If I make it this far then everything is a success!

You know if he builds a solar collector and a k-bot factor I might have to call it successful <laughing> !

I have three goals:

[1] Very easy to modify AI code.
[2] Ability to work with any mod.
[3] A moderately challenging/interesting AI at the least.

<edit>Oh, I want to say I love C! But, it is really a pain in the butt when I try to prototype or do some really high conceptual work.</edit>

[hoijui]

when talking about AI Interfaces, or AI Interface plugins, i mean the yellow boxes in the first diagram at this page:
http://springrts.com/wiki/AI:Development:System
Wrappers are the green boxes, though usually you only care for the green boxes inside the blue and purple ones, not for the ones inside the yellow boxes, as these are just utility function libs.

i agree, the names are not chosen so well, as there is ambiguity for interface, as it could be the basic C AI Interface (part of the engine) or an AI Interface plugin.
as i got it so far, you are coding a C AI (from the engines point of view), which internally consist of mainly Lua code.
is that it?

i tried to use your repository:

Code: Select all

> git clone http://www.kmcguire.org/spring.McGuireAI.git McGuireAI
Initialized empty Git repository in /home/user/Projects/spring/repos/master/AI/Skirmish/McGuireAI/.git/
fatal: http://www.kmcguire.org/spring.McGuireAI.git/info/refs not found: did you run git update-server-info on the server?

looking at man git-update-server-info, i guess you had to run the following in the git repo on your server, to make it work:

Code: Select all

git update-server-info

.. or use github

i see. you probably know more potential path finder coders then me, and will have a better grasp of how many would do it only if they do now have to setup a compile env. also, i wont complain, as it is not me having to do the additional work , and as you are fine with doing it.

[kmcguire]

Yes, basically, nothing but Lua code. Wow, I am glad you posted that diagram since it helped me understand everything better!

[very_bad_soldier]

The problem is the thread creation and synchronization calls being win32 specific.

You may want to take a look at the pthread library. It is available for most (all?) operating systems and offers a consistent API.

[hoijui]

i am glad it helped :D
i like the diagram. i would like to have more of them, but they are cumbersome to do. it does not by accident feel so lonely in the spring community
also.. even doh it is linked in the wiki, hardly anybody that should have seen it has found it by himself yet.. so if you have an idea from where it should be linked to best, please change it

[kmcguire]

I wanted to post on the rough answer to viability and performance of running the AI in a separate thread from the game engine thread that sends events by calling your event function when using the C interface, and in using Lua to do most of the work from packing and unpacking message data.

The glue code was written in C and handled the simple process of packaging game events into messages and placing them into a ring buffer which was then read by the main thread and passed into a Lua event handler function. The glue code also composed of a function called from Lua which handled a Lua table with messages which were referenced by a message placed into a separate ring buffer where the main game thread serviced. The main game thread would then convert the messages into the appropriate function calls to the function pointers provided in the interface structure, and write the results into a third ring buffer and finally set a mutex state which allowed the function called by Lua to convert the messages back into a Lua table and exit back into the Lua interpreter where Lua code unpacked and routed the messages.

The Lua side uses a buffer to hold pending asynchronous calls with a optional callback and callback data argument. The buffer is processed explicitly by calling a execute function (used to create a synchronous call) or before the event function exits it will execute the buffer.

For a lot of messages the buffer was partitioned into set number of messages and these are processed in chunks to reduce the processing time of the main game engine thread. This was not a problem except when executing functions that queried lots of game information such as enumerating the unit definitions when no cache existed. The number of calls would be well over a few thousand.

The programming style was different because you had to write multiple functions in the form of callbacks. Your algorithms had to be broken down into layers and calls batched together to be efficient. This is mainly only a major enemy to viability for algorithms that required lots of game engine calls and needed certain data before continuing.

Some of the drawbacks summarized are:

1. If you need immediate results from a game engine call you have to execute the buffer and this suspends the calling thread until the next game engine event.
2. You have to create callbacks for results that you need but do not have to get at the very moment.
3. You have more overhead per game engine call since messages must be created, transferred, and answered (which by default are even if no reply is expected).
4. Your incoming message buffer has to be processed or it may overflow or grow to a large size from game engine events. So if your thread entered into a large computation you have to be careful that you can handle the load of messages generated during this time.
5. The EVENT_UPDATE event was not viable to be used as a message, and likely will need to be sent using a global flag. Since you will end up getting way too many.

I say rough answer to viability and performance because I have yet to test the architecture during a point in the game where you would normally see large amounts of events generated and therefore can not comment on how that would be handled or any potential problems.

The main gotcha I encountered was the incoming message buffer filling up mostly with update events from the game engine, and the fact that I had to use a lot of callbacks and the parallelization of some of my algorithms so that messages were batched together.

Also, the secondary gotcha is in tracking mobile unit locations. You, as far as I have found, will have to approximate their locations at times and implement a update algorithm that does not flood the game engine with function calls. My current one likes to update when units are known to be moving to destinations and do it over time.

The good sides are:

1. You reduce game engine thread wait time. Since you are only doing the minimal processing on message handling and not actual AI thinking. So the game thread is less likely to have high latency from the AI. Where the player notices the game play getting choppy from the AI.
2. You can take advantage of a multi-core machine to further reduce load on the main game engine thread.

I think that the work involved was worth it only if your AI actually does enough processing that it becomes more work to write you code where it has to exit out and come back to finish processing, or you do processing that could benefit from having more processing time when executed on a multi-processor machine.

I like that I do not have to worry about freezing the main game thread.

[Neddie]

http://springrts.com/phpbb/viewtopic.php?f=15&t=19583

Please modify your entry or add a new one to this thread to keep track of your current AI development.