The coolest thing I’ve seen all year (AI)

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,

TS Galpin

This entry was posted in Games, Military Strategy, Strategy and tagged , , , , . Bookmark the permalink.

4 Responses to The coolest thing I’ve seen all year (AI)

  1. fapestniegd says:

    “Most interesting of all, the contain-harass-expand strategy was a completely emergent behavior.”

  2. Casey H says:

    You might get a laugh out of this- fast forward to present day, and an AI specializing in what amounts to asymmetric warfare recently won a tournament. Here’s a hilarious example of such a strategy in action:

    I’ve been thinking about how to build an AI myself, but am having trouble formulating how to create one capable of decisive action. Left to their own devices, the good ones can efficiently build an army and set up a competent defense. That said, they lack offensive capabilities outside of hit-and-run attrition tactics. Humans can consistently defeat both the Berkeley Overmind and its more evolved successors simply by taking the initiative.

    Of course, “initiative” is a rather abstract concept. How does one create a bot that knows when and where to strike?

    • Ted Galpin says:

      My though would be simply – John Boyd’s Theory on OODA Loops. If People now know how to beat the Berkley overmind – let’s be honest, all it doe is swarm with Mulalisks – You can adapt to that. The real secret sauce to that AI is the Path mapping and awareness software, plus the Valhalla tactical learning AI. The rest of it is just conventional target prioritization.

      When and where to strike is easy – recreate your pathing and situational awareness meta mapping, create prioritization of targets, maybe add some scenarios and custom maneuvers to the mix… But simply program the AI to know – build a queen , go parasite and goop priority targets in priority sectors, use sacrificial scouts to get better intel, and let the AI attack when it has adequate units to achieve the needed outcome of a maneuver against the known opponents. if you are building teams and agents, and having them work in concert as they become ready, you can do some damage if they are good enough to avoid death.

      Taking initiative is simply a matter of forcing you opponents to make more decisions faster than they are capable off. Keeps them reactive rather than proactive. Way back Sun Tzu did this by ignoring an invading Army and attacking their home land. The invaders had to quickly decide if an undefended territory was worth the loss of their own supply chain, farm land, towns and cities. They quickly turned around to chase Sun Tzu’s forces around their homeland – leaving Sun Tzu’s Kingdom in Safety.

      In Programming an AI – say Star Craft – I would take the initiative by using a combination of hit and fade attacks against multiple targets with harassment by specialty units. Teach those zerg the right distance to dig at away from detectors, and have them use area effect abilities on deffenders just to distract your opponents, time attacks from multiple squads to hit in different places at the same time, times with harassment. Keep it a constant chain of events, ambushing scouts, attacking territory, punishing soft targets and harassing hard targets, in constant succession – every ten seconds or so a new event happens, even if it is inconsequential – what you can do is simply distract and overwhelm a player or AI with more things than it can handle.

      Now if you are REALLY fast with hot keys – I pulled off similar Strategies years ago in Battle net play in a 2-3 game where on teammate bailed early, and my remaining teammate was a noob. Luckily I was playing Zerg, and was using a simple my of buried zergling scouts, buried defilers, queens and lurkers I was able to keep 3 human players reactive for an hour until they got tired and their decision making got sloppy enough that I could guide the noob to build up and counter attack……

      Ultimately lost that game after a couple hours. The other three where using Protoss mind control to have effectively 5 armies on the map and eventually just overwhelmed us by brute force. You can’t leave the map and that traps you in a video game. But If I could keep competent human players reactive for an hour just by hot keying through 3 queens, 3 defilers, while launching some fly by attacks with mutalisks and covering choke points with lurkers… My rate limiting step was the energy recharge time on the units.

      Imagine what an AI could do running at the speed of scripts….

      Now you want to get scary – consider the scale of institutional stock and investment trading on earth – most of the investment trades on the earth have been manage by AI scripts for over a decade now. While people do make the strategic decisions, the AI scripts are built to play defense in reacting to market changes, and go offensive on opportunities that pop up faster than a person can react – to the point of making / saving money in a volatile market. That’s basically what the micro traders where doing.

      Now historically speaking, a good hedge fund manager with a large enough fund, could play Napoleon with the market. He could place his resources in such a way to create a small manipulation in trades, that creates a small opportunity to take advantage off. A goo hedge manager can find a good target to pull other investors out of position and literally capitalize on it.

      Napoleon would do that by know how lines of men in an army reacted to movement of opposing soldiers. he would move his lines in such a way that it created openings in the enemies lines, which napoleon would then maneuver on and out position the enemy.

      If you know how your opponents think, how the react to what the see, you can create false situations and make them reposition their assets to your advantage.

      Knowing that the investment markets are mostly managed moment to moment to moment by AI scripts. You should be able to create a mal ware that basically manipulates the AI scripts into doing what you want. You start small, and build up assets over a matter of time using trading scripts that manipulate the institutional AI into re positioning and giving up money.

      I’m certain there is basically an algorithmic arms race of that very nature going on now. The trick is manipulating the market is very illegal, so you have to do it in ways that are small enough, spread out enough to not get caught. This is a good way to make good money easily a few $million a year if you have the skills and resources to get it going.

      Now if you don’t care about breaking the law – given say a decade or to to build up your assets, market penetration, and refine your code… You could probably tank stock markets intentionally if you say had a zombie net linked by malware making a few hundred thousand trades per second to manipulate the big boy’s AI software into reactive mode and automatically selling everything off. After 90 seconds the damage could be so great that the people making decisions would likely panic and make things worse….

      Now this is all theory. But imagine if “bad guys” thought like hacker hedge fund managers…. It’s very difficult to do, but you could build an AI to take the initiative away from the stock market, and probably end the world economy, once you consider the effects of contagion of global markets.. And you could probably attack multiple trading floors at the same time. If you Hit NYSE, London, Tokoyo in the same hour…. You could probably tank the whole system.

      Of course, I think Tom Clancy already wrote a book about that 20 years ago, so It’s not exactly an original idea. But it is doable if you hate the world that much. I’m guessing right now everyone who knows how to do that either does not have the resource to do evil, and those with the resources are motivated by greed and not getting caught.

      SO much more than what you asked for. I guess I was inspired today. Thanks!

  3. test says:

    My brother suggested I might like this website. He was once totally right.
    This submit actually made my day. You can not believe just how so much time
    I had spent for this information! Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *