PCGRL: Procedural Content Generation via Reinforcement Learning (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper rl reinforcement learning level design game design video game sobokan sokoban zelda maze agent turtle observation reward action space deep rl deep reinforcement learning content minecraft
#ai #research #gaming

Deep RL is usually used to solve games, but this paper turns the process on its head and applies RL to game level creation. Compared to traditional approaches, it frames level design as a sequential decision making progress and ends up with a fast and diverse level generator.

OUTLINE:
0:00 - Intro & Overview
1:30 - Level Design via Reinforcement Learning
3:00 - Reinforcement Learning
4:45 - Observation Space
5:40 - Action Space
15:40 - Change Percentage Limit
20:50 - Quantitative Results
22:10 - Conclusion & Outlook

Paper: https://arxiv.org/abs/2001.09212
Code: https://github.com/amidos2006/gym-pcgrl

Abstract:
We investigate how reinforcement learning can be used to train level-designing agents. This represents a new approach to procedural content generation in games, where level design is framed as a game, and the content generator itself is learned. By seeing the design problem as a sequential task, we can use reinforcement learning to learn how to take the next action so that the expected final level quality is maximized. This approach can be used when few or no examples exist to train from, and the trained generator is very fast. We investigate three different ways of transforming two-dimensional level design problems into Markov decision processes and apply these to three game environments.

Authors: Ahmed Khalifa, Philip Bontrager, Sam Earle, Julian Togelius

ERRATA:
- The reward is given after each step.

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there! Have you ever wondered how video game levels are made? Yeah, me neither, but this paper has. And in this paper you can see a reinforcement learning agent that has learned how to make video game levels in various ways. So this is implemented for this game here where the goal is simply to make the longest maze. This game here is an adaptation to The Legend of Zelda where you have to get a key to the door. And this game here is called Sobocon where you have to put all of the crates onto the green squares in order to solve it. So it's a puzzle game. Alright, and this is done via reinforcement learning. So the paper we're going to look at is called PCGRL Procedural Content Generation Via Reinforcement Learning by Ahmed Khalifa, Philippe Bontrager, Sam Early and Julian Togelius. Now this paper is basically just a fun paper I feel, and it shows how to frame a problem in terms of reinforcement learning and then how to solve it. It's pretty straightforward, it's fairly short and the code is available and all so you can go check it out yourself. They say we investigate how reinforcement learning can be used to train level designing agents. So usually we do reinforcement learning for playing games themselves and now we use reinforcement learning to train an agent that can design a level. So we don't design the level itself straightforward, we design the agent that designs the level. And what's the advantage here? The advantage is of course the agent could then potentially generate multiple different levels once we have trained it. Let's say this represents a new approach to procedural content generation in games where level design is framed as a game itself. So the design of the level is now the game. And the content generator itself is learned. By seeing the design problem as a sequential task we can use reinforcement learning to learn how to take the next action so that the expected final level quality is maximized. This approach can be used when few or no examples exist to train from and the train generator is very very fast. So this is the outset of the problem formulation. Now we're going to go through the steps you have to do in order to make this work. There are a few things that I think this paper does quite well. The first thing is you actually have to frame the problem in terms of reinforcement learning. So what is reinforcement learning? It's pretty simple. In reinforcement learning you have this agent-environment split. So at each step the environment is going to send the agent an observation. So the environment is going to send an observation to the agent and the agent needs to take an action in response to that. Now something happens in here. We don't worry about that. The environment is going to send the next observation that is a result from taking this action and it is also going to send the reward for this action. So at each step the agent gets an observation and a reward for the last action it took and it has to output the next action. Now the environment of course has to somehow decide how do I represent the observation. This is the representation. How do I transform one observation to the next observation given an action? The action comes in and transforms the last state to the next state and then how do I give the reward? How do I calculate the reward? So these things are the things you have to decide on. The observation space, how the reward is calculated, the action space and how an action transforms one representation into the next representation. So this is what we're going to look at, the different variants. We're not going to look at specifically how reinforcement learning is done because once you have an environment like this you can just plug it into a standard reinforcement learning algorithm and it will solve it for you. So that's the power of basically having standardized or representations. So the observation space of this problem is going to be pretty simple. All the games we're dealing with here are in this... Oh, I already did some drawings... are in this framework of this grid world game. So you have this grid, this level is subdivided into this grid and that naturally corresponds of course to a 2D matrix. Now each point in this matrix has a number and the number describes what type of tile this tile is. So as you can see right here, the 1 is going to be a wall while the 0 is going to be empty space. 3 here is one of these crates and 2 is the player. So you get the point, right? Each number corresponds to a type of tile. So far so good. That's the observation space. Now what is the action space? What is the agent can do? At each step they say the agent can change one of these tiles. So you can change one of these tiles, let's say this one right here. You can change it to a different one or you can just leave it. So this is a wall right now and it makes the problem fairly interesting to have a wall right here in the middle. So since we're looking at this tile, we might just wanna leave this right there. We could also change it. We could actually change it such that to a 2, such that there is another player right here. Can I even draw this? This yellow isn't. Such that there is now two player tiles in the game. This would of course be an invalid level and the reinforcement learning agent ultimately should learn to produce valid and good levels. So at each step you can change one tile and of course the goal is to make a better and better and better level over time. Now how do you choose which tile to change? That's a thing you have to define and they define three different ways in which the agent can choose which tile to change. In the narrow formulation they themselves, so the environment, chooses the frame, the tile to change. So the environment will say now you can change this tile if you want. And in the next step it will say now you can change this one if you want. Now you can change this one if you want. Now this is completely random how the environment chooses. Actually it doesn't have to be, but the environment chooses and that is problematic for the agent because the agent cannot kind of predict which tile it can change next and therefore it cannot really plan ahead how it wants to change the level. It can only make very very local very greedy choices. It can be like oh I'm right here I might actually build a wall right here. Yes that seems good. An example is maybe you want to make the level more interesting. Maybe you think that the crate up here is a bit close to this field here. You have to push it onto this field and that's fairly easy right? So you just push it like up and then to the left. Actually it's not that easy because there's the wall right here and you have to go around. Actually you probably have to push this down. But let's say the level is too easy and you want to move the move the crate to a bit like let's say here. In this framework where the environment tells you which tiles to change. Once you come across this tile you can delete it. But then you have to wait and wait and wait and wait until at random this tile where you want to put it is selected. This might actually never happen because the episode might be over and if it never happens you are in an invalid level. So the agent here is basically forced to greedily make the level valid before it can make it interesting and then it can only make it interesting in sort of local ways. So the second way that the second formulation here is the turtle formulation. Now you might know this from the turtle graphics where basically you have this little turtle thing and you can always move it either like you know down, up, left or right and then you can always put a dot or not put a dot and thereby you can like trace out things. This is like intro to programming. Same here. So now the agent is given a starting square and it can choose to change it or not but it can also choose how to move to the next square. So to the right, up, left or down. So it can choose. So you can go along and say okay now I'm here I want to change it to a 2, now I'm here, I want to change it to a 2, now I'm here and so on. So it can basically do things like build long walls and things like this so it can plan ahead more considerably. But still if you regard the problem from before if it wants to place the crate to a different location it can, like if maybe it's here okay the agent is here and then it can say okay I wanna not change but move, not change and move, not change move and then it can delete and then it has to move over here step by step until it can place it again. So it can plan ahead considerably longer actually it can just move straight over because the agent itself is not constrained by walls. So it can move ahead quite a bit but it's still kind of localized changes because it can move one tile at a time right and if in between the episode ends it's again an invalid level. So the third formulation is the most powerful formulation. It's called the wide formulation and this is where the agent at each time step cannot only choose how to change the tile but can freely choose the next tile to change. So it could say in one step it could say I want to delete this tile and then in the next step it could say I want to place it right here. So this is, so it can plan ahead considerably. So how you design the action space is very important for how your agent, for what your agent can possibly learn and how easy it is for the agent to learn because it's gonna be pretty easy for this agent to learn to move crates like this where even though the other agent that moves one tile at a time can also do it it has to plan ahead for longer so it has to sort of invest more of the reinforcement learning power into doing these sorts of things. But of course it's being more constrained also means you have less actions at your disposal. Like this last agent it has a lot of actions it can do. It can choose any tile at once right so that can also introduce considerable exploration dilemma and you have to trade these things off when you design things like that. Alright so this is the action space. Now how the observation evolves into the next observation should be fairly clear. I mean that's already given by the action space. If you ask yourself if you're in this situation right here and the agent deletes the crate then the crate is no longer there. So if it changes this to a zero then it's just empty space now. So that's fairly obvious here. Now the last thing we need to do is the reward calculation. What reward do you give the agent? Here you can give the agent the reward either let's say at the very end. You cannot give it a reward for the entire episode and give it a reward at the very end. Reinforcement learning algorithms are able to deal with this to a certain degree. You can also decide to give it at each step. Now the way they do it here I believe is they give it at the end and they have multiple components to the reward. So the reward in this case is how well the level fulfills certain goals that the programmer sets. So the goals in Sobocon are basically the rules of the game and that means there is only one player. If there are two or none then the reward is less. There are at least one crate and there are as many crates as green fields. So here you can see there are only two crates but three green fields so the agent will get a penalty for producing a level like this. And then the last thing is the level has to be solvable. And for checking solvability the authors of this paper simply employ a Sobocon solver. They have a Sobocon solver that is like a tree search algorithm that tries to solve the level. If it can't solve the level then the level is invalid and the agent gets a worse reward than whenever the level is solvable. So how you design the reward is also very important. If you only give a one reward when all the goals are fulfilled and give a zero reward as soon as one of the goals is not fulfilled, a reinforcement learning agent is going to have a very very much difficult time to learn that. So you have to kind of design the reward so you help the agent realize what's important. So maybe if there's only one crate missing but you know in fact the level is solvable, except for that maybe one green field is going to be empty, then you could still give a fairly high reward but you could just give a higher reward when the level is actually solvable. Or all the rules are fulfilled and there is a crate here. The other thing to notice here is that in this case you actually do need a solver for the level since it's a puzzle game. That means your agent is only going to produce levels that are as difficult as your solver can solve. So that's going to be a considerable problem. But that's a limitation here. But all of their rewards are hard-coded so to say. So the reward is given by the environment. So now that we have observations which are these matrices right here, we have actions which and we actually have three different ways of formulating actions and we have reward, they can simply plug this into a standard reinforcement learning algorithm. Now they have one last thing that they have which is this change percentage parameter. So what they say is they give the agent an initial state and then the agent is allowed to change it around like here. So on the left you have this initial state. This is sort of a random initial state and you allow the agent now to change it in this stepwise fashion and you always update the agent. By the way, the agent, as you might imagine, the agent takes this matrix right here and puts it, shoves it through like a few convolutional layers and then decides on an action. I'm almost forgetting that this is so obvious by now that the agent is like a standard deep learning taking in a 2D, doing some convolutions and then having like a policy output. So you shove this into a proximal policy optimization algorithm which is a standard reinforcement learning algorithm and you allow to change these things. Now what they do is they only allow the agent to change the levels by so much because what they say is if we start out from these different states we would, you can decide on two things. Either you can train the agent to find you the best possible level ever, right? But then it would sort of ignore the starting state. It would just learn which level gives me the highest reward and it would just change all the tiles always to that. It would just try to change the, to always reach that best possible state and forget the start state. So they say, okay, the last constraint is the agent can only change like 20 percent of the tiles at most and after that we end the episode or we just don't allow the agent to change anything anymore. It needs to first, so if it changed this here to empty space and wants to change something else, first needs to change this back and then it can change something else. So you can do that. So this constrains the agent and kind of teaches it that in order to get a higher reward it must sort of adjust the starting state to something that gets higher reward. And that's one way of making the the levels that you generate more diverse. It's sort of a unique problem to this particular kind of reinforcement learning problem because sometimes, like most of the time, you just want to find the highest reward, whatever. But here you also want to maximize diversity of the levels you generate and therefore you could say that's a pretty good, you know, that's a pretty good constraint to put into that. So that's a thing I like here about this paper. This change percentage constraint. Now at inference time you can change that. So at training time you only change, whatever, 20 percent. But at inference time you can technically let the agent run for longer. As you can see, I think here they just let it run until it, you know, finds something good, like this one right here. Fairly good from the starting state. And you can see it sort of still adjusts to the starting state right here. So you can see that this it connects the the two dots on the top. So the goal is to make the longest possible maze or a long maze. So it connects these two. You can see here also this one connects them. And then it goes out here and connects to this one. So it's fairly good at relying on this starting state. You can see that these turtle and wide representations that can actually choose where to go and where to change something are considerably or, you know, more powerful than this narrow thing. Especially if you look at this level right here. Which again is the importance of designing the action space. Well, it is going to directly affect the outcome that you're going to have. Alright, and you see the same thing here for this Zelda game. Now here you can see the starting state often involves, let's say, here you have two players and you have three keys and that's an invalid starting state. And sometimes the door cannot be reached. Sometimes the door is actually not even there, like here. And you can see that the agent, all of the agents, sort of learn to make at least valid levels where you have the player and the door and the key right here being able to reach everything. So that's, you know, fairly cool because counting is one of these things that the neural networks aren't necessarily super good at. So it's nice to see that, you know, they can... Here they have two players and they they're deleting one of them. Here they have three crates and they actually make it such that the number of crates and the number of green tiles agree. So, you know, that's fairly cool that this comes out. And here you can see the different power of the algorithms. So in this binary problem, and this is the Zelda problem, this is Sobhakan problem, you can see that as you allow the agent at inference time to change more and more of the level, the percentage of levels where the agent gets a good level, like succeeds in building a valid level, goes up and up. And now this, as I already said, this narrow representation here appears to be a bit less powerful than the others. Interestingly, in Sobhakan, the best one is this turtle representation where you can only change one tile at a time and not the more powerful wide representation. That's probably because, I'm going to guess that's because the either the reinforcement learning algorithm isn't, you know, powerful enough or their representation, like the CNN is maybe mis-architectured a bit. You know, technically this representation should be able to achieve higher scores, but not as easily because, as I said, the action space is so much higher. So it's more difficult to learn, but ultimately, it should learn it better. Alright, so this is, this was this paper. It's, I think it's fairly cool and fairly fun to view it from this particular perspective. And they discuss that the future could be that humans solve this together, because usually when you have assisted level design, you would have something, some sort of like an optimizer running to optimize the level you're working on directly. Like you'd say, okay, make something here and it would sort of run for a while and that takes, you know, takes time. Now this here, this agent at inference time is very, very fast. So it can, you know, work together with humans. So the human would say, for example, oh here, please make a wall right here, because that's gonna make the level more interesting, but make it such that the level is still, you know, interesting and solvable. And then the agent can, you know, go across, do some things that's gonna be super fast. And agents and humans could work together at this. Now one drawback, of course, is that in a puzzle game like SoboCon, you know, you have to make sure the level is solvable. And here, luckily, you can employ a solver, but as the puzzles get more difficult, that's not super, like that's not going to be the case that much. And also they remark that most of the levels generated are fairly easy, because their reward only depends on whether or not the level is solvable by an easy solver, right? So you could give some reward for how difficult the level is, but then again, that depends on your solver. So an interesting next step would be to evolve these or to train these as you train reinforcement learning agents to solve these kinds of games. So kind of do a curriculum learning, sort of a GAN setting between level generator and reinforcement learning algorithm, like reinforcement learning game player to sort of evolve levels and agents at the same time. I think it's sort of like these poet approaches, except you would directly learn. I think that would be a nice direction for this work. In any case, the code is available. You can even plug in your own games and make your own levels, so check this out. And with that, I'll see you next time. Bye bye.
 Hi there! Have you ever wondered how video game levels are made?
 Yeah, me neither, but this paper has.
 And in this paper you can see a reinforcement learning agent that has
 learned
 how to make video game levels
 in various ways. So this is implemented for
 this game here where the goal is simply to make the longest maze.
 This game here is an adaptation to The Legend of Zelda
 where you have to get a key to the door. And this game here is called
 Sobocon where you have to put all of the crates
 onto the green squares in order to solve it. So it's a puzzle game.
 Alright, and this is done via
 reinforcement learning. So the paper we're going to look at is called
 PCGRL Procedural Content Generation Via
 Reinforcement Learning by Ahmed Khalifa, Philippe Bontrager,
 Sam Early and Julian Togelius. Now this paper
 is basically just a fun paper
 I feel, and it shows how to frame a problem in terms of reinforcement learning
 and then how to solve it. It's pretty straightforward, it's fairly short
 and the code is available and all
 so you can go check it out yourself.
 They say
 we investigate how reinforcement learning
 can be used to train level designing agents.
 So usually
 we do reinforcement learning for playing games
 themselves and now we use reinforcement learning
 to train an agent that can design a level.
 So we don't design the level itself
 straightforward, we design the agent that designs the level.
 And what's the advantage here? The advantage is of course
 the agent could then potentially
 generate multiple different levels once we have trained it.
 Let's say this represents a new approach to procedural content generation in
 games
 where level design is framed as a game itself.
 So the design of the level is now the game. And the content generator
 itself is learned. By seeing the design problem as a sequential task we can use
 reinforcement learning to learn how to take the next action
 so that the expected final level quality is maximized.
 This approach can be used when few or no examples exist to train from
 and the train generator is very very fast.
 So this is the outset of the
 problem formulation. Now we're going to go through the steps you have to do
 in order to make this work. There are a few things
 that I think this paper does quite well.
 The first thing is you actually have to frame the problem in terms of
 reinforcement learning.
 So what is reinforcement learning? It's pretty simple. In reinforcement learning
 you have this agent-environment split.
 So at each step the environment is going to send the agent an
 observation. So the environment is going to send an observation
 to the agent and the agent needs to take an
 action in response to that. Now
 something happens in here. We don't worry about that.
 The environment is going to send the next observation
 that is a result from taking this action
 and it is also going to send the reward
 for this action. So at each step the agent gets
 an observation and a reward for the last action it took and it has to output
 the next action. Now the environment of course has to
 somehow decide how do I represent the observation.
 This is the representation. How do I transform
 one observation to the next observation given an action?
 The action comes in and transforms the last state to the next state
 and then how do I give the reward? How do I calculate the reward?
 So these things are the things you have to decide on. The observation space,
 how the reward is calculated, the action space
 and how an action transforms one
 representation into the next representation.
 So this is what we're going to look at, the different variants.
 We're not going to look at specifically how reinforcement learning is done
 because once you have an environment like this you can just plug it into a
 standard reinforcement learning algorithm
 and it will solve it for you. So
 that's the power of basically having standardized or
 representations. So the observation space
 of this problem is going to be pretty simple. All the games we're dealing with
 here
 are in this... Oh, I already did some drawings...
 are in this framework
 of this grid world game.
 So you have this grid, this level is subdivided into this grid
 and that naturally corresponds of course to a 2D
 matrix. Now each point in this matrix has a number
 and the number describes what type of tile this tile is.
 So as you can see right here, the 1 is going to be
 a wall while the 0 is going to be empty space.
 3 here is one of these crates
 and 2 is the player. So you get the point, right? Each number corresponds to a type
 of tile. So far so good.
 That's the observation space. Now what is the
 action space? What is the agent can do?
 At each step they say the agent can change
 one of these tiles. So you can change one of these tiles,
 let's say this one right here. You can change it to a different one or you can
 just leave it. So this is a wall right now and it makes the problem fairly
 interesting to have a wall right here
 in the middle. So since we're looking at this tile, we might just wanna
 leave this right there. We could also change it. We could actually change it
 such that
 to a 2, such that there is another player
 right here. Can I even draw this?
 This yellow isn't. Such that there is now two player
 tiles in the game. This would of course be an invalid level and
 the reinforcement learning agent ultimately should learn to produce
 valid and good levels.
 So at each step you can change one tile and of course the goal is to make a
 better and better and better level
 over time. Now how do you choose which tile
 to change? That's a thing you have to define
 and they define three different ways in which the agent can choose
 which tile to change. In the narrow
 formulation they themselves, so the environment,
 chooses the frame, the tile to change. So the environment will say
 now you can change this tile if you want. And in the next step it will say
 now you can change this one if you want. Now you can change this one if you want.
 Now this is completely random
 how the environment chooses. Actually it doesn't have to be, but the environment chooses
 and that is problematic for the agent because
 the agent cannot kind of predict which tile it can change next
 and therefore it cannot really plan ahead
 how it wants to change the level. It can only make very very local very greedy
 choices.
 It can be like oh I'm right here
 I might actually build a wall right here.
 Yes that seems good.
 An example is maybe you want to make the level more interesting.
 Maybe you think that the crate up here
 is a bit close to this field here. You have to push it onto this field and
 that's fairly easy right?
 So you just push it like up and then to the left.
 Actually it's not that easy because there's the wall right here and you have to go
 around.
 Actually you probably have to push this down.
 But let's say the level is too easy and you want to move the
 move the crate to a bit like let's say here.
 In this framework where the environment tells you which
 tiles to change.
 Once you come across this tile
 you can delete it. But then you have to wait
 and wait and wait and wait until
 at random this tile where you want to put it is selected.
 This might actually never happen because the episode might be over
 and if it never happens you are in an invalid level.
 So the agent here is basically forced to greedily make the level
 valid before it can make it interesting and then it can only make it interesting
 in sort of local ways.
 So the second way that the
 second formulation here is the turtle formulation.
 Now you might know this from the turtle graphics
 where basically you have this little
 turtle thing and you can always move it
 either like you know down, up, left or right
 and then you can always put a dot or not put a dot and thereby you can like
 trace out things.
 This is like intro to programming. Same here.
 So now the agent is given a starting square
 and it can choose to change it or not but it can also choose
 how to move to the next square. So to the right,
 up, left or down. So it can choose. So you can go along and say okay now I'm here
 I want to change it to a 2, now I'm here, I want to change it to a 2,
 now I'm here and so on. So it can basically
 do things like build long walls and things like this
 so it can plan ahead more considerably.
 But still if you regard the problem from before
 if it wants to place the crate to a different
 location it can, like if maybe it's here
 okay the agent is here and then it can say okay I wanna
 not change but move, not change and move, not change move and then it can delete
 and then it has to move over here step by step
 until it can place it again. So it can plan ahead considerably
 longer actually it can just move straight over because the agent itself is not
 constrained by walls.
 So it can move ahead quite a bit
 but it's still kind of localized changes because it can move one tile at a time
 right and if in between the episode ends
 it's again an invalid level. So the third formulation is the most powerful
 formulation.
 It's called the wide formulation and this is where the agent at each
 time step cannot only choose how to change the tile but can freely choose the
 next tile to change.
 So it could say in one step
 it could say I want to delete this tile
 and then in the next step it could say I want to place it right here.
 So this is, so it can plan ahead considerably.
 So how you design the action space is very important
 for how your agent, for what your agent can possibly learn
 and how easy it is for the agent to learn because it's gonna be pretty easy
 for this agent to learn to move crates like this
 where even though the other agent that moves one tile at a time can also do it
 it has to plan ahead for longer so it has to sort of invest more
 of the reinforcement learning power into doing these sorts of things.
 But of course it's being more constrained also means
 you have less actions at your disposal.
 Like this last agent it has a lot of actions it can do. It can choose
 any tile at once right so that can also introduce considerable
 exploration dilemma and
 you have to trade these things off when you design things like that.
 Alright so this is the action space. Now how
 the observation evolves into the next observation should be
 fairly clear. I mean that's already given by the action space. If you ask yourself
 if you're in this situation right here
 and the agent deletes the crate
 then the crate is no longer there. So if it changes this to a zero
 then it's just empty space now.
 So that's fairly obvious here. Now the last thing we need to do is the
 reward calculation.
 What reward do you give the agent?
 Here you can give the agent the reward either
 let's say at the very end. You cannot give it a reward
 for the entire episode and give it a reward at the very end.
 Reinforcement learning algorithms are able to deal with this to a certain
 degree.
 You can also decide to give it at each step.
 Now the way they do it here I believe is they give it at the end
 and they have multiple components to the reward.
 So the reward in this case is how well
 the level fulfills certain goals that the programmer sets.
 So the goals in Sobocon are basically the rules of the game
 and that means there is only one player.
 If there are two or none then the reward is less.
 There are at least one crate and there are as many crates as green fields.
 So here you can see there are only two crates but three green fields so the
 agent will get a penalty
 for producing a level like this. And then the last thing is
 the level has to be solvable. And for
 checking solvability the
 authors of this paper simply employ a Sobocon solver.
 They have a Sobocon solver that is like a tree search algorithm
 that tries to solve the level. If it can't solve the level
 then the level is invalid and the agent gets a
 worse reward than whenever the level
 is solvable. So how you design the reward
 is also very important. If you only give
 a one reward when all the goals are fulfilled and give a zero reward as soon
 as one of the goals is not fulfilled, a reinforcement learning agent is going to
 have a very very much
 difficult time to learn that. So you have to kind of design the reward
 so you help the agent realize what's important. So maybe
 if there's only one crate missing but you know in fact the level is
 solvable, except for that
 maybe one green field is going to be empty,
 then you could still give a fairly high reward but you could just give a higher
 reward
 when the level is actually solvable. Or all the rules are fulfilled
 and there is a crate here. The other thing
 to notice here is that in this case you actually do need
 a solver for the level since it's a puzzle game.
 That means your agent is only going to produce levels that are
 as difficult as your solver can solve. So that's going to be
 a considerable problem. But that's a limitation
 here. But all of their rewards are hard-coded
 so to say. So the reward is given by the environment.
 So now that we have observations
 which are these matrices right here, we have actions which
 and we actually have three different ways of formulating actions and we have
 reward,
 they can simply plug this into a standard reinforcement learning algorithm.
 Now they have one last thing that they have which is this
 change percentage parameter. So what they say is they give
 the agent an initial state and then the agent is allowed to change it around
 like here. So on the left you have this initial
 state. This is sort of a random initial state and you allow the agent now to
 change it in this stepwise fashion and you always update the agent.
 By the way, the agent, as you might imagine, the agent takes this matrix
 right here and puts it, shoves it through like a few convolutional layers and then
 decides on an action.
 I'm almost forgetting that this is so obvious by now that
 the agent is like a standard deep learning
 taking in a 2D, doing some convolutions and then having
 like a policy output.
 So you shove this into a proximal policy optimization algorithm
 which is a standard reinforcement learning algorithm and you allow to
 change these things. Now what they do is they
 only allow the agent to change the levels by so much because what they say is
 if we start out from these different states
 we would, you can decide on two things.
 Either you can train the agent to find you the best
 possible level ever, right? But then
 it would sort of ignore the starting state. It would just learn which level
 gives me the highest reward
 and it would just change all the tiles always to that.
 It would just try to change the, to always reach that best possible state
 and forget the start state. So they say, okay,
 the last constraint is the agent can only change
 like 20 percent of the tiles at most
 and after that we end the episode or we just don't allow the agent to
 change anything anymore.
 It needs to first, so if it changed this here to empty space and
 wants to change something else, first needs to change this back and then it can
 change something else.
 So you can do that. So this constrains the agent and kind of teaches it
 that in order to get a higher reward it must sort of adjust the starting state
 to something that gets higher reward.
 And that's one way of making the
 the levels that you generate more diverse. It's sort of a unique problem
 to this particular kind of reinforcement learning problem because
 sometimes, like most of the time, you just want to find the highest reward, whatever.
 But here you also want to maximize diversity of the levels you
 generate and therefore you could
 say that's a pretty good, you know, that's a pretty good constraint
 to put into that. So that's a thing I like here about this paper.
 This change percentage constraint. Now at inference time you can change that.
 So at training time you only change, whatever, 20 percent. But at inference time
 you can technically let the agent run for longer. As you can see, I think here
 they just let it run until it, you know, finds something good, like this one right
 here. Fairly good from the starting state. And you can see it sort of still
 adjusts to the starting state right here. So you can see that this it connects the
 the two dots on the top. So the goal is to make the longest possible maze or a
 long maze. So it connects these two. You can see here also this one connects them.
 And then it goes out here and connects to this one. So it's fairly good at
 relying on this starting state. You can see that these turtle and wide
 representations that can actually choose where to go and where to change
 something are considerably or, you know, more powerful than this narrow thing.
 Especially if you look at this level right here. Which again is the importance
 of designing the action space. Well, it is going to directly affect the outcome
 that you're going to have. Alright, and you see the same thing here for this
 Zelda game. Now here you can see the starting state often involves, let's say,
 here you have two players and you have three keys and that's an invalid
 starting state. And sometimes the door cannot be reached. Sometimes the
 door is actually not even there, like here. And you can see that the agent, all
 of the agents, sort of learn to make at least valid levels where you have the
 player and the door and the key right here being able to reach everything.
 So that's, you know, fairly cool because counting is one of these things
 that the neural networks aren't necessarily super good at. So it's nice
 to see that, you know, they can... Here they have two players and they
 they're deleting one of them. Here they have three crates and they actually make
 it such that the number of crates and the number of green tiles agree. So, you
 know, that's fairly cool that this comes out. And here you can see the
 different power of the algorithms. So in this binary problem, and this is the
 Zelda problem, this is Sobhakan problem, you can see that as you allow the agent
 at inference time to change more and more of the level, the percentage of
 levels where the agent gets a good level, like succeeds in building a
 valid level, goes up and up. And now this, as I already said, this narrow
 representation here appears to be a bit less powerful than the others.
 Interestingly, in Sobhakan, the best one is this turtle representation where you
 can only change one tile at a time and not the more powerful wide
 representation. That's probably because, I'm going to guess that's because the
 either the reinforcement learning algorithm isn't, you know, powerful
 enough or their representation, like the CNN is maybe mis-architectured a bit.
 You know, technically this representation should be able to achieve higher
 scores, but not as easily because, as I said, the action space is so much higher.
 So it's more difficult to learn, but ultimately, it should learn it better.
 Alright, so this is, this was this paper. It's, I think it's fairly cool and fairly
 fun to view it from this particular perspective. And they discuss that the
 future could be that humans solve this together, because usually when you have
 assisted level design, you would have something, some sort of like an optimizer
 running to optimize the level you're working on directly. Like you'd say, okay,
 make something here and it would sort of run for a while and that takes, you know,
 takes time. Now this here, this agent at inference time is very, very fast. So it
 can, you know, work together with humans. So the human would say, for example, oh
 here, please make a wall right here, because that's gonna make the level more
 interesting, but make it such that the level is still, you know, interesting and
 solvable. And then the agent can, you know, go across, do some things that's
 gonna be super fast. And agents and humans could work together at this. Now
 one drawback, of course, is that in a puzzle game like SoboCon, you know, you
 have to make sure the level is solvable. And here, luckily, you can employ a
 solver, but as the puzzles get more difficult, that's not super, like
 that's not going to be the case that much. And also they remark that most of
 the levels generated are fairly easy, because their reward only depends on
 whether or not the level is solvable by an easy solver, right? So you could give
 some reward for how difficult the level is, but then again, that depends on your
 solver. So an interesting next step would be to evolve these or to train these as
 you train reinforcement learning agents to solve these kinds of games. So kind
 of do a curriculum learning, sort of a GAN setting between level generator and
 reinforcement learning algorithm, like reinforcement learning game player to
 sort of evolve levels and agents at the same time. I think it's sort of like
 these poet approaches, except you would directly learn. I think that would be a
 nice direction for this work. In any case, the code is available. You can even
 plug in your own games and make your own levels, so check this out. And with that,
 I'll see you next time. Bye bye.