The 17x17 challenge. "Worth $289.00. This is not a joke." • Hacker News Board

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#71

Post by machrider » Tue, Dec 01, 2009, 7:23 PM UTC

DarkShikari wrote: post #61

machrider wrote: post #54

Earlier quoted context omitted.

Out of curiosity, what's the lowest score you've seen on 17x17 so far?

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…

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."

#72

Post by ganley » Tue, Dec 01, 2009, 7:29 PM UTC

DarkShikari wrote: post #48

scythe wrote: post #47

Earlier quoted context omitted.

I've got a script running right now that should be able to color everything by a sort of random walk. It colors around 230 nodes quickly and then slows down, so I suppose I'll find out soon enough. edit: nah, at this rate it won't finish. source here for those interested; you probably just need to iterate over the remaining empty values in a more effective way than I am: http://ctrl-v.org/3708

I wrote a simple genetic algorithm in C, took about 30 minutes, but I suspect a break-it-down approach starting at small blocks and working up might work better. It did 13x13 really fast but I have a hunch it might not work very well for 17x17... ( Link: http://pastebin.com/m51149dd9 )

This is a class of problems that Monte Carlo optimization (GA's, simulated annealing, etc.) typically can't solve, because almost-solutions are generally really deep local minima that the search machinery can't climb out of.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#73

Post by DarkShikari » Tue, Dec 01, 2009, 7:40 PM UTC

machrider wrote: post #71

DarkShikari wrote: post #61

Earlier quoted context omitted.

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…

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…

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."

#74

Post by cjg » Tue, Dec 01, 2009, 9:23 PM UTC

cjg wrote: post #68

brent wrote: post #14

Earlier quoted context omitted.

A related and unsolved question (and thus legitimate) could be: what is the smallest c such that 1000x1000 is c-colorable.

According to http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf c would be either 17 or 18.

Sorry, misread the parent post.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#75

Post by lkozma » Tue, Dec 01, 2009, 11:42 PM UTC

machrider wrote: post #71

DarkShikari wrote: post #61

Earlier quoted context omitted.

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…

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…

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."

#76

Post by PieSquared » Wed, Dec 02, 2009, 2:08 AM UTC

mshafrir wrote: post #57

PieSquared wrote: post #5

I know the professor who writes this blog, Bill Gasarch. I was thinking of interning with him (at our high school, we do an internship + report about it in our senior year), but then decided against it because the math is a bit too abstract and unapplicable to (as Gasarch would put it) make me "properly enthused". He seems like a great guy. Anyway, while I haven't read the entire thing, I would suggest reading the bo…

magnet program?

Yup, it's the Montgomery Blair High School Magnet Program - it's in Silver Spring, Maryland. The funding cuts are kind of hurting it, but it's a very good education, especially if you put your own effort into it too.

(Are you, perhaps, somehow associated with this or another magnet program in the MD area?)

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#77

Post by ganley » Thu, Dec 03, 2009, 1:35 PM UTC

machrider wrote: post #71

DarkShikari wrote: post #61

Earlier quoted context omitted.

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…

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…

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."

#78

Post by mshafrir » Wed, Dec 23, 2009, 6:56 PM UTC

PieSquared wrote: post #76

mshafrir wrote: post #57

Earlier quoted context omitted.

magnet program?

Yup, it's the Montgomery Blair High School Magnet Program - it's in Silver Spring, Maryland. The funding cuts are kind of hurting it, but it's a very good education, especially if you put your own effort into it too. (Are you, perhaps, somehow associated with this or another magnet program in the MD area?)

I graduated from the Magnet program in 2000.