{"id":112,"date":"2019-11-08T16:51:37","date_gmt":"2019-11-08T15:51:37","guid":{"rendered":"http:\/\/localhost\/CvWebsite\/?p=112"},"modified":"2020-12-15T16:16:19","modified_gmt":"2020-12-15T15:16:19","slug":"genetic-algorithm-doodle-jump","status":"publish","type":"post","link":"https:\/\/oussamaameur.fr\/index.php\/2019\/11\/08\/genetic-algorithm-doodle-jump\/","title":{"rendered":"Genetic Algorithm : Doodle Jump"},"content":{"rendered":"\n
\n

Genetic Algorithm : Doodle Jump<\/p>\n<\/div><\/div>\n\n\n\n

<\/p>\n\n\n\n

The project consists of 2 main components: A minimalist Doodle Game type of game, playable by the user as well as by a genetic algorithm. The latter must improve the performance of a bot each new game.<\/p>\n\n\n\n

Game Description<\/h2>
<\/div><\/div>

<\/p><\/div>\n\n\n\n

Doodle jump is a mobile game. The player controls an alien that needs to rise. Thus, he needs to bounce from platform to platform. The character bounces automatically and the player only needs to focus on the direction (left, right, stationary). There\u2019s also enemies and special platforms, but because of a tight schedule, we couldn\u2019t implement them.<\/p>\n\n\n\n

Game Functions<\/h2>
<\/div><\/div>

<\/p><\/div>\n\n\n\n

We have three commands: Left, Right and Down (landing). We have a mid-air time, after which the player falls down unless he hits a platform to reset his mid-air time. Every time the player reaches a platform, the score increases, and the platform loses its ability to grant points. When the Y-pos of the player equals 0, the player dies.
The platforms are generated randomly but they still need to be close to each other to be reachable by the player. When the players reach a certain height, everything scrolls down and platforms that are below a certain height are modified so they reappear at the top. Click here <\/a><\/span>to see a sample of the code<\/p>\n\n\n\n

Genome<\/h2>
<\/div><\/div>

<\/p><\/div>\n\n\n\n

We created a 3x3x3 matrix that contains random float numbers [0;1]. They represent the probability of going left, right or down according to the X-position relative to the next platform and the mid-air time left. Click here <\/a><\/span>to see a sample of the code.<\/p>\n\n\n\n

Crossovers and Mutations<\/h2>
<\/div><\/div>

<\/p><\/div>\n\n\n\n

The crossover function generates a 3x3x3 matrix randomly filled with 0 an d 1 as a mask. It also generates an \u201cinverted\u201d mask by switching the state of each cells (0 to 1; 1 to 0). It then selects the two best players by their scores and applies the mask to them. Therefore, you will have 2 matrixes with blank cells that can merge into one complete gene.
The mutation function selects a random part of the gene and changes its value, it has 3 options to pick randomly from: no mutation, slight mutation or complete mutation. Click here<\/a> <\/span>to see a sample of the code.<\/p>\n\n\n\n

Conclusion<\/h2>
<\/div><\/div>

<\/p><\/div>\n\n\n\n

Genetic Algorithms are powerful tools for the optimization of a function’s parameters. However, I think that backing it up with another type of Artificial Intelligence, such as a neural network or reinforcement learning, could help improve the performances even further.<\/p>\n\n\n