Basic strategy: how do you get into the top 10?

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'm not much further through than you are, and I doubt many other people have solved this puzzle this far in the way I did, but... When I found I could solve them by hand faster than my automated algorithm, I just did that, after making a nicer UI than the flash one (e.g. backtrack support). I got to level 160, I think (wherever I am now, not sure exactly) before getting distracted with other things to do. It was fun, though.

I found a lot of the things I implemented to detect failure sooner were actually slower to calculate than just continuing with the brute force. But this is one case where I think the data layout in my Python program was poor. e.g. for Runaway, I changed the data structures as well as the algorithm from time to time, and it made a big difference there.

I did have some good ideas for better ways to reduce the complexity and make larger boards more efficient to solve, but never implemented any of them. They're based on things I found myself doing mentally when solving by hand. The best idea I had was partitioning, as you said - I think it's very practical, if you do it right - but I haven't had time to implement anything.

The thing I've always found awkward with Mortal Coil is the endpoints, and generally the fact that the order of path segments matters. The endpoints make it hard to apply certain prunes, e.g. creating a dead-end, because that dead-end might be the one you're meant to end on.

(I'm actually below you, but that doesn't mean I still can't have points ;P)

As gfoot said, having herustics can help, but many of them will actually take more time to compute. On the ohter hand, there are some really great ones that are pretty quick to check.

Dead ends are pretty interesting. Its great if you can find one: even better if there's 2.

Although I haven't actually implemented it yet: I think that partitions are possible. The trick is in how you create them & define them. On one prior puzzle I was able to mentally make partitions when I manually tried to solve it: but I never realized what I was doing.
I don't want to reveal too much, though Wink

Good luck.

Hi,

In my opinion, partitioning is practical and very effective. I think it's a must-do in high levels.

And, as gfoot and therethinker say, finding the endpoints is another essence to do. And it works well together with partitioning. If you find two parts with endpoints inside, then all the other parts can be solved almost independently with few try-and-errors. That greatly saves the time.

I agree it's fun to solve this puzzle by hand. But it's getting just hopeless as the level getting higher.

I'm at level 604 now. It's because it was the last level when I solved it (now I see the next level ready on the server). I guess adum and ernie also reached the last level respectively at that time.

heh, i wish i could claim that my solver only stopped when the site ran out of levels, but the truth is that my solver ran out of steam.

i don't think we should get too particular on solving techniques, because coming up with them is half the fun and challenge. but i will say that there are two very basic techniques that most people come up with independently, and they get you pretty far. bok and abes, for example, just use those two. my solver has a lot more stuff, and ernie's even more so.

hi

sorry but I've deleted this post Smile

Last edited by baha'a on Wed May 19, 2010 7:34 pm; edited 1 time in total

this one too Smile

Last edited by baha'a on Wed May 19, 2010 7:35 pm; edited 2 times in total

Level 1000 - how big is the grid? My brute forcer is getting stuck at level 141 (soooo slow!) which is 50x50.

_________________
There is no spoon.

level 1000 is around 250x250. it goes up fast to level 1010, which is around 500x500. then it switches to tails' generator for levels 1011 to 1110, and starts at 100x100.

Goodness! That's a bit big! I'll have to rethink my data structures.

_________________
There is no spoon.