News for hackers. Stuff that matters.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by machrider on Tuesday December 01, 2009 @12:36AM (#969301)
Out of curiosity, what's the lowest score you've seen on 17x17 so far?
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Tuesday December 01, 2009 @03:51AM (#969472)
Down to 39:

    1 0 1 0 2 0 2 1 0 2 1 3 3 2 3 3 1
    3 3 0 3 1 2 3 0 0 1 1 1 2 2 2 0 1
    3 2 3 2 2 0 1 0 3 0 3 3 1 1 0 2 1
    0 3 1 2 1 1 2 3 1 0 3 0 0 3 2 0 2
    0 1 1 3 3 3 1 0 1 1 2 2 3 2 0 2 0
    3 1 2 2 3 1 0 1 0 3 0 2 0 3 0 1 2
    1 1 1 2 0 2 3 2 3 3 0 0 1 2 0 0 3
    2 2 0 0 3 1 0 1 3 1 3 0 1 2 1 3 2
    0 0 2 0 0 2 0 3 1 2 1 2 1 3 3 1 3
    3 2 2 1 0 3 0 1 1 0 3 1 2 0 3 2 3
    1 3 3 0 1 3 2 2 1 3 0 2 2 0 1 3 0
    2 3 2 1 2 1 1 2 0 0 1 0 3 0 2 3 3
    1 0 3 3 2 2 1 0 2 3 2 1 0 0 3 1 2
    0 2 1 1 0 3 3 2 0 2 2 3 0 3 1 1 0
    2 1 3 2 3 0 0 3 2 2 1 3 2 1 1 0 0
    0 2 0 1 1 0 3 3 2 3 3 2 3 0 2 1 1
    2 0 0 3 1 2 2 3 3 0 0 1 1 1 3 2 0
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by machrider on Tuesday December 01, 2009 @02:23PM (#970473)
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

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by ganley on Thursday December 03, 2009 @08:35AM (#974292)
I'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

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by lkozma on Tuesday December 01, 2009 @06:42PM (#971097)
Something 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.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Tuesday December 01, 2009 @02:40PM (#970524)
Link 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.)

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by lkozma on Tuesday December 01, 2009 @10:00AM (#969828)
34 here (after some tweaks):

  0 0 0 0 0 1 1 1 2 2 2 2 2 3 3 3 3
  0 1 1 3 3 0 1 2 0 1 2 3 3 0 2 2 3
  0 1 2 2 3 0 0 0 3 3 3 1 2 1 1 2 1
  0 2 3 3 2 1 3 3 1 1 0 0 0 2 3 2 1
  0 3 0 1 1 3 2 3 1 2 1 1 3 3 0 0 2
  1 1 3 2 0 3 0 1 3 0 1 2 3 2 2 0 2
  1 2 0 2 1 0 2 3 3 0 2 3 0 1 3 1 0
  1 3 0 2 2 2 3 0 2 1 0 1 1 0 1 3 3
  2 0 1 2 1 0 3 1 3 2 3 0 1 3 2 0 1
  2 0 3 1 0 2 2 1 0 1 3 2 0 1 0 2 3
  2 1 3 1 0 3 2 0 2 3 2 3 1 2 0 3 0
  2 3 1 3 2 1 0 2 3 3 0 1 2 0 0 1 2
  3 0 2 3 2 3 0 1 1 2 3 0 1 0 2 1 0
  3 1 2 0 1 1 3 2 0 3 0 2 3 2 3 0 0
  3 2 2 0 3 1 1 3 2 0 1 0 1 1 0 3 2
  3 2 3 1 3 2 1 0 0 0 1 0 2 3 2 1 1
  3 3 2 0 1 2 1 0 1 2 2 3 0 0 1 0 3
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Tuesday December 01, 2009 @01:35AM (#969353)
I think about 51, I haven't been saving the best so far. I'll tee it to a file from now on.

Edit: Oops, my random-restart code had an obvious bug. It's probably not very useful anyways, so I removed it.

http://pastebin.com/m63191b11

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by scythe on Tuesday December 01, 2009 @03:00AM (#969431)
Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by RiderOfGiraffes on Tuesday December 01, 2009 @07:52AM (#969626)
I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by abentspoon on Tuesday December 01, 2009 @11:46AM (#970056)
I've placed 74 using an IP solver

      1 1 . . . . . 1 1 . . . . . 1 . .
      . 1 1 1 1 . . . . . . . . . . . .
      1 . 1 . . 1 . . . . . 1 . . . . 1
      1 . . 1 . . 1 . . . 1 . . . . 1 .
      1 . . . 1 . . . . 1 . . . 1 . . .
      . . . 1 . 1 . 1 . . . . . 1 . . .
      . 1 . . . 1 1 . . 1 . . . . . . .
      . . 1 . . . 1 1 . . . . 1 . . . .
      . . . . 1 1 . . 1 . . . 1 . . 1 .
      . . 1 . . . . . 1 1 1 . . . . . .
      . . . . 1 . . 1 . . 1 1 . . . . .
      . . . . . . 1 . 1 . . 1 . 1 . . .
      . . . 1 . . . . . 1 . 1 1 . 1 . .
      . 1 . . . . . . . . 1 . 1 1 . . 1
      . . 1 . . . . . . . . . . 1 1 1 .
      . . . . 1 . 1 . . . . . . . 1 . 1
      . . . . . . . 1 . 1 . . . . . 1 1
The solver chokes on anything larger than a 6x6 grid, but I've had good luck adding one row at a time to a smaller solution.

http://pastebin.com/m4c4696af

edit: He mentions that he already found a size 74 set in one of the linked pdfs. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf