Weekly challenge of 2015-01-09: Genetic Algorithms

GitHub repository

Sandbox post for this week's challenge

then thank you so much more for all the work you've put into this

spec golf

Google Doc with spec draft

I love that we still get submissions 4 days in

with just empty, walls, traps, you could learn which cell is what and then just solve the problem locally. with teleports, you can't decide locally if it's safe to use one (if it sends you outside your field of view)... you have to learn it through evolution

Individual scores: [0, 27, 71349, 3, 2, 89915, 0, 37899, 73682, 3, 1, 0, 2800789, 6236, 38153, 93375, 0, 94, 0, 0]
On average, your bot got 160576.4 points

TODO: add todos

lets first finalize on spec and then discuss about implementation shall we ?

@NathanMerrill no one knows what the nodes in a neural network represent

Someone with way too much time on their hands needs to summarize decisions that were locked in and maintain a list for those of us who can't be actively here for 6 hours on end.

I like the death mechanism

@NathanMerrill I can see it now. Luigi Wolf. Mario Wolf. Yoshi Wolf

there should be a number of games tested column

The only feedback loop passes through the DNA, and the only means of winning the game is to let the controller kill and breed your rats until the assumptions they make about the reliability of the informations contained in their DNA become true for a sufficient number of specimens.

So basically, until the controller (which has the knowledge you lack of which color is what) sends you some feedback, you can chop and mix the 25 colors around all you want, you will be none the wiser.

Now if you plan on using a network with no feedback, the only added value would be the ability to correlate informations extracted from the 25 neighbouring cells. These cells have been carefully designed to look like white noise (all colors are practically equiprobable, even though the track is reworked a bit to insure a viable path exists from all possible locations, but that is certainly not enough to identify which color is which with a statistical analysis).

To work as such, a neural network would have to get a measure of the success of a given configuration. In the context of this challenge, the only two metrics of sucess are (1) the fitness score (i.e. the horizontal position of the track and number of completed runs) and (2) the death of a rat. Neither of these is accessable to the player, so you can grab your weights and kiss your feedback goodbye.

Dang...My rodents are too successfull.

right, the idea is if you are cheating it should be on purpose

frankly I'm not sure the controller is the bottleneck here. Consider the breeding process, it's only called 10 times per turn, while the population of rats will typiccally be a few hundreds. It means the player's code is the real bottleneck. And when your rats start to proliferate (they can reach a population of tens of thousands), the controller code does little more than call the player's code.

What could work is a neural network that takes the same input as the current bots, but is allowed to have persistent memory (to store the weights). This could be setup with little work. You would just have to modify the controller to let it pass a specimen identifier, so that you can associate the neural network memory to it

lol, be nice

Hi guys! I had an idea about score stability. You could have the controller compute the current mean after each turn, watch the relative variations over the last few dozen of turns, and stop when they remain within some limits. What do you think?

reddit.com/r/MachineLearning/comments/2t7ezl/…

lol I was joking about that - it's a friendly game so discussion is fun

we've got more stars than CH! :)

each coordinate refers to the surrounding squares

@TAbraham but seriously, I'm considering trying to make a layered neural network and reuse the weights so I can fit more into the genome

my approach was to print the seed of each board to console, in case it needs to be reproduced

we're replacing the arithmetic mean with a geometric mean

the problem with the geometric mean is 0 scores

no problem, your exam has priority ;)

with the breeding, do we include newly bred specimens? i.e. can a specimen we just create breed immediately? (spec implies yes, as did Python controller last time I checked)

(also, they wouldn't know if their changes are any improvement until they break non-zero scores)

There's already lots of scope for ambiguity

The finish line is column 49

If your bot says "go right" regardless of what the genome looks like, then your specimens will never learn, they will just always go right. If you choose a different approach, then the direction they choose will depend on the genome, allowing them to change behaviour for different genomes

yuck, the python magic numbers are randomly scattered through different files

Running board #1/1
0% 0.00799989700317 sec - 0 points - Population: 25
1% 5.04200005531 sec - 3 points - Population: 376
2% 13.0009999275 sec - 6 points - Population: 350
3% 20.5580000877 sec - 18 points - Population: 363
4% 28.4819998741 sec - 32 points - Population: 331
5% 36.0509998798 sec - 50 points - Population: 356
6% 43.9849998951 sec - 74 points - Population: 357
7% 51.7779998779 sec - 121 points - Population: 366
8% 60.1019999981 sec - 265 points - Population: 422
9% 71.2379999161 sec - 593 points - Population: 468

@TAbraham training them would be adjusting the weights. You can also use genetic algorithms to adjust the connections and the number of nodes. The more different things you are changing the less chance of getting meaningful results, but it's possible (we are examples of neural networks where both the shape of the network ad the weights are the result of genetics)

basically you've got a "population" of candidate "solutions", where each individual has a genome (just a binary string). then you evaluate how each individual performs, kill off the worst ones, keep the best, and then you cross breed them (by mixing their genomes) and mutate them (by flipping some bits) to get a new generation. rinse and repeat.

@TAbraham I think the description from BoxCar2D is pretty good: boxcar2d.com/about.html

@TAbraham The random bot doesn't use the genome, just chooses a random move, so it can't improve. The idea is that people will submit code that takes the genome and the 5x5 view of the surrounding squares, and outputs a move.

@TAbraham It will always take a while to run because it's running 10000 turns

I guess we can invite comments requesting new language controllers, as long as we have a few to start with

I was pointing out that rooms are frozen automatically. Just wanted to make sure that wasn't a waste of typing.

If we pass the dna and vision as strings they won't have access to the specimen to read its bonus