reactive vs. predictive AI

[intently]

I'm guessing that they're used to approximate the effect of a 23.65 degree angle between the two points.  Since you're not using sqrt you need to account for the fact that the points won't be on the same x or y line.  The closer the points are to a 45 or 0 degree angle, the more error you'll get from your approximation.  However, "if ( max < ( min << 4 ) ) approx -= ( max * 40 );" will mitigate the worst of it.

[x4000]

I should clarify that the first is not my work in any way, shape or form -- I should have noted that from the start.  At any rate, all I did was port it to C#, which was trivial given it was already in C++.  The original source article about that method of approximation, including graphs of its accuracy, is on flipcode, and is by Rafael Baptista.

[intently]

Thanks for the pointer to the source for your distance approximations.  Looking at the geometry I think I'm right about the significance of the constants.

Another question: do you use heat maps (http://en.wikipedia.org/wiki/Heat_map)?  I know you prefer stateless AI, but heat maps can be a very handy way for storing all sorts of knowledge.  For example, you wrote about the common RTS AI failure that causes an AI player to throw limitless units through a small breach in a wall, to their inevitable doom.  A heat map that reflects recent deaths could be used to record this knowledge and then inform the pathfinder that the breach in the wall should be considered a killing field.

There are numerous other uses for heat maps with emergent AI, and I find them to be extremely powerful.  (Though not "stateless"... you'll need to record them in your save game files.)

[RCIX]

One could say there's a primitive sort of heat map already; the planet alert status. When you do something important like amass a big fleet and send it out or use a missile or something, the nearby planets get "excited" and start reinforcing a lot more.

[x4000]

Thanks for the pointer to the source for your distance approximations.  Looking at the geometry I think I'm right about the significance of the constants.

No problem, glad I could help.

Another question: do you use heat maps (http://en.wikipedia.org/wiki/Heat_map)?  I know you prefer stateless AI, but heat maps can be a very handy way for storing all sorts of knowledge.  For example, you wrote about the common RTS AI failure that causes an AI player to throw limitless units through a small breach in a wall, to their inevitable doom.  A heat map that reflects recent deaths could be used to record this knowledge and then inform the pathfinder that the breach in the wall should be considered a killing field.

There are numerous other uses for heat maps with emergent AI, and I find them to be extremely powerful.  (Though not "stateless"... you'll need to record them in your save game files.)

Nope, it remembers literally -- I mean literally -- zero about past events.  I understand the premise of heat maps, but I don't know that they are terribly a good fit for what I'm doing.  I don't know how I would integrate that into the target weighting, etc.  Often the best strategy for the AI in AI War is to plunge right into a killing field and disrupt it, create a diversion for poking through that killing field, or take out a key target that is being protected in that killing field.

Instead of heat maps, the AI does on-the-fly danger assessments in any given area -- it is pretty good at predicting if it will die in a given engagement, without past knowledge.  Of course, this is only on a given planet; when the AI goes through a wormhole, it is always doing so blindly (in a tactical sense), which means it is able to fall into traps there, etc.  The strategic AI, as RCIX points out, has different rules about reinforcements, alert status, etc, which are current-situation-analytical rather than past-event-analytical, as well.

I see the point of heat maps, and if I were coding (for instance) FPS AI, I'd do so very differently.  But in AI War, the scope and scale of the game make it so that individual ship actions have a fairly low opportunity cost for both the humans and the AI, and so the methods for creating an AI can be pretty vastly different, I think.  In other words, the AI methods that I use here would absolutely, absolutely, tank with an FPS.  The general premise is all wrong.  But for a large RTS, or any other game with a large number of agents, I think that this sort of method leads to the optimal result.

One other note about heat maps in the traditional sense: often the time between battles at a given location are so far apart that a heat map would be non-purposeful, anyway.  Players and AI ships are always moving all around.  Plus, players are able to move huge amounts of firepower around at will, and so as soon as that moves the heat map is then invalid for another reason.  You could exploit heat maps by having a huge army at wormhole, trouncing the AI so that it learns not to go there, and then moving that army away with the safe knowledge that it will be some time before the AI probes that other location again.  In order to combat that, you'd have to then have the AI making realtime danger assessments, and you're right back to the current design I have, anyway.

[intently]

Yeah, the fact that power is so mobile does reduce the potential utility of geographic-based heat maps for AI War.  Heat maps do not need to be geographical though, or even two dimensional.  Multi-dimensional heat maps can be used to track all sorts of things. 

Yes, using historical knowledge opens the AI up to being manipulated, just like any non-random strategy in Rock-Paper-Scissors.  A random RPS strategy will tie with any other strategy, random or not... but if you want to WIN instead of merely tie, you have to use a non-random strategy.  AIW obviously has several RPS-type interactions (ship types, tech development...).

But yes, it's not at all obvious that these sorts of techniques would enhance the gameplay of AIW.  Expensive power is mobile, and immobile power is cheap.  However, if you ever decided to incorporate more geographic features (planet upgrades, immobile powerful defenses, dynamic jump gates, space "terrain" effects...) they could be useful.

(As for learning "wrong things", heat maps are normally designed so that heat decays over time, "unlearning" whatever knowledge was represented, wrong or right.)

[TheWordWillSetYouFree]

I guess this way the AI only ever does strategic mistakes, and they are all based on where the warps end up on.

Maybe what is needed is a improvement on warp target selection? Use cross planet attacks to find weak spots and exploit them with warps?

[eRe4s3r]

The AI is the way it is for a reason, remember it starts with 79 worlds, and you with 1. And at Dif 7 - it can outproduce you

I am sure x4000 could make the meta and in-sector ai endlessely smarter, but then how many players could still win the game? The only way to play Player vs AI is when the ai behaves slightly dumb. If it behaved smart, you would NEVER win.

Think about this, what kind of winning chance would you have when a player would control every AI action (raids, cpr's ,alert levels and reinforcements and inner-system targets, trader actions etc.)

This tells you how smart a system with that power should be to be fun. Ie. Less smarter than a human.

[deMangler]

The AI is the way it is for a reason, remember it starts with 79 worlds, and you with 1. And at Dif 7 - it can outproduce you

I am sure x4000 could make the meta and in-sector ai endlessely smarter, but then how many players could still win the game? The only way to play Player vs AI is when the ai behaves slightly dumb. If it behaved smart, you would NEVER win.

Think about this, what kind of winning chance would you have when a player would control every AI action (raids, cpr's ,alert levels and reinforcements and inner-system targets, trader actions etc.)

This tells you how smart a system with that power should be to be fun. Ie. Less smarter than a human.

Also, from the point of view of the game that is being played....
The AI is not paying attention to the conflict. If the humans get it right, the AI is not even registering there is a conflict until it is too late.
The player is in a world where he wants to be just fighting drones and getting out of the way of trains (for example), not flagging any meta intelligences to react. If the humans start to actually fight an 'AI' that fights back, they are biomass.
I can see how, as the game development progresses there may be a place for very rare instances of 'directed intelligent' behaviour, perhaps because of an entity becoming involved that is not directly part of the AI 'hive' for some reason - either a rogue or an alien or something.
But to introduce some kind of algorithmic 'meta' element in to the AI behaviour seems like missing the point.
As an aside, I used to be involved in teaching and I was lucky enough to have some opportunities to talk to one of the worlds top consultant neurologists about emergent behaviour in neural networks - he was involved in advising a group developing specific types of emergent 'reactions' from neural networks.
One of the things I took away from those conversations was an awareness that actually, predictive algorithms are constructs to try to replicate a reactive emergent behaviour that is really just only ever going to be useful in a descriptive way, - to attempt to describe 'reactive' emergent behaviour that happen in the real world.
Even when we humans 'think' we are being predictive, the mechanism behind that is reactive and emergent. It can, however be described in predictive terms and in fact this is what we do when we experience it as predictive.
erm...... blimey, here I go again....
dM

[TheWordWillSetYouFree]

I don't really agree with your views here. Because the AI has no memory and scout intel whatsoever it will always do very badly strategic wise.
It's like playing chess while not seeing your opponent's pieces.
I strongly think that it should have some sort of plan. I am not suggesting "wave got crushed here, don't attack it again" kind of scenario but a more thoughtful one. The AI already has the capability of deciding what planets under its own control are important. So why not apply that to the human planets? If there is a human planet with say; connection to a homeworld,  spacedock, starship constructor and power plants on it then the AI should definitely consider attacking that more often. Maybe have a certain weight of that option imposed on the way that the AI chooses which planet to warp to?

[x4000]

TheWordWillSetYouFree, the thing is, if I hadn't pulled back the curtain and said "it doesn't remember stuff," then people read intent where there is none.  In fact, people do it anyway -- the forums are full of stories about things that were emergent behavior that seemed "scary smart" to players.  I'm not reinventing the AI anytime soon, so as an intellectual discussion it's interesting, but for practical purposes I'm refining what I have, not looking to majorly redefine it.  As eRe4s3r notes, too, at the moment it is balanced so that it makes enough mistakes to actually be playable -- if the AI played inhumanly perfectly, then it would seem to have too much information (and thus be "cheating") as well as being unplayable to most players.  As deMangler notes, the story fits with the gameplay mechanics, and he brings up very good points about us humans thinking that more about what we do is predictive than perhaps it is.

Even when we humans 'think' we are being predictive, the mechanism behind that is reactive and emergent. It can, however be described in predictive terms and in fact this is what we do when we experience it as predictive.

This has been a key thing I have learned in working on creating the AI for AI War, actually.  If you think about us at a cellular level, or at an atomic level, or at the level of organs and nervous systems and so forth... what are we?  We seem to be more than the sum of our parts, but from a purely empirical scientific point of view why is that?  Religious views of anyone aside, if you look at purely the mechanics of any living thing, they exhibit behaviors and certain amounts of compound intelligence that were never "programmed" into their cells.  Even plants, on a slower timescale, do all sorts of interesting things -- without a brain.  This is emergent behavior in the same way that AI War has it, and the fact that the plants have no overall plan doesn't stop them from destroying your house over time, or seeking out and populating desolate areas, or what have you.

That's the key thing: the AI in AI War is not truly random, either -- to intently's comment, this isn't just random RPS or something.  The AI has a lot of various imperatives that it acts on with individual entities (preserve myself, find and kill the best opponents, and a host of other specific goals that it might seek to achieve), and these wind up acting rather like the biological imperatives in plants or animals.  From a neurological sense, they provide enough direction that the AI winds up doing purposeful things in a quasi-random way.  Same as how plants might function, except a bit more complex perhaps.

My trouble with describing my own AI is that it's so complex that it's hard to sum up, and when some people hear things such as "it doesn't remember anything" this strikes them as a huge, huge deficit -- because, after all, memory is integral to humans, right?  How could it possibly be omitted in any viable opponent?

There has been a lot of talk over the years about "instinct," things that we know how to do implicitly.  I think that most people imagine that instincts are in some sort of meta-memory storage, or programmed into our DNA in some mystical sense, or something.  This is how you get stories about genetic memories and things of that sort, I'd wager.  But, I think there is a much simpler explanation: there is no meta-memory for instincts.  Rather, those are emergent low-level behaviors based on how our bodies are constructed.  Those are high-level behaviors in many cases, which come about completely without any form of memory, based on underlying interactions and imperatives in our bodies.

And that's how the AI in AI War works, if you want to a model to conceptualize it by: it plays by damn good instincts, but doesn't "think" in the human sense.

[Trurl]

And that's how the AI in AI War works, if you want to a model to conceptualize it by: it plays by damn good instincts, but doesn't "think" in the human sense.

I agree with everything you said, except the notion that "thinking" can't also be an emergent low level behavior based on how our nervous system is constructed. Thinking could simply be a result of neurons following simple rules and interacting with other neurons and organs of the body (e.g. the eyes (or more specifically: rods and cones)). Perhaps we could take the analogy even further and say: your AI doesn't "think" because there isn't any entity in your AI that functions like a neuron (e.g. interacts with other AI entities and maintains state via its connections to other entities and perhaps its own internal state).

As a concrete example, imagine adding a piece of data to ships that would store the ID of the last planet that ship retreated from (let's call it last_retreat_planet). Since ships retreat from planets that are too powerful for them to overcome, a rule could be added to add a small bias against going to planets stored in last_retreat_planet. Ships could also communicate with their nearest neighbors and add a small bias against going to planets stored in their neighbor's last_retreat_planet weighted on the number of neigbors with the same planet stored. The emergent behavior from this would likely be that AI fleets would avoid going into planets that were well defended in the past. Maybe you'd want to add an expiration time on the last_retreat_planet member that would clear it when it gets too old to be reliable.

Anyway, the above may not be practical, but it is certainly interesting to talk about. 

[Trurl]

I don't really agree with your views here. Because the AI has no memory and scout intel whatsoever it will always do very badly strategic wise.
It's like playing chess while not seeing your opponent's pieces.

It won't "always" do very badly. At the very least it will sometimes do the right thing by just random chance. Also, we aren't talking about something theoretical here. We are talking about an AI you can actually play against, and, at least in my experience, it does a good job of making you work for a victory, which is what really matters in any game. Who cares if the AI makes bad strategic moves, as long as it is a challenge?

Edit: Also, for the record, I think maybe the AI has become sentient and x4000 no longer knows how it really works, because I played a game recently where we had a cross planet attack that kept wiping us out. We kept reloading to a previous save and building better defenses, and the AI would then come in through some other wormhole elsewhere that had worse defenses. It really did appear that the AI had scouted our defenses and was exploiting our weaknesses. In the end we beat the cross planet attack by finding where the ships were massing and attacking them with a coordinated focused attack.

[x4000]

I agree with everything you said, except the notion that "thinking" can't also be an emergent low level behavior based on how our nervous system is constructed.

Well, actually, I didn't mean that I don't believe that -- it's entirely possible, and I think is pretty much what the neurologist noted above was referring to.  But, I suppose it is easier to conceive of the AI War in terms of instinct rather than cogent thought, at any rate -- it is not self aware.  The problem with a discussion like this is that it is so multifaceted and really delves into what people believe "to think" means, or what "intelligence" is defined as.  Working so closely with emergent AI has certainly altered my own beliefs on those points quite substantially.  It's made me watch the behaviors of pets and other animals, for example, and realize that they may be closer to us in intelligence than we like to give them credit for.  The degrees of separation between language, toolmaking, and all the sophisticated stuff, and simply existing in an animal-like state, may be somewhat lesser than humanity as a whole likes to imagine.  Who knows -- it's not my field, and it's impossible to say for sure.  But when evaluating an AI, it does raise some interesting questions.

The other ideas, about having ships individually carry a bit of memory, is an interesting one, sort of an extension of the hotspots idea making it per-agent instead of geographic in the same sense.  I'm still not sold on the idea for AI War, but it's definitely interesting to at least ponder the many different possibilities that abound.

[Trurl]

But, I suppose it is easier to conceive of the AI War in terms of instinct rather than cogent thought, at any rate -- it is not self aware.  

I don't know man. Like I mentioned above with my cross planet attack example, maybe your AI has gone beyond you and is self aware now.  Did you accidentally give the AI a way to modify its own code?  

Edit: Actually to be serious, you wouldn't have to code in self awareness, if self awareness was an emergence behavior of the system. So, in theory, your AI could become self aware without you purposefully making it that way or even knowing about it.