3 ms·
I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like the
by machrider 17y ago
I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like they stop progressing. Haven't seen 11 yet.
Score: 12
2 3 0 1 3 2 1 2 2 3 1 2 0 3 1 3 0
2 1 1 2 2 1 1 0 3 3 3 3 3 2 0 0 0
2 2 1 1 0 3 3 3 1 0 2 0 1 3 3 0 2
3 2 0 1 1 1 0 3 2 1 3 0 2 2 0 3 1
1 2 1 3 1 0 2 2 0 2 0 0 3 3 1 1 0
1 1 3 3 0 2 2 0 0 1 3 1 0 2 3 1 2
3 2 3 0 2 1 0 0 0 0 1 2 1 3 2 1 3
1 3 3 2 3 1 0 1 2 2 0 3 0 1 2 0 2
2 0 2 1 3 0 3 1 0 2 3 1 2 0 0 1 3
3 0 2 0 1 3 1 2 3 3 2 1 1 2 2 0 0
0 0 2 3 2 3 2 0 2 1 0 3 1 1 1 3 3
2 0 1 3 3 0 2 3 3 0 1 1 0 1 2 2 1
0 1 0 2 1 0 2 3 1 3 2 2 2 1 3 0 3
3 2 2 2 0 2 0 1 1 1 1 3 3 0 3 2 0
3 3 0 3 2 1 3 2 1 0 0 1 2 0 1 2 2
1 3 3 0 0 3 1 3 1 2 0 2 3 2 0 2 1
0 1 3 0 2 2 3 1 3 2 2 0 0 0 1 3 1
Edit: I can't reply to you, so...
http://pastebin.com/m33bccec1 http://pastebin.com/m33bccec1
It's not pretty, but I did a few things. Instead of taking the top n candidates and breeding them randomly, I kept all of them (NUM_STATES 200 and KEPT_STATES 200), but weight them according to score. So the best scores have the highest chance of passing their DNA down to the next generation, but the occasional loser gets lucky too.
Mutation is also weighted, so the most likely number of mutations is zero, but it's possible to have up to 4. Increasing this value made the performance go down, but it's also possible that there is no way to get to a solution by incrementally tweaking a decent attempt. Which could explain why I'm stuck at 12.
There are a few optimizations that may or may not make a difference, for instance in the scoring function. I think the pick_best_states function was not actually picking the best states. If you had two states with the same score, the first one is kept, but the next one is not. I fixed this. The stupid thing is, with NUM_STATES and KEPT_STATES at 200, it's basically an n^2 sort now. I never bothered to improve that.
Finally, compiled with -O3 and let 'er rip.
- DarkShikari 17y agoLink to a diff of your fixes/tweaks? I've only got to 30 here running 8 instances of mine. (Also, I imagine this could probably benefit from a really fast PRNG, like an LCG.)
- lkozma 17y agoSomething that might help would be to have the grids in some sort of canonical form: as swapping rows and columns doesn't change the score, for every configuration there is a reordering such that the whole grid value is minimal (i.e. if we read out as a 279 digit number). Intuition says that if grids were brought in such a canonical form, recombination might work better.
- ganley 17y agoI'm not sure minimizing the score (at least, until you get to 0) is interesting, but anyway, I wrote a simple hill-climbing-with-random-perturbation routine and let it run over and over for the last couple of days. So far my best has a score of 10: 12032213310013002 21301001102213023 30120303220111321 03330220131122010 22313133001012230 03123321011233102 20313010123321102 03022111302120233 31232100023232131 03201103213001212 11000232021331223 20221213031300031 13130132102302302 31103210230220313 12310021322030311 21012022213103330 12201332333120100