Page 1 of 12

EggPlant AI ramblings

Posted: 13 Jan 2012, 23:25
by aubergine
I tried explaining to the wife that I was hacking together a JS AI bot for an open source game, and that in fact my AI is actually a collection of AIs that communicate amongst each other and decide what actions to take based on current game situation... and she just sort of stared at me as if I was insane (which I probably am).

So, I thought I'd create a topic here to jot down my rambling thoughts and hopefully some will be useful for other newbie AI developers setting out on creating their first AI...

BTW, huge thanks to everyone that's been putting up with the gazillions of questions I've been asking over the past few days, especially Per and NoQ who have really got me motivated to build an insane AI :)

Re: EggPlant AI ramblings

Posted: 13 Jan 2012, 23:28
by Berg
aubergine wrote:BTW, huge thanks to everyone that's been putting up with the gazillions of questions I've been asking over the past few days, especially Per and NoQ who have really got me motivated to build an insane AI :)
The only way to do it!

I have been watching your questions on the forum and the amount of interest you show is encouraging!

Keep at it..

I am interested in the AI too but till now have not looked into it.

Multiple AIs

Posted: 13 Jan 2012, 23:42
by aubergine
The structure (flowchart) of the AI is shown at the top of this page. Each box on that diagram (with exception of EP which is currently just a namespace container) is actually an AI that deals with a specific thing, boxes higher up the diagram coordinate and summarise what's going on beneath them.

For example, a map Sector might realise it's not very well defended and and ask the Boss to do something about it. The Boss looks at everything else that's going on and decides the Sector deserves a defensive Outpost. Boss creates a Task (tasks = Boss's "to-do" list) that will make sure the work gets done and report back if there are any problems. Task, seeing that there's no defence in the sector yet, asks War to send in an AirDefGroup to clear any enemy units while construction takes place. War adds a Mission (missions = War's "to-do" list) with a note to let the Task know when the area is clear. All the AirDefGroups are busy with higher priority tasks, but eventually one becomes available and after restocking with units from a FeederGroup it accepts the Mission. Having confirmed the area free of enemy troops, Mission lets Task know it can begin work. Task creates an Outpost and attaches it to the relevant sector. The Outpost then tells the trucks what needs building and where. When the construction is complete, the trucks are returned to their OilerGroup and the AirDefGroup sets off on it's next mission.

That all sounds petty complex, eh? But it's actually a fairly simple way of handling a very complex scenario. I want my AI (called EggPlant) to constantly adapt to the changing game situation. I wanted some way to set out tasks but have them "intelligently" prioritised - there's no point building an outpost (requiring air support) if my base is about to get destroyed - obviously the air support should go to the base and protect that instead.

The main AI's in my EggPlant AI are:

* War - in charge of warfare and the AI's armies
* Map - in charge of strategic planning and defence
* Boss - in charge of construction, maintenance, and oil distribution
* Ally - in charge of collaboration with allied players (this is just a stub for now, until the JS API provides some ways for an AI to communicate with other AIs and humans)
* Group - in charge of building droids, assigning them to groups and ensuring groups are replenished to replace lost units, etc.

Map sectors

Posted: 14 Jan 2012, 00:14
by aubergine
On current APIs, most of the map is left undefended and unless you run in to some enemy troops you can move around quite freely until you get near the enemy base or a fortified oil derrik.

So, one of my early design decisions is that I wanted the enemy to have to fight all the way to get to my base. I also wanted additional intel on each area of the map so that my War AI could better plan missions - eg. if there are two similar missions, which will have the higher chance of success based on what's between the attack group and their target?

For these reasons, and a bunch of others, I decided to split the map in to sectors. In order to decide what size to make each sector, I assessed a number of factors including:

* VTOL circle radius (yes, I'm going to use VTOLs for defence as well as attack)
* Artillery range (with both early and late research)
* Sensor range (with both early and late tech)
* Damage resilience - eg. level of overlap for sensors and artillery

After much pondering I decided to go for a sector size of 20x20 tiles. I did some mockups in OmniGrafffle (mac flowcharting app) to get an idea of how things could play out and drag shapes around to find out how different scenarios would affect sensor & defence coverage of a sector. I've uploaded a pic (below) of a best case scenario (which would require the whole map to be flat and buildable) as it's one of the clearer diagrams and easier to explain.

Different sized circles of the same colour indicate sensor/artillery coverage for early (smaller) and late (bigger) tech. As you can see, as the game progresses each sector can attack enemy units in adjacent sectors.

I'm not sure how this will work out in practice until I my AI gets nearer to completion, but that's where I'm headed for now.

Re: EggPlant AI ramblings

Posted: 14 Jan 2012, 01:13
by Goth Zagog-Thou
I'm very interested in your AI project. :) I encourage you to keep at it and don't give up!

Making the AI adaptive

Posted: 14 Jan 2012, 18:10
by aubergine
I'm currently doing lots of small sprints on various aspects of the AI to sanity check my thoughts about how the various AI's within it will worth together to achieve success. My current sprint is focussed on having the AI adapt its missions...

From what I can see, the current breed of WZ AI's all tend to use the same tactics over and over again - essentially a hard-coded approach to playing the game. They keep using the same tactics regardless of how successful they are, but because the human is adaptive they will learn a way to beat the AI sooner or later.
Albert Einstein wrote:Insanity: doing the same thing over and over again and expecting different results.
I don't want EggPlant (EP) to exhibit symptoms of insanity.

In EP, there are multiple AIs - any of them can request a military mission by sending a task to War AI. A task contains a bunch of information, for example what sort of mission is required:

Code: Select all

const EP_TASK_DEFEND    = "Defend"; // defend location (War chooses how)
const EP_TASK_ATTACK    = "Attack"; // attack location (War chooses how)
const EP_TASK_AIRDEF    = "Air Defend"; // defend location with an EPAirDefGroup
const EP_TASK_AIRATK    = "Air Attack"; // attack designated target(s) with an EPAirAtkgroup
const EP_TASK_LANDDEF   = "Land Defend"; // defend location with an EPLandDefGroup
const EP_TASK_LANDATK   = "Land Attack"; // attack designated target(s) with an EPLandAtkGroup
const EP_TASK_LASERSAT  = "Laser Satellite"; // attack location with laser satellite
const EP_TASK_HALFNUKE  = "Half Nuke"; // half of all available attack groups nuke target
const EP_TASK_FULLNUKE  = "Full Nuke"; // all available attack groups nuke target
const EP_TASK_CAMPDEF   = "Defend Camp"; // all applicable nearby groups defend camp
const EP_TASK_RECON     = "Reconnaissance"; // scout an area covered by Fog of War 
And what are the targets (if applicable):

Code: Select all

// EP target types for War
const EP_TARGET_ONE     = "Target One"; // specific an individual structure, droid or feature
const EP_TARGET_TYPE    = "Target Type"; // specific type of structure, droid or feature
const EP_TARGET_ENEMY   = "Target Enemy"; // structures and droids
const EP_TARGET_FEATS   = "Target Features"; // destroyable features (trees, etc)
const EP_TARGET_STRUCTS = "Target Structures"; // structures
const EP_TARGET_DROIDS  = "Target Droids"; // droids
const EP_TARGET_VTOLS   = "Target VTOLs"; // VTOLs
const EP_TARGET_BORGS   = "Target Cyborgs"; // cyborgs
const EP_TARGET_TANKS   = "Target Tanks"; // wheel/halftrack/track/hover vehicles
const EP_TARGET_TRUCKS  = "Target Trucks"; // construction droids
const EP_TARGET_SAMS    = "Target SAMs"; // surface-to-air defence structures (flak, stormbringer, etc)
const EP_TARGET_RANGED  = "Target Ranged"; // long-range defence structures (artillery, missiles, etc)
const EP_TARGET_DEFENCE = "Target Defence"; // defence structures of any kind
const EP_TARGET_LASSAT  = "Target LasSat"; // laser satellite command post
const EP_TARGET_FORTS   = "Target Fortresses"; // large fortress structures (missile fortress, etc)
const EP_TARGET_WALLS   = "Target Walls"; // walls and gates
const EP_TARGET_SENSORS = "Target Sensors"; // sensor + satellute uplink structures
const EP_TARGET_EMPS    = "Target EMPs"; // EMP mortars and towers
const EP_TARGET_POWER   = "Target Power"; // power gens and derriks
const EP_TARGET_FACORY  = "Target Factories"; // droid factories
const EP_TARGET_REPAIR  = "Target Repair"; // repair facilities and rearming pads
const EP_TARGET_PADS    = "Target VTOL Pads"; // VTOL rearming pads
const EP_TARGET_LABS    = "Target Labs"; // research labs
const EP_TARGET_COMMAND = "Target Command"; // command centers
War assumes that the AI making the request has a fairly good idea of what's needed (eg. because it's "on the ground" so to speak) but sanity checks the task request. War will do one of the following, after consulting with other AIs if necessary:

* Reject the request - eg. it might already have a similar request in the Mission queue (which would have it's priority increased as a result), or the targets are already destroyed, or there are too many higher priority requests in the queue, etc.
* Modify the request and queue it - eg. it's an air attack and War spots lots of SAMs so it adds a prerequisite mission to destroy those first (after first checking to see if there is a mission to do that already in the queue)
* Queue the request as is

I'm hoping this sort of approach will make EP avoid insanity - decisions will be made by War and other AIs based on current state of play, rather than a static hard-coded approach.

Re: EggPlant AI ramblings

Posted: 15 Jan 2012, 02:05
by Rman Virgil
.

:hmm: Decision Tree Learning ? (Weak or Strong Supervision ?)

.

Re: EggPlant AI ramblings

Posted: 15 Jan 2012, 02:49
by aubergine
I've never made an AI before so I'm making this stuff up as I go along - know any good intro guides to decision tree learning?

Re: EggPlant AI ramblings

Posted: 15 Jan 2012, 04:20
by Rman Virgil
aubergine wrote:I've never made an AI before so I'm making this stuff up as I go along - know any good intro guides to decision tree learning?
Ic. Impressive native ability. :3

I first explored the nut and bolts of it in Chapter 7 of the 2006 first edition of Artificial Intelligence for Games, Second Edition (2009) by Ian Millington & John Funge. Top of the line resource but the cheapest you can buy the book for is about $50 US. (It partly inspired a year long WZ map-mod experiment I called SP 8c-ManGodAi4x & 4c-AquaCoop MP)

The following free .pdf will give you the intro: An Implementation of ID3 --- Decision Tree Learning Algorithm
(Demo in Java - source available too.)

The ID3 Learning Algorithm is basic - the starting place. From there you go to the simplest and most useful in the context of game a.i. - the Incremental ID4 (possibly the ID5 - which looks more promising for certain projects.)

Free .pdf paper correlating the ID3, ID4 & ID5 Algorithms: Incremental Induction of Decision Trees

I'm sure you'll run with it from here, assessing the scope of what it all entails. :)

- Regards, Rman. :hmm:
.

Class Inheritance

Posted: 16 Jan 2012, 05:09
by aubergine
@Rman: Wow - thanks for all the info and links. I'll start reading through that this week depending on RL commitments.

So, an update on EggPlant. For the past few days I've been battling with class hierarchies and in particular proper OOP inheritance model in JS. Here's why...

I have a bunch of "Group" AIs - one that's good with VTOLs, one with construction trucks, one with feeder groups, and so on. Each of these AIs have a herd of similar features - such as "move group to x,y" or "retreat to nearest safe base" and so on.

There's some functions that are the same across all the group AIs, some that are the same across a few of them, and some that are unique or only relate to one or two group AIs. Now, I could just create named references to existing functions like this:

Code: Select all

function GroupAI1() { ... }
GroupAI1.prototype.doFoo = function() { ... }

function GroupAI2() { ... }
GroupAI2.prototype.doFoo = GroupAI1.doFoo;
In fact, that's how my AI script started out. But I kept running in to lots of fringe cases where I just wanted to extend an existing function (eg. wrap it in some other code) or whatever, or where I wanted to use practically everything from an existing Group AI but just override a few functions. As time went on, I was becoming more and more frustrated with growing mess inside my script caused by all these little things - it was like death by a thousand paper cuts.

So, I decided it was time to do some proper OOP where ClassA could inherit ClassB - this would give ClassA everything that ClassB has, but allow bits to be overriden to suit the needs of ClassA. And, because ClassA would still be able to call superclass (ClassB) methods (eg. from within a ClassA method of same name), it would make my code a lot cleaner and more understandable.

Key requirements are:

* Constructors (especially superclass ones) shouldn't get called unnecessarily - eg. during inheritance or instantiation.
** By default only the constructor of the instantiated class should get called, however it might choose to call it's superclass contructor and so on (using .epSuper() method)
* Functions should remain untouched (ie. not wrapped in crufty activation objects) when doing inheritance
* There should be no (or as close as) cruft added to objects, classes, instances, etc.
* Calling supertype methods/constructors should be a doddle, and not break if I change names of classes or functions, etc.
* Inheritance should happen very quickly and easily
* Changing superclass prototype should affect all classes based on it, including their instantiated instances
* Class inheritance != merging objects together! OMFG so many libraries use this approach!
* typeof and instanceof should work as expected

Let's say I have 3 classes - cChimp, cBar, and cFoo. I want cBar to inherit cChimp, and cFoo to inherit cBar (which has inherited cChimp):

Code: Select all

function cChimp(){this.name="Chimp"};
cChimp.prototype.c = function(){console("chimp (cChimp)")};

function cBar(){this.name="Bar"};
cBar.epInherit(cChimp);
cBar.prototype.b = function(){console("bar (cBar)");this.epSuper();};
cBar.prototype.f = function(){console("foo (cBar)")};

function cFoo(){this.name="Foo";this.epSuper();};
cFoo.epInherit(cBar);
cFoo.prototype.f = function(){console("foo (cFoo)");this.epSuper();};
(epInherit and epSuper are functions I've made which I'll describe later)

If I now make a new instance of cFoo, which I'll call 'foobarchimp' to illustrate that it contains those three classes, I want things to work this way:

Code: Select all

var foobarchimp = new cFoo();
console(foobarchimp.name); // = Bar - because cFoo constructor called .epSuper() = cBar constructor
foobarchimp.f(); // = foo (cFoo), foo (cBar)
foobarchimp.b(); // = bar (cBar)
foobarchimp.c(); // = chimp (cChimp)
For JS heads, the prototype chain should ideally look like this:

Code: Select all

foobarchimp // = {}
	.name // = "Bar"
	.prototype // = cFoo.prototype
		.constructor // = function cFoo(){this.name="Foo";this.epSuper();};
			.prototype // = Function.prototype
		.f // = function(){console("foo (cFoo)");this.epSuper();};
		.prototype // = cBar.prototype
			.constructor // = function cBar(){this.name="Bar"};
				.prototype // = Function.prototype
			.b // = function(){console("bar (cBar)")};
			.f // = function(){console("foo (cBar)")};
			.prototype // = cChimp.prototype
				.constructor // = function cChimp(){this.name="Chimp"};
					.prototype // = Function.prototype
				.c // = function(){console("chimp (cChimp)")};
				.prototype // = Object.prototype
I thought "Simple - I'll just look at a bunch of JS libraries and grab one of their inherit/extend approaches to use in my AI script". This problem has been solved a million times by now, right?

OH THE PAIN!

I was utterly shocked to see how crappy most OOP is done in JS land these days. It's been 7 years since I was a JS developer, meaning that I've not written a line of code for 7 years until I started this AI project. I thought there'd be a bunch of awesome ways of dealing with proper OOP inheritance and stuff, but no.

Most of the existing libs out there make all sorts of crufty modifications to classes and their methods (functions) - like wrapping them in activation objects, or requiring hard-coded references to superclass methods and so on. And it seems I'm not the only one that's unimpressed with what's on offer today: The JavaScript _super Bullshit (that post covers several of the issues I spotted with libraries I was looking at).

So, I started hunting around for more information, particularly from blog posts and websites. I eventually found Understanding JavaScript Prototypes. which helped refresh my memory on a whole bunch of stuff I'd forgotten about, but it still left me with a sense of impending doom. However, there's a link at the bottom of that page to this masterclass of in-depth JS under-the-bonnet detailed knowledge: ECMA-262-3 in detail. Chapter 7.2. OOP: ECMAScript implementation. Suddenly the task seemed achievable again, although it didn't give much information on how to call superclass methods from an instantiated class.

Well, after almost 2 days of pulling my hair out, cursing the lack of in-game JS debugger and less than useful exception messages in game logs, I have finally cracked it. What's below won't work well in web browsers, but it works beautifully in WZ's JS environment (which I assume is something derived from SpiderMonkey or something like that?)....

First, the epInherit method:

Code: Select all

// allow functions to inherit a superclass
Function.prototype.epInherit = (function(){
	function F() {}
	return function (parent,child) {
		child = child || this.prototype.constructor;
		F.prototype = parent.prototype;
		child.prototype = new F;
		child.prototype.constructor = child;
		return child;
	};
})();
if FuncA wants to inherit FuncB, it's as simple as:

Code: Select all

FuncA.epInherit(FuncB);
Obviously, FuncB has to be defined already, and the epInherit needs to happen before you start adding anything to the prototype chain of FuncA (because the epInherit method replaces FuncA.prototype with a new object (the "new F" line in the code above).

Now the epSuper method:

Code: Select all

// allow classes to call superclass methods/constructors very easily
Object.prototype.epSuper = function() {
	var proto = this.__proto__;
	var match = epSuper.caller;
	var name  = epSuper.caller.name;
	while (!!proto && !!proto.__proto__) {
		if (proto.hasOwnProperty(name) && proto[name]===match) { // found the method
			return (!!proto.__proto__[name]) ? proto.__proto__[name].apply(this,arguments) : undefined;
		} else if (proto.constructor===match) { // found a constructor
			return proto.__proto__.constructor.apply(this,arguments);
		}
		proto = proto.__proto__;
	}
	return undefined;
};
That allows you to call the overriden superclass constructor (if used in your class' constructor) or method (if used in a method of your class) simply by calling .epSuper(). You can of course pass in parameters - there are several approaches depending on what you need to do:

Code: Select all

// eg. if you called: .foo(1,2,3,4) on an instance of SomeClass, you could do:

SomeClass.protoype.foo = function(a,b,c) {
 ...
 this.epSuper(); // call the overridden superclass "foo" method with no params
 ... or ...
 this.epSuper(a,c,"bleh"); // send some/custom args to the overriden superclass "foo" method, eg: 1,3,"bleh"
 ... or ...
 this.epSuper.apply(this,arguments); // send all arguments to the overriden superclass "foo" method, eg. 1,2,3,4
 ...
}
I must now sleep for about 3 days to recover. Hope it is useful to someone :)

Re: EggPlant AI ramblings

Posted: 16 Jan 2012, 05:16
by aubergine
Oh, one last note on the epSuper() method...

It looks quite crufty, but it's not really that bad - it's doing almost the same sort of task as "instanceof" does, but obviously a bit more work as it needs to look at properties of the proto chain rather than just pointers. epSuper is only used on occasion so it won't add much overhead to script processing.

Re: EggPlant AI ramblings

Posted: 17 Jan 2012, 00:35
by Rman Virgil
.

To clarify my PoV, let me start here:
The Boss looks at everything else that's going on and decides....
I want my AI (called EggPlant) to constantly adapt to the changing game situation.
I wanted some way to set out tasks but have them "intelligently" prioritized...
This is not a critique of what you're doing aubergine because I consider myself a rank newbie with all this, bottom line, so an expert analysis is not what I can claim to offer here..

That said, the above quotes made me wonder if those stated goals are achievable just using the WZ-JS API.

This was the question in my head and was explicitly what prompted my initial query:
Rman Virgil wrote: :hmm: Decision Tree Learning ? (Weak or Strong Supervision ?)
I know you may not have time to speak to this and that's totally cool. :3 Just wanted to better spell out my PoV, for whatever it may be worth - or not ! :lol2:

- Regards, Rman. :hmm:
.

Re: EggPlant AI ramblings

Posted: 17 Jan 2012, 01:44
by aubergine
Yes, I think it's all achievable with the WZ JS API, especially as new features keep getting added to it.

I'm still deep in JS coding of EggPlant, however I'm headed towards some brick walls where I will need new features in the JS API - eg. the ability to detect when something new (be it friend or foe) appears on radar, and ideally a method for getting map objects (and indeed map terrain data) within a given bounds rectangle, to name but a few. But as for the general AI stuff, JS is very flexible language so I have lots of "tools" at my disposal :)

I managed to read some of the links you posted and it does appear I've been stumbling in the general direction of a decision tree, albeit a slightly strange one. Currently I'm writing a small in-memory database to log mission data, and will then embark on development of a jQuery-like approach to querying that data.

As usual, I'm coding in several directions at once - I'm also creating an intelligent targeting computer AI (called Target) which will enable EggPlant to make tactical target acquisitions whilst carrying out mission objectives, and which will allow me to start properly developing the 30+ targeting algorithms I have planned. And I also have the beginnings of an adaptive research AI (imaginatively named Research) that will hopefully adapt research based on data gathered from enemy encounters, which would in turn allow me to enhance my Army AI (in charge of droid recruitment, etc) to adapt unit designs based on data from other AIs.

I also have to make the hard decision as to whether to name map sectors numerically (eg. 0307) or alphanumerically (eg. C7) or alphabetically (eg. CG) or something else due to my desired sector size (20x20 tiles) resulting in 12.8x12.8 sectors on a max size map (256x256 tiles). That decision is stalling lots of things so I shall go and have a think about that now...

Update: I've decided to use Base-26 encoding for sector IDs as it seems the most trivial and lightweight approach to implement.

Update 2: And that approach also allows me to put some new JS knowledge in to practice:

Code: Select all

1..toString(26) // a

Re: EggPlant AI ramblings

Posted: 17 Jan 2012, 01:57
by Rman Virgil
.

Ahh, I c aubergine and better understand just how you're going about those goals. Thanks for taking the time to explain. :3

- Regards< Rman. :hmm:
.

Re: EggPlant AI ramblings

Posted: 17 Jan 2012, 12:16
by zydonk
Fascinating. Really hope this works for you. It will be a major development.