One of the workshops in Rasta Summer School 2022 was named Artificial Intelligence and its content was mostly about evolutionary algorithms, In particular, genetic algorithms. Students learned about the core concepts of a genetic algorithm. Concepts like population, natural selection, mutation, crossover and fitness.
The following games are implemented with the help of a library called P5JS and are intended to help students get intuition about the concepts of genetic algorithms.
This one is a pretty simple game in which the player has to guess a password. After every 7 trials, the player gets a score for each guess. The score is the number of letters which are exactly correct (For example, if the password is "apple", "aleppe" gets score of 2 because of a_p__ which is present in the guess).
In this section, students watched a brute force algorithm trying all 10 letter long possible passwords and realized the approach wouldn't work simply because the size of the set of all possible passwords is exponentially large.
Lastly, students come up with a genetic algorithm to solve this problem more efficiently. This game is the implementation of their algorithm.
The only difference is the fact that after every 200 trials we get a score(and not 7), and the password is now 26 letters long (which is much harder).
In this part, students are faced with the famous 8 queens puzzle.
Students first tried the original problem in the link above.
Just like the first game, students could see a brute force algorithm in action. This algorithm is also very slow for large(>4) sizes of the chessboard.
In the end, students came up with a genetic algorithm to solve this problem.
The last problem students had to solve was Travelling-Salesman Problem. TSP is a NP-hard problem in computer science. This time, students also tried the problem themselves and then came up with a genetic algorithm to solve it.
A notable difference in the implementation of the genetic algorithm for TSP was the mutation algorithm. In this game, students had to apply a new type of mutation called inversion in order to eliminate crosses in the TSP path.
This game is TSP in action. Students should help a tourist visit all capitals of Iran in an efficient way.