Hi there world.
First – A warning to all you young turks out there gearing up to change the world. It will vary with circumstances, but infants are resource consuming schwerpunkts, that will make it difficult to finish any other projects (Apologies for the slow trickle of articles).
Teaser – the lead in is a little long, but the topic is recent developments in AI managed strategy.
On to the topic at hand. As a Strategy geek, growing up I spent inordinate amounts of time playing strategy games. As with many this fascination started out with Chess and Axis and Allies, but quickly moved on the the likes of Herzog Zwei, Star Control, and Star Wars: Rebellion… Leading to a long list occasionally continuing now with distractions like Sins of a Solar Empire. I learned all about resource management, maneuver and misdirection, and the limits of computer interface and computer opponents. My pipe dream for years has been an in game macro building interface that would allow me to automate repetitive tasks and coordinate complicated tasks requiring multiple commands issued simultaneously; like coordinating multi vector combined arms assault. Something nearly impossible to pull off with a mouse and keyboard, hot key, click, drag and drop interface.
I digress. The standard in real time strategy (RTS) games is Blizzard’s franchise StarCraft. Published in 1998, it’s still heavily played and the subject of multiple professional leagues (mostly in South Korea) despite it’s sequel being released last year (something I’ve avoided, my time being stretched too thin already).
StarCraft is simply the standard because it’s known as the most refined, polished, and accessible yet complex RTS game available, with arguably the best game balance. A reputation made possible by years of constant user feedback and updates to an initially best of class software.
So what? Star Craft is nothing new. Cool, but basically just a good diversion. Though many would argue that due to the sophistication of the game, it does make a good laboratory for experimenting with strategy and tactics. Personally I’ve successfully been able to use it to play with concepts like Shock & Awe, OODA Loops, using psychology against human players; and geometry and pattern recognition against AI (artificial intelligence or computer programed) opponents. One of the limits I found with the AI in StarCraft (and pretty much every other game I’ve played), is eventually, if you survive long enough, it seems like the AI reaches the end of it’s script, and basically falls asleep into a passive state. In Star Craft it only takes a few hours; even playing against 7 AI players, I know if I can last about 3 hours the AI will slow down and give me a chance to take them out one by one. In newer RTS games it may take longer, but inevitably I found in playing AI opponents, if I can set up a strong defense and economy; I can basically wait for the AI script (or scripts for multiple opponents) to run out and go passive on me (something I found by accident in Sins of A Solar Empire, this can take 30 hours, but a good defense will last if you leave the game running while you sleep and go to work). Then winning the game is easy. Now the same tends to work with human opponents, typically after hours of play they get tired and sloppy, resorting to attrition (especially late on Friday nights), and even the best players will make mistakes and give you opportunities if you can wear them down or confuse them.
Which brings me to the coolest thing I’ve seen this year. I was looking online to see if my theory on AI scripts running out was correct. During that search I unexpectedly stumbled into the Coolest Thing I’ve seen in at least a year.
Apparently the University of California Santa Cruz has a thriving AI research program in computer science; and when the StarCraft API was made available to the public in 2009, and a new opportunity was quickly recognized. You could create a stand alone AI player program that could control StarCraft through the API. In the spirit of Deep Blue and Chess AI, they decided to take AI research to the next level by organizing a StarCraft AI game competition. Chess is hard because you have to consider all moves and see the future, but the moves are limited. AI playing Poker is mostly a matter of probability. Go is harder because you have many more pieces and more moves to consider, but you can always see the whole board. In Star Craft you have to deal with all of the above, plus the fog or war (i.e. the unknown areas of the game you can’t see), resource management, and the rock paper scissors limitations of different units in battle. And you have to do all this in real time, the other players don’t have to wait to take their turn. They can keep making moves while you are still making a decision. Until now, all AI research done with RTS has been limited to buggy, open source home made games with their own host of issues. For the first time AI research has access to a reliable and refined commercially developed RTS software for research.
To quote an AI instructor at Berkley “I can literally walk down the list of concepts we cover and show you where every one of them show up in StarCraft and in our agent.”
So simply put, programing an AI to play Star Craft is not only a legitimate activity for research in computer science and artificial intelligence, but there are multiple professional leagues on different continents that can provide highly ranked players to test the AI against.
So it’s great for computer science research, and yeah, programing a computer to play a real time strategy game is fun. But what does this have to do with strategy?
AI is already here
Forces you to formalize the basics
It gives you a lab to experiment in
Lessons learned
A Culture of Innovation
My Wish List
AI is already here
As a Strategist, the concept of Artificial intelligence is a fun idea. If I program a computer correctly, can it execute strategy for me? My early lament in college was simply just to have a macro script interface for Star Craft, so I could automate repetitive and predictable tasks; like resource gathering and scouting; not to mention more easily coordinate the actions of a hundred units better. Hot keys help to speed up a mouse and keyboard interface, but it’s almost impossible to really manage a good Cannae style pincer moment clicking a mouse as fast as you can ordering a few units at a time.
But the potential is there. That type of automated strategy is already present in the stock market. You can look at price history of stocks, and where the price changes go from a relatively smooth curve of deliberate human decision changing to the saw tooth up and down of algorithm based trading is really obvious; especially to my friends that engineer industrial controls systems where you see the same phenomena. Computers react faster, and typically more decisively. They trade stocks, run industrial equipment, and keep our power, communications, and financial infrastructure running reliably, by reacting faster and taking in far more information with more precise memory than a human operator. The limit being they don’t yet think, and for the most part automated control systems, typically SCADA based, can only deal with situations they are programed for. Anything weird happens, in a hedge fund or an industrial control circuit; the computer doesn’t think, it defaults to a human operator to make the hard choices. Now when it comes to keeping the lights on and the value of my 401k, I’m glad they are not experimenting with artificial intelligence that can out perform human decision making; the price of mistakes is too high.
But in a game? A video game play tested for over a decade to be arguably the best available real time strategy environment? I though a computer playing Jeopardy was Cool, but the guys at IBM got to have all the fun. Now I have a playground for testing AI. I have a playground for testing Strategy. Best of all, I have a playground for testing AI controlled tactics and strategy. And there is a formal competition where I can compete against my peers. Makes it easy to figure out what theoretical strategic fundamentals are needed, and which aren’t. You can measure, record, replay. All the things you can’t do in the real world that makes after action analysis so much the purview of opinion and guess work as much as fact.
Forces you to formalize the basics
The military strategy community is working on ideas like 4th Generation Warfare, 5th Generation warfare, asymmetric warfare, swarming, and network centric warfare. An exercise like the StarCraft AI Competition forces the participants “back to basics” especially in terms of strategy. They couldn’t just program in tactics and maneuvers. Given the rules of the game, they had to invent decision making and management software to obtain and manage resources; i.e. the had to start with logistics. Then teach software to scout out targets, have a memory and then decide what to invest your resources in, and what resources to use against what targets.
But the point is they had to start from scratch and do everything. Formalize the computer basics of logistics and resource planning into computer algorithms; before the computer could even build an army to maneuver. Strategy doesn’t get more fundamental than that. They can’t ignore anything as details to be handled later by subordinates, there are no givens. Every behavior has to be programmed in, and when they miss something, it was readily apparent in testing as a weakness that was exploited by an opponent.
It gives you a lab to experiment in.
It gives you a laboratory to test your theories against both theoretical AI frameworks, and test against expert human players, to validate or prove the theories wrong. Once you get the fundamentals down, you can still fine tune them, test them hundreds of times quickly to see what the algorithm is missing. And as the AI gets more sophisticated, you can layer and prioritize different techniques and theories in the program, and see what works, and what doesn’t.
The academically built parametric models used for AI research and military defense planning simply are not as sophisticated or refined as the millions of man hours that have gone into StarCraft. This is a far better Sandbox than we’ve ever seen before. Powerful, sophisticated technology that’s already built and very affordable. A Strategy Theoretician’s dream come true. Now I just need to work on my programming skills.
Lessons learned
The UC Team, creators of the Berkley Overmind AI that won the first competition in 2010 has shared it’s experiences in many places online.
The learning experiences from the first competition are note worthy to the larger practice of strategy. Static scripted plans just didn’t work, they were easy to out maneuver or disrupt. Strategies had to be flexible and able to adapt. Creating “agents” or sub processes in the AI to handle different responsibilities and decision making was the next step. They had to create list of responsibilities, an org chart, and division of responsibility. And they each had to be flexible and interactive to respond to the ever changing competitive environment. Just like a modern business or army.
They gave the computer a series of schwerpunkts for different situations, and let the AI decide when to do what based on the current conditions. Just like the practice of letting middle management/ tactical commanders dictate their own tactics to achieve their objectives.
Most of the AI development was spent purely on resource planning and management.
When It came to combat strategy, they were already short on time, so they picked Zerg Mutalisks, a very versatile and affordable air unit to base their entire offense on. They programmed the Mutalisks to fly in groups, and gave them essentially a vector field that pushed them to attack targets, and push away from danger. Using several clever techniques to fine tune the vector field and teach the agent target selection resulted in an expertly executed hit and run cycling swarm that picked off the most dangerous enemies first while avoiding enemy attacks. A level of tactical control I could never pull off with my mouse.
But their offensive strategy was simple. Find the easiest to use weapon available, and figure out of to maximize it’s potential. Simple strategy executed by very refined and simple yet effective tactics. Not really different from Pepsi selling cola or WD40 selling cans of lubricant. Pick something simple and reliable, and just get really good at it. The refinement was done by programming a game that ran multiple iterations of encounters with the vector field at different settings and letting the AI experiment and use metrics to optimize the settings. Trying different settings, measuring results, and applying lessons learned (conceptually close to Six Sigma).
Target selection in the end was a simple matter of predicting return on investment (ROI) – another empirical exercise. If the cost of engaging a target outweighed the benefit, don’t attack. The trick was developing the values of different behaviors; and the trade off between tactical advantage versus strategic outcome. Once developed, the computer automatically analyzes all known targets and engages the targets that have the best strategic effect (as weighted by the values programmed in) while avoiding battles it can’t win until it has more resources to take on harder targets of value. If set up correctly, it will allow the AI to ignore unimportant targets of opportunity (red herrings) in favor of strategic targets. Again, something that is hard to manage when you only have one set of eye keeping track of hundreds of units on the map.
Path Planning. One lingering bug StarCraft has; when left to their own devices, units on the move can get stuck on walls or in corners, especially when traveling long distances. For a human player this is a small annoyance, but for an AI, it meant they had to develop their own agent to plan and control the path and movement of units. Once they had Path Planning, they combined that with the danger avoidance agent, and they could have multiple scouts constantly traveling around the battlefield, with good situational awareness given by crossing lots of terrain, but high survivability from being able to avoid known and suddenly appearing danger.
With that high level of situational awareness, the resource planner is able to adapt resource planning and prioritization based on the behavior and resources of other players. (i.e. If an opponent starts building air power, you need air defense and vice versa.)
And danger aware path planning and high situational awareness also allowed the hit and run swarms to circumvent patrols and penetrate small gaps in defenses and quickly wipe out strategic targets before opponents could respond. This level of awareness is kept in a precise database giving a more exact awareness than the limited attention and memory that forces a Human player to act on memory and instinct.
Purely by following what made sense in programming the AI for the competition; the Berkley Overmind Team developed a network centric swarm that won the competition over other strategies. Which repeats similar research done in the defense community by Rand and others. Makes you wonder if anybody on the Berkley Overmind team was aware of network centric warfare or not. I’d love to ask that question.
A Culture of Innovation
In terms of AI. The first obvious innovation is seen in the results of the competition. Many AI’s were able to utilize and defend against many of the unconventional tactics used in professional play; but also showed unexpected adaptation and decision making to unexpected situations and strategies.
Within the somewhat limited environment of StarCraft, the AI’s had managed to make decisions and successfully solve problems using a mixture of processes and procedures. Businesses would be so lucky to be so effective and efficient in their decision making. Given a clear set of rules and relationships, the computer was able to succeed in surprising ways. Or as one article put it, “Most interesting of all, the contain-harass-expand strategy was a completely emergent behavior.”
Secondly, one of the articles mentioned going forward, after the competition they will be publishing the source codes of the AI’s as part of the proceedings of the conference. The idea being that each year the competitors will be standing on the shoulders of the giants from the previous year; instead of reinventing the wheel every year you get an innovative and escalating arms race. In a few years, I’d expect to see some very sophisticated AI’s simply because each competition is building on the previous year’s work.
My Wish List
Well, first I’d love the chance to play some of these AI’s. In fact if I was one of the teams, I’d be tempted to set up a server that people could connect to and play. While there is a potential counter intelligence concern there, the amount you could learn by looking at replays would really improve your learning curve, especially if you have a learning AI playing a variety of human players.
Second, I’d love to participate in the competition somehow. But given how rusty my limited programming skills are, and how limited my time is already; I doubt I could produce a work product comparable to what dozens of university students can produce over the course of a year. But as an avid Star Craft Player and more importantly Strategy Researcher, I’d happily do pro bono consulting just to get to participate in such a cool experiment.
Ghost Tactics
Combining their hit and run behavior, threat tracking, path planning, and scouting used by Berkley’s Overmind AI gives a wonderful view of the battle space where you put your strengths precisely against the enemies weaknesses. This would make Sun Tzu proud.
It also is a variation of one of my favorites from the Strategy Bag of tricks.
In the book Conventions of War: Dread Empires Fall by Walter Jon Williams, the Author postulates a space navy tactical method co developed by 2 characters; called either the “Martinez Method” or “Ghost Tactics”. Is actually a very similar concept if a little more sophisticated than what the Berkley Overmind used. This is a mathematical technique that applies great for things like Star Craft and Naval Warfare, but more creatively could be applied to other military or even business environments, as always, the trick would be in proper application of the model.
Ghost tactics is similar to the Berkley Overmind overall effect. You track all the known positions of all the units, obstacles, etc. Create a 4D Vector field showing the areas over time of each units weapons effect and ranges, sensor effect and ranges, and use that data to generate a constantly updating Convex Hull (This makes me glad I signed up for that differential geometry elective in college). Simply put, a Convex Hull is a path showing the intersection of two different overlapping data sets (typically represented by vector fields or shapes). The idea is that you create 2 data sets. First an enemy data set showing where and when they are strong and weak. You create the same data set for all of your units.
Giving the 2 data sets knowing where and when all the safe and dangerous places are, relative to each individual unit, changing over time and as new data comes in. You create a convex hull in the computer overlapping all your strong positions with all the enemies weak positions. You prioritize them by the best and worse places to go. The Berkley Overmind basically accomplished this result in real time without resorting to complex geometry.
Now the Author Walter Jon Williams takes it a step further, suggesting you move your forces along that convex hull with a path planning algorithm that uses a chaos based function to maneuver randomly across that convex hull, so the opponent cannot predict where you will be or anticipate your strategy, beyond that you will always have your forces lined up where you have a tactical and strategic advantage. Great for attrition, but I’m not sure how you reconcile unpredictable target selection with high value target selection.
Sounds great in theory. Would be fun to try using a convex hull and chaos theory to make a highly dynamic and unpredictable AI, always wanted to see what that would look like and how well it would hold up in the real world.
Combined Arms
This is likely already on the way. Just like in the real world, the advantages given by using different weapons in a complimentary fashion will likely show up soon in the AI competition. The one I would really like to see is complimentary use of special abilities certain units have. Apparently the Second place team had Terran Workers constantly repairing units in battle, and gave that AI a competitive advantage only really overcome by old fashioned attrition.
OODA Loops
I can hear the skeptical half of the military community groaning already. But there is two applications of OODA that I would love to see in this context.
1 – The 30 second battle plan. Not sure how they do it now, but as detailed in One Bullet Away, by Nathaniel Fick; a decade ago Marine officer training taught officers to make their OODA loops faster. The idea being if you could plan and begin a battle plan, or for that matter change a battle plan in 30 seconds, you could react to a changing battle field faster than the enemy, and eventually out maneuver him. In the AI competition, ironically this would probably result in a programming exercise to optimize and tighten code for the purposes of making decisions and making analysis faster; ideally to be able to react and adapt faster than your opponents.
One possibility would be to code Ghost Tactics to compute the Convex Hull in the Graphics processor; which is specifically designed for differential geometry computation (assuming the competition server has a graphics card installed).
2 – Shock and Awe. I doubt you will demoralize an AI through fast attrition. But if you can hit an AI with different problems very quickly; you should be able to confuse it or slow down it’s decision making, may be even able to get it into decision lock, simply by giving it more problems than it can deal with. Now you’d have to be an expert in AI psychology (i.e. a Programmer) to do this properly. But it should result in some interesting effects if you can figure out how to pull it off.
Well, That’s all I have. The future is coming. If you believe the world is flat (or at least that I’m not the only person who reads outside my industry) I guarantee you people in the Defense industry are already looking to adapt the techniques from the Berkley Overmind into use of drones and C4ISR systems (I would love to use the Berkley Overmind to control say a few dozen Predator Drones on Patrol, you’d need human eyes to verify targets and give attack permission, but still at the very least would be a great way to determine path planning for scout drones, and maybe even to coordinate them on tactical offensive in a large scale conflict). Some aggressive financial types may even be able to translate those algorithms into highly adaptive and competitive day trading software somehow (they already figured out high frequency microsecond trading). When It comes the SCADA, I’ll just say I’m curious what could be done with smart SCADA, I’ve heard of several half baked failures already. But I’m a Post Modernist at heart, have to mix everything together and see what ideas I can adapt from unrelated places. I’m looking forward to seeing more good things come from the Star Craft AI Competition.
Thanks for Reading,
Your humble wishing he had more time to write and do research strategist,
Ted S Galpin
Leave a Reply