UselessGameDev logo UselessGameDev title

I let an AI design my couch

Wed 07 September 2022 #UselessGameDev
This text is a written version of the video above, with future plans to incorporate graphics and figures for illustration.
As I'm working my way through the backlog of videos that were published before this website, I suggest reading the article alongside the video for a comprehensive experience.

I’m moving into a new flat in a couple weeks, which is great because I will finally have enough room to get a couch so I can binge watch Code Bullet videos.

The only issue is, the apartment is located at the end of a long corridor. The corridor is 1m wide, and at some point there's a 90° right turn. I now need to find the biggest couch that can fit in that space.

A square 1m-wide couch would do, but I think we can do bigger.
A rectangle couch would do because it can turn, but if it's too large it will get stuck in the right turn.
A circle would turn nicely but I feel there's wasted space.

Luckily for me, this is actually a known math problem called the Moving Sofa Problem. Unfortunately for me, it’s a problem for which no proven answer has been found yet. There is a shape that is currently conjectured to be the best, as in, the largest that can go through a 1m-wide corridor with a right turn, but it was found empirically and there is no formula that proves it to be the best.

Today I'll attempt to design my empirical dream couch.

Genetic Algorithm

I think that a good empirical approach would be to try and approximate the best shape by using a Genetic Algorithm. To put it simply, the goal is to simulate evolution by generating a group of random shapes. Then having them go through the trial of moving through the corridor.

Then it's survival of the fittest, the fittest here meaning the shape that makes it the furthest along the corridor.

The best shapes of that first generation will then be selected to breed the next generation of couches, that will have similar properties as their parents but slightly tweaked.

This natural selection process means that over multiple generations, the couches should evolve towards a shape that's fitter to survive that specific trial of going through a corridor.

Shape Generation

Let's talk shape generation.

I've made a simple stadium shape with a segment at the center, and a bunch of vertices around that segment.
The center segment has a variable length.
The distance from each vertex to the center segment is also variable in length.

Each variable length will be a gene in our Genetic Algorithm. A single couch is defined by its list of genes, and should this couch be selected for reproduction, its children will inherit its set of genes, with slight mutations on top.

With this setup I think I can generate most shapes, including rectangles of different sizes, triangles, circles, or... weird thingies. I’m confident this technique is versatile enough to find my dream couch.

“Natural” Selection

So let's suppose I have a generation of... 15 couches.

They try and go through the corridor.

Most of them will get stuck at first, but that's okay. We need a piece of code that selects the best couches from this cohort, the ones that are fit to breed the next generation of couches. We’ll call it the fitness function.

This fitness function is rather simple:

public float ComputeFitnessScore(Couch candidate)
{
    flat score = GetClosestPointOnPath(corridorPath, candidate.transform, position); // Get 0-1 path completion

    return score;
}

Each couch gets a score that is the percentage of completion of the course. If they get stuck right away, they'll only score a few points, if they go all the way they'll get the full 100 points.

I'm worried this will encourage smaller couches though, as small shapes will go through the 90° turn no problem.

So I'm adding a new rule: once you get the 100 points for completing the course, you get a bonus that's equal to the area of the shape. The larger the shape, the more points you get. This should encourage them to not only evolve toward a couch that I can get into my apartment, but the biggest one at that.

public float ComputeFitnessScore(Couch candidate)
{
    flat score = GetClosestPointOnPath(corridorPath, candidate.transform, position); // Get 0-1 path completion

    if(score == 100)
    {
        score += candidate.Area;
    }

    return score;
}

So that's how we rank our population of couches. We will then select, let's say, the 3 highest-scoring couches of this generation as "champions".

Breeding

Our champions will breed a new generation of couches, and for this we have multiple options:

Crossover, is when we take two champions as parents and produce children with a mix of their genes. For instance, a child will get half the genes from parent A, and half the genes from parent B.

So let's breed champions A and B together, then B & C, then A & C, and generate... 2 children for each couple why not.

The other option we have is asexual reproduction, or Mutation. With this technique, we take a single parent and create a child that has the same genes, but with a certain chance of mutation that results in slightly different couches.

Let's say each of our three champions gives 2 offspring that way, and add them to our next generation.

That’s all nice, however there is a slight chance that all of these children are less fit than their parents, meaning their mutation makes them perform worse at the task of going through the corridor. To avoid losing the good genes of the parents, we reintroduce them into the new generation, just in case they would still be top ranking.

With that, we get to 15 couches, a full new cohort of couches, and we're ready to start again.

And again. And again. And again until we see the couches evolve towards fitter shapes, and the fitness score starts to reach a plateau.

The Great Showdown

And now it's time to show you how the simulation went.

It started with a terrible first generation, which was to be expected because the shapes were truly random at this point.

But over time, things started to get better.

You can see already after a few generations the shapes are a lot less random and we can expect them to evolve towards better shapes over hundreds or thousands of generations

Let’s jump to generation 77, where couches seem to have learned that having this sort of crescent shape makes it easier to turn, which allows to have larger shapes

By Generation 400, the crescent shape has become a round notch at the bottom, allowing the couches to turn easily even though they are way larger shapes than before.

We’re now at generation 609 and… I’m about to go to bed, I’ll leave this running overnight and check it again in the morning.

Taking a look at the area of the best couch of each generation so far, we see that it had a sort of logarithmic evolution, which is to be expected, however it also means we get diminishing returns so right now to get a significant improvement we need to wait a lot more generations.

And here it is folks, after 2660 generations of genetic evolution, my ultimate couch is ready.

Sure it’s imperfect, I mean with the course being symmetrical, one could expect a symmetrical shape to work, which means it could be larger in some corners, rounder in some other, and overall smoother.

But it’s the game, I have to accept the outcome.
I’m proud of my design. Ready to order myself an expensive custom-made couch.

... But oh, wait. I forgot.

The corridor has a second 90° turn before reaching my apartment. Except this time it's a left turn.

And our couch doesn't fit anymore.

Bummers. I guess it's back to square one.

Well not exactly square one. Our genetic algorithm approach is still valid, the only thing that changed is the trial. So we just need to adjust the trial to reflect the new environment.

The fitness function doesn’t need to change, we just need to adjust the path the couches will follow, and we're back to the simulation.

I thought about starting the new simulation from where the first one stopped, so we could see what changes the new environment would make to our champion couch, but I figured it would just get stuck in the second turn forever until it evolves by accident.

I’ll spare you the details and just jump to the result after a few thousand generations.

And here it is. My uh, mathematically optimal couch. I'm uh... happy I guess?

I hope you enjoyed this video and I'll see you in the next one.

Check these out

Music Credits