Basic strategy: how do you get into the top 10?
Posted: Sun Dec 07, 2008 5:46 pm
Hi!
I'd like to ask whether any of the top scorers in this puzzle would be willing to give some hints as to how their solutions work.
I started out with a straightforward brute force approach; this got me to about level 50, when it became clear it was too slow. Technical optimizations and a multi-threaded implementations only got me a few levels more. Then I implemented first one, then another method to identify unworkable solution paths early, in order to reduce the branching degree. This resulted in massive speed improvements, but currently, at level 130, it looks like it's not enough to get me much further, certainly not to level 300 or 600 as some of you have managed.
So how do you do it? Do you use the same basic approach and have simply found more and better ways to eliminate unworkable branches? Or do you use a fundamentally different approach?
I tried using a hashtables to find recurring patterns, but they were so rare it didn't help. I also thought about partitioning the board into "territories" that have to be connected so that complexity would grow only with the number of territories (or possibly their entry points) rather than the much larger number of cells, but I'm pretty sure that can't work, since an entry point into such a territory can be eliminated by the coil passing it, thus making any algorithm depending on such entry points flawed.
I'd like to ask whether any of the top scorers in this puzzle would be willing to give some hints as to how their solutions work.
I started out with a straightforward brute force approach; this got me to about level 50, when it became clear it was too slow. Technical optimizations and a multi-threaded implementations only got me a few levels more. Then I implemented first one, then another method to identify unworkable solution paths early, in order to reduce the branching degree. This resulted in massive speed improvements, but currently, at level 130, it looks like it's not enough to get me much further, certainly not to level 300 or 600 as some of you have managed.
So how do you do it? Do you use the same basic approach and have simply found more and better ways to eliminate unworkable branches? Or do you use a fundamentally different approach?
I tried using a hashtables to find recurring patterns, but they were so rare it didn't help. I also thought about partitioning the board into "territories" that have to be connected so that complexity would grow only with the number of territories (or possibly their entry points) rather than the much larger number of cells, but I'm pretty sure that can't work, since an entry point into such a territory can be eliminated by the coil passing it, thus making any algorithm depending on such entry points flawed.