Finally I’ve solved it, all 3 episodes. Man, what a relieve. It only took me about 6 months with an year break in the middle. Using C++. I had to go through almost all physics learned in school from this site:
I was determined to solve the task using Genetic Algorithm. I had to go through many tutorials, such as:
But I still couldn’t get my algorithm to converge. I enrolled in online course for the Genetic Algorithm:
Which took me about a month to complete to get deeper knowledge in the field.
I cannot imagine writing such an algorithm without visual debugging.
I had very difficult time coming up with good evaluation function also, used above 10 of those.
After above 100 iterations of my code my algorithm started to converge, this was AWESOME. But it was very slow…
I’ve started to analyze my solution using Visual Studio native profiler. And I’ve found out that I’m using very much memory and started optimizing it. I couldn’t get very good results until it hit me, I could use only 2 populations the current and the next after each crossover next becomes current and current is overwritten with next. And for this I had to rewrite again the whole solution.
The thoughessest puzzle of all 3 episodes was “Initial speed, wrong side” There I have some convergence to a local maximum and my algorithm needed above 400 populations to escape that maximum.
The puzzle for which biggest optimizations were needed, to get in the time frame, was “Cave, wrong side”. It passed for around 150 populations, but was slow
And also the biggest optimization was to reduce the use of STL to minimum.
After this optimizations I still didn’t get in time for all solutions until I found that I use too few genes in each chromosome. And BOOOOOM the tests and the submit passed
After that I took it further to pass the “Stalagtite” test form the tech.io tutorial. There 200 chromosomes were needed in each population and above 1000 populations.
I feel very proud of myself, to see all efforts paid off is one of the best feeling ever. The main lesson I learned from this: “Keep it simple” no need to overengineere something, no need of all C++ fancy syntax, at the end I solved the task using plain old C++. Never stop beliving