Creating a game with dynamic difficulty and reinforcement learning.

Student: João Gabriel Basi Supervisor: Prof. Dr. Roberto Hirata Jr.

Introduction

Player versus environment (PvE) games, in contrast to player versus player (PvP) games, are games where the player fights several enemies controlled by artificial intelligences in order to fulfill the game’s objectives. In this style, developers commonly model enemies as autonomous agents, since they make decisions without human intervention.

The creation and balancing of agents occupies a good part of PvE game development, since a large portion of the game experience is provided by them. For the game to become interesting, it is desirable that the agents offer challenges easy enough so that the player does not get frustrated, hard enough so that they do not get bored, and that there are new challenges at each stage.

Motivation

Developing these agents can be a difficult and laborious task if traditional methods are used. It is necessary to consider all possible game situations and synthesize them into a complex algorithm. As a consequence, often either the game difficulty ends up above or below what was expected, or the algorithm ends up making decisions that were not foreseen during the development phase, making the player lose immersion in the game’s world.

Some authors cited in the work show through user experiments that games with dynamic difficulty are enjoyable to the player, however it is very hard to find games on the market that actually use such adaptation algorithms.

Objectives

This work aims to create a prototype of a PvE game for computers that can adapt its difficulty according to the player’s progression and mastery, in addition to a system that eases the creation of AIs for the game. For this, the game will have a system that identifies the player’s proficiency and adversary agents that can learn strategies through machine learning.

Since learning algorithms generally require a lot of processing, it is also necessary to add the restriction that the game’s processing must occur fast enough so that the reduction in frames per second is not noticeable, minimally impacting the player’s experience.

Furthermore, for the game to be as simple and portable as possible, it must not use information external to the program (such as the frames of the game window), data from physical sensors attached to the player, or information stored in the cloud.

Documents

Game

Story

In a fantasy world there are people who risk their lives exploring unknown places, such as forests, caves and ruins; such people are called adventurers. During their adventures they find the most fearsome monsters and the most cunning traps, and also find the most valuable treasures, forgotten in time by ancient civilizations. Some adventurers are famous throughout the nation for being brave and fearless. The protagonist is a young man who dreams of becoming an adventurer, but has neither the skill nor the money for it.

How to play

Arrow keys or WASD move the character, E interacts with NPCs and objects, SPACE attacks, I opens the backpack and numbers 1 to 4 use items from the quick-use bar.

The game is currently only available for Linux. Download and play the latest executable.

If it is not possible to run it, try one of the following solutions:

  • Change the file permission to executable using the command chmod +x gameapp-linux.AppImage.
  • Extract the executable’s content using the command ./gameapp-linux.AppImage --appimage-extract, enter the generated squashfs-root folder and run the AppRun file.
  • Check the AppImage format’s troubleshooting page.

Screenshots

Menu

City

Shop

Adventure

Subjective comments

About this work

Since high school I have always been interested in the process of creating games, so much so that this was the main reason I chose to study computer science. Already at university I met the extension group USPGameDev, where I learned and taught a lot about the subject. In the middle of the third year I got an internship in the area, which I fell in love with and kept interning until today (end of the fourth year). Given my trajectory it would be no surprise if my final thesis were a game, however during university another subject captivated me: machine learning.

The growing advance in AIs for games by OpenAI and DeepMind in recent years motivated me to combine the useful with the pleasant, however I was not very pleased with the fact that these AIs were produced only to explore the limits of the techniques, and not to evolve the existing techniques for creating AIs in games. That is when I had the idea of testing for myself how it is possible to create a game from scratch taking into account the existence of machine learning methods.

Since I learned the Q-learning algorithm in MAC0425 I had been thinking about using it to create AIs for games, and I saw in MAC0499 the opportunity to test this idea. As I have developed games for four years, both for leisure and professionally, during the course I developed a game focused on exploring the reinforcement learning mechanic as much as possible and implemented methods that help train these AIs.

As the project touched on several other topics (such as user experience, difficulty adaptation, AI performance, state machines, etc.) it was a challenge to make it not stray from scope and demand more time than available. To work around these problems, from the beginning of the project I thought about each thing that should be implemented and ordered them by priority, a method that helped a lot to prioritize important features and estimate the project’s duration as a whole. Several of the ideas I thought of were not implemented, as mentioned in the last chapter of the monograph, so I will try to continue developing this game after the course.

About the course

Overall I was quite surprised by the course, it gave me the opportunity to develop a lot personally and professionally. One of the positive points is that the BCC professors are open to the students’ suggestions, which is why the extension groups emerged and why the curriculum was modified in 2016. On the other hand, it would be interesting if some more advanced systems development course (such as MAC0332, MAC0413, MAC0467, MAC0470 or MAC0472) were mandatory, so more students would have a better notion of the job market.

Through USPGameDev I was able to express my desire to develop games, I learned from other people and got to know people outside the university who work in the area, which is why I am very grateful to it. In my opinion the course has been doing a great job supporting the existence of extension groups and recognizing that they play an important role in the undergraduate degree.

Courses I used in the project

  • MAC0425 - Artificial intelligence: The course introduced me to reinforcement learning and the Q-learning algorithm, which were essential to this work.
  • MAC0460 - Introduction to machine learning: The course helped me better understand how learning methods work. Specifically, I learned how neural networks work and how they are trained, which is also an essential part of this work.
  • MAE0515 - Introduction to game theory: To describe the interaction between agents (player vs. AI) it was necessary to use some knowledge about decision theory, which I learned in MAE0515.
  • MAE0119 - Introduction to probability and statistics & MAE0221 - Probability I: Both courses were important for me to understand how all the more complex algorithms used in this work work (such as Q-learning, neural networks and CAP) and for it to be possible to develop probabilistic algorithms (such as random graph generation).
  • MAC0110 - Introduction to computing & MAC0121 - Algorithms and data structures I & MAC0323 - Algorithms and data structures II: The three courses were fundamental to the development of the whole project. MAC0110 taught me to program, MAC0121 introduced me to data structures and MAC0323 showed me how to deal with object inheritance and how to organize code so it is more modular.
  • MAE0228 - Notions of probability and stochastic processes: The behavior of an autonomous agent is described as a Markov decision process. MAE0228 introduced me to this concept and helped me better understand how it works.
  • MAT0112 - Vectors and geometry & MAT0122 - Linear algebra I: Neural networks and the error backpropagation algorithm are based on matrix multiplication and inner product; the navigation in the space of functions by the network requires knowledge of vector spaces.
  • MAT2453 - Differential and integral calculus I & MAT2454 - Differential and integral calculus II & MAT0236 - Differentiable functions and series: The three courses were fundamental for me to understand the neural network algorithms.
  • FLC0474 - Portuguese language: The course helped me remember high school content and helped in writing the monograph and the presentation.

Courses that may be useful if the project continues in the future

  • MAC0328 - Graph algorithms: Since the adventures are graphs, the course provided algorithms that can be useful in developing more complex adventures.

Other courses that could have been useful if taken

  • MAC0346 - Programming for digital games: Probably the knowledge that would have been acquired in this course was already acquired through USPGameDev and the internship, but I think the course is important for people who want to have a notion of game development as a whole, since this knowledge can take a while to be acquired in practice.
  • MAC0322 - Software engineering: Could have been useful in organizing the software as a whole, from the design of the classes’ APIs to how they relate to each other.
  • MAC0426 - Database systems: Could have been useful in developing the game’s data persistence system.