Nice game

coderT · Post by **coderT** » Thu Nov 13, 2008 3:05 am

This game is pretty fun.
I wrote a java program to solve it for me, currently I am at Lv. 95, now it's getting slower to find the right path.
How's you guys' programs, does your program also get a lot slower when level is getting high?
Maybe I should try another algorithm.

gfoot · Post by **gfoot** » Thu Nov 13, 2008 3:24 am

Higher levels are more complex, so the solve time does go up, but you should be able to find ways to keep that increase under control. By the end of the game, my program could solve any level in under two seconds, but the algorithms I used on the way started taking days... there comes a time when you need to rethink!

coderT · Post by **coderT** » Fri Dec 26, 2008 6:56 am

Finally reached 513...
That was a fun experience.

m!nus · Post by **m!nus** » Fri Dec 26, 2008 10:33 am

took you quite some time

i'm stuck on 155, my bot needs about 20 minutes to solve one level now, i guess there's a lot of optimization needed.

soeschmid · Post by **soeschmid** » Fri Dec 26, 2008 12:24 pm

if you have the right idea...

Sometimes its like that, i woke up in the night and had a fantastic idea for an algorithm to that challenge.
After implementing it, my computer took less than a second for a level (even for the last ones...)

For the other puzzles i'm still waiting for that moment

coderT · Post by **coderT** » Fri Dec 26, 2008 6:34 pm

Yeah, I was doing brute force with recursion before, and that only took me to around level 165, I guess m!nus is doing the same.
Need to do something with the board first, make it smaller.

gfoot · Post by **gfoot** » Sat Dec 27, 2008 1:34 am

soeschmid wrote:For the other puzzles i'm still waiting for that moment

Yeah. But somehow I don't think it always comes!

I had a great idea for Modulo, implemented it, and found it didn't help much, though in theory I think it should have done. Sometime I should find time to work out why - more profiling is needed. I then had another idea, implemented that, and it did help a bit, but still not as much as I wanted, and I wasn't prepared to just throw idle cycles at the problem any more, so I stepped back. I think I could combine the two, but I'm concerned about memory usage.

For Mortal Coil I had a good idea over a year ago, but never got around to implementing it until recently. I've been implementing it, on and off, for over a month now. I underestimated the amount of code required (or rather, the number of separate sub-problems I needed to solve separately and join together), so while I thought I'd have something good in about a weekend, it's taken much longer. I'm confident it's going to be a good solution though, overall, and right now it just needs some glue and sticky tape. Plenty of that left over from the christmas presents, at least.

I've also got a better idea for Mortal Coil, which could be really interesting for very large boards - hopefully one day I'll need to try it out!

But I'm pretty sure that in most of these cases everybody is finding the same algorithmic improvements. I'm less sure for Mortal Coil, though, because my approach has taken so long to code up - I wonder if other people have found simpler solutions, and if so, whether those are more or less effective than mine.

There's also an interesting distinction between efficient brute force solvers, which will eventually find a solution no matter how obscure, and heuristic solvers which converge on solutions most of the time but without a guarantee. For example, my runaway solver could fairly easily find *every* solution to a grid, with a few modifications, while my One Of Us solver wouldn't be able to do that. I've resisted heuristic solvers for any other problems, but that's probably why I suck at Bricolage and Pusher Boy. But I find heuristics harder to define, and worry about having to pay attention and change the heuristics if/when it gets stuck.

tog · Post by **tog** » Sat Dec 27, 2008 9:50 pm

gfoot wrote:I wonder if other people have found simpler solutions, and if so, whether those are more or less effective than mine.

I think my current Mortal-Coil-Solver performs similar to yours. It is a relatively simple brute-force-solver (actually based on the example solver). I just applied some optimizations and implemented two additional ideas that where quick to do. But nothing that required hours of coding so far.

soeschmid · Post by **soeschmid** » Sat Dec 27, 2008 11:19 pm

It would interest me, too, what algorithms and optimations others implemented.
Adum, what do you think about "solver topics" for the puzzles.
I thought about topics like "solved above 100", "solved above 200" etc.
I don't want to see full code there, but the solvers could discuss general ideas for their algorithms and optimations.
As far as i got till now, i already had some good ideas, but i'd like to learn more, different approaches...

Post by **adum** » Sun Dec 28, 2008 12:39 am

hey, i've had the idea of having "solved" puzzle forums too, but just don't have the time to implement it right now =) someday...

antirem · Post by **antirem** » Mon Dec 29, 2008 6:14 am

how hard would it be to then move this ontop of other games? like runescape?

abcvirus · Post by **abcvirus** » Sun Apr 12, 2009 5:41 pm

any ideas on writing any script code to make a supercomputer?

A normal computer with 2,3,4,8,16 Gb would start to lag behind at <100 level...

But with a supercomputer at somewhat 30 Gb - 1.45 teraflop would crack all levels within seconds...

Give me your opinions?

Increase the memory capacity of your computer = less time you use to solve for the "equations"

Chocoholic · Post by **Chocoholic** » Sun Apr 12, 2009 7:08 pm

Apart from the fact that nothing you say makes any sense... you may want to read this: http://www.lump.org/?p=135

abcvirus · Post by **abcvirus** » Mon Apr 13, 2009 4:00 am

Chocoholic wrote:Apart from the fact that nothing you say makes any sense... you may want to read this: http://www.lump.org/?p=135

good job, on doing research... (you are excellent!)
Thanks for helping me on not to waste time on a personal developing supercomputer.

I really appreciate when somebody tells me the pure truth from alot of lies...

Adzeye · Post by **Adzeye** » Mon Apr 13, 2009 6:42 pm

You could always try to make an algorithm that doesn't need much memory? Mine doesn't even reach a meg.