hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Great puzzle!
Goto page 1, 2  Next
 
Reply to topic    hacker.org Forum Index » Tapeworm View previous topic
View next topic
Great puzzle!
Author Message
tails



Joined: 10 Jun 2008
Posts: 191
Location: Tokyo

Post Great puzzle! Reply with quote
Not only because the hex board looks beautiful :-)

At first glance, this puzzle looks easy, and it is acturally easy under level 100 or so. But it's getting harder around level 140. I thought it would be hard if the board got very large, but suprisingly it's getting hard while it keeps smaller than the size of level 0 :-)

Furthermore, it's a great aspect of this puzzle that we can't simply apply well-known algorithms when we make solvers. It would take forever with DFS even to solve low levels. My simple solver took less than 1 second for each of low levels, but it got almost useless above level 100. It seems that the key is how to implement human intuition.

I never imagined the hex board had such possibilities. It' really fresh! And I never imagined JavaScript had such capabilities :-)
Mon Aug 31, 2009 2:08 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
glad you like it! =)

it's been a long time since i put up a new puzzle, so i thought i'd release one and try something a little fresh at the same time. a hex board is a little different, but the nature of the puzzle is really a new beast. as you say, classical brute force algorithms aren't going to get very far!

i honestly have no idea myself on how to tackle this one, so it will be very interesting to see where people go with it...
Mon Aug 31, 2009 5:22 pm View user's profile Send private message Visit poster's website
therethinker



Joined: 28 Mar 2008
Posts: 144
Location: #hacker.org on Freenode

Post Reply with quote
Very awesome puzzle.

Hex board is fun, yet a PITA to work with (in a good way Very Happy) As tails said, its amazing how well this puzzle scales.

How are you generating the puzzles? I was doing some by hand and noticed a few (around level 30, when they were harder) that consisted of only 1 snake and took 2 moves to solve. I guess it averages out, though.

Props to the first person that uses Javascript to solve it Very Happy
Mon Sep 07, 2009 9:05 pm View user's profile Send private message AIM Address
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
for generating the puzzles, there are a bunch of factors to play with, such as board size, number of worms, num colors, worm length, spaces left over, spaces blocked, etc. i don't know which will turn out to be hardest, so i try a lot of variations of all these factors at each board size. some will be harder than others...

good luck with your solver! =)
Wed Sep 09, 2009 5:21 pm View user's profile Send private message Visit poster's website
therethinker



Joined: 28 Mar 2008
Posts: 144
Location: #hacker.org on Freenode

Post Reply with quote
Also, does everyone have the same problems?
There really shouldn't be an issue of sharing answers since solvers/code could be shared too...
Thu Sep 10, 2009 1:45 am View user's profile Send private message AIM Address
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
yes, everyone sees the same problems for this puzzle.
Fri Sep 11, 2009 12:01 am View user's profile Send private message Visit poster's website
prop



Joined: 16 Jun 2009
Posts: 6

Post Reply with quote
Wow it's very intriguing puzzle! Very Happy level 60-65 were the best I think(Now I'm solving lv.74, so I know just a little of them).

Anyway I like to solving it w/o brain though Rolling Eyes plus lv 73 was not THAT horrible. i think lv 7 was the most horrible Sad

_________________
HI!
Thu Oct 29, 2009 6:30 am View user's profile Send private message
dangermouse



Joined: 05 Jun 2011
Posts: 89
Location: deep space computing AG

Post Reply with quote
lvl 73 is horrible! i had a bad start with this puzzle, i tried to implement it as a iterative DFS but had some bug in the implementation and had to give up. I tried to do it iterative knowing that the recursion depth of this thing is awesome. I then implemented it as recursive DFS with weighted moves on shortest paths and still can't solve level 73...

one good thing i am using is: to debug the code i inject into a html level template my current board as javascript variable, and then look at the result in a browser as it would be a level on hacker.org. This probably works with other puzzles as well, but i never tried it before.

and still i have some ideas, but its' really an awesome puzzle Smile
Wed Aug 29, 2012 1:58 pm View user's profile Send private message Visit poster's website
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
I used to play easy levels by hand till I got to level where it become hard.
This gives me feeling of the game ... I am now above 100 and still not having troubles to solve it manually ... According to what was said, I have to do next about 60 levels?

In any case, it's fun to pull them so Smile.

BTW: The comp is ususally solving other puzzles meanwhile ...

Seems 165 is good enough to start codding ... Smile ... hmmm still not, ... solved, but so far no code.
I expect (at least for start) I would implement iterative deepening with only one puzzle dependent trick ... I would code cyclic worm as one state regarding the search (may be with simple heuristic guess of required steps to finish).
Mon Oct 27, 2014 10:19 am View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
Hmm, my code is running now, but seems IDA* needs better heuristics than I have.
It went rather smoothly (often under 1s, once above 1minute) to level 73, when it stands for several minutes ... either I have in code more bugs than I have expected or the method does not work that great.

level 79 was not solved overnight, seems solving (one of several) puzzles with more different colors than the original one could improve heuristcs lower bounds navigation a lot ... I should concentrate on this.
Fri Jun 05, 2015 2:23 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
So artifical coloring color components helped with level 79, but level 81 looks hard for IDA*
(I already use statistics of ida subgraph sizes to have better controll on deepening).

I am starting to think about checkpoints adaptation of IDA* (I have never heard about such algorithm).

The situation when I solve level faster manually than IDA* is motivating.

Artifical colors and checkpoints are helpfull, but even with them I have not solved several levels with it.
For some levels splitting components could be helpfull, but I don't know how to speed it at all.

Let us see how far it will go ...
wow! level 201 ... my heuristics navigation said ... one step missing immediately, but the step was not found overnight. Seems I should concentrate on better heuristics navigation.

OK, better heuristics helped with 201, but levels 161, 165, 173, 175, 178, 181, 192, and 196 were not solved quickly enough with it so seems I should work on it more.

Levels 161,165 solved with use of single worm exact solution heuristics as lower bounds (but some debugging is needed). OK after debugging all these levels solved.

Level 103 would need color exact solution heuristics lower bounds (it will be implemented in near future).

Grrr, I have solved 211 faster by hand again Sad, and 222, 225, 228, 236 as well.

Finally I have implemented heuristics switching by time allocation.
Current version solved 211 ans 222 in reasonable time, so I hope I will go further soon.

... and level 298, 326 were again easy for brain and much time consuming for my code Sad.
Oops ... back to debugging with color heuristics...

Ohh, my solver fails on 298 even when I remove all worms except team 2. When I recolor worm of length 6 (and 6 squares), it finds solution quickly. Seems sometimes splitting of color components will be must.

Hmm, I have not coded color components splitting, but I have helped my solver in some levels by adding additional colors to the task. ... approaching level 400.

OK, it's definitely must to implement color component splitting ... for levels above 450. There is probbaly no need to find all solutions. In most cases any solution would work.
Fri Jun 12, 2015 6:05 am View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
I have added color complement splitting and it didnot help much.

Free space economy ... When one have local solution blocking free space on the edge...making se real steps to move free space to the middle what could be undone easily. But

... no free space economy yet, I had to change the time management strategy for the checkpoints to search ... original strategy to search each to the same depth failed, so if the search exceeds some time T I go for another checkpoint ... of course T must me slowly increased (until a new checkpoint is found).

Roughly ... I use for each sum of worm loop lengths ... the heuristically nearest position as checkpoint.

I still use 3 different heuristics and either component splitting (randomized) or not (5 algorithms randomly chosen). Each try runs for given time (starting at 90seconds) and time for tries is slowly increased.

... combinatorial complexity of levels as 587 of too many worms of same length ... kills all these startegies ... as I start for each of variations how to distribute worms ... I should switch to chosing only much limited amount of them (probably selecting by the heuristics function).

So I had to limit the starting positions by sampling...

I often "cheat" by solving level by hand as it is clearly simple ...
Tue Jul 21, 2015 12:57 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
Really bad performance of the algorithm on trivial level 607 (i hope) persuided me to extend set of 'basic/macroŽ moves to allow removing small subworm and adding subworm of same length what is applicable on looped worms. I will start on length 1 extension. I hope it would be suffitient.

My solver is still extremely slow on several levels ... still on levels about 660 I am often much faster when I solve the puzzle manualy ... dividing the solution to unblocking phase, moving near the target phase and final arranging would be helpful in several levels (sometimes direct arranging without unblocking is must).
The "free space economy" was not still codded ... may be this is still the bottleneck.

Level 698 is a nice joke.
Sat Aug 08, 2015 7:20 am View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
Big performance improvement was achieved by remembering position with longest total loop length as starting position for algorithm restart. So a later search is invoked from positions with worms more untangled.

This much more corresponds to human solution with entangling worms first than trying to put worms to places.
Sun Aug 30, 2015 10:04 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
Oh on level 847 I have noticed the task is not constant ... the same appeared probably earlier ... and I was surprised why my solver was moving worms from nonexisting positions ... to let the comp solve the puzzle and to look at it occassionally could be bad decisiton.
Mon Sep 07, 2015 6:01 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Tapeworm All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.