Grace

Come in here to talk about your sky-net style world-destroying super bots!

Moderator: Defcon moderators

User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Grace

Postby smc » Mon Jun 28, 2010 9:05 pm

Hi all,

Hopefully I'm not too late for this bot party... I'm working on a DEFCON bot called Grace (named in honour of Grace Hopper). I'm using the Lua framework by Peter Cawley.

Things are at a pretty early stage, but the intelligence within Grace will be distributed in a roughly hierarchical manner at four broad levels:

Strategy engine
This is a high level, game-theoretic approach to the broad aspects of DEFCON. All quantities (e.g. force concentrations, areas to take/defend) are defined in terms of heatmaps.

Task Group Co-ordination
The hard part. This routine takes strategic priorities generated from the Strategy engine and converts them (probably via a simulated annealing algorithm) into specific tasks. Allocate these tasks to task groups of units. The TGC also looks at tactical issues such as targets of opportunity, checking for unhandled enemies, and checking for win-opportunities.

Task management
The tasks (e.g. "Sweep and Clear", "Territory Air Defence") allocated by the Task Group Co-ordinator are implemented as finite state machines. For example the "Sweep and Clear" task is broken down into a activity (i.e. one of the finite states) of scouting toward a defined point, an activity of being in combat, and an activity of being at the target point.

Unit management
All unit specific management goes on here. Each activity will give specific jobs to each unit in the task group. These are embodied in atoms. These embody the simplest possible actions, and wrap any calls to the API. For example the movement atom will move units but also embody the intelligence to keep a minimum distance between the units in a task group


The roadmap is (currently I'm at 0.1.1):

Grace 0.0 - "Hello world"

Grace 0.1 - Single TGs only. Hard coded Strategy and TGC behaviour. SaC TG behaviour only, at MI. Partial Fact engine implementation. Fight Activity at MI. Scout Activity at MI. Attack atom at MI. Move atom at MI. Wait atom at MI.

Grace 0.2 - Strategy engine and TGC hard coded. Multiple TGs. Fact engine running at MI. SaC running at MI.

Grace 0.3 - Add Territory Air Defense task and related activities/atoms for airbases.

Grace 0.4 - Add subs. Sub combat in Fight activity. Sub sneak and sub strike tasks. Anti-sub patrols. Movement activity.

Grace 0.5 - Add strategy engine, with simple heat map for fleet, air defense, silos and sub-strike. Add silo strike task.

Grace 0.6 - Add carriers (anti-sub only). Add coastal defense task. Add bomber strike.

Grace 0.7 - Add carrier launching to naval combat. Add coastal strike. Add coastal scout.

Grace 0.8 - Implement simple TGC. Deployment according to strategy map.

Grace 0.9 - Working TGC

Grace 1.0 - Working minimum implementation. Strategy engine and TGC working to MI standard.

Grace 1.1 - Add spawned TGs.

Grace 1.5 - Add basic belief engine.

Grace 2.0 - Learning behaviour complete.

Grace 2.5 - Task Group interaction.

Grace 3.0 - Angels and demons complete.
Last edited by smc on Sat Jul 17, 2010 10:23 am, edited 2 times in total.
User avatar
trickser
level5
level5
Posts: 1823
Joined: Thu Mar 06, 2008 2:15 pm
Location: The Senate ; GMT+1
Contact:

Postby trickser » Thu Jul 01, 2010 6:16 pm

That sounds like a plan. :wink:
Welcome and good luck with your Bot.
User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Heatmaps

Postby smc » Fri Jul 02, 2010 12:32 am

Thanks Trickser...


I expect that Grace is going to rely a lot on heatmaps. As I'm defining it, each heatmap is a 36 by 20 grid of 10 degree squares. For example here's map[land] (a box represents a 1, no-box represents a 0) which tells Grace where her fleets can't go:

Image

I haven't done a huge amount of research into what the best length of side is for the grid, but 20 degrees seemed too much and 5 degrees seemed too little. Interesting question though - what is DEFCON's 'length scale'? Perhaps I'll need to sub-divide the squares for some applications. Of course larger areas can be represented by mini-maps. So each task group could have a mini-map that defined it's shape and allowed simple proximity detection.

To give credit where it's due the idea was inspired by Chris' Subversion blog, and by some uni lectures on optical computing that I vaguely recall. But they are just _so damn useful_. For example, if you want to define a corridor around your coastline to fly bombers along on anti-sub patrol you can do it by

Code: Select all

bound_map(grow_map(map[my_territory]))


or in English... expand the map of my territory to all the surrounding squares, then select only the squares on the edge. That gives you a list of heatmap squares with centres roughly 10 degrees off your territory's boundary. Convert the centre point of each square back into (long,lat) co-ordinates and you've got the bombers flight plan.

For Africa it looks like:

Image

or if we throw in a mult_map with map[sea] like:

Image

Of course you could hard-code all these routes for each continent, but that's a pain to transfer to modded maps and (more importantly) doesn't easily allow you to do cool stuff like re-compute your bomber routes based on where enemy subs might be, where your cities/structures have already been nuked or other in-game factors.

As another example, say you want detect enemy planes over your territory...

Code: Select all

if max_map(mult_map(map[my_territory],map_add(map[enemy_fighter],map[enemy_bomber])))>some_threshold then
--launch fighters
end


... and again with a bit of tweaking of some_threshold and an added multiplication with map[my_population] and map[my_structures] Grace won't be launching at enemy fighters over Siberia when all her stuff is clustered around Moscow.

Already it seems to me that heatmaps are pretty useful for any application involving proximity detection or spatial reasoning (lost an enemy sub? diffuse_map(map[enemy_sub_old]) will estimate the probability distribution of its location for you). They won't do everything, but I expect most of Grace's high level strategy engine will be based on them, and they are already making my life easier coding some of Grace's low-level logic.
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Fri Jul 02, 2010 1:25 am

That's some fairly cool ideas you have going there.It's a little like I was vaguely planning on making some of Joshuas high level strategic planning work.

I should really get back to working on him sometime...
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Fight Activity

Postby smc » Sun Jul 04, 2010 11:50 pm

Thanks Martin, I hope you do continue working on Joshua. At some point Grace will need a playmate...



I've been thinking about how to make the Fight activity work. This will be used for task groups made up of some mixture of battleships, carriers and subs fighting some other mix of battleships, carriers and subs (though sub-only task groups might get their own set of tasks & activities by Grace 0.4).

Initially I thought about setting up a list of situations that might describe such a fight, and then rules that would drive behaviour in those situations. Things get complicated quite quickly, and there are plenty of difficult cases like having enemies approaching from multiple directions. Possibly some pattern matching might help, both for defining where the enemy is, and where friendly ships should position themselves but getting human equivalent performance at something this complicated is a huge sticky hairball of a problem.

Another approach seems to have more traction: using some form of swarm intelligence, along the lines of the Boids algorithm. Each unit follows a small set of simple rules relating to its immediate environment. This has some significant advantages:

1. It's easy(ish) to code.
2. It's conceptually easy and all the tough stuff happens as an emergent process.
3. It's efficient - each unit only needs to look at its immediate environment.
4. It can deal well with complexity (potentially at least, assuming the ground rules are well chosen).
5. It's powerful - emergent effects can do surprisingly complicated things (again potentially) - take a look at a flock of boids routing around a set of obstacles to see this.

So then... what might the rules be?

As a first stab I'm going to define a 'Centre of Mass' (CoM) for all the units in my task group, and another CoM for all the visible enemy units in the vicinity. Half way between the two you can imagine a dividing line which joins all points equidistant from the two CoMs - kind of like the boundary between the two fleets.

Battleship's movement vectors are made up of
1. Vector toward point between nearest carrier and nearest enemy ship.
2. If nearest friendly ship closer than 2 degrees vector away from it.
3. Vector toward dividing line.

and carrier vectors are made up of
1. If closer than 15 degrees to nearest enemy ship vector away from it.
2. If nearest friendly ship closer than 2 degrees vector away from it.
3. Vector toward line parallel to the dividing line through friendly CoM.

If the resultant vector is longer than some minimum (2 degree perhaps) then the ship executes a move atom toward its current position plus the resultant vector.

So far I've only coded the first rule for battleships and carriers, but there is already some surprisingly intelligent behaviour happening. For instance in the sequence below Grace has two task groups of 6*battleShips, 6*carriers 'Sweep and Clearing' towards two randomly selected points off the enemy coastline.
Image

One task group encounters an enemy fleet. This is detected by looking for an overlap between an expanded heat map of the task group's units and a heat map of enemy units:

Code: Select all

 max_map(mult_map(grow_map(grow_map(task_group_map)),enemy_unit_map))


When this returns a non-zero number the task group has an enemy in its vicinity and switches from its "Scout" activity to its "Fight" activity. The battleships switch their move point to midway between their nearest carrier and nearest enemy battleship (it's still DEFCON 4 so they don't go into attack mode). The carriers vector directly away from nearest enemy ships. The other task group is still moving towards its target off the coast of Algeria.

Image

A little later on the carriers have backed off (probably a bit too far) and the battleships have placed themselves in the line of fire, but are backing away a little to follow the carriers because they want to be halfway between the carriers and the enemy.

Image

The battleships are too clumped together, but rules #2 and #3 should fix that. I expect the rules will need a fair bit of tweaking to optimise the emergent behaviour...
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Mon Jul 05, 2010 12:31 am

The swarm intelligence is part of how I'm thinking Joshua will work. THere will be multiple levels of command AI, each one defining objects for the next one down to manipulate. For example a high level AI might define target areas to be defended by sea, a more detailed one will define patrol route objects, the next splits up forces and creates task group objects to follow different patrols, the next is individual AI of each unit to follow the task group and engage enemies etc.

I got back to coding Joshua yesterday, and promptly gave up because my defcon key has been revoked, hopefully that will be sorted soon and I can get back to work.
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
Ace Rimmer
level5
level5
Posts: 10803
Joined: Thu Dec 07, 2006 9:46 pm
Location: The Multiverse

Postby Ace Rimmer » Tue Jul 06, 2010 6:56 pm

This is all way above my head so two questions (one might have been asked already):

1. What's the ETA on Grace being playable.
2. Can we get a look at the code?
Smoke me a kipper, I'll be back for breakfast...
User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Postby smc » Fri Jul 09, 2010 1:42 am

Martin - my bot will soooo beat up your bot...

Ace - Define Playable... I expect Grace 0.6 or 0.7 will beat the CPU reliably, Grace 0.8 or 0.9 will challenge a new human player, and Grace 1.0 will challenge an intermediate human player. A wild-ass-guess suggests that I'll get though each decimal point revision in 3 weeks or so. Perhaps 1.0 by the end of the year? Maybe?

I've had a think about the code - I'll publish it starting with Grace 0.4. Between now and then I'm going to clean up some of the more shameful hacks I've used so far. That will delay things a little so 0.4 will be available around the end of July.
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Fri Jul 09, 2010 2:20 am

Not a chance ;)

That is, if Joshua ever starts playing, I do a tiny amount of coding on him, since he's the least important of my three projects :(
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Postby smc » Fri Jul 09, 2010 8:02 pm

Quick update...

After some tweaking I've come up with the rules below for battleship and carrier task groups.

Battleships
1. Move towards mid point of nearest enemy battleship and friendly carrier, or nearest enemy carrier and friendly carrier. Weight 3.
2. Move away from closest friendly ship if separation <10. Weight 6/(0.1+separation)
3. Move towards enemy Centre of Mass. Weight 1

Carriers
1. Move away from closest enemy battle ship if separation <15, closest enemy carrier if separation <20. Weight:3.
2. Move away from closest friendly ship if separation <10. Weight 6/(0.1+separation)
3. Move toward friednly centre of mass. Weight 1

I've dropped the idea of using the mass separation lines. The intention of these was to try and force Grace to adopt a human-style battleline to face the enemy fleet. After seeing an encounter between one of Grace's Task Groups and two enemy fleets coming in from different directions I changed my mind. As soon as the second fleet got into range two battleships broke off from the original combat and moved to intercept the new threat while the carriers fell back from both enemies, all driven by rule 1 for battleships and rule 1 for carriers.

More generally I think it was a mistake to try and make Grace fight like a human. Watching her take on the CPU is like nothing I've seen before in a DEFCON game. New human players and the CPU move their 6-pack fleets around in a stately way, experienced human players move large fleets in well controlled geometric formations to ease the micro-ing (I know, with the odd exception). Grace plays much more organically. Her battleships boil and seethe like angry insects and her carriers scamper away from danger like mice. Robin Baumgarten commented on similar behaviour in his thesis (section 8.6) - swarm intelligent behaviour does not look human and might violate suspension of disbelief in what is 'appropriate' behaviour for a naval task group. Grace, however, is playing to win.

Interestingly, I believe (though haven't tried) that with the rules above Grace will partially mirror what her opponent does. Against 6-pack fleets she will concentrate her battleships close to a single point, against a human style battleship wall she will spread them out in response to the multiple attractors of the various enemy battleship and friendly carrier combinations.

A couple of other observations:

The relative weighting of the rules is vital. If one weight is much larger than the others that rule dominates and the others are ignored. So if ships get too close together the inverse separation kicks the effect of Rule 2 to huge levels (the "0.1+" stops pesky Div by zero errors) and the ships drop what they are doing and head away from each other. If weights are comparable then ships will compromise their actions between the competing rules.

Rule 3 for battleships is weak and generally opposes Rule 1. - but gives some nice behaviour in some circumstances. If there are no carriers nearby (e.g. the task group is battleship only) Rule 1 will not apply and the battleships will charge the opponent fleet. If there are no enemy ships nearby but there are enemy planes the battleships will move toward the enemy planes.

It's worth considering carrier rule 1 - it means that Grace's carriers cannot be caught by enemy battleships, unless they are trapped against a coastline or in a pincer manouver.

There is more work to do on the Fight activity (adding bombers, fighter and subs for a start) but I'm going to KISS and declare it working at a minimum implementation level, which brings Grace to 0.3 status on the roadmap. Coming up next is the Territory Air Defence task for airbases. Hopefully that will allow Grace to improve her high score of -62 against the CPU...
User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Postby smc » Sun Jul 11, 2010 9:07 pm

Hi all,

Grace is at 0.3.17 - mostly I've been working on the Territory Air Defense task which controls how the airbases behave. This turned out to be a little harder than I imagined. My first model was a finite state machine which launched fighters when there were enemy planes in the vicinity and tried to resupply airbases when not. This didn't really work too well - fighters don't have the range to overfly a silo cluster to defend against attackers coming from the other side of your territory, and if all airbases launch at attackers you very quickly run out of fighters and get pwned by the next couple of enemy carriers that come along. Also there are long periods when you are constantly under attack. Some form of graduated response is needed.

What you actually want is the closest airbases launching interceptors at attacking planes while those further back resupply them with fighters. Of course they synchronously need to defend the back of your territory against simultaneous attacks (this happens quite often, even against the CPU) and keep the bombers in the air.

As an aside - Grace's bombers will spend almost no more time landed than the minimum needed to re-launch them. One of the advantages of a bot is that it can constantly micro all its units with infinite patience. As soon as DEFCON 3 hits every bomber will launch and go to where it can do the most good.

Okay then, the Territory Air Defence algorithm I'm going with for now is

1. Assess threat
2. Allocate responding airbases in order of distance from threat
3. Launch fighters from responding airbases
4. Allocate maintenance action atoms to remaining airbases
5. Launch fighters or bombers from maintenance airbases to perform maintenance atoms.

At the moment step 2 is that Grace tries to keep at least as many friendly fighters as enemy planes in her airspace. Step 4 is a random allocation of tasks. Random allocation might seem odd, but this code is running every other tick or so - if there is a useful thing that a maintenance airbase can do then a random pick will probably find it in less than a (realtime) second. I might need to tweak these to play against humans though.

Strategically the maintenance atoms are quite interesting, they are:

1. AtomAirbaseWait - does nothing. Will be useful in future to allow the strategy engine to switch airbase behaviour off.
2. AtomScoutFighter - launch a fighter at a point outside radar range that is close enough that the fighter can get there and back. Because punching a incoming bomber cluster in the nose with a fighter is just sweet.
3. AtomMusterBombers - launch bombers at a specified (long,lat) for strategically directed bomber strikes.
4. AtomEqualiseFighters - compare numbers of landed fighters to other airbases, if the difference>2 then resupply the other airbases with a fighter.
5. AtomEqualiseBombers - if another airbase has spare nukes and the airbase has bombers but no nukes, send it a bomber.
6. AtomSupplyFightersToCarriers - if the airbase is full and the nearest carrier is short of fighters and in fighter range, send it a fighter.
7. AtomSupplyBombersToCarriers - if the nearest carrier has spare nukes and the airbase has bombers but no nukes, send it a bomber.

Now the plan is that task groups with carriers in are going to be following a similar set of rules from Grace 0.7 (these airbase rules are the prototype for the more complicated carrier air-defence situation). Rules 4-7 in particular will cause a particular form of emergent behaviour (I hope). Fighters will diffuse from carriers and airbases that have many to carriers and airbases that have few or none. Nuke-less bombers will diffuse toward nukes (actually it's a bit more complicated for bombers and nukes but I'll skip over that right now). All without any planning or any difficult optimisation, it will just happen automatically. Now, this means that if Grace is attacked by a large force on one side of the continent then as she loses planes more will be sucked in from any other of her forces in range: by using low-level rules to drive tactical and logistical behaviour Grace will fight and react as a single organism.

But that's for the future, let's see some action:

Image

Grace is playing EU against S. America. Right after DEFCON 3 she starts launching bombers. There's already a fleet combat happening in the Atlantic.


Image

Main fleet combat, as Grace's carriers aren't launching any planes she's going to lose this. Meanwhile she has got all her bombers in the air (currently they are being launched at the start points for the two naval task groups, until I can code a proper coastal defence).


Image

The survivors of the fleet combat retreat away from the enemy ships. You can see both fighter scouting down into North Africa and fighter re-supply between airbases.


Image

Later on after sub attacks and a silo strike from the CPU, Grace defends against bombers intruding on her Territory Air Defence zone (indicated by the red map squares) by launching from the nearest airbase. Fighter re-supply is still happening from the other two airbases.

Coming up next before 0.4 are a bunch of utility routines to tie plane launching and landing in with the rest of Grace. I think for every process function I write to let Grace do something interesting I have to write two utility functions to make it all work...
User avatar
Schubdüse
level5
level5
Posts: 1210
Joined: Tue May 08, 2007 10:00 pm
Location: Seoul

Postby Schubdüse » Mon Jul 12, 2010 12:20 am

Just to let you know. I'm reading your stuff. I don't understand everything, but it sounds nice and scary.
Vorsprung durch Kraft - Triebwerke saugen - Präzisionsarbeit... Schubdüse.
User avatar
Ace Rimmer
level5
level5
Posts: 10803
Joined: Thu Dec 07, 2006 9:46 pm
Location: The Multiverse

Postby Ace Rimmer » Mon Jul 12, 2010 2:49 pm

It does sound great, but I can see many flaws in Grace's overall tactical/strategic ability as well as immediate handicaps being built in. I'm hoping these will be removed once real combat trials begin, but not before I can take a look at her code so I can see how I need to be doing things to get Midnight up and running enough to kick Grace's skirt. :P

Actually, I'm very glad somebody is making so much progress as it (a functioning bot) will add so much to Defcon. Two functioning bots will add to that even more. I just wish I knew how to code as well as smc does.
Smoke me a kipper, I'll be back for breakfast...
User avatar
Mogwai
level2
level2
Posts: 172
Joined: Tue Oct 28, 2008 9:48 pm
Location: Norrland

Postby Mogwai » Tue Jul 13, 2010 12:00 am

How about pooling your resources to together to create some mad Ace-Smc bastard child with 7 heads and teeth made of burning razors that eat Mogwai's for breakfast??

On topic, very nice to see another bot taking it's first steps, keep it up.
User avatar
smc
level1
level1
Posts: 21
Joined: Sun Jun 13, 2010 2:18 am

Postby smc » Tue Jul 13, 2010 12:52 am

Schubdüse - thanks

Ace - since you're a significantly better player than me I'll take your word for it, could you tell me what you think the worst 2-3 flaws are so far? And I wouldn't praise my programming skills until you've seen my code :) Grace is written procedurally, and uses a few global variables to carry data around - both frowned upon by the kool koding kidz...

Mogwai - Ace (and anyone) is welcome to use my code, and I'd happily use some of his (the structure placement stuff looks like the business) but this is a solo project for me.

Not a lot of progress tonight - have spent several hours trying to figure out why sometimes bombers were simply vanishing from airbases. Turned out to be a "feature" of either the Lua framework, the API or DEFCON itself: if you launch a bomber at a co-ordinate that has a longitude or latitude of exactly zero then (at least some of the time) it disappears into a phantom dimension, never to be seen or heard from again. There you go.

Return to “AI Bots”

Who is online

Users browsing this forum: No registered users and 1 guest