A History of AI Research in StarCraft | AI and Games #26

Key Takeaways

[Music] hi i'm tommy thompson and this is ai and games a series on research and applications of artificial intelligence in video games throughout my case study series i've looked at a variety of games that present real challenges to even the most state-of-the-art techniques in ai one of the most demanding game genres out there is real-time strategy or rts games my recent series on the ai of total war highlights the continued effort by series developers creative assembly to improve and expand the suite of ai systems required to craft the epic battles and nuanced diplomacy players come to expect from that franchise it's pretty good the the video series i mean i mean i'm biased now but i really think you should check it out in this video i want to take a look at another game that's arguably most synonymous with the genre blizzard's ever popular starcraft franchise i want to take a look at the challenges that starcraft presents to ai research and the significant efforts made in developing new ai techniques that adopt starcraft as a test bed perhaps more importantly i want to challenge the narrative that's quickly being established in the media of starcraft research and rts games in general contrary to how it's being reported of late ai research in the serena dates back to the turn of the century and has been a rather regular feature of the game ai academic community for quite some time now this isn't some new idea that google or facebook suddenly decided would be cool to check out so in this video i'm going to take a look at the earliest rts research why and how it all started the variety of competitions and benchmarks that are now coded into the original 1998 game and the future that awaits with the recent surge of activity behind starcraft hell it's about time but first let's take a quick overview of rts games and the challenge they present starcraft adopts many of the principal components of the real-time strategy genre with a focus on the control of territory and assets players assume command of one of three factions the human terrans the insectoid zerg or the advanced protoss as they take control of land and resources within a defined area by working through the occlusion that covers the map referred to as the fog of war players lay waste to enemy forces and fortifications in order to establish resource locations build structures and enhance their existing capabilities by updating existing assets using technology trees all of these mechanics and features ultimately influence the challenge that that game presents in more professional play it impacts the strategies that are in effect during the beginning middle and end of a match and these will shift quite dramatically in early game the real focus is establishing enemy locations and defending whilst construction is taking place with the acquisition of materials and the correct build orders shifting based on the world state this can result in more defensive behaviors or rush tactics to try and break down enemy structures or forces all of this progresses through medium to end game as players seek to construct the best army configurations for assaulting the opposing players whilst ensuring they're keeping the pressure on as they seek to advance their own tech trees it all gets pretty chaotic in the closing period of battle and any ai we seek to build to play the game has to be able to recognize numerous strategic elements at play and shift between the appropriate strategy dynamically this is why there's a lot of fuss about starcraft for ai research given the overall complexity of the problem space in computer science we researchers often seek to quantify the difficulty of problems in order to establish whether they're worth trying to solve this computational complexity theory allows for researchers to formally define whether a given problem is interesting or challenging from a scientific perspective this complexity notation models the amount of memory and resource as well as the time it will take for good solutions to be found for that problem it's been proven that classic nes and snez era of video games such as super mario brothers the legend of zelda and donkey kong country can be formally classified as non-deterministic polynomial time hard or np hard for short this means in essence that the games aren't easy and carry some level of challenge before players can begin to control and master them in the long term not just for ai players but you know humans as well meanwhile rts games are considered at minimum to be np hard but are predicted to be p space complete or in the worst case exp time meaning that it's anticipated that systems that can solve them effectively would take exponential time to do so which you know in layman's terms just means they're really [ __ ] hard okay so yeah starcraft rts research let's go back to where it all started i was straight up with you i think it started cast germaine back to 2003. metallica were going through a rough patch metroid prime was finally released in europe and terminator 3 rise of the machines was out in cinemas god i hate that movie a number of academics most notably michael bruro a professor of computer science at the university of alberta but advocating the rts games such as warcraft starcraft and age of empires with the next killer app for ai to be exploring given that there are many facets of these games that make for really interesting decision problems for a system to try and solve so with this in mind burrow and other academics began seeking to conduct research within the rts space but the problem was that video game companies were typically reluctant to provide open access to their game engines and apis back then as such conducting research in starcraft itself was not possible less significant effort was made to either replicate mod or break the original game problem is cloning or breaking a game is generally frowned upon given it can place academics and their host institution in a spot illegal bother a problem that the mario ai competition which i covered a couple of years back had to contend with this led to bureau leading the development of the open real-time strategy or orts platform a free and open source reduction of classic rts games that was designed for researchers and hobbyists to experiment in building ai controllers for a variety of in-game activities such as combat or construction this system slowly grew in scale complexity and faithfulness to classic rts games courtesy of around 30 undergraduate and grad students who slowly contributed to the project over a period of around seven years this led to a small but steady body of research in building ai controllers for rts games such as the use of classical planning an idea adopted in commercial games such as first encounter assault recon and empire total war to create intelligent build order systems to creating improved pathfinding ai and even using monte carlo methods to evaluate the effectiveness of strategic plans now this is an idea that was explored in 2005 a year or two before the rise of the monte carlo research algorithm in itself and its eventual adoption in total war room 2 wouldn't even happen until 2013. orts started running competitions back in 2006 encouraging developers to submit their own rts controllers each tournament had bots compete in multiple game types some of which are subset of the main game such as gathering resources or unit combat and flat terrain to the eventual complete rts experience with economies tech trees and fog of war in place the fourth and final tournament for orts ran in 2009. the big reason for this was that the focus was moving towards building something within starcraft itself this was thanks to the release of adam heinemann's brood war application programming interface or blappy hang on do you pronounce it blappy or blappy or nah you know what i'm just never going to utter that abbreviation aloud again the broodward api is an open source c plus framework that is designed to interact with the original starcraft it provides a full suite of tools that allows for programmers to build their own ai controllers within the game what's pretty interesting and vital to the broadboard api being useful in a research and competitive capacity is that it accurately reflects the available information that human players would have in a similar situation bridward api provides information on the overall game state the available unit types technologies and weapons as well as provide full control of build behaviors as well as individual units in addition while a unit's position and properties can be made available to your custom ai player it's only permissible if the enemy unit is not occluded by the fog of war and will be removed from the world model should it leave the player's view again this prevents ai bots from cheating and forces them to maintain their own representation of the perceived active units in the game at a given time despite this a brood war api bot could conceivably cheat given there is no limit to the number of actions they can issue to the game in a given frame as a result it was possible for strange behaviors such as walking ground units over walls and making buildings that slide around though the community of bot developers have come to adopt the api heavily enforce a code of conduct for appropriate and legal moves that can be executed by a bot in a tournament context fast forward to 2010 and with the brood war api in place academia swung away from orts to full-blown starcraft with the original competition hosted at the 2010 artificial intelligence for interactive digital entertainment conference ada as we like to call it is one of the largest game ai research conferences in the world and arguably the most prominent in the united states so it's a pretty fitting location to kick-start this new tournament the starcraft ai competition was first coordinated by ben weber a phd graduate of uc santa cruz who also collaborated with johann hagelbach and mike prouse for a small follow-up competition later that year at the ieee computational intelligence and games conference however since 2011 it's been coordinated by dave churchill a phd graduate of the university of alberta and at the time of publishing this video an assistant professor at the memorial university of newfoundland the original event was structured around four tournaments that much like orts are focused on delivering a variety of game types tournaments one and two focused on unit management and combat on flat and uneven terrain respectively tournament 3 had players explore a tech limited version of starcraft without any fog of war and a requirement that they used the protours race without any advanced units permitted lastly tournament 4 was the complete starcraft experience with fog of war enabled all factions permitted in a double elimination format for entrance with each match comprised of the best of five games the first ada tournament was a huge success with 26 entrants to the competition victory was handed to the zerg playing bot over mind built by a team of developers from the university of california its success came in rushing towards building mutualist aerial units to maintain an active defense and attack where necessary this was achieved courtesy of a refined path planning system and active memory of threat locations that could allow ground units to attack more effectively during early game the whole point of this was to destabilize enemy construction followed by then use of overlords to remove fog of war and identify when resources needed to be diverted to building anti-air defenses once mutalisks were unlocked and trained it could maintain defense of their base during any continued construction whilst also targeting the occasional enemy the mutilisks adopt a method called artificial potential fields a principle from robotics that creates a field of attractive and repulsive potential forces in an environment with valid targets considered attractive and threats to the enemy considered negative this leads to behaviors such as what you see on screen now where a hit-and-run strategy can be established by disabling any attractive forces during attack cooldowns the parameters used to dictate field strengths were tested by repeatedly running trials and test maps but despite its success could overmind have any chance at competing against human players well you see overman was actually tested by playing against and occasionally defeating berkeley phd graduate auriel vignales who was not only one of the developers behind the bot but was formerly spain's national starcraft champion while overmind is long behind him vignelles is still actively involved in starcraft ai given at the time in this video he's working over at google deep mind as part of the starcraft 2 research team the competition has subsequently continued with an increase in scale and organization with some changes made to format as churchill assumed responsibility for the competition in 2011 all bought source code had to be made public and tournaments one through three were removed from the competition due to low entry rates in the first year in addition all competition matches are now executed on a client server framework rather than the previous attempts which were conducted on two laptops meanwhile 2012's ada competition allowed for persistent storage meaning that bots could actually learn from the events that were happening in individual matches by watching replays the subsequent years saw numerous entries with three participants regularly competing for the top spot between 2011 and 2013 at both the ada and sikh conferences this is largely because overmind didn't actually participate again in the competition however this doesn't diminish the fact that the winning bot in 2011 called skynet was developed by a single person british developer andrew smith skynet was a protest bot that was reliant on an early game defensive strategy whilst periodically attacking using a zealot rush an offensive tactic to push enemies off guard by attacking with large quantities of zealot units meanwhile the airbot another protoss player that frequently scored in the top three used similar strategies to skynet this included a photon cannon rush strategy referred to as the cheese as well as heavy use of a zealot and dragoon army from mid-game air is once again a one-man team developed by florian rucho then a graduate student of the university do not and at the time of this video now an associate professor at the institution as part of the laboratory numerique do not air is an acronym for artificial intelligence using randomness with the bot reliant on the idea of having a mood system that dictates gameplay decisions moods are selected against a probability distribution for a given opponent this distribution is continually being improved as the system records how effective a given mood type is against that player this keeps enemies on their toes given the opponent can't say with any certainty how air will play against it in any two subsequent matches the final big contender is the you alberta bot submitted by the competition organizer david churchill and developed in conjunction with a number of students at the university of alberta this bot is interesting given the team switched out from playing as zerg after the 2010 competition to protoss thus cementing the dominance of protoss forces in ai competitions the reason for the switch and indeed the dominance of protoss was that the strategies using that faction are easier to build you albertabot's biggest innovations come in two distinct subsystems the boss build system and the sparcraft simulator the build order search system is a simulation for planning build orders to ensure optimal execution meanwhile spacecraft is a combat simulation module that would enable the bot to more accurately estimate the outcome of combat between two forces thus helping the bot identify when best to push and continue an attack or to retreat to base and consolidate its forces spar craft can be configured to use different search algorithms such as alpha beta pruning and the upper confidence bound and tree or uct algorithm for more information on uct check both my ai101 exploring the monte carlo tree search algorithm as well as part three of my series on the ai of total war the competition continued on with newcomers beginning to exert control in 2013 pushing skynet air and you albertabot down the rankings but it was at this time a second strand of competitions arose courtesy of the starcraft student ai competition in 2011 the student starcraft ai competition was announced a separate tournament for those interested in applying their work in starcraft ai the ssc ait as it's often abbreviated was founded by slovakian phd student mikhail certike and operated under his supervision in his current capacity a senior researcher in the games and simulations ai research group at the czech technical university in prague the tournament is aimed at being a more open event than the main starcraft ai competition with competitors ranging from hobbies to students and academic researchers as well as live streaming of both tournament and practice matches live on twitch to accommodate for this change in scope there are some changes to the format and submission procedures the tournament is reduced to one match type 1v1 melee with victory achieved should the opposing player lose all buildings their ai code crashes or the decision decision-making processes they're relying on result in some significant slowdown of in-game execution should you want to write a bot programmers can develop one in either c plus using the standard broodwar api or in java instead the java bots need to utilize one of two interfaces aimed at wrapping the core functionality the jni broodwar api or bw mirror the latter being a much easier one to pronounce whilst bought source code is required as part of submission the actual code isn't made public and is only used to run plagiarism checks against other existing works the two competitions largely exist in harmony with the likes of the ualberta bot competing in both competitions now with all these innovations in mind how far of starcraft ai players came to been able to compete against the best human players whilst the media has placed emphasis on the more recent competition matches held against human players have cropped up once or twice at the ada conference 2015 saw the top three ranking bots of the starcraft ai competition tsc moo by wigard miller triple zed cable by chris cox and overkill from xi jazu being put to task against dgm5 a pro-starcraft player from russia regarded as one of the best non-korean protoss players in the world all three bots were similarly destroyed by dgen5 with no matches won by the ai bots fast forward to late 2017 and another competition took place at xi jeong university in seoul south korea four ai competitors stepped up to the plate the mj bought from xi jong university triple said k tsc mu and lastly cherry pie developed at facebook's ai research lab their opponent seongbyong goo a high-profile professional starcraft player from south korea considered one of the best in the world it's at this point that the gulf between human and ai play becomes more readily apparent all four ai opponents were defeated within 27 minutes and the easiest victory was achieved in under four and a half so yeah now that we're up to speed let's consider some more recent developments and most notably google deepmind's interest in starcraft having successfully tackled the game of go courtesy of their alphago system and the well-documented competition against expert player lisa doll deepmind have set their sights on starcraft the ai research space the players involved and the collective interest in game ai research has changed quite drastically in the past 15 years as such what seemed like fantasy in the days of orts is now a reality with blizzard the developers of starcraft openly collaborating with google to provide an official ai api for starcraft 2. deepmind in blizzard launched the sc2le or starcraft 2 learning environment in august 2017 with fans getting a chance to try their hands at it with help from blizzard themselves at the 2017 blizzcon in november of that year over in anaheim california sc2le is a collection of exciting tools for developers and researchers that effectively provides many of the same features as the brood war api only for starcraft 2 but it also has some pretty cool new features as well this includes a complete api built for both machine learning and classic ai techniques that enables complete control of starcraft 2 using the python programming language not just controlling an ai within the game developers can start a match get observations of the current state conduct in-game actions through bot controllers and watch match replays the ability to run the game faster than regular speed which is highly useful for training machine learning players means to build and deploy custom maps within starcraft 2 7 mini games developed by deepmind to test and experiment with specific ai tasks and objectives a collection of data that represents in-game play-throughs by human players that can be used for machine learning training purposes the api is broken up into two distinct collections the raw api which is more akin to the broodward api that allows programmers to access specific information on a given frame and the main api that is largely for purposes of machine learning this api takes all information from the game and analyzes it to provide feature layers that are more accessible for a machine learning algorithm these feature layers such as height maps unit density and selected units are scraped from the same user interface that players utilize well roughly it's not 100 accurate to a human player's ui given that it renders this from a separate orthographic camera so it's like 99 the same so whilst the game is rendered in 3d the api represents a series of 2d images that are reflective of the feature layers in the current state why bother with this well those feature extractions can prove more useful for machine learning algorithms to isolate and focus on key elements they wish to control and improve this is elaborated upon in the research paper published by deepmind themself as they show how these feature layers are adopted in two convolutional neural network solutions they've tested to date the agents implemented by deepmind today run around 180 actions per minute when testing in the main game itself on the abyssal reef map it's clear there's still a long way to go given their yet to win games against the built-in starcraft 2ai this is largely to be expected given the difficulty of the challenge faced and only really beginning to look at how machine learning can crack this problem however the test games i mentioned earlier look a lot more promising with some of the strategies formulating in these instances performing reasonably well they still can't compete at human level yet but give them time and you might be surprised by what comes next [Music] starcraft continues to be a relevant and exciting problem domain for ai research and it sure seems to still be pretty popular with players themselves we can be sure to see more innovation and success for ai players and starcraft in the coming years though how long it will take for ai to successfully challenge if not defeat the best human players is difficult to ascertain hopefully having watched this video you now recognize the significant challenges that need to be overcome for ai to reach a level playing field nonetheless if and when these innovations come to light you can be sure i'll do a follow-up video to bring you up to speed assuming i'm still making the iron games content in like two months or five years or whatever but another critical point in this video that i think is equally if not more important is the dangers found in corporations becoming increasingly involved in game ai research in 2001 john laird and michael van len's publication human level ais killer application interactive computer games sought to legitimize and advocate the use of video games as means through which to challenge the state of the art in artificial intelligence at a time when it was dismissed and considered a pointless use of our time we sit here less than 20 years later as the biggest tech giants in the world be at microsoft google facebook and others are taking this very seriously and investing tremendous resources behind it we're in a new age of ai sensationalism in our media and not only do the big guys latch on to this their involvement will reframe the narrative on a given topic and obscure all existing research in this field sometimes through no fault of their own we saw this as deep mind took a crack at go and it's happening again with starcraft in some cases it's failing to acknowledge preceding research a point that deepmind got right in their papers on their c2le other times it's well it's just sensationalist [ __ ] vying for a cool headline a point that will resurface in my upcoming video on the recent surge of research both academic and corporate in moba games such as dota 2 and league of legends that's it for this video i hope you've enjoyed it and don't forget to like subscribe and click that bloody bell thing so you know when i actually post new videos are you a starcraft fan or even a creator of one of the many bots submitted to competitions get some discussion rolling down in the comments if you're interested in trying your hand at this yourself be sure to visit both the competition web pages as well as starcraftai.com which has a variety of useful links to tools tutorials and research papers on ai bots and study this video as always is only scratching the surface of what's out there so get hunting both the starcraft ai competition and the student competition can be followed on twitter and facebook via the urls on screen now and in the description plus you can even follow ai and games and my personal account on twitter as well my thanks as always to my sponsors of this series over on the crowdfunding platform patreon whose names are on screen now your support helps me to continue to produce this content without your help these videos would cease being made if you enjoyed this or any of my other videos and want to contribute head on over to patreon.com forward slash ai underscore and underscore games all right how do you go and figure out how to help you play dota 2 for some half decent footage terrible at that game see you later you