Building the AI for Athena Crisis

Oh, hello there. I'm just playing Athena Crisis on my Steam deck. Thanks so much for joining me for my talk about building the AI for Athena Crisis. I'm Christoph, and I run a small startup in Tokyo called Nakazawa Tech.

If you haven't heard about Athena Crisis before, recently at React Summit a few months ago, I did a talk that explains how the game is being built, and it's all built with JavaScript, React, and CSS. I highly recommend if you haven't seen it, to go back and watch that talk.

If we go even further back, if you have never worked with me before or if you don't know me, I used to manage the React Native and JavaScript infrastructure teams at Facebook, and I built a JustJavaScript testing framework. We do a lot of stuff at Nakazawa Tech, including building video games, but we do leadership coaching, and we can help you with your JavaScript problems, with developer velocity, productivity, or help you with whatever problems you might run into while building JavaScript-based applications. Please work with us, please reach out at nakazawa.dev.

First, before we get into building an AI for Athena Crisis, let's spend a bit of time figuring out what Athena Crisis is. I'm just here in the game in the menu, and you can see the overview page right now, and I can jump into a game from right here. And just like that, I can play the game. Not all of the attacks have sounds yet, but some of them do. But the cool thing is, once I finish my turn, let me just build a few units. When I finish my turn, the AI takes over and takes care of their turn. It does attacks, it moves, it can capture buildings, it can do everything that a player can also do. Turn off the music again.

So let's figure out how we could actually build an AI like that. The warning here is that this is a code-heavy talk. We'll be talking a lot about code, but at the same time, it'll be beginner-friendly. So please stick with me as I go through all the pieces.

So the prerequisites that I found for building an AI is that you need to have good abstractions. You need to have strong primitives, you need to know about search algorithms so you figure out where things are in the game, and you need to know about math to decide on which action to take.

So the way I approached this is that my problem was that I've never built an AI for a video game before. So I had no idea how to do it. I would read articles on the internet about how they built an AI for specific types of video games, and it just kind of didn't make sense to me because these things I feel like are really hard you hard to understand when you're just reading about that when you just watch somebody else do it. So the best way I found to build an AI is by having all these like basic abstractions in place and then just building it as if imagining what would I do if I'm playing the game.

And so the assumptions that I made is that I want to build an AI that's fast, stateless, deterministic, and composable. So I threw a lot of words at you. And the way I look at it is that I think if I'm building an AI that behaves like a human player, like the same way I'm playing, I need to have abstractions in the game that I can hand to the AI code that are basically the same as what I'm giving to a player. Of course, it's a bit different because the player sees a map, it's rendered in a browser and all that, but below that, there needs to be a level of abstractions that you can work with if you're a human or if you're an AI.

And for that, you need strong primitives, you need to have a map state, you need to have actions. And then if we go back to the assumption is that I wanted the AI to be super fast. I wanted to be stateless. So it takes one action, it doesn't have any memory, it figures out what is the next action that I can take to maximize my chances of winning. Obviously, a smarter AI would actually have a memory or would plan ahead and figure out what's the best way over the whole time of the game that I can win. But for now and for this example today, we're just going to think about how can we make a stateless AI that just does one action at a time.

In terms of making it deterministic, the thing that I care about is that there's no randomness involved. Obviously, in the real game in Athena Crisis, there's some randomness in the AI just so that it mixes things up. Because if you tell the AI, hey, go and build the unit that you think is the most useful one to build, then what you end up doing is you build the same unit every time, every turn most likely, right? So you want to have some variety in the gameplay. So you might want to add some randomness. We're not going to do that today.

And in terms of composability, it's really useful for the AI to... for all the modules to be reusable across the system. So if you're doing something for path searching, or if you're figuring out what's the unit that I should attack that brings the most value to me as a player, you should abstract those away so you can compose them in other ways. And so if we look at the Athena crisis architecture, I kind of naturally over time arrived at something where it was pretty solid base for building an AI. First off, and again, you can go back to that talk at React summit to learn more about the basic setup for Athena crisis. But everything is using immutable persistent data structures. So you have a map state, you transform it, you get a new state back. And so you're not doing imperative changes on the map or on the game state. So everything is declarative. You're just telling, here is the game state that I would like to execute. Here's the change I would like to execute on a game state, and you get back a new game state and these sort of architectures.

They also work really well in a server and client relationship because Athena crisis is going to be a game that can be played with many people across the internet. And so naturally a lot of the code is running on the server. For example, the AI that I showed you earlier was running entirely on the backend and it's not being sent to the client at all. It only tells you the behaviors that the, or the actions that the AI is taking. And in that sense, it works exactly the same as another player. Because when you're playing a game on the internet against somebody else, you don't know the decision-making process they're going through as they take actions. And the AI works the same way, except it runs on a server and tells you the decisions that it made in the end. In terms of optimistic updates, the idea is that the entire client always takes an action at the same time as the server.

And like, because there's no randomness in it, that should ideally work and then all the user experience should feel good. And then let me talk you through this actions transformers and action-response architecture, because that's the core piece that we are going to work on as we're building an AI.

So the way it works is whenever a player plays the game, they take an action. So for example, earlier, I was moving my unit around. So moving or attacking, those are actions. Then we execute them against the game state, and we get an action response back. And basically, that just confirms, okay, the player wants to move this unit from here to there. We execute that action. And if we get back an action response, it means that action actually is applicable to the game state. So for example, it validates that you can actually move that unit. It validates that you can move it to that place and whether that is all acceptable within the game's rules.

And then on a per player basis, we're computing visible actions. So I only showed you a basic game map earlier, but there's also a system called fog of war, where each unit gets a vision range and you cannot see beyond that. So there's a lot of the game state that's hidden from the player based on what your units can see. And the only place that has the full game state is the server. Right? And so, you might move a unit from, or like another player might move a unit from A to B and it goes through a few different fields, but then one of the other players can only see one of those fields. And then when you're computing visible actions, it will drop all the parts of the move that the player is not allowed to see. Then after you compute those, you get action responses for each individual player, then on the client, you animate them and then you apply them to the game state.

Let me walk you through the code here, actually. So as I showed you earlier, there's an attack unit action. If you execute it, you might get back an attack unit action response. And then this is compressed into a tuple where it just strips away all the overhead from having objects when you're sending it over the network. There's a code generator that generates these action encoders and decoders for all of the actions in the game. So it's all automatic. And this is what executing an action looks like. So for example, for attacking a unit, you receive the map data structure. You fetch the units from that structure. You ensure that when you're attacking one unit to another, you ensure that they're not the same player and they're not on the same team. So you're ensuring that they're an opponent. You ensure that the unit that is attacking can actually execute an attack and it's not completed yet.

And then you do a bunch of damage calculation. And then you return the stats for the new units. And then when you're looking for, when you have fog of war, you have to, as I said, compute whether those actions are visible or not. So there's a definition that I use, basically it says if both of the fields are visible, then you can receive the regular attack unit action response. If only the source, only the unit, that is attacking is visible, then it transforms that action response into a hidden target attack unit. And if only the target is visible, it transforms that into a hidden source attack unit. Those are obviously flipped around, because if only the target is visible, then the source of the attack is visible. So it's a hidden source attack. And then later on, there's a bunch of animations involved here. I'm not going to show that today because it's not relevant for building the AI, but we're applying those action responses. So we look at all the action responses and if it's attacking a unit, we receive all the new unit data. We fetch the existing units and then depending on the state, we update the unit with the new unit data. Everything here is immutable. And I found that this architecture works really well for building an AI. Here's a quick example. I'm just moving and attacking the pink tank here. So first off, we apply the action response from this position up here and move it onto the bridge and then we're using that unit that's on the bridge to attack the unit that's next to it. And so that's kind of how the architecture works. So all we need really if we're building an AI is to generate a bunch of these actions that are valid for the current game state. This simplifies the project problem quite significantly. Because imagine, you don't have an abstraction like this where you're applying actions to a game state and for each player action, you're kind of like manually modifying the game state. You say, OK, attack, and then you just go in and you have imperative code that changes everything in one place. And then if you're trying to build an AI, you have to either copy that all to your AI and then you have problems. But also, it provides this common abstraction layer where you don't give the AI access to do any things like cheating. If you're making an attack or executing an attack with this sort of abstraction, the AI cannot have an attack that's twice as effective or something like that if that's not also allowed for the player to have. Of course, you might want to have a system like that. But in a game like Athena Crisis, you want all of the players to play by the same rules. Finally, let's implement AI behaviors. We do that by just outlining the most basic behavior that the AI could have. We're going to put together a small class.

You don't have to use classes here, but it's a little bit easier. The first version of our AI can only do one thing. When the AI starts its turn, it ends the turn. And that's a really good way to make sure that the AI stops playing, because otherwise you deadlock the game pretty quickly. In this case, we're just going to add a single action that is called End Turn. We're executing the End Turn action on the game state. And we're going to add a helper here that's going to be useful for later. Basically, we're adding this method, act. If we execute an action here, it adds it to this array of responses, and we can fetch those later and send it to the player. And then, the interesting thing here, we'll use this function called action to chain all of our AI behaviors together. And once this function returns null, it means the AI is done. In this case, when the AI is executing an End Turn, we will just return null. And this is how we could use this AI. So, we just instantiate a new instance, and then while the current player is a bot, we just action on the map and then replace, the important thing is, also, we have to replace the map with the new game state. And then, at the end, we receive all the responses and we can stream those to the client. So, in this case, it would just return an End Turn action response and then send it to the player. As you can see here, the game is just looping. Any time I'm ending my turn, the AI is ending theirs. So, now, how do we add a move? So, for example, we looked at this action function earlier. So, now, the way we're extending this is that, first off, we're always going to try to move a unit. And if there's no more unit that we can move, so this function returns null, then we'll end the turn. And so, the way we can implement a move function is through a bunch of different helper functions. So, first off, we'll just get the first unit that's available that we can move. So, assume there's, like a helper function here that, like, allows us to extract that. And then how would a human play, right? And this is kind of how I thought about how I would play. It's like I'm going to look at what's interesting on the map, like, you know, based on the current situation, based on this unit, based on the map state, where does it make the most sense for that unit to go? Once I have this list of positions, I figure out, what are the clusters of where I need to go? I'll get into details on that later. But basically, I might have, like, a hundred interesting positions, but I need to figure out where to actually go. And so, the way this cluster function works is it will take all those positions and reduce them into a smaller amount of clusters where it makes more sense to look into where to actually go. And then based on those, we look at, you know, which target should we actually go to. So, if you look at this as, like, you know, we might have a lot of positions.

We only have, like, a few clusters. And then we'll only find one target. And then if we have a location to go to, we'll execute a move action. Otherwise, and this is where it gets really important, we'll execute a complete action. So, the important thing here is that each of these functions always needs to return an action. Or sorry. It always needs to mutate the game state. So, either the unit is going to move or it's going to complete, which means it won't take any other actions.

Because the problem you run into, otherwise, if you run this action function in a loop, it will enter the move function and then always try to recompute all of this, only to realize there's nowhere to go. So, you always need to make sure every one of these functions, when there's no more actions to take, they return null or they mutate the game state so that you can go back into that function to move the next unit. So, ideally, as you execute game actions here, the number of available units trends down to zero so that you can enter the endTurn function here.

All right, now, let's figure out this whole thing about how to actually move. There's a very common algorithm. There's many algorithms to search about, search on a 2d grid about where you're going. I landed on A star, it works really well for this type of game. And the one thing here is that you're basically doing depth-first search on a 2d grid to figure out where you should go and you're trying to do that in the fastest possible way with the lowest amount of cost. If we just look at the game map, this unit cannot go into the mountains and it costs more to go into the forest than staying on the street. So, we're trying to optimize how do we get from this green tile, from this unit to over here. In this case, there's only one path, right? But we still need to figure out, okay, is this the way to go or should we go through the river. But you know, this unit can't go through the river, so once you do this sort of path searching, you kind of have walls or you have a higher movement cost than certain tiles. And then once you have this radius and this ability to figure out where can this unit go, then we can figure out, okay, what are the interesting positions on a map and then figure out if the unit can actually travel there.

This is obviously a simplified version of it, but here's like three things that you could look at. The actual implementation in Athena Crisis is like a couple hundred lines, depending on the state of the game and the unit that you're asking about what to do. So, for example, units can capture buildings, units can attack others, units can supply other units with fuel and ammo. So, for example, you might have a system here where a unit that can supply others will think that other units if they're low on ammo, right? Or in this case, if the unit doesn't have an attack or it's out of ammo, it is in danger. So, if it's at the front lines, it will actually think the interesting locations are the buildings back at where my bases are. And through that, if we feed that into the system that I outlined, that unit will try to retreat. And here, for example, if the unit has the ability to capture other buildings, then the most interesting place to go to is other buildings that are owned by the opponent. And finally, if the unit has regular attacks, most likely it will find other units interesting to go to, like opposing units to go to.

And so, now let's think about this whole thing with clusters.

So, on the left side, we have the whole map, right? And so, you have the yellow units here and you have the pink units there. So, once we get the interesting positions for this unit to go to, the map will look like this to the AI. It will be like, okay, I think there's a pink one here and a pink unit there. Which one shall I actually go to?

And there's a really useful function. This is one of the few times where I'm happy to use a third party library because it's a bunch of math that's simplified by just pushing it down into another library. Basically, you might have 100 points on the map. In this case, I know we only have two. So, this is a very simple example. But we're just using a K-means algorithm and there's an NPM package called sk-means that's pretty fast where we can feed a bunch of positions and then tell it, here's which algorithm to use and how many iterations you should take and how many locations or clusters you should return at most, and then it will reduce those and group them based on how interesting they are. And then, finally, we'll just feed those clusters into a function called find path to targets where we're actually just going to look at, okay, this unit can only move from one place to one other place in this turn. So, let's just find the closest target.

And then we can just, maybe in this case, use the distance on the grid. But the actual implementation, the way it works is it will actually look at the movement radius, because you might actually have a unit that's really close to another one, but there's a mountain in between, so it cannot access that unit. So you need to actually look at the radius, the movement radius for that unit to see which one is the easiest to get to. And then once we know what's the closest unit, we'll figure out how do we actually get there. And then try to position the unit just next to the target. So in this case, target.parent, this function returns a list of paths where each... sorry, a list of fields and where each field has a parent, so you can navigate it. And we cannot move the unit on top of another one, so we have to move it to the parent of that unit. And then finally, we can piece it all together and our unit moves to the bridge. As I said, we're looking for the interesting positions, reduce those two clusters, figure out a path to one target, and then we execute a move action. Once we're done with the move action, we're ending the turn. All right, and then the other thing that I wanna show is how to build an attack. So right now all we do is the unit is moving, but how do we add attacks? And it's all actually very similar to moving. So how about every time when the AI starts, we first look at attacks. If there are no attacks to do, to take, then we move to interesting places, and then finally we end the turn. So the way I've implemented this is I just at every point of the game, I look at what's the best attack that has the best outcome for the current player. And if there is an attack available, then we just make sure that either we have to move there. And if we do, if the distance is greater than one, then we first move closer to that unit, and then we attack that unit. Okay, so how do we actually figure out what's the best attack? Here's a basic implementation for figuring out the best attack.

First off, we look at all of the units that the player has. And then we figure out, okay, earlier I showed you the A star algorithm, and we can extend that to not just give you the movement radius, but also the attack radius, which is usually the movement radius, plus one field on each side, something like that. And then for each unit that that other unit can attack, we figure out what's the likely damage that we can do, and then we assign a weight to it. And, you know, just stick with me for a moment, we just assume that the maximum damage has the highest weight. And then we push that into a list of possible attacks. And then we just return the one that has the highest weight. In this case, the highest damage. But it might not be ideal to just always think about doing the largest amount of damage. So you want to actually introduce weights. And so in this case, depending on the game state, it might be more valuable to attack certain units in a certain state than it is to attack other units. So for example, if you're defeating that unit, it is much more important to actually execute on that action than if you're just reducing its health by a little bit. And this is a slightly more complex calculation because what I found is that you don't want to have the maximum kind of damage to a unit that's already damaged. You actually want to find the unit that can do the least amount of damage to a certain unit to take it off the field because that reserves other stronger units to do stronger attacks on other units later. And another thing that I found is that, you want to skip very low damage actions because you might just have a unit that runs into another unit, does no damage at all but then the counter attack is so strong that that unit gets taken off the field. So you might want to prevent that too. And then it gets much more interesting here on this side also says, okay, what if there's a building here and then there's an opposing unit on that field and that unit is trying to take over your building that is probably much more important than taking out a random unit that's completely somewhere else on the field. And then, there's a bunch of cases where, if this unit is transporting other units or if the building in question is the... If the building where that unit is at is your own headquarters, you're most likely to lose. So we'll prioritize that. Or in some cases, some units have the ability to attack and others only have other special abilities. Most of the time, it's more important to attack those units. And then, we piece that all together and then, we'll see how our unit is moving and attacking that other unit. All right.

So I showed you how to add an AI to a video game, how to move it, how to execute attacks. What would be next? So first off, you'll want to support all the unit and building capabilities that the game has, so that the AI has the same capabilities as a human player. We haven't thought about Fog of War at all in this AI. We actually have to make sure that the AI doesn't get information that the player doesn't also have. So we need to remove all the information that is not visible to the AI.

One thing that I found to be really fun that I thought was going to be really hard, but then turned out to be relatively easy is to add customizable AI behaviors. You can make an AI more aggressive or defensive or passive, or you can adapt its style depending on the game state, when it gets attacked, it will change from defensive to aggressive, something like that. If you have been following this and you're interested in building an AI, I highly recommend you to build your first version and then think about, okay, how do I make it defensive or how do I make it more aggressive? It's really fun to tinker with that and to see what kind of outcomes it has to adjust the small weight of prioritizing one thing over another.

Finally, as I said in the beginning, we just want this AI to be fast and stateless and composable and it doesn't do any sort of planning. It doesn't look back. It doesn't have a memory. It doesn't think ahead five turns of, here's the smartest move I could make now that will set me up for success later. Real AIs in video games most likely do some sort of optimization to predict what's gonna happen in the future. They plan what's the best action, not just now, but also if we think down, depending on how the game might evolve. The problem with that is that it tends to become really slow because the AI has to think really hard. Like what if I'm moving this way and then the opposing player has five options and they might take one of those five, which then generates seven options for me and then you kind of have this explosion in terms of decision-making. So it becomes really slow. But I hope that this overview was useful to you if you've never built an AI from scratch to just figure out like, okay, this is kind of how you build an AI for a 2D turn-based video game. Now, the next step could be, how do you build an AI for a real-time strategy game that's maybe also built on a grid or something like that?

One more thing I wanted to share is that this entire talk was designed with React and MDX. I built a system called reMDX that you can use to make slide decks and you can find the source for this entire presentation on GitHub as well. And again, I'm working at Nakazawa Tech, a small startup in Tokyo. If you'd like to work with us, please reach out.