Flappy Bird AI - uml.edu

1 Flappy bird AI Dalton James Department of Computer Science at University of Massachusetts Lowell Lowell, MA Michael Begonis Department of Computer Science at University of Massachusetts Lowell Lowell, MA ABSTRACT In this paper we will discuss our Artificial Intelligence project on Flappy bird . Flappy bird is a mobile game that involves a bird flying over and under pipes to avoid them. The bird can only fly up and down to avoid them as the pipes move by. For our project we recreated the game in the Racket programming language for a human to play. We then implemented an Artificial Intelligence to play the game. It uses a breadth-first search algorithm to evaluate possible states and returns the action that will bring the bird to the best state. Author Keywords BFS, breadth-first search, path finding, Flappy bird , Racket INTRODUCTION The problem was to recreate a popular game using Racket and then develop an Artificial Intelligence to play the game.

2 After establishing this problem there were a few questions that still needed to be answered. First was how to make the game. To do this we used the 2htdp/image and 2htdp/universe Racket libraries. These allowed us to display the game on screen. To learn about basic game creation, especially for teaching, look at the article Using a simple game engine in teaching CS1 . After the game was made we had to decide how the Artificial Intelligence would play the game. For more on Artificial Intelligence relating to mobile games the article Enhancing artificial intelligence on a real mobile game is a good place to start. We researched a few possible options and in the end we decided on path finding. The path finding uses the ability to see future states to decide the best action at each time step.

3 This allows the bird to always end up in the best location while being memory efficient. PROBLEM DESCRIPTION To recreate Flappy bird there were a few steps involved to have a working version of the game running. First, both of us played the game so we had a good feel for the physics and display of the game. After this, we found, on Google Images, a picture of the bird , a background, and, on the pipes the bird must avoid. Everything was made using an objected oriented approach so different images were made as different classes. Each class has unique features that are necessary for their existence in the game. One example is the collision class which included pipes and the ground because they will kill the bird if they come in contact. Once the classes were added, the gravity for the bird was implemented.

4 This involved giving the bird acceleration and velocity. These are needed so that changes in velocity would appear fluid and not as if the bird was teleporting. Once the gravity existed, the ability to jump was added to the bird which gave the bird s means to combat gravity and fly over the pipes. The bird could now get input to jump upwards at any point or wait and allow gravity to move it downwards. With the gravity and jumping implemented it was now time to give the world movement. Having the entire world display move was a large challenge while creating the game. The world ran using a tick handler that was called 28 times per second. At each tick the world is redrawn with the pipe moving to the left and the bird changing its y value as necessary. On top of this if the pipe moves off of the left side of the screen a new pipe is randomly generated and drawn to the right side of the screen.

5 Having all of the functions the tick handler called work in unison took a lot of testing to have all of the timing correct. At this point the game was fully playable by a human. The jump ability was bound to w and restarting the world was bound to i so all of the games intended functionality was available to the user. This is when the Artificial Intelligence was implemented to play the game. The first attempt at an Artificial Intelligence was to use reinforcement learning. This would have the AI play the game numerous times and get a reward based on how well it did. The AI would eventually learn an optimal policy over time and therefore play the game with perfect efficiency. This was attempted by generating a list of possible states and updating the reward for each state as the bird moved through them.

6 To update the reward at each state a function was made that would iterate through the list and when it found the state it was in it would modify the reward associated with it. This method seemed to work when the state size was all of the possible y differentials between the bird and the pipe but the agent was not learning correctly. It would always learn that jumping is the best option and kill itself. The inclusion of velocity into the state space helped with learning but significantly impaired the engines ability to run the game. At this point the state space had become 14,000 states as a combination of all of the y differentials and velocity and it still was not able to play the game without eventually learning a bad policy. At this point the approach to the Artificial Intelligence was reevaluated.

7 It was decided that switching to a path finding algorithm would be more efficient on both the game engine and the Artificial Intelligence. This was because at any point the Artificial Intelligence could see the next possible states at each tick. This meant that with a reward function based on general features of states nothing needed to be saved in memory or updated at each tick of the game. A breadth-first search was used to check the future possible states at each tick. After the functions were developed the a key was bound to a toggle that switched the AI on or off. The reward function that was used to determine the next possible state was fairly simple. First, either a top or bottom action function was called so it would know if the pipe was on the top or bottom of the screen.

8 Then it would calculate the location of the bird for the next two possible states. After returning the location the function would return whether or not to jump at the current state. This was based on a set distance under or over a pipe being the optimal distance to be away from the pipe. After all of this was implemented the final deliverable was complete. This consisted of a fully playable Flappy bird game by either a human or an Artificial Intelligence. When the AI was toggled on it could start playing from any location and as long as it did not die right away it could survive indefinitely using the path finding strategy. This allows the user to observe how well they can stay on an optimal path by comparing themselves to the AI. ANALYSIS OF RESULTS The project was completed to success.

9 The game both looks and feels like the original Flappy bird . All of the human controls work as intended and after spending a few hours testing all of the edge cases we could think of we did not find any bugs in the game play. The path finding algorithm also works as intended. It will survive indefinitely, we let it play for 2 hours and it was still going when we checked its progress. DISCUSSION After completing this project I have concluded that, when applicable, a path finding algorithm is generally superior to reinforcement learning. This is because it is far more time and space efficient to run. Reinforcement learning needs to save a set of states and rewards in memory to look up at each step and this must set must be constantly updated. It also must take extra time to learn the optimal path.

10 Path finding does not have the additional need of saving or updating states while it runs. On top of that, path finding will start at an optimal path so the run time to prove success is essentially nonexistent. CONCLUSION After recreating Flappy bird we learned a lot about what it takes to develop a game that includes an Artificial Intelligence. Building a game engine that could integrate with an AI was a challenging task in its own right. Then trying to make an agent that could play the game without losing was also difficult. We found that the best solution was to try to imagine the best possible path and then make an agent that would be able to follow that path. Even with this strategy it took a lot of testing to create an agent with the ability to play the game without dying.