Intro to ML with Procedural Content Generation

Introduction

I have been reading this book on Procedural Content Generation and its integration with ML. As I go through this book, I will try my best to implement the concepts we go over in small, easily implementable examples. In this chapter, we will start our investigation of using ML in a PCG setting by approximating a platformer level with a regression model.

The Notebooks used in this article can be found in the below repository.

PCGML/intro_MLPCG at master · mattmacf98/PCGML

Framing the Problem

In this chapter, the book introduces us to our first problem where we will use some ML, we want to model a platformer level. The first section of this chapter focuses on how important framing the problem space is.

If we took the above image and had a very naive task of “take this input image and create a level generator” we may try to implement some fancy vision model with some recurrent network architecture. However— if we peel back the problem — we realize that this level is simply a bunch of y values for each x position

We can go one step further and show that these are just points in 2D space

y_values = np.array([1,1,1,2,2,1,1,2,3,4,1,1])
x_values = np.array(range(len(y_values)))

plt.plot(x_values, y_values, marker='o', linestyle='')
plt.ylim(0, 6)
plt.show()

Now this problem becomes “Given a set of (x,y) coordinates, find a function which best models these points”. This complex vision problem just became a very simple regression task.

Regressions

In regression calculations, we are trying to find the weight matrix W such that we minimize the difference between Y and XW. We do this by setting (XW — Y)² = 0 and getting the derivative where it equals 0 (indicating the point at the bottom of the parabola). This means we are solving W = (X^T X)^-1 X^TY.

We also want to try a couple different models with different numbers of features in X to see what model performs well without overfitting.

We will split our data in train and validation sets so we can test our model after training is done.

indices = np.arange(len(y_values))
np.random.shuffle(indices)

num_validation = 3 

validation_indices = indices[:num_validation]
training_indices = indices[num_validation:]

x_validation_values = x_values[validation_indices]
y_validation_values = y_values[validation_indices]

x_train_values = x_values[training_indices]
y_train_values = y_values[training_indices]

Linear regression

We will start with the easiest regression — linear.

X_train = np.vstack([x_train_values, np.ones(len(x_train_values))]).T
m, b = np.linalg.inv(X_train.T @ X_train) @ X_train.T @ y_train_values
y_pred = m * x_values + b

plt.plot(x_train_values, y_train_values, marker='o', color='red', linestyle='')
plt.plot(x_validation_values, y_validation_values, marker='o', color='blue', linestyle='')
plt.plot(x_values, y_pred, color='blue', label='Linear Regression Line')
plt.ylim(0, 6)
plt.show()

We calculate our predicted y values and plot the line for them. Our y_pred has a very familiar equation of y = mx + b (a line). We plot the entries in our train set in red and the ones in the validation set (which we did not use in computing y_pred) in blue.

Below is what our predicted level would look like

We can compute the loss of this regression on the training and validation data using simple Mean Squared Error.

y_train_pred = m * x_train_values + b
train_loss = np.sum(np.pow(y_train_pred - y_train_values, 2))/len(x_train_values)
print(f"Train Loss: {train_loss}")

y_validation_pred = m * x_validation_values + b
validation_loss = np.sum(np.pow(y_validation_pred - y_validation_values, 2))/len(x_validation_values)
print(f"Validation Loss: {validation_loss}")

Train Loss: 1.0229468599033817
Validation Loss: 0.14803437653154108

Quadratic

We will now perform a very similar analysis, but we will give our model one extra variable to use in trying to fit the line.

X_train = np.vstack([np.pow(x_train_values, 2), x_train_values, np.ones(len(x_train_values))]).T
a,b,c = np.linalg.inv(X_train.T @ X_train) @ X_train.T @ y_train_values
y_pred = a * np.pow(x_values, 2) + b * x_values + c

plt.plot(x_train_values, y_train_values, marker='o', color='red', linestyle='')
plt.plot(x_validation_values, y_validation_values, marker='o', color='blue', linestyle='')
plt.plot(x_values, y_pred, color='blue', label='Quad Regression Line')
plt.ylim(0, 6)
plt.show()

our X_train matrix now has an extra column of the x values squared. The line now takes the form y = ax² + bx + c.

Computing the losses

y_train_pred = a * np.pow(x_train_values, 2) + b * x_train_values + c
train_loss = np.sum(np.pow(y_train_pred - y_train_values, 2))/len(x_train_values)
print(f"Train Loss: {train_loss}")

y_validation_pred = a * np.pow(x_validation_values, 2) + b * x_validation_values + c
validation_loss = np.sum(np.pow(y_validation_pred - y_validation_values, 2))/len(x_validation_values)
print(f"Validation Loss: {validation_loss}")

Train Loss: 0.9174686497521143
Validation Loss: 0.15748605571285487

We can see that we did slightly worse against the validation set and slightly better against the training set.

6th Degree

Now we will give ourselves a lot more variability to play with in the graph

X = np.vstack([np.pow(x_train_values,6),np.pow(x_train_values,5),np.pow(x_train_values,4),np.pow(x_train_values,3),np.pow(x_train_values,2), x_train_values, np.ones(len(x_train_values))]).T
a,b,c,d,e,f,g = np.linalg.inv(X.T @ X) @ X.T @ y_train_values
y_pred = a * np.pow(x_values, 6) + b * np.pow(x_values, 5) + c * np.pow(x_values, 4) + d * np.pow(x_values, 3) + e * np.pow(x_values, 2) + f * x_values + g

plt.plot(x_train_values, y_train_values, marker='o', color='red', linestyle='')
plt.plot(x_validation_values, y_validation_values, marker='o', color='blue', linestyle='')
plt.plot(x_values, y_pred, color='blue', label='6th Degree Regression Line')
plt.ylim(0, 6)
plt.show()

We nearly perfectly fit the train data (red) but do pretty poorly on the validation data (blue)

y_train_pred = a * np.pow(x_train_values, 6) + b * np.pow(x_train_values, 5) + c * np.pow(x_train_values, 4) + d * np.pow(x_train_values, 3) + e * np.pow(x_train_values, 2) + f * x_train_values + g
train_loss = np.sum(np.pow(y_train_pred - y_train_values, 2))/len(x_train_values)
print(f"Train Loss: {train_loss}")

y_validation_pred = a * np.pow(x_validation_values, 6) + b * np.pow(x_validation_values, 5) + c * np.pow(x_validation_values, 4) + d * np.pow(x_validation_values, 3) + e * np.pow(x_validation_values, 2) + f * x_validation_values + g
validation_loss = np.sum(np.pow(y_validation_pred - y_validation_values, 2))/len(x_validation_values)
print(f"Validation Loss: {validation_loss}")

Train Loss: 0.003188955553657004
Validation Loss: 38.325178862175285

We can see the training loss is incredibly low but the validation loss is quite high.

Perhaps our perfect model lives somewhere in the 3rd-5th degree?

Conclusion

In this article we took a very complex Procedural Content ML Generation problem of modeling the structure of a platformer level and re-framed it into a very simple regression problem. We split our data into train and validation sets to evaluate a few different models. We saw that creating a good model requires striking a balance between under-fitting the data by not providing enough variability and overfitting the train data by providing lots of variability which then makes the model unable to generalize to data outside the train set.