Programming Challenge - Let's build some AI!
Hi everyone! In this challenge, we will build simple genetic algorithm.
The goal is to create genetic algorithm that will learn and output predefined text ("Hello World!").
The goal can be achieved with any language and you'll need just simple loops, collection and knowledge how to create and use objects, even beginners can try to complete this challenge.
How?
I'll try to explain it as best as I can. Genetic algorithms are approximation algorithms - they often do not find the best solution, but they can find very good solutions, fast. It's used when traditional algorithms are either way too slow, or they even don't exist. It's used to, for example, design antennas, or wind turbines. We will use it to write "Hello World".
First of all, we define our Entity
. It is solution to given problem, it can be list of integers that describe antenna shape, decision tree, or string ("Hello World"). Each entity contains the solution (string solution
) and fitness function. Fitness function says, how good our entity is. Our fitness function will return, how similar is entity solution
text to "Hello World" string.
But how will the program work? First of all, we will create list of entities List<Entity>
. We will make, for example, 1000 entities (randomly generated). Their Entity.solution
will be randomized string of length 11 (because "Hello World" is 11 characters long).
Once we have these entities, we will repeat following steps, until the best entity has fitness == 1.0
, or 100% similarity to target string.
First of all, we compute fitness function of all entities. Then, we will create empty list of entities of length 1000. Now, we will 1000-times pick two entities (probably weighted based on their fitness) and combine their strings. We will use the string to create new entity and we will add the new entity to the new list of entities.
Now, we delete old entities and replace them with entities we just made.
The last step is mutation - because what if no entity has the "W" character? We will never get our "Hello World". So we will go through every entity and change 5% (or whatever number you want) of characters in their solution to random characters.
We let it run for a while - and it is done!
So to sum up what we did:
entities <- 1000 random entities
while entities.best.fitness < 1:
for every entity: compute fitness
newEntities <- empty list
1000-times:
choose two entities from "entities", based on their fitness
combine solutions of these entities and make newEntity
newEntities.add(newEntity)
for every entity: mutate // Randomly change parts of their strings
print(entities.best.solution) // Hello World!
Now go and create the best, fastest, and most pointless, genetic algorithm we've ever seen!
Here is my C# solution. The code is long, so I'll give you a link instead. You can even run it right there.
Solution
Please note, that my solution is not optimal. There are some lines where I was too lazy to make it efficient and breeding should not be done this way. But it works and it could help you when you get stuck :-)
Here's a 'quick' python solution, also on tio.run as @Soptik used.
Code
The "combination" portion of the challenge was rather open ended and drastically changes the code, so I just went ahead and did what I felt was fun. After getting all entity fitnesses I simply allowed only the top 10% percentage of the population to reproduce. To reproduce, I simply randomly look through the entity list until I find two entities that are allowed to reproduce and then combine their solutions to make a new entity.
There are parameters at the top of the code if you want to play with them:
Only 7 generations to find solution, nice!
If you wanted to experiment with this further, you could try this:
Make world with some obstacles. Each entity is bird or something like this, trying to get from left to right without hitting an obstacle. The fitness function is based on maximum
x
position of each bird. The solution could be, instead of string, list of numbers, where each number indicates, if the bird turns left, right, or flies straight.I made it and it looks really good, especially when you watch entities learn how to get through the map and then you add new obstacles to their path.
That sounds fun, maybe I'll check it out tomorrow when I have more free time.
That could make an interesting ascii screensaver :)
Here is my basic python solution. I have never done anything like this and I think its pretty neat, so thanks for the challenge!
So intimidated by the code that’s been posted so far and the challenge, lol.
I think I understand how some of the code works, but when I try to make my own from scratch or reverse engineer it, I get so lost.
I’m gonna keep cracking at this while also going through some basic python exercises. This is so much fun!
If you find yourself at a loss, feel free to check out some of the other challenges that have been posted to get some extra practice in. There's even a classic FizzBuzz problem :)
I know you just started with programming, do you know how to debug? Google "[name of your editor] debugging", it'll help you a lot
If you get stuck, just ask me (or someone else here), we will help you :-)
For now, I’m mostly getting hung up on syntax. I just learned how to use for x in/not in y, lol.
Don’t be surprised if there are some zombie posts in the older challenges in a few days.
Many of the challenges are being drawn from Project Euler, which is a great way to practice programming either as a new programmer or simply learning a new language. I'd definitely recommend trying out some of the earlier problems as you get started.
The first few problems can be easily brute forced and just test your syntax, but it quickly moves to more thought provoking problems that require a reasonable approach to find the solution in a timely fashion.
Thanks for pointing me there!
I tried the first few and I feel like I’m starting to get the hang of it. I found this place that has some solutions and when I looked I was like, ‘Wow, I am doing caveman Python’ 😂!