Create an AI opponent for your game using a genetic algorithm

A while ago I created a TypeScript 8-ball pool game.
While I was very pleased with the outcome, I was missing someone to play my game against.
That's when I decided to add an AI opponent to my game.

So take a look at the image below.
try to think how would you write an algorithm that finds an angle to shoot the cue ball towards and also determines how hard.

We have to think outside the box here, there are endless possibilities to set these two parameters - angle and pace.
A bunch of if-else statements probably won't do the job.

Random simulations

Let's say that we have a function called "shoot" that shoots the cue-ball and displays it to the player, and another one called "simulate" that simulates the shot and returns a score for how well it went.

We can calculate the score based on the information that we have about the game at the given moment.
If a foul occurs during the simulation we should decrease the score, and if a correct ball got inside a pocket we should increase it.
We can also combine some heuristics such as "A simulation deserves a better score when the balls on the table are further away from each other."

One approach is to run multiple simulations and eventually pick the one that had the best outcome.
The code for that would probably look similar to this:

const MAX_PACE = 75;
const MAX_ITERATIONS = 100;

let bestParams = null;
let highestScore = 0;

// Run simulations
for(let i = 0 ; i < MAX_ITERATIONS ; i++) {

    const params = {
        angle: (Math.random() * 2 * Math.PI),
        pace: (Math.random() * MAX_PACE)
    };

    const score = simulate(params);

    if(!bestParams || score > highestScore) {
        bestParams = params;
        highestScore = score;
    }
}

// Play
shoot(bestParams);

The problem with that approach is that our AI doesn't get any better from one simulation to another. We completely rely on luck.

Genetic Algorithm

The basic idea of genetic algorithms is knowledge transfer from one generation to the next and improvement over time.
Similar to lifeforms, we want our AI to evolve and become better at the task we give him to do.
To make our AI better over time, we can take in each iteration the best set of parameters we had so far and mutate them just a bit.
It's important that once in a while we create a completely random set to add some diversity. That helps in cases our best set of parameters is not that successful.

const MAX_PACE = 75;
const MIN_PACE = 1;
const MAX_ITERATIONS = 100;
const DIVERSITY_INDEX = 10;

let bestParams = null;
let highestScore = 0;
let paceMutation = 0.005;
let angleMutation = 0.001

for(let i = 0 ; i < MAX_ITERATIONS ; i++) {

    let angle;
    let pace;

    if (i % DIVERSITY_INDEX === 0) {
        // Randomize
        angle = (Math.random() * 2 * Math.PI)
        pace = (Math.random() * MAX_PACE);
    } 
    else {
        // Mutate
        angle = bestParams.angle;
        angle += angleMutation * (Math.random() * 2 * Math.PI - Math.PI);

        pace = bestParams.pace;
        pace += (Math.random() * 2 * paceMutation) - paceMutation;
    }

    // Limit pace
    pace = pace < MIN_PACE ? MIN_PACE : pace;
    pace = pace > MAX_PACE ? MAX_PACE : pace;

    const params = {
        angle,
        pace
    };

    const score = simulate(params);

    if(!bestParams || score > highestScore) {
        bestParams = params;
        highestScore = score;
    }
}

shoot(bestParams);

That's it, that what it takes to create a simple, yet very powerful AI that knows how to play 8-ball pool.

You don't believe me?😜
Play the game by yourselves in the following link:
https://henshmi.github.io/Classic-8-Ball-Pool/dist/

Let me know in the comments if you were able to win against the AI and on which difficulty level. The difficulty level is determined by the number of simulations running in the background.

You can find the code for the game here:
https://github.com/henshmi/Classic-8-Ball-Pool
The code in the repository looks different from the examples above but the principles stay the same.

Enjoy!