-
-
screenshot of website
Name
Albert Kang (discord: albert kang#7099)
Inspiration
Artificial Intelligence has always been a fascination for me. I am taking a class on Artificial Intelligence at school right now and we have recently learned about genetic algorithms, which was my favorite unit by far. We used genetic algorithms to solve and decode substitution ciphers, which amazed me by how well the genetic algorithm performed. Before learning about genetic algorithms, I had no idea what they were, how they worked, and the fact that they existed. I hope that my project can teach others about what genetic algorithms are and how they work so that they may share the same fascination with genetic algorithms as me.
What it does
The website has three main buttons, one for starting a genetic process, another for continuing a saved genetic process, and the last one to display step-by-step the moves the best strategy in the saved genetic process makes after playing a game. A strategy consists of 6 numbers, 3 for coefficients and 3 for exponents. These coefficients and exponents are applied to 3 different heuristics that grade a Tetris board, which return a score for each board. These 3 different heuristics were found online and are height, bumpiness, and the number of holes. The height is calculated by adding the maximum height that a block is present for each column. Bumpiness is calculated by taking the maximum height of a column and comparing the difference between the maximum height of its neighboring columns. The number of holes is calculated for adding each time a blank that is below the maximum height for its column is present. A strategy is graded by letting it play 5 games and taking the average of the 5 scores it ends with. A strategy can play a game by grading every possible board based on the current piece it needs to place, and choosing the board that is most favorable to that strategy. A genetic process or algorithm starts by initializing a population of randomly generated strategies. Then it starts the process of breeding. To select which two strategies breed, it randomly pools a number of strategies twice to create two pools of strategies. The pools are then iterated through starting from the best strategy to the worst. It has a percent chance (75%) of choosing the current strategy as one of the “parents” and breaking the loop. This allows other strategies to get a chance to breed as well. After selecting two parents, breeding occurs, which takes 3 numbers from one parent and 3 from the other to create a respective unique strategy. There is, however, a chance (80%) for mutation where a small random number is added randomly to one of the six numbers of the new strategy. This allows for unique strategies to be created to avoid repeats. This breeding process continues until the next generation or population of strategies is full.
How we built it
I built this website by using mainly python scripts. I used a Django server to run these python scripts through HTML events and the GUI was created using JavaScript and CSS.
Challenges we ran into
One challenge I ran into was while coding the genetic algorithm, which took a considerably long time since I also needed to find a way to model Tetris at the same time. The specific problem I ran into was the genetic algorithm not improving over each generation significantly. I found online a solution to this problem was to add exponents to each strategy, which would lead to drastic changes. Another challenge I ran into was trying to run a python script through HTML events. I found a solution through Django, but had an extremely hard time trying to work with Django since it was my first time using anything like Django. I eventually figured it out and got the hang of it.
Accomplishments that we're proud of
An accomplishment I am proud of is being able to run python scripts through HTML events. I always struggled with this issue but previously, I would just give up and resort to coding in JavaScript. I am not familiar with JavaScript whereas Python is one of my most comfortable languages to code in, allowing me to be more efficient in coding and giving me a variety of options to code. This will be a major help to me in future projects as well. Another accomplishment I am proud of is how well my genetic algorithm worked. The highest score (not average of 5 games) I have ever seen scored by a strategy through my genetic algorithm was greater than 300,000, which is a considerably high score in Tetris.
What we learned
I learned how to run python scripts through HTML events, how to use Django, and the fact that whitespaces are automatically stripped in HTML, which was a nuisance when trying to display Tetris boards that relied on whitespaces for formatting reasons. I found a solution to the whitespace problem by using the " tag.
What's next for Tetris Genetic Algorithm Maker
I plan to add more user control over the genetic algorithm. This includes allowing the user to change certain parameters, such as the size of one population, the percentage chance that the best strategy is chosen in a pool of strategies, and the percentage chance that mutation occurs when breeding two strategies. Furthermore, I plan to let the user input their own strategies and watch them play as well, and add these to a genetic population list. Minor changes for front-end design include adding color to the tetras board. Finally, I plan to improve the efficiency of the genetic algorithm since it can take a long time at times for the genetic algorithm code to run.
Log in or sign up for Devpost to join the conversation.