Chapter 1

What is Bonk.io

Bonk.io is a fun physics game that many people have played in their childhoods. It contains maps, which are user built levels that contain many shapes such as death, bouncy, or normal shapes, where shapes can be rectangles, polygons, or circles.

This blog will be about the Classic gamemode. In this gamemode, players can press the X key to gain weight which allows them to smash into people harder which could be used to push people off the edge or into death shapes.

There are many many competitive Classic maps, here are a few:

In the next chapter we will be reviewing how normal Online reinforcement learning works.

Chapter 2

How does Reinforcement Learning work for 1v1?

PPO

What is PPO? PPO is the acronym for Proximal Policy Optimization, and is one of the state of the art algorithms for Online reinforcement learning. Online reinforcement learning is when you only train on recent gameplay to avoid feeding the ai stale gameplay (for example the ai doesn't need to be trained on old game data where the bot suicided).

PPO has 2 main components, actor and critic, which are both neural networks.

The actor predicts what keys to press, in our case since we are making a Classic 1v1 bot there are only 18 keys to press. The critic predicts the sum of all expected rewards, also known as value.

Reward Structure

I chose to use a terminally rewarded structure, where

• Win +1
• Loss −1
• Timeout −1

How does it learn?

When training a bot for 1v1s, we have to use self play, which means the agent fights itself.

Each time the agent gets a reward, it is stored in a buffer which gets used later for training. After a full rollout is completed, we calculate the values and advantages. Advantages are just numbers per action that depict how each action affects the value. For example, if an agent is losing according to the critic, and pulls off a move which lets it win, that action has a positive advantage.

Training

The actor is trained on these advantages, the moves that had positive advantages are trained to be selected more often at that state, and moves that had negative advantages are trained to be selected less often. To avoid the algorithm from zeroing out the probability of a specific action, we use entropy which basically pushes the probability of each action to be more even. This allows exploration and so the agent can sometimes stumble across moves it thought it was bad but turns out to be good in some states.

The critic is trained on the values we calculate from the rewards earned in game. Since the only reward our game has is the final state, the critic is trained to predict that reward for every state in the game. Over millions of games, it learns a distribution of how each game ends based on the current state.

Now that we know the basics of PPO, lets try applying this to the most basic map, Simple 1v1.

Chapter 3

Agent learns to play

There are a few other things before we can just let ai play against itself.

Simulating the game

Since we want to play millions of games we cannot just sit in a browser tab and wait 6 months. We have to simulate the game, and speed it up and parallelize it. On my machine I can run approximately 50,000 steps per second (Bonk.io runs at 30 steps per second).

If you want the src code for the games simulation, make it yourself.

Some required things before we start

Here are some techniques often used in self play that we will also employ.

Historical Buffers

This is by far the most important, if we just use normal self play and let the ai learn to beat itself, it will fail because it will invent a strategy against itself, but then invent a counter, and it will just lead to a rock paper scissor strategy.

To solve this, we clone and freeze the agent into a pool, and make the agent play against a random agent from the pool 50% of the time. This way the main agent has to learn a strategy that works against all old strategies.

Main Exploiters

This is an optional technique but it helps a lot. Every few hundred thousand games, we freeze the main agent, and let a brand new agent (or a clone of the agent but start it at a higher entropy) overfit to the main agent. This essentially lets the new agent, aka the exploiter, find strategies that work against the main agent. Once it reaches ~75% winrate, we add it to the pool, and let the main agent continue training.

Fictitious Self Play

Once the historical and exploiter pools exist, we need the agent to sample from them. A naive approach would be to make the agent play itself 50% of the time, a random agent from the historical buffer 25% of the time, and a random agent from the exploiter pool the other 25% of the time. This doesn't work so well.

What a better strategy is to base the sampling based on the winrate of each agent against the main agent. We track the winrate of each agent against the main agent's winrate.

I personally use a

• 20% chance to play itself
• 70% chance to play a weighted-random agent from the pool (old frozen selves + exploiters)
• 10% chance to play an idle bot that does nothing, so it never forgets how to fight a passive opponent

You would think that we should sample models based on if they have a higher winrate against the main agent, as to let the main agent learn more from them, but it's actually better to sample more from agents that have a ~50% winrate, as a 50% winrate contains more balanced win/loss results, and class imbalance is a real problem in ML.

the formula I use is to assign a weight to each model

and then sample based on the weights.

Letting it run

After about 60 hours of training and 20 million self-play games, the Simple 1v1 model was genuinely strong. In casual matches against real people it won the large majority of games, roughly 9 wins for every 3 losses, and it had almost entirely stopped throwing itself off the edge. For a first proper model on the easiest map, that was a great sign that the whole setup actually worked.

Chapter 4

Solving complex maps

So this approach worked very well in Simple 1v1. Why wouldn't this work in other maps? So I let this run on Death.

Results

After 10 million games, the agent learns to camp and never engages in battle. It is unlikely that the agent has ever experienced battle due to the large pit it has to cross just to meet the other agent. After millions of games, the agent learns that staying still yields more rewards than trying to explore the map and kill the other agent, since exploring the map yields no rewards, and it's super risky.

I proposed 5 new improvements I could implement.

Improvement 1

Since our model only has the win/loss/timeout reward, why should the critic predict a continuous number, especially since GAMMA = 1, meaning each state's outcome is either +1 or −1. This is where we can use a categorical head instead of a linear one. Instead of the agent learning the exact number of the value, all it predicts is the probability of the game resulting in a win, loss, or a timeout. This makes the critic way more stable, and we can always get the value as a numerical value for training the actor by using a weighted average across the probability distribution.

We can also help representation learning by adding auxiliary rewards onto the critic. I tried adding 4 heads, in order:

• predicts player position in 1 step,
• predicts player position in 4 steps,
• predicts player position in 8 steps,
• predicts player position in 16 steps.

These heads help the critic learn the distribution better, but in my testing, I didn't find that much of a meaningful impact.

Improvement 2

Instead of using the spawns that death offers, I wrote a script that scatters a thousand spawns and filters out the ones where an idle agent would die. This way, we can get more spawning positions and hopefully agents would be able to fight easier.

Improvement 3

An idea I had which was to pretrain an agent to fight an idle opponent, and then fine tune this pretrained model. To do this we need a new reward structure.

New Reward Structure

• Win +1
• Loss −1
• Timeout −1

But we also have a new reward for moving closer to the opponent. Every step, the agent gets a small reward proportional to how much closer it got to the opponent than it was the step before. The important detail is that we reward the change in distance, not simply being close: if you reward being close directly, the agent just parks itself in a safe spot and never commits, because moving around is risky. We also bound this reward so it can't be farmed by hugging the opponent forever.

Testing it out

After a couple million games, the agent has a 90% winrate against an idle agent, whilst in our old approach it would have never discovered a safe path to the opponent.

Moving into self-play

Now we can finally use this model to begin self-play. Our earlier improvement uses a categorical critic as it is much much more stable, but our agent right now predicts value linearly. All we have to do is let the agent play against itself while the actor is frozen. We discard the old critic, and let the new categorical critic converge.

Improvement 4

Lets talk about how exploration works, the agent is forced to keep each action evenly likely to be selected based on the Entropy coefficient. A super high entropy coefficient forces each action to have the same chance to be picked. A low entropy lets the agent choose the best action but also still have a chance to pick moves it wouldn't otherwise pick, which is good since sometimes it could pick those unlikely moves and stumble across a better strategy.

However, a single unlikely move that was pressed is very unlikely to stumble across a new strategy, especially since in this realtime game, you need a sequence of moves to do anything significant.

My new improvement is instead of the actor predicting the action, it should predict the action alongside how long it should hold it. Normally the actor is configured to hold the action for 2 steps (personal preference), and it re-chooses the action next step. We add a categorical head that predicts amongst the buckets {1, 2, 4, 8, 16, 32, 64}. If the actor picks 64 for example, it will be forced to hold that action for the next 64 decisions (aka ~4 game-time seconds). This boosts exploration significantly, as now it is committed to that strategy for a significant time.

In the future, I plan to come up with a better way for exploration to affect learning.

Improvement 5

The agent still fails to fight opponents that act differently from itself. Remember, the agent is primarily trained against itself, so it does well against opponents that act similarly to itself. This is also why exploiters help so much, they give the agent a new playstyle to adapt to.

The improvement that we can do is to train a separate exploiter whose goal is to stall. The cool thing about using a categorical critic is we don't have to change how the critic works, since we can just change the way value gets calculated from the critic's predicted probabilities.

So against a staller, a win is worth +2 and a timeout is worth 0 to the main instead of −1. The critic still predicts the same win/loss/timeout probabilities; we just weight a win at +2 and a timeout as neutral, so the main is no longer punished for a draw it can't avoid and is instead pushed to actually go for the kill.

I use a 25% chance for an exploiter to be of the staller variant.

Results

The agent plays Death very well, and trying the exact same approach on Somewhat large burger

leads to similar results. Against most of my friends, this ai was able to beat them with just 48 hours of realtime training across ~40–50 million games.

Things not mentioned

To make sure my model is actually usable in the real bonk game, I train the network with random input lag, each game has 2–6 steps of input lag. This is because in the real bonk game, I cannot execute frame perfect inputs.

Since some maps are horizontally mirrored, we can double the data we collect.

The state that the actor and critic sees is a 33-number vector:

Further Improvements

There are a few other improvements that could be done. One is to use tree search, where the agent searches into the future for the best move, this is the best way to make agents learn smarter without learning from trial and error, but it is much more computationally expensive.

Add a recurrence to the model so it can adapt to behaviours. Using an LSTM is probably too expensive as we need the full game history to keep track of the hidden state, so I could try an EMA.

I could also use a smaller model for faster training, as the current model of 70k params hasn't reached its capacity.

Here are links to the death and burger model weights along side the code to run them, Bonk Commands is required.