Game over, man! Reversing Video Games to Create an Unbeatable AI Player
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Subtitle |
| |
| Title of Series | ||
| Number of Parts | 93 | |
| Author | ||
| License | CC Attribution 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/36229 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Game theoryHill differential equationGraphical user interfaceoutputGoogolVideoconferencingQuicksortFamilyHacker (term)Level (video gaming)PlastikkarteInformation securityInheritance (object-oriented programming)SupremumWeb 2.0Software testingPerformance appraisalWeb applicationMultiplication signLecture/Conference
01:15
Game theoryVideo gameRight angleGreatest elementTouchscreenAdditionMultiplication signLevel (video gaming)Information securityStrategy gameVideo gameGroup actionTerm (mathematics)FamilyField (computer science)Inheritance (object-oriented programming)
02:41
Large eddy simulationGame theoryStrategy gameFrame problemDigital photographyData miningVideo gameReverse engineeringBinary codeNeuroinformatikComputer programmingQuicksortDemosceneRight angleDependent and independent variablesInformation securityDemo (music)Level (video gaming)SubsetSinc functionInformationVideoconferencingComputer animation
03:59
EmulatorState of matterGame theoryArchitectureState of matterGame theoryConnectivity (graph theory)Universe (mathematics)Virtual machineDemo (music)Level (video gaming)RobotComputer architectureEmulatorDescriptive statisticsInformationTouchscreenGame controllerRight angleDiagramProgram flowchart
05:00
Level (video gaming)Demo (music)Line (geometry)Demo (music)Level (video gaming)Multiplication signRight angleGame theoryEmulatorMoment (mathematics)JSONXMLComputer animation
05:40
Infinite conjugacy class propertyMoment (mathematics)EmulatorMultiplication signCuboidComputer animationSource code
06:20
CurvatureTime zoneGreen's functionSynchronizationLimit (category theory)Computer configurationRight angleGroup actionPhysicalismGame theoryLevel (video gaming)MereologyMoment (mathematics)Slide ruleBitFlowchartState of matterSoftware bugPoint (geometry)FreewareMoving averageComputer programmingMultiplication signQuicksortMultitier architectureProcess (computing)Order (biology)WindowInstance (computer science)Frame problemEmulatorCASE <Informatik>ExistenceData recoveryBasis <Mathematik>PredictabilityMultilaterationSoftware testingGreen's functionFigurate numberRobotMatching (graph theory)WeightTask (computing)Latent heatComputer animation
13:37
Matching (graph theory)Software bugMultiplication signRow (database)Point (geometry)Tournament (medieval)Order (biology)QuicksortProcess (computing)DemosceneCASE <Informatik>Local ringSoftware testingComputer animationLecture/Conference
14:50
Perfect group2 (number)MereologyReverse engineeringMatching (graph theory)Computer animation
15:28
Level (video gaming)Roundness (object)Matching (graph theory)BitStrategy gameSingle-precision floating-point formatFrame problemHierarchyPhysical systemMultiplication signRight angleLevel (video gaming)Computer fileSource codePoint (geometry)Range (statistics)Finite-state machineHeuristicWaveAbstractionTerm (mathematics)SequenceMenu (computing)ChainCombinational logicRobotSeries (mathematics)CausalityReverse engineeringComputer animationProgram flowchartSource code
17:29
ArchitectureEmulatorComputer-generated imageryoutputGame controllerReverse engineeringBitGame theoryBlack boxTouchscreenDialectRight angleUsabilityLatent heatWindowPointer (computer programming)Term (mathematics)Virtual machineFunctional (mathematics)Position operatorGoodness of fitOpcodeMemory managementHacker (term)Semiconductor memoryInterface (computing)1 (number)Computer hardwareSoftware testingPhysical systemVideoconferencingEntire functionMultiplication signRobotDemosceneContent (media)Level (video gaming)Instance (computer science)InformationProcess (computing)Cheat <Computerspiel>CausalityVideo game consoleData structureOnline helpCASE <Informatik>Key (cryptography)CuboidGoogolReading (process)Figurate numberOcean currentQuicksortAddress spaceConsistencyState of matterSpreadsheetEmulatorCodeComputer fileVirtualizationIntegerUniverse (mathematics)PowerPCGreatest elementBinary fileUMLDiagramProgram flowchartComputer animation
22:34
Game theoryoutputGame controllerReal-time operating systemGame theoryComputer programmingRight angleGame controlleroutputMedical imagingSingle-precision floating-point formatMultiplication signPosition operatorReal-time operating systemFinite-state machineFrame problemBitPoint (geometry)Process (computing)Loop (music)TouchscreenCausalityReal numberComputer animation
23:49
Game controlleroutputGame theoryFrame problemGame theorySoftware bugRight angle
24:36
Inheritance (object-oriented programming)Task (computing)Software bugGame theoryRight angleFrame problemComputer animation
25:17
SynchronizationState of matterGame theoryGame theoryOrder (biology)InformationBitFrame problemFunction (mathematics)Point (geometry)outputEmulatorLoop (music)BefehlsprozessorRobotRight angleMechanism designRevision controlProcess (computing)2 (number)Semiconductor memoryState of matterShared memoryView (database)CodeComputer scienceDecision theoryComputer hardwareProgrammschleifeHand fanMereologyPhysical systemCausalityReal-time operating system
27:32
outputInstance (computer science)Focus (optics)Mechanism designKeyboard shortcutFrame problemKey (cryptography)Perfect groupLibrary (computing)QuicksortWindowVirtualizationGame controlleroutputType theoryUMLDiagramProgram flowchart
28:53
CodeDataflowState of matterComputer programmingBitLogical constantProgrammer (hardware)Point (geometry)Multiplication signDiagramProgram flowchartXML
29:37
Metropolitan area networkAvatar (2009 film)Hydraulic jumpIntegrated development environmentSingle sign-onLoginCodeMultiplication signLevel (video gaming)RobotSoftware bugNeuroinformatikRight angleEntire functionMechanism designGame theoryFrame problemTerm (mathematics)State of matterComputer fileFlagSource codeEmulatorComputer animation
30:53
Frame problemPerfect groupMultiplicationSoftware bugHydraulic jumpLoop (music)Basis <Mathematik>Moment (mathematics)Hacker (term)output
31:50
Game controlleroutputGame theoryVideo game consoleState of matterCoroutineThread (computing)Software bugState of matterMemory cardBitGame controllerRight angleGame theoryProcess (computing)Frame problemoutputPatch (Unix)Graph coloringComputer filePoint (geometry)Task (computing)Video game consoleMereologyComputer hardwareOrder (biology)Sinc functionSemiconductor memoryNeuroinformatikTournament (medieval)Buffer overflowInformationCodeLaptopVirtual machineQuicksortNormal (geometry)PlastikkarteFlow separationHacker (term)CubeDiagramProgram flowchart
34:47
MereologyBitDemosceneHacker (term)Game theoryProcess (computing)Computer animationMeeting/Interview
35:23
Term (mathematics)Multiplication signInsertion lossLevel (video gaming)BitMeeting/InterviewSource code
35:59
Game theoryLine (geometry)Game theoryRight angleRobotComputer animationJSONXMLLecture/Conference
36:55
Multiplication signPerfect groupRight angleBitCASE <Informatik>Figurate numberRobotLevel (video gaming)ExistenceSoftware bugFrame problemPoint (geometry)Computer programmingVirtual machineGoogolRange (statistics)TouchscreenMoment (mathematics)DeadlockMultiplicationGame theoryDifferent (Kate Ryan album)Projective planeWindowSimilarity (geometry)AnalogyTournament (medieval)Random number generationoutputSemiconductor memoryPatch (Unix)AreaNeuroinformatikBit rateNichtlineares GleichungssystemCovering spaceMathematical optimizationStrategy gameScheduling (computing)Video game consoleEmulatorTask (computing)QuicksortParameter (computer programming)Inheritance (object-oriented programming)Game controllerLoop (music)Machine learningArtificial neural networkFirst-person shooterChatterbotSet (mathematics)TheoryCodeScripting languageLimit (category theory)Term (mathematics)Source codeUniverse (mathematics)Position operatorMereologyElectronic visual displayRandomizationChainWaveEntire functionData miningOpen sourcePlanningMobile WebPrimitive (album)Goodness of fitComa BerenicesCausalityAiry functionAbsolute valueLibrary (computing)Flow separationReal-time operating systemClosed setLecture/Conference
Transcript: English(auto-generated)
00:00
So I would like to introduce uh Dan uh Pietro uh his tag is alt 4 um he is here to talk about creating a super smash brothers melee uh AI that abuses frame perfect inputs and uh which makes things really really difficult for humans um and uh he's gonna talk to you
00:23
about how he created it and it's gonna be pretty awesome so enjoy. Cool, thanks a lot. Sup Defcon, we're gonna talk about melee today, we're gonna have some fun. So I am Dan, uh I uh am a
00:42
penetration tester at a company called Bishop Fox, um I do things there like hacking web applications, we do security evaluations for like the fortune 1000 high tech start ups, that sort of thing. Um I also have uh talked at Defcon a couple times, uh last year we uh gave this great talk about um hacking smart safes, before that I was known for something of a roller, uh I came up with a little device that um uh hijacks the google chrome cast, uh and can
01:06
play arbitrary video to that which has to this day not been fixed, um not because their google is silly, just a low level design problem. But that's not really why I'm here. If you're like me, and if you're in this room I suspect you are, it's cause you're into
01:20
video games right? Before we got into the information security field, before I got into hacking, if you talked to middle school me, I was super into video games right? That was a thing that got me into technology. And so that's always been a side thing that uh I've been interested in. Particularly uh this game, Super Smash Brothers Melee. Um Smash Brothers Melee is not like just a video game in that sense, it is also an esport. Um by
01:42
that it means that there are competitive players, in fact there are professional players. Um you can see in the bottom left hand screen here, uh those are some competitive esports teams that have professional players that do nothing but play this game, Smash Brothers Melee, for a living right? Um uh there's even more popular games and it's also known as uh one of the most technically demanding games. So it's very very
02:02
fast. You can see in the bottom right hand corner, even though that's not Melee, that's Street Fighter. Um it gives you a good example of what they call APM, actions per minute, just how fast and technical the game can be right? So in addition to like the high level strategy of what it is that you're going to do to your opponent, you also have to worry about the low level intricacies um of the game in terms of like how to
02:21
actually button mash fast enough. So it's not just that you're pressing buttons very quickly, but also with very precise timings. So um it's known as a very demanding game and has a lot of respect. It's also um a very very old game, um Melee has been out for just short of 15 years now. Um the I think it came out in November, so it would be uh 15 years in just a couple months here. Um and I am a player. So this is me, um I asked
02:44
my wife to get me uh some of the most embarrassing and socially compromising photos that she possibly could of me playing uh Smash way back in the day and I think I turned out alright. Um so uh yeah I've been playing the game basically since it came out, uh it can competitively more or less since that has been a thing. Uh and um those have been sort of
03:04
my two loves, right? Information security, this is like what I wound up doing for a career and is also a big passion of mine, as well as playing video games, so hey, why not combine them, right? So the story is I was playing, I was playing um some Melee uh something like last year with a friend of mine uh back in the uh Arizona uh Smash scene
03:22
since I'm from Phoenix and uh I talked to him afterward and said hey so like what do you think a computer could be like if you could play the game frame by frame like perfectly? Um how good do you think a computer could be? And he responded that uh the game requires too much high level strategy, too much like mind games, that there'd be no way that a computer could be really good. So of course I thought fucking
03:42
challenge accepted. So I then begun on a months long journey of binary reverse engineering and AI research and programming until eventually created um what is now SmashBot. So uh before we get into uh some live demo stuff I just want to give you a
04:00
really brief hi- uh high level architecture um description of like what SmashBot is and how it works. Um so uh there are four major components here that we're gonna discuss. Um first is the dolphin emulator, right now at least, um it works on the dolphin emulator which is uh runs uh GameCube and uh Wii games. Uh the uh game then uh
04:21
will export all the relevant game state information so all the like information about how the like universe like where characters currently are and things like that out to a separate process so we're not running we're not modifying the in game AI in any way. SmashBot is its own um AI written from the ground up running a separate machine. Uh which then does some AI magic for now um that we'll uh get into uh later, decides
04:45
what buttons to press and then presses them on a virtual controller. So importantly uh SmashBot doesn't cheat, it doesn't just like make itself invincible and it doesn't do anything that you in principle couldn't do. So it's just pressing buttons on a virtual controller and looking at the screen in much the way that you would look at it.
05:01
Alright, so before we get too far we're gonna do a live demo. So this is the time for you to come right up on stage right here and give SmashBot a try. So go ahead and line up, we're gonna do this where uh uh you can take like a... we're gonna get some...
05:20
there we go. One sec. Just restart emulator. Just set up the game. Hopefully we'll get audio. Oh is it? Oh that's ok if we don't have audio for the moment. Let me just kill
06:00
the emulator, I should've done this ahead of time. SmashBot, run, yip, doo doo doo, we're
06:23
going to turn off pause. I'm not currently getting audio but I can twiddle with that in just a moment. Ok. And we will begin here. So uh just take one stock um uh oh dear just look
06:48
right there. Yes. Uh so uh yeah I just gonna I just set it up so that you can uh uh take... so SmashBot is the Fox um as you can probably tell here. This is gonna run... ok let me
07:05
try to switch the audio then. That's alright. This is gonna get in your way. Sorry. Uh it's on headphones. Should I put it to HDMI? Should I put it to HDMI? Yeah yeah. Is it
07:20
testing? It should be playing. Yeah we'll do it afterward. There we go. Yeah. When I take focus away from the window SmashBot stops playing. So that's what you saw. Just play. So there's a couple things that SmashBot is doing right here. I'll talk to it
07:45
as the game is going. Um so uh it's gonna be uh trying to take advantage of primarily uh of the human player in two main ways. So it uh does reactions and predictions right. So reaction is the easiest way to describe how this works. Um because uh the game will uh
08:01
often require that you commit yourself to some sort of an action before you are able to get an attack out right. So you're gonna start in a forward smash attack and the very moment the very exact moment you start this attack it knows how long it's going to take and at what point the hitbox is going to come out. And so from there it can predict exactly where to go um in order to avoid it or to shield the attack right. And so
08:23
strictly right from the the uh the uh the ability to react like frame perfectly to attacks. Oh there we go. Um it's able to get quite an advantage on a human player right. Um it turns out that quite a bit of the game um depends on reaction. Uh and so uh SmashBot is able to get itself pretty far entirely on the basis of that.
08:42
However that's not good enough. Um the emulator sometimes has the trouble like lagging but it's basically good enough. The uh what is it thinking? Oh okay. I'm I'm amazed this is working at all by the way. I want to give a huge shout out to Dwango AC who gave the amazing TaskBot talk which I hope you uh get to talk to her later. This this whole
09:01
thing almost didn't happen. Yeah. So it gets you in a tech chase combo. Oh the emulator is having a hard time. Okay. Uh so this tech chase combo you see is a fox will grab Marth and throw him to the ground. And then uh from there there's only a handful of options that the human player has. Um at that point uh you can like fall to the left, fall
09:21
to the right. And no matter what you do um SmashBot can um in reaction uh figure that out right. He he can he can uh uh uh cover all the options that the human player has. So uh the other thing that SmashBot does is uh uh prediction. So he's able to look forward into the future um in the game state right. And like know the physics of the game,
09:44
know all the attack animations of the game. And then once you've committed to some action um take advantage of that into the future. Um so um depending on whether it actually comes to it one neat example of this. Um one of them is the rolling right. The very moment, the very instant that the uh opponent starts a roll. SmashBot knows precisely where he's going to end up rolling and exactly when. So he can just throw at a
10:04
grab at that exact moment. So there's no way even in principle to get out of it. Um it's a little bit more evident during the edge guarding situations uh when uh the opponent is off the stage. Where the uh flow charting of the like options the opponent has um is a bit more uh apparent there. So we're just gonna let this run until the uh time out
10:21
basically. And I can uh talk a little bit more about um the the uh the so um uh it should be noted that right now as of this moment um the one uh matchup that SmashBot knows really well is this one. Which is um Marth against Fox on FD. Um and it shows that for a specific reason right. I wanted to tackle one problem at a time. Um I believe in the engineering principle of just solving one easy problem at a time right. And then
10:43
eventually try to add support for other characters in other stages. Um so one is that Marth uh the green uh player that's currently getting beat up uh is the uh is a high tier character. So he's a very top tier character amongst uh human players. Um so you will see lots of uh competitive even professional players play that character. So it's not
11:00
simply the case that SmashBot is like beating up on some low tier character right. Um and in fact this exact uh matchup the Marth on FD matchup um is considered almost unwinnable for the Fox player um amongst high level players. So this is something that like if two human players were to be playing, Marth has a massive advantage. So you can take that as an example of like what you know is going on here. Try to get
11:27
some audio after this is finished I guess. Um so the um uh some other parts to talk about here um the the tech chase combo um is basically unavoidable. Um it is possible to kinda like slide off the stage or something like that. Um but uh it's uh very strong. So uh
11:44
almost. Um the uh oh we actually missed enough Smash. So I'm not gonna pretend to have created the world's first bug free program. Um the certainly um some instances where SmashBot would have sort of um derped off the stage or something like that. Um it's
12:01
been an iterative process. Nope. It can it knows about that. Um so um if ever you see it actually get hit um it's almost surely due to um what's called a shield stab. So you can see when Fox puts up his shield is this big blue bubble right? Um as it turns out um the way that Smash works the it only shields exactly where that blue bubble is. And
12:24
so if you're able to like hit his like foot that's kinda sticking out of the shield um that will actually land. And it's hard to predict ahead of time when that's gonna happen. Also Fox will only shield after you've done your attack. So first you have to commit to the attack and then SmashBot will put up the shield. Which means it's not
12:40
really reliable for you to try to hit it. It's basically like a random thing that will happen something like one out of a hundred times. Um where uh like SmashBot will try to shield and then it just like won't work. K. Now uh you can tell when somebody
13:01
actually knows how to play Mei like oh yeah like you can kinda do a recovery there. Um actually it was funny um for the first uh maybe like six months or something of SmashBot's existence I discovered that um the novices uh did actually better than competitive players and partly due to the fact that like they were just doing weird random things that I hadn't considered. Um whereas like all the competitive players um
13:21
like like were doing things that I had anticipated. Um or like maybe just I would never consider that I would oh eh okay emulator's having a hard time for a moment there. The um uh particularly like standing there and slashing for like the first like six months of SmashBot's existence I'm like I don't know how I'm gonna deal with that. I'm just gonna come back to it and hope that nobody does it. Um so uh to give you an idea about
13:43
just how um competitive um SmashBot's become um it has I've been bringing it out in secret to the local um Smash tournaments in the Arizona scene and um I don't wanna like name some names of people that it has beaten because that wouldn't entirely be fair but um something like the last like 50% of its matches JV5 stalks um the players
14:02
there. Which is to say that it doesn't take a single hit throughout the entire match. Um and sometimes it'll like randomly take a hit. Um basically people realize um pretty quickly that you can't just fight it, that you can't just like play it like a normal person as if it were a human being. You basically have to try to pen test it right? To try to find some bug, some corner case that it's not considering. Um and if you're able to
14:22
do that and then execute that like four times in a row in order to like take four lives then you can beat it. But that's just sort of been an iterative process over the last while um to try to find all those little bugs um and then fix them before you know bringing it out to the next thing. So um this is really the first time that I've like shown off SmashBot in any um like major way aside from kind of like in secret
14:43
showing some of my friends. Um so it's definitely good enough to uh like you know show off at this point. Though it's worth saying that there's still a lot of um work to be done. So yeah in exactly 20 seconds here we'll get back into like um how this whole thing actually works or how it began. Um the AI parts of it, the reverse engineering parts of it. Um see if we can get one hit in in seven seconds. Oh no, it's still got
15:12
you. Cool. It does. It's uh it's frame perfect start pressing. Really wants to start
15:29
the next match. I'll go and kill this. We uh I'll do um another uh round at the end uh during questions so. Okay so uh now a little bit about um the AI. About how does
15:42
SmashBot think right? How does it decide like what buttons to press? Um it's not simply just a series of heuristics. Um so the the top level has a four tiered hierarchy of goals. So at the very top level are uh like the what I just call goals right? It's the high level of like what is SmashBot trying to accomplish? What is the thing it's trying to do? So these are things like kill opponent. But it's not always kill
16:03
opponent right? Sometimes it's just like navigate the menu system cause it wants to like select its own character things like that right? Um and so the way that this works is that the the little bubbles on the right hand side that you see here are actual source code files right? These are like the C++ files um then the whole point of the file uh is to determine the next lowest strategy. So the next level is strategies. Things like bait or
16:25
sandbag. Like if our opponent just got back um from the invincibility then we might not want to attack them we just sandbag um or bait. Um try to like bait our opponent into a wrong move. And so like kill opponent might choose bait as for example as a strategy. And this basically keeps on going down and down so then alright we're trying to
16:43
like bait our opponent into a bad move we're gonna like weave in and out of their range, hope that they make an attack and then punish them when they do. And so like bait might then choose punish. We say aha like we know that this person has exactly 17 frames of lag say and so we know that we can run up and then give them an up smash in that time. And then the very last level is chains. Um chains are like uh button
17:06
combinations that smashers would recognize. Things like wave dashing or dash dancing, up smash, things like that right. So these are the lowest possible level of uh abstraction in terms of the actual like button press sequences. And so then the punish would say okay I'm exactly in range and I'm in a place where I can't up smash so
17:23
let's go ahead and do the up smash right. And then this is going to change frequently every single frame. Alright so uh let's talk a little bit about reverse engineering right. Um this is something that uh was a lot of fun because you know being a penetration tester um this is sort of up my alley. And so I uh there is an awesome uh
17:44
melee scene of hackers. Um people like uh Dan Salvato actually has been a huge help as well as some other guys there. Um there's an entire google spreadsheet that we eventually made about like uh getting this sort of information. But in terms of reverse engineering what SmashBot needs to know is it needs to be able to figure out a picture of
18:00
the universe right. It wants to be able to see the screen in the same way that you do. Um there's no hidden information in uh Smash, not in a way like poker is right. Like if I made a poker bot and said that it just plays by like reading your hand lol like that wouldn't be interesting at all right. So there's no hidden information uh to Smash, it's all just available on the screen. Um that said, uh how do we actually know where
18:20
all the pieces are? So we have to make a couple of assumptions here. Um one is that the game does have the game state information represented in some way, it has to right. It's gotta know where the current player positions are, it's gotta know where your damage is. And so rather than like parking a camera in front of the screen and trying to like visualize it that way, I knew right off the bat that would never work right. So we
18:40
want to be able to get information out of the game. The only trouble is, to the game or to the emulator, the game is a black box. So it doesn't actually have any idea of what's going on inside it, it's just a virtual machine basically right. In the same way that VMware or VirtualBox has no idea what's going on inside your like Windows VM right. It's just running op codes and present uh presenting uh virtualized
19:01
interfaces uh for hardware. So unblack boxing this black box is the reverse engineering that uh is behind Smashbox. In particular we don't actually care a whole lot about code, and more than that we care about data. So inside of the game there's going to be a couple of pieces of key data right. Things like your exact character position, XY, like what uh what character is my opponent, what stage are we
19:23
on, what damage do we have. I want to be able to take that information, figure out where it's stored in memory, and then uh ship that off to an external process. So it should be known that like when I started this almost a year ago, none of this was like worked on at all. There's a lot of trailblazing involved. So uh there's also not a great way of
19:41
doing this reverse engineering. Um there are some tools like Cheat Engine, but Cheat Engine wasn't exactly going to do what I needed it to do. I mean a lot of the in bu- uh built in debugging functionality to Dolphin, and there is quite a bit, um also wasn't quite going to do what I needed it to do. So um most of the debugging functionality is about trying to like disassemble code, and again that's not exactly what I'm looking
20:00
for. I don't necessarily care about the code, and that's a good thing because um the GameCube runs on PowerPC, um and I really didn't want to have to learn PowerPC, so um basically what we did, what I did was take memory snapshots. The GameCube is super old and only has about 24 megs of usable RAM, there are other RAM, there's like specific video memory, there's like registers, but the main system RAM behind the
20:21
console is only 24 megs. Um which means I can just write it to a file, and then inspect it manually basically. All the stuff that Cheat Engine does, um I'm just doing more or less by hand. So I had to make a fork of Dolphin, uh that every time it would take a snapshot, um would write the entire contents of RAM out to a file, and then I would just be doing VBIN diffs on the like memory instances right. And so I would put the game to a
20:43
known state, say like I'm gonna put my damage to 47 right, so I'll have 47 damage on a particular character, and then put the damage uh up to, take a snapshot, put the damage up to 98, and then just do a search to see what regions of memory have changed from 47 to 98. Great. Um and that works really really well um when the memory regions
21:04
are stable, um that tends to happen if it's like stack allocated right. Um however not all of the information is stack allocated, in some cases it's dynamic, uh so in those cases it gets a little bit more complicated. So that tends to be when there's like a struct, so all the player information, um the stuff about like actually what damage you
21:22
are, or things like what character position you are, XY character positions, um are stored in a big struct that's allocated on the heap, and so first you have to try to find where the struct is right. Um that tends to be pretty easy, um we could just look for like damages or something like that. Um and then you have to search for the memory, so suppose um that was found at a particular address. Then you just
21:40
scan the entire uh RAM again to find out is there any regions in memory that contain that address, and if so, that's probably a pointer to our struct. And now we have a stable pointer to our dynamic memory region that otherwise we'd be moving around. So this sounds sorta kinda easy, and in concept it is, in practice this one's being a total bitch, um the some data structures make no sense, it should be um uh going without
22:04
saying that uh these data structures were never meant to be read in the way that we're reading them, cause of course this is like a 15 year old console game, so why would they have made these data structures to make any sense? So sometimes there's um floats where there should be integers, cause it's clearly monotonically increasing uh uh like value,
22:21
but fuck it they gave it a float, um uh and that took like forever to figure out, or sometimes there's uh there's no consistency to whether um things are indexed at 0 or 1, it's just sorta like figured out. Um so before we go any further I want to talk a little bit about game programming, um cause if you've done some programming before, this is probably very different than what you might have experienced, so there's the concept of a
22:44
frame and a frame loop, um which is very important. So, uh on the left there you can see in real time, um Marth doing his forward smash attack, so he's just taking his sword and throwing it down super hard, and it looks super fast and in fact looks really really smooth, um when in reality that's not how it actually works. When you slow the
23:01
game way down, which you can see on the right hand side there, you can see that basically just an animated gif, and not only is it um like uh kinda choppy, but it um uh the animations are predictable, so at exactly frame 10, um on the 10th frame of the forward smash, every single time, Marth will be exactly in the same position every single time, right, so um the game is basically just a finite state machine running very very
23:24
quickly. Um so the game runs at 60 frames per second, which means a single frame lasts approximately 16.66 uh milliseconds, and so the processing looks basically like this, you start at 0, it pulls your controller input to see like what has the player pressed, it runs the game engine and produces an image on screen, and then keeps
23:43
looping, and that's more or less how the game works, also basically every 3D game works, and so what's important here is that it's not just that the game is displaying at 60 frames per second, it's that the game engine fundamentally runs at 60 frames per second, so you can use this to cause all kinds of really cool bugs, so if you are
24:02
running very very slowly right, and suppose you're somebody who's totally not Mario, and you're trying to get to some treasure, through that's past a locked door right, if you walk slowly, you might just kind of run into the door and not be able to get through it, but if you're moving super super fast, on one frame you might be here, on the very next frame you might be here, and then on the very next frame, you'll be there, right past
24:24
the door, and the game will have no idea that you ever collided with the door, right, because it never, you never touched the door, on one frame you were before it, next frame you were behind it. So this leads to some really cool bugs like this, so this is actually a task from Super Mario 64, where you can see exactly that, this is the very
24:42
beginning of the game, and Mario is going to switch, go right through what is supposed to be a locked door, just by going super super fast, so hopefully some audio is here, if not it's not critical. Yeah so basically what you saw is that you just did some little
25:08
tricky bug thing to go super fast and then just zips right through some doors, so that's important, not because we're going to be doing some like zipping through doors, but just to give you an idea of uh that the game is running with this internal frame loop, so um the game looks a little bit more like this, where inside the game
25:23
there's this looping thing that the uh emulator actually has no idea about, so the emulator is just the hardware right, it has no idea that there's this internal frame loop, that's the game's business, um and whenever it receives frames it will go ahead and output them. Um so in order to get the game state information out, now we've
25:40
figured out where the uh like bits are inside of the game right, we have to have some mechanism of exporting it out to a separate process, and so my first foray at this was really hilarious, so first uh I set up a segment of shared memory between the dolphin emulator, it was a modified version, another fork that I made of the dolphin emulator, um to uh SmashBot, so this is a shared segment of memory, there's no like
26:04
input and output, it's actually just the same memory that's shared between two processes, um so what I had to do is write some code that took the game memory um and copied out the relevant data into a struct that's in that game, so had to like move the data out into that struct, but of course I don't have um any concept of when the frame is running, cause the emulator doesn't know when the frame is running, so the
26:24
natural uh thing to do here is just make a spin loop, so we have one entire CPU doing nothing but spinning, doing absolutely nothing but copying data into that uh shared memory region, so now SmashBot has this like constantly updated real time view of all the game, relevant game state information, but it doesn't know when the frame has
26:42
processed, it has to like trigger per frame, and when a frame triggers is one of the pieces of game data, so of course I had to write a second spin loop inside of SmashBot that would regularly check that struct, um this is what computer scientists would refer to as suboptimal, um so uh eventually this um was um
27:03
integrated into the official Dolphin build, as of Dolphin 5.0 there was a new feature called uh Memory Watcher, which does this without the terrible spin loops, so um I would like super big thanks to the Dolphin guys for that. Um so now we have 3 parts of the whole running system, we've got the Dolphin emulator, we have SmashBot making
27:22
decisions, we're able to pipe that data out um over uh a named pipe basically, but it's still not playable at this point because we still can't actually press buttons, and so that was another kind of funny instance where my uh initial attempt to uh press buttons on like on a virtual controller, um Dolphin didn't have any mechanism for actually doing
27:42
that, but what it did have is the ability to type on a keyboard, so you can like map the A key to press the A button or something like that right? So I thought okay great, what I'm going to do is I'm going to write a like uh helper that uses um the Xorg uh libraries to like press the button like on the con- on the uh the keyboard, um and it actually like sorta works, it's terrible and I would not recommend
28:02
it whatsoever, um partly because if you like move your focus away, it just starts pressing buttons like into the random window, whatever you like gain focus to, and just goes haywire and it's like hard to cancel, um but also because uh basically all of these mechanisms are going to be buffered input, and so there's going to be some indeterminate amount of latency from when it presses the button to when it actually happens, and
28:24
normally you don't care about this, if you're just a human being, like pressing buttons on a keyboard, it doesn't matter to you if when you press the A button, it doesn't happen for the next 30 milliseconds, or maybe the last couple of buttons get buffered together, like you just don't care, you're just incapable of physically noticing that, but SmashBot cares, um it needs to be able to have exactly frame perfect
28:42
accuracy on all the button presses, it needs to get there super fast. So um eventually wound up getting that integrated in with Dolphin as well, so now we have a mechanism for pressing buttons. So, about programming, uh if you're anything like me, uh programming looks a little bit like this, where uh you're more or less in a constant state
29:02
of confusion, um because if you understand the problem that you're trying to, like, trying to uh program, then you just solve it pretty quickly and move on to the next problem, and so to be a programmer is to be in a constant state of confusion, interrupted only shortly by tiny bursts of like epiphany and coding things up. So if you were to walk up
29:22
to me at any point while I'm programming SmashBot, usually the Saturday morning eating some like breakfast cereal and drinking some tea, and you say hey Dan, how's it going? I have no idea what the fuck's going on. Nothing's working, nothing's working and I have no idea why. So I wanted to give you uh one cool example uh of what this looked like. So for the longest time in SmashBot's history, um up until maybe a couple
29:42
months ago, there was just this nagging bug that I had no idea how it worked. It was like the only logical explanation for it was that there was a gremlin inside of my computer pulling on wires, and so it looked something like this where like SmashBot would be totally cool and then just derp right off the stage. And I was like what is going on here? There's no reason for it to do this, I couldn't pinpoint in code why this
30:03
was happening, and it manifested itself in all kinds of ways, it wasn't just derping off the stage. So I implemented this entire debugging mechanism where um I could, you give it a dash dash debug flag, it will take the entire game state per frame and write it out to a big CSV file. Um that winds up being like megabytes large. It's actually the best thing I ever did in terms of debugging because um this lets you
30:22
retroactively walk through what happened throughout the entire game and see like oh yeah like it pressed this button when it should have pressed this button or whatever right? Um so I could see in here that sometimes, not all the time, just randomly seemingly, um I would press a button and it just wouldn't happen for a frame late. That was the source of the bug. I finally figured okay so like there's for some reason it's
30:42
pressing a button frame late. I don't know why, it was only ever one frame late and not all the time. So this is super weird, I was kind of chalking it up to a uh a dolphin bug maybe, there was some bug in the emulator. And so um I eventually uh tried out this. This is um what you're gonna see here is uh Fox doing frame perfect multi shines. Uh this is uh Smashbot not it's not just doing these blindly, it's actually
31:01
reacting. So on the exactly the third frame of the jump animation, Fox is going to hit down B to start the shine, the little flashy animation. And then jump out of it and then loop through it again. So what's important here is that he's even a single frame late on any of the inputs, he will jump accidentally. So it looks like this. So he's going along happily doing frame perfect multi shines and then start jumping. He's
31:23
going to jump, and then go right back to multi shining again. And then you start to notice that this is actually cyclical, this is like not random, this is happening um on a uh an exact like predictable basis. So he'll do it again in just a moment here. I was like that's weird. I do like it when bugs are reproducible. So eventually um
31:46
me and uh uh Dan Salvato, another awesome melee hacker, um figured out that this picture of how the game input thing uh works was not entirely accurate. And so uh what happens is that the game um input and the game engine processing are on separate
32:01
threads. And they're not perfectly synced up. And so what happens is on one frame uh it'll look like this. On the very next frame the controller input will drift by a tiny bit. And then the next frame the controller input will drift a tiny bit. Until eventually they swap. And controller input is pulled afterwards. So in the
32:21
game, it's a button, right? It's 0 right? The game pro- the game will process without having read your input. Then it'll read your input and not process it until the frame afterward. Until eventually it would drift backwards. Um so then we put together a patch, oh I should say Dan put together a patch, um for uh actually like fixing this, we moved the controller input um routine onto the same thread as the game engine
32:42
basically. So um and that way we patched, relived in memory a 15 year old bug in the game that had up to this point no one has ever noticed. So that was pretty cool. Um so some of the bits about the future as it were. Um the I wish I could have gotten this working for Defcon it's like it's like 75% working. It is uh running on live unmodified
33:03
console. So as it turns out um this uh is actually completely possible. Um and I was talking with uh uh Dwango who did the Taskbot talk right before this about how some of the parts about physically like how do you send buttons, presses over to the uh the console. But one of the more interesting stories is actually um how to get information out of
33:22
the console. So remember I want to do this on an unmodified console so I don't want to just like put some like little leads and open up a hardware, open up the game cube or something like that right? Um and so in order to do that we have to use a really fun exploit uh through the memory card port. So it turns out that um uh in uh melee you're able to give yourself a little name tag like uh what my name is that's 4
33:42
characters. And of course since it's 4 characters people name it lots of colorful things. But um if you go into the actual save file that's on the memory card port and change your name manually to be longer than 4 characters, it overflows the thing. And you can get code execution on the game. And so there's already people that have been exploiting this and
34:01
using them to make modifications to the game. Um if you've ever seen the 20XX uh hack pack or 20XX um actually no it's 20XX tournament edition is the one that uses this name tag overflow. So it's a great way of getting code execution on the game which we can then use to um grab game state information and ship it off over the uh memory card port which is then attached over USB to a laptop. That way we can get live um frame
34:24
data out of the lot like running machine. So we then put SmashBot inside of a controller that would then like be pressing buttons um and uh you would just be sort of looking like you're playing the game like normal. And you would never notice that it was uh computer playing unless you like looked closely and noticed that SmashBot the
34:40
controller was plugged into the memory card port instead of the controller port. Or probably both actually. Um so yeah before uh we start getting back to the um the end part here, I want to uh impart on you a little bit of Smash philosophy. So um being a part of any uh like uh competitive scene for sure um imbues you with a certain amount of the
35:01
philosophy from that game. And so uh I want to share this with the uh the hacker world. John, John, John, what's a John? It was like 2 AM and he was tired. John's
35:23
like John's. He'll get me on my on the days where I'm just not playing too well. John's, just John's. A lot of people don't know where the term came from, it just started, but I believe it was a guy in Texas, his name was John, and no matter what, every time he'd lose he'd have an excuse, he'd have a reason for losing. My controller wasn't working, the stage, there's a little bit of lag on the TV. I didn't sleep last night
35:42
or I don't know why I'm not commenting. It's too cold, my hands hurt. I need a warm up. Yeah. We have a like a Swedish term. Inga Jonas is pretty much no John's. He used to like using much John's back in time. My favourite one I think was uh I was playing somebody and they were like someone's touching my shoulder and I was like no John's. So yeah, no John's. And thanks a lot. And
36:18
we're hiring. We've got something along the lines of 8 minutes, so I'll go ahead and
36:27
start the game up again. If you want to line up here, I guess we'll have to do 2 lines, one for playing the game and one for questions. And uh we'll do that uh right now. Uh if you want to take questions there's a microphone right there. You're gonna have to, otherwise I will not be able to hear anything you're saying. Uh here let me set up the game
36:46
first actually. Hello? Can we see Smashbot versus Smashbot? Ah yeah so that's a question that people actually ask a lot. Um is like what would happen if Smashbot played itself or like um the right now there's just a small logistical problem with it which is just that
37:01
um it only knows uh it's it plays on player controller port 2 and it assumes its opponent is on player controller port 1 and so there's just that. But I can get that solved. But the more interesting question is like what would happen if it played itself or like what is um like truly perfect um play look like? Let's just give it 7 minutes. Here. Um so uh turns out that optimal play um I gave uh quite a bit of thought to this
37:26
um is uh really really complicated. And this is actually a good question. So in case you're sitting in the audience thinking like hey I bet I could make a like a better Smashbot that would like beat this one right? Well let me uh take you on a tour of what actual optimal play looks like right? So first off um all projectiles can be
37:41
reflected there's a 2 frame window at which point you can reflect projectiles and so all those are suboptimal. And so the uh the only way to uh like attack is to just basically walk forward. And so the fastest move in the game is shine which is um foxes down B attack and uh both uh and both um uh both foxes both bots would basically walk at each other until they're exactly within range and both use their perfect 1 frame
38:03
move at the exact same moment. They would clang off of each other not hit. Um and then it's uh a deadlock from there. At at each point both the uh optimal play for both characters is to jump and then do frame perfect multishines until the time limit runs out. When the time limit runs out the game goes into sudden death. At sudden deaths
38:22
like uh the game goes for a little while and then Bob-ombs start falling from the stage um sorta like randomly right? And so it would be possible to put your opponent in a position where they have to either run at your attack or into the Bob-omb so it would be kinda sorta random. But they're not actually random right? They just use the endgame's random number generator which is entirely predictable. So back up.
38:42
The optimal strategy is not just simply run at your opponent and shine it's to put yourself in a position where once you deadlock your opponent into that shining you know that in exactly 8 minutes from now the random number generator will be seeded such that the bombs will fall in a way such that you can put them in a
39:00
disadvantageous uh position. So before you go around thinking I'm gonna make the perfect bot, know what you're getting yourself into. Yes? Uh no and no. Uh I'm sorry I think questions at the microphone. Yeah. Have you taught him to do taunts at the most insulting times? Yeah with that uh it does do um uh taunts that was like it didn't do
39:25
taunting for the longest time it just sorta sat around um uh but now it does uh frame perfect multishines in between stocks as the like how to taunt basically. I figured that would be a pretty cool way to do it. Yeah. So you mentioned that um the beginner
39:42
players will like confuse this so how'd you get around it? Do you use machine learning or do you just keep on programming people? Yeah there is actually a separate um machine learning fork of Dolphin called Phillip I wish I had more time to talk about it here. Um that uses the Google's um TensorFlow um neural network library. Um at first it had a really hard time doing more than just kinda moving around um but it's
40:01
actually getting uh pretty cool now. Um and so one of the neat parts about Smashbots design is that those like lowest level like chains like maybe there's no need to make an AI learn how to wave dash all on its own right? Why don't we program that in as a primitive and then use um AI to kinda choose which lowest level primitive um would be best? And so that's actually like a goal of mine for the project is to do exactly
40:22
that. Um this is about as far as I've taken it like right now but it's absolutely um uh actually I should have mentioned this is an active open source project that's available on my GitHub um just github dot com slash alt f4 um or just Google for this basically and you'll find it. Yeah. Um you mentioned that with the game in the future you
40:41
had plans to have this run on an unmodified console. Yeah. Um do you anticipate that you'll be able to overcome like was it strictly on the emulator side with uh the drift problem with the controller that was causing the bug where? So it is actually a bug in the game that isn't like uh so the game is responsible for that frame loop and the
41:00
controller poll uh polling so that is actually a bug in the game. Um that said um we haven't been able to empirically verify that right? So in theory that bug should be present on console um but uh without smash base there's really very difficult there's basically no way to know without um like verifying that via uh um like maybe some task
41:22
way of doing it but smash bot would actually be the best way of uh verifying that because it is reacting in real time to the frames rather than just like having a scripted set of button presses. So. Do you anticipate that there will be some way to maybe overcome that so that you can uh have that? Oh exactly so we can code execution on the game right? So we can just modify the running game to fix the bug just patch it
41:41
live. Oh yeah. Yeah. Thank you. Hey uh first question are you coming to Super Smash Con? I'm not I actually um only discovered um that Smash Con existed um after the CFP closed. Uh that's too bad. Um so I really would have liked to have done this uh at Super Smash Con um I'm uh I'm based out of the Phoenix area so if ever you wanna like
42:02
play Smash Bot near me um if you wanna run it yourself just you know download the source code source code run it yourself um otherwise um I'll be around in the kinda Phoenix area. I'm hoping to take this out to a larger tournament sometime in the near future but I have a you know busy travel schedule with work and stuff like that so no promises. The other thing was I just wanted to say thank you so much for figuring out that bug the uh 3.5 to 5 frame thing because I actually had an idea for a
42:24
project a long time ago where I was like alright I'm gonna take a high FPS camera solder an LED to a controller and figure out the amount of input lag difference. Yeah. And. There's so many problems that happen in the analog world that like there's. Yeah. Yeah it's really difficult. This way it doesn't matter what's going on on the screen Smash Bot's reading the live bits out of memory. So the very frame that something
42:42
happens it knows about it with taking the entire analog universe of display refresh rates out of the equation. Yeah. But um it's it's so awesome that you guys figured out that bug and I was just wondering what went into it cause like I would have been like really freaking confused and I have measured. Oh I was really freaking confused. I have measured the FPS lag and you can see it it's like every like quarter
43:02
frame something like that it just takes longer and it makes no sense. Yep that is absolutely correct. So thank you. You bet. Oh. I had a couple questions um so can it be any but can it be anyone else other than Fox or does it have to be Fox? Um Smash Bot plays Fox and probably will for the indefinite future um it's clearly at this level
43:23
like at the TAS level um the best character in the game it's just faster than every other character. Um one could make an argument for Falco but I'm not so sure. I mean it is kind of an open question about what is optimal play like at the highest levels um who knows maybe like if you could play it this fast Donkey Kong is like super broken. I don't
43:40
know right? I doubt it. There's good reason to believe that Fox is the best character um and so this is my best stab at making that happen. And what about having Smash Bot play like 3 other characters at once? Simultaneously yeah so right now it only um acknowledges the existence of the fluff player 1 because I just wanted to make that work first um I suspect that that's just a losing battle like once you
44:03
actually have 3v1 at the theoretical level you just lose cause even though I can frame perfect shield stuff um there's lag after the shielding and so like uh you could just hit me after that happens. And one last question is there any possible plans for other fighting games that you would use this for? Um Smash is really the only
44:22
game that I personally play competitively like at that level. Um so not for me but um there actually are similar projects and other AIs for other games. There are Starcraft and Starcraft 2 um AI tournaments that actually happen um so there's very similar um sort of endeavors in that world. Thanks. So you said that um this uh uh bot is
44:47
supposed to be more it's you if you look at it. So my question is when I notice whenever you die it goes left and right really really fast. Yeah. Um was that on purpose? Yeah so it
45:01
does um it's just called a dash dance right it just moves moving back and forth. For the first um uh it depends on each character I think it's 7 frames or maybe 10 or 11 or something like that for a fox. Um the first when you start up running you're in a dashing animation at which point you can dash backwards very quickly. Um it's a good way of keeping mobility base. It's something that even like high level players do. But never
45:21
with that exact amount of precision and that amount of speed. Um I guess to the earlier point um Smash bot is not uh intended to um like make you feel better, it's not meant to play like a human, it's meant to play like a computer. In the same way that like an aim bot right for like a shooter does not play like a human would. Um and so we're trying to break fundamentally how the game is played at that level. So um if you're
45:44
playing like a shooter game with like team based strategy there's a lot of high level thoughts in terms of like mmm like getting your opponent to use like are you using cover getting your opponent to like move into the center stage. But if you're a computer optimal strategy is to stand in the center of the stage, spin 360 as fast as
46:00
you can and then blame people in the forehead the very moment they come out right. And so Smash bot's kind of taking advantage of that in that it's not trying to play like you do, it's trying to play like a computer does. Thank you and thank you for letting me uh try it out. Absolutely. I don't know how, is that time? Yep. Alright uh thanks a lot for
46:21
coming out.