Behaviour Design and Irregular AI Development

If you've played Bump!, you know that it can be hectic and free-form. While handling hectic data has never been a problem for a PC, you can't say the same for free-form data.

Unnecessary Premise

[The following is an introduction regarding why I chose to implement an AI in Bump!. If you are not interested, skip ahead to the "Necessary Premise" paragraph.]

At the start of my development journey, I was fixated on not having a single-player mode. Heck, I was set on not having a menu to choose anything, but just plunge the two (TWO! 2, I couldn't stress enough how you had to be two to play the game) players into character selection and then the game. I actually wanted to drop the character selection menu, too, but I couldn't help wanting different characters, too, so I had to make compromises with myself.

With time, however, I learned how actually game distribution works: you are randomly browsing Itch.io, you see a game's logo, you get interested and open the game's page. You quickly read through the description and then decide to download. You try it out, you enjoy it and then you play it with your friends.

As you can see, up until the very last step, the player is all alone with the game. This is extremely bad news for multiplayer game developers, since they will have to face a tough cliff right out the bat: if the player is surfing Itch alone, they'll also have to try the game alone. If they don't enjoy the game, which they couldn't try to the most of their abilities since it needs a second seat, they'll also discard the game altogether, cutting off a potential player.

As such, before making the game public, I felt compelled to put up a solution of some kind, so enter the single-player mode. However, Bump! doesn't feature a campaign of any kind nor did I want it to: the focus of the game is the 1v1, nothing should move the player's attention from that and no one should ever say "I'd rather play alone than with someone else" in any condition EVER. Period.

With that said, there was only one solution: AI.

Necessary Premise

First of all, you should try Bump! out before reading on: although I'm trying to keep this post as generic as possible, the post covers my experience with the game, and some of it is strictly related to the game's mechanics. Also, as for important notation: a game of Bump! starts when both players have a score of 0 and end whenever either of them reaches 15 with at least two points of difference. The time between one waitscreen and the other (so in between points) is called a "stock".

Secondly, there's a lot of confusion around the term AI, so let's clear that out first. AI stands for Artificial Intelligence and is a term that indicates any form of "intelligent" behaviour (actually, "intelligent" could be omitted for the definition) in something that has no such thing as intelligence such as a computer. It doesn't have to be elaborate in any way whatsoever, nor does it have to implement matrix multiplication or sigmoid functions in order to work. Even a simple "endlessly go right" is an instruction that would make an AI. As such, an AI is as "intelligent" as you want it to: if you want to make a "dumb" AI for Bump! which suicides, you only have to tell it to press up as quickly as possible, as many times in a row as possible. If you want to make a worthy opponent, though, that's a whole 'nother beast.

Thirdly, we have to actually define what you want your AI to do, which some people overlook: is the objective making an almost undefeatable AI? Is the objective making a AI that never spontaneously suicide? Do you want it to be aggressive? Do you want it to make visible mistakes or only to overlook the best options sometimes? Those are a lot of options which make up what I call Behaviour Design.

The Behaviour Design in Bump!

In order to design the behaviour for you AI, you need to think what the objective of your AI is. For example, Bump! is a game best played by two players sitting next to each other, but every player needs to start, and not everyone has someone near them to play the game with the first time. As such, I wanted an AI that was approachable but challenging for beginners, such that when they could consistently beat the AI they'd be at a decent level for playing other players. As such, some key features for our AI will be good, but not overwhelming. Also, it's allowed to visibly make mistakes (such as just moving right while already near the spikes on the right and die), since those happen a lot between beginners and they will also be free points for the absolute beginner, which will end their first game with some points under their belt, at least, instead of a wrecking 15-0 (hopefully not zero, but let's take note of the possibility).

Another important point for the AI in Bump! is that it shouldn't ever wait for the other player to make the first move: Bump! is a game that strongly relies on the first at most 2 or 3 seconds of each stock, rarely going over that, so it's important to teach someone who barely knows the buttons to play the game when most of the gameplay is focused. As such, on their first stock ever, the player will probably be crushed before even attempting anything and then be tossed into a waitscreen where they will try to understand what happened. Hopefully, the player has enough pattern recognition abilities to learn that they have to do something quickly at the start of each stock. This leads us to another important point: aggressiveness.

With these key points we have a couple of options to complete the Behaviour Design. The most relevant two I found were:

1. Probably move in the general direction towards the opponent, occasionally randomly choose another option.
2. Move towards the opponent, with a probability proportional to the distance along that axis (i.e., if the opponent is on the upper left from you with an angle of 10 degrees with the horizontal, it only has the options to move upwards or left, but it's much more likely they will move left).

Option 1 felt a bit too random, but worthy, while option 2 felt a bit too deterministic, perhaps easy to predict. The solution chosen was a simple midpoint of the two: the general behaviour would be option 2, but sometimes at random choose another option.

AI Technical Design

So, first of all, Bump! accepts inputs at every frame, as such you would think we'd need 5 options for the game: up, right, down, left, stay. Making stay much more common than all the directions might have made for a nice behaviour, but you risked that the AI pulled off an inhuman series of inputs that sent it godspeed towards the player, helplessly dying without having had the human reaction time available to answer the opponent. All the same, a completely static opponent for a couple of seconds might happen, too, which is a huge no-no for Bump!.

As for that, the final choice was to define a timeToMove variable that, upon reaching 0, generates a move using only the directions. timeToMove is randomly picked every time between a certain minT and maxT, which can be used to ensure that the moves are not "rythmical" but at the same time more regular than something completely luck-based.

That said, at any given time we want the probability of each option (which have to add up to 1) to be dependant on the relative position of the opponent to the AI. Let's call the unit vector pointing to the opponent dir and the angle it forms with the positive x axis theta. Since the solution is strongly based on what we called "option 2" before, let's start by implementing that.

Since we are dealing with angles and we want the two options to add up to 1, it's plenty obvious if you have any trigonometry know-how that we are going to be using the pythagorean identity sin^2(theta) + cos^2(theta) = 1. It's not the only option, nor the simplest one, but it's the one that gave me the best feeling. Let's do an example:

AI is at position (0, 0), opponent is at position (1, 4). We want it to be more likely to move upwards rather than right. We want to measure theta as the angle between dir = unit_vector_of((1,4) - (0,0)). Then, let P_X = cos^2(theta)~=0.04 be the probability of moving along the x axis (right, since the opponent is on the right) and P_Y = sin^2(theta)~= 0.96 the probability of moving along the y axis (up, since the opponent is on top of the AI).

Now it's simple: let's generate a random number 0 <= psi <= 1 and if psi <= P_X, move right, else move up.

If we want to add in the random factor, we have a couple of ways. The way I wanted it to be is "downscale all probabilities by a certain amount, then add the removed amount equally to all options". Let's introduce the Random Reduction factor R. As such, in the scenario from before, we'd have P_Up=0.094 P_Right=0.05, P_Left=P_Down=0. Let P'_Up = P_Up * (1-R). We then have to add the whole removed equally between all directions, so we have P''_Up = P_Up * (1-R) + R/4~=0.73 with R=0.3. If we do the same for all other options, we have that P_Down=P_Up=0.075 and P_Right~=0.12.

The AI you can now try in Bump! is exactly this algorithm with well-tweaked minT and maxT (which are critical for the AI behaviour). I've been stunned by how well it fit my reasoning: I though that I'd have a lot more "inertial suicides" (which happen when the AI rushes towards you, goes over you for some reason and then try to move down since that's the most likely direction without braking and consequently crash into the spikes), however tuning down maxT gave it just enough reaction time to remedy to their mistakes.

Final Thoughts

This has been my first start-to-finish AI development for a game with continuous features: I've done some for board games and similar, in which the AI could just simulate the next N steps and choose to do the wrong action sometimes, however continuous features make precise planning extremely tough to handle.

If you want to forget the whole write-up besides one thing, I'd ask you to remember the Behaviour Design step. It happens pretty often that a developer just plunges into code trying to make something that can play the game well. "Playing the game well" is too vague a definition of a behaviour to write some code for.

(Bonus) Going Overboard with Machine Learning

Another option I had for the AI was the machine learning route. I've wrote down an as-small-solution-as-it-gets that uses ML techniques to develop an AI for Bump!, but I left it as a last resort, since the simplest version still needed me to build a development build for Bump! that let me train the AI other than a lot of code. If you are familiar with Neural Networks, and maybe a bit of Genetic Algorithms, you may want to keep on reading.

The most basic implementation of an AI would have been either a Decision Tree or a Neural Network (also, Markov would get a say in this, but I'm not familiar enough with Markov Decision processes to build something this big from scratch). If you ask me, I think a Decision Tree is generally more fit for a game (as long as some random decision making is added to make it less deterministic while in game), however building a well-made Decision Tree in Unity, while purposely capping its strength is definitely over my current abilities. As such, the decision fell on Neural Networks. The idea is that by purposefully "chocking" the NN (i.e. having less layers or neurons per layer than a problem would need), we might make the AI choose more roughly. Also, that would have made for easy data storage (since you only need to save the weights for each AI in order to have the data handling down), definitely a plus.

So I was thinking of a NN that took 8 inputs (position and speed of both players), with one hidden layer with probably 4-6 neurons and an output layer with 4 neurons. The outputs could then make a four-vector which can then be divided by the sum of its components to make a probability vector. To do so, we need to use a ReLU on the output layer and (probably) a sigmoid in the hidden layer.

The first idea was a simple "two randomly generated AI fighting each other, the winner survives, the loser dies and is replaced by a mutation of the winner, then rinse and repeat". A mutation would simply be a small variation to each weight (since we don't have any gradient to follow here). However, this method was quickly discarded since it would have most likely got stuck at AI that just tried to survive and made for extremely long games.

The only solution that I could think of with GA and NN was a more complex system that used families of solutions. To be precise, N families with 2M members each. The j-th member of the i-th family will be denoted as P[i,j].

We also define a fitness function f(t,w) = e-S*t * w, where S is a constant parameter, t is time since the start of the game and w is 1 if the AI won, and -1 if it lost. f(t,w) is defined for a single stock, but since there are 15 stocks (at least) in one game we have to define a total fitness F(P[i,j], P[i',j']) P[i,j] is the evaluated AI and P[i',j'] is the enemy. The total fitness of a game is simply the sum of all the fitness functions on each stock divided by the number of stocks.

Then, P[1,1] fights P[2,1] and we compute the total fitness for each. P[1,1] fights P[3,1] and so on, until all possible cross-family fights are done. At the end, we'll have inside each family a leaderboard, in which the M worst will be replaced with mutations of the first M in that family. The mutation may also be affected by the fitness function: the lower, the more drastic the mutation.

This method would ensure variation between the families while also making sure that an AI survives not because it wins a fight against a slight variation of itself but because it can handle other different play styles.

That said, thanks for reading through the whole post.