Overview

This is a billiard ball simulation game with integration of force simulation, collision detection, event handling, and adaptive AI opponent algorithm (the difficultest part of this project).

Keypoints

1. Use Open Asset Import Library (assimp) to load various 3d file formats into a shared, in-memory format, which supports not only .fbx and .obj files but also have a nice general compatability over 40+ formats and integration with C++ codes. (Some models are slightly adjusted using blender and 3dsmax for a better effect)
2. Handle the physics force simulation, process collision detection, and render object behaviors between physical entities, with optimized algorithm complexity and reliability tests to ensure a smooth user experience and stable system functions.
3. Real time shadows are dynamically rendered under each billiard ball for a better visual effects.
4. Design two game mode with respective game rule and global scoring mechanism.
5. Implement an adaptive AI opponent with intellginent behavior and adaptive features to select optimal shots and strategies according to different scoring rules. (The specs are explained in the following chapters)

AI Opponent Algorithm

To implement an AI opponent for billiards game, I consulted a number of papers to learn about successful methodologies, for which I combined and applied in this project using an adaptive approach.
“Running the Table: An AI for Computer Billiards” (Michael Smith, 2006), proposed an adaption of game search techniques to the continuous, stochastic domain of billiards. This paper deeply analyzed the gaming logic behind billiards game, that is to consider three factors affecting the quality of shots: contribution to goals, shots safety, and resulting state. It discussed and compared two search algorithms: probabilistic search (a special case of expectimax) and Monte-Carlo sampling search, with the following pseudocode:

Another paper “AI Optimization of a Billiard Player” (Jean-François Landry, Jean-Pierre Dussault, 2007) broken down the billiards simulation with optimization techiniques. It first defines the ball movements equation on a pool table:

• Sink aimed ball in the pocket with minimum speed.
• Prevent scratching of cue ball.
• Insure good repositionning of the cue ball for next shot.
• Insure the shot is legal (we do not hit an opponent’s ball first)

And this gives rise to the complete object function:

Genetic Algorithm Optimization

For the above algorithms we have discussed so far, the key is to find the most appropriate angle and force to shoot the cue ball. Given that nice analytical solutions are presented in the exsited papers, the random serach is an inevitable part of their algorithms, despite the complexity can be reduced by ignoring unnecessary parts from the mathematical computing results.
In this project, based on the presented analytical models, we take Genetic Algorthm to optimize the efficiency of search function, making the whole AI simulation and evaluation process even faster.
Similar to lifeforms, we want our AI to evolve and become better at the task we give him to do. And the basic idea of genetic algorithms is to utilize the knowledge transfer from one generation to the next and improvement the AI performance over each iteration. To implement this, in every iteration, we store the best sets of parameters we had so far and mutate them with a little variation and put them into next iteration.
But we should also consider to introduce a completely irrelevant random set to add some diversity into simulation, which could help to resolve overfitting issues and avoid falling into local optimization situation. The skeleton code of genetic algorithm is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

MAX_PACE = 0.5;
MIN_PACE = 0.01;
MAX_ITERATIONS = 150;
DIVERSITY_INDEX = 10;

bestParams = null;
highestScore = 0;
forceMutation = 0.005;
angleMutation = 0.001

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

    angle=0;
    force=0.05;

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

        force = bestParams.force;
        force += (Math.random() * 2 * forceMutation) - forceMutation;
    }

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

    params = {
        angle,
        force
    };

   score = eval(params);

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

simulate(bestParams);

Miscellaneous

1. The Billiards table and ball models are sourced from Sketchfab, with minor modifications to fit the scene by myself using Blender and 3dsMax 2022.

   

2. In proposal, an animated character referee of the game is suggested. Actually this was implemented, but with the introduction of AI opponent and relevant complicated algorithm, the system will become very laggy if trying to simutaneously render the animation of character with thousands of vertices in the same scene.
   So I have to split the character into independent scenes, but this reduces the logic relationship between them. They will only function separetely, so the existence of referee becomes meaningless. Considering the focus of this project is on AI algorithm, so this part is not included in the final presentation. However, here is a clip of video showing the work I have done to render the animated referee, which will behave differently according to the scoring status on game.

   Note that the animation of character can be dynamically switched without interrupting the physical simulation of bouncing balls, which was designed to correspond to the gameplay status of billiards.

3. References

• Assimp Library: https://github.com/assimp/assimp
• Academic Papers: “Running the Table: An AI for Computer Billiards” (Michael Smith, 2006), “AI Optimization of a Billiard Player” (Jean-François Landry, Jean-Pierre Dussault, 2007), “Billiard-AI” (Lukas Seglias, Luca Ritz)
• Github repositorys: Classic-8-Ball-Pool, Billiards