Author 
Message 
camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 

Any hints? 

Porting my "early out heuristic" solver to c++ allowed me to do lvl 32 to 36 ... but now the search space is exploding. Even with said heuristics I can't possibly solve the level ...
Any hints on how to approach this puzzle? I have been working on this for a few days every year and I feel that I am missing something fundamental?
Basically I am using a recursive approach. I sort the pieces by the number of fields they can toggle (or "inc" as in increase by 1/++) and ignore branches of combination of tiles which lead to a board which can't possibly be toggled to allzero by the remaining tiles.
I have been thinking about representing the entire puzzle as a mathematical problem but ultimately failed.


Board Size: 56 Depth: 2 Number of Pieces: 16 Number of total combinations: 8.45731e+020 
Last edited by camel on Wed May 28, 2014 4:37 am; edited 1 time in total 

Fri Feb 28, 2014 2:52 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



Got to level 40 using my solver. I just found out about another approach on a different forum but it looks very similar to mine ... it just seems to represent the board and pieces smarter than having zero filled vectors like I do currently ... investigating ...
I just tested my solver with level 97 from http://www.neopets.com/medieval/shapeshifter.phtml ... and those levels are a joke. The inc power of all pieces combined is often only 45 off the solution. I can solve that level in 3 seconds ... so apparently their solvers are as good as mine. Bugger.
I converted a level 97 into the hacker.org format ... just so you can test your solver. Huge board, many tiles ... but only takes like 3 seconds to solve using the early out strategy based on the inc (as in ++) power of the tiles.


my $doc='<param name="board" value="0040040400000,4434244404040,4433242322330,0040443314340,0000004010244,0004043442044,0003434302334,0444334004030,4403334004444,0333400404334,0040044440404,0040004444000,0434000403440,0404000444000"><param name="depth" value="5"><param name="pieces" value=".X.X,XX.X,.XXX,XX.. XXX ..X,XXX,X.. XXX,X..,X.. X,X,X X.X,XXX X..,XX.,.XX XX,XX XX X.X,XXX,X.X .XXX,..X.,XXX. X.X,XXX X..,XXX,..X X XX.X,X..X,XXXX,..X. XX.,.XX X.X,XXX,X.X XX.,.XX X.X,X.X,XXX XXX,X.X,XXX .X..,XX.X,.XXX ...X,X.XX,X.X.,XXX.,X.X. XXX,X.X X.X,XXX XXXX,X...,X... X..,XX.,.XX .XX.,XX..,.XXX XXX.,..XX,XXX.,.X.."><input type="text" name="gotolevel" size="3" value="9999" />'; 
Solved in 3 seconds ...


k: 2 Stack: 43 18 48                          b: 00400404000004434244400000443324233334000404433104000000000021244000000444204400044443
023340440444004030440434400444403334004043340040044440404004000444400004340004034400404000444000 +: 000000000000000000000000000000000000000000000000000000000000
11010000000001001000000000111100000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000 r: 0040040400000443424440000044332423
3334000404433104000000000032204000000440200400044443134440440444004130440434400444403334004043340040044440404004000444400004340004034400404000444000 nfp/rfp: 14
1/131
k: 2 Stack: 43 18 49                          b: 00400404000004434244400000443324233334000404433104000000000021244000000444204400044443
023340440444004030440434400444403334004043340040044440404004000444400004340004034400404000444000 +: 000000000000000000000000000000000000000000000000000000000000
01101000000000100100000000011110000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000 r: 0040040400000443424440000044332423
3334000404433104000000000022340000000444304000044443034400440444004040440434400444403334004043340040044440404004000444400004340004034400404000444000 nfp/rfp: 131/131
Solution found!
k: 27 Stack: 43 18 49 36 30 64 64 98 5 13 70 28 13 53 11 17 97 2 133 139 106 99 69 115 141 132 109 14 b: 0000000000000040000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +: 00000000000000100000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 r: 000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000 nfp/rfp: 0/0
solution based on original piece order: 18,141,13,53,132,11,17,99,109,64,64,97,2,14,49,69,98,115,5,30,13,43,133,139,28,106,70,36

Last edited by camel on Wed May 28, 2014 4:36 am; edited 5 times in total 

Mon Mar 03, 2014 3:35 am 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



So my solver is as fast as their fastest and I am still looking for hints on how to get past level 40 ...


Mon Mar 03, 2014 6:01 am 


Hckr
Joined: 25 Mar 2010 Posts: 27




For me its always helpful to think about variations of the problem. Maybe for you to


Mon Mar 03, 2014 4:12 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



Wow ... someone else still active? )
What do you mean? Like similar puzzles with different rules?


Mon Mar 03, 2014 9:12 pm 


contagious
Joined: 12 May 2009 Posts: 35 Location: Greece 



Its really hard to give a hint to someone that is further in the puzzle
Well maybe i can share some of my thoughts.(Even though i haven't implemented anything more than a simple brute force.)
 threading (its sensible to use it in these kind of problems)
 custom nbase number system (maybe it will work or maybe it will provide an additional overhead)
 maybe there is a better heuristic you can use. (a greedy approach)


Tue Mar 04, 2014 6:35 am 


Hckr
Joined: 25 Mar 2010 Posts: 27






Wow ... someone else still active? 
Yes, as long as there are unsolved puzzles
Currently i'm also working on Modulo and hoping to get my ideas implemented soon.


What do you mean? Like similar puzzles with different rules? 
Yes, changing some rules can help. But even slightly different setups could possibly give you new insights.
In Modulo you could for instance vary the board or number of shapes. But of course the hint is a general one, not specific to Modulo.


Tue Mar 04, 2014 11:37 am 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



Upgrading to a 64bit compiler helped a lot ... thinking about using a high memory aws instance ... my 8gig are not enough for my solver


Tue Mar 04, 2014 7:22 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 





Its really hard to give a hint to someone that is further in the puzzle :D
Well maybe i can share some of my thoughts.(Even though i haven't implemented anything more than a simple brute force.)
 threading (its sensible to use it in these kind of problems)
 custom nbase number system (maybe it will work or maybe it will provide an additional overhead)
 maybe there is a better heuristic you can use. (a greedy approach) 
 I am using threading in all 3 of my solver's components already. :) I have written 2 programs to precompute board states and the final one uses a recursive approach.
 I thought about this many times but converting the representations will slow down the entire thing more than it helps. I have not yet tried it though. It would definitely reduce memory consumption to use a hex system (the value space of 10base 64bit Ints isn't sufficient for depth^(8*8) boards?)
Also I am thinking about representing all valid board states after having used npieces as a tree or even multiple trees. Like 1 tree for every starting_tile<>solution_power<>solution_length index/combination. Clearly you know the inc/++ power, the amount of tiles that aren't yet zeros and the starting tile for every "H1"* board state and can do lookups in the right tree much faster that way.
*) See http://en.wikipedia.org/wiki/Meetinthemiddle_attack
Thus far everything I tried (and I have tried a lot) was slower than just representing every board state as a single string. Precomputing all valid board states for the largest 56 tiles generates billions of combinations of course. The trick is to do it tile by tile (breadth first) and to apply the modulo operator before moving on. This way you can rule out millions of duplicate solution paths a recursive approach would all need to explore.
) I can't think of any heuristics that would actually improve my solver. Computing islands that can't be solved with overlapping tiles (i.e. an "E" shaped and an "I" shaped piece can solve 3 islands with 2 tiles) and stuff slows the entire thing down by a few magnitudes. Also the early outs for the last x<depth pieces (only 3 piece left but one tile still needs 4 incs) are pointless to compute because my lookup tables are already ruling them out.
In the lower levels the most powerful heuristic is probably "remaining inc/++ power" based. My solver runs through those levels just using that heuristic.
Once I am satisfied with the speed of my lookup table creation I will move on to a 200gig memory aws instance ... it's only 3$ an hour ... ;)
p.s.: "Luck" also plays a HUGE role. At the very same level you can get a board which will hit the "inc/++ power" based heuristic after placing piece 34 (start with the largest pieces fist of course) and thus resulting in not having to explore 2/3 of the entire search space. Even if you got a lookup table for 567 pieces this will speed things up a 1000 times. I can tell how hard a level will be to solve after testing the recursive (stage 3) solver without lookup tables for like 5 minutes. Just compare the performance of your solver with various boards for the same level.
I hope that I will solve lvl 44 next week but ultimately my goal is to have a solver that will also be able to solve the harder levels. It's still not that performant. Took 5 minutes to compute 100mil board states and like 8gig of memory ... damn STL ... :///


C:\Users\camel\Documents\Visual Studio 2013\Projects\ConsoleApplication1\x64\Release>test2.exe
BoardWidth=8 BoardHeight=8 BoardSize=64
Board:
1 0 0 0 1 0 0 0 1 0 2 0 2 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 2 2 0 1 2 0 1 0 2 0 0 1 0 1 1 0 0 0 2 2 1 0 0 1 0 1 0 2 2 0 0 1 2 0
Remaining Flip Power Lookup Table (nfp):
0 4 8 12 16 21 27 35 43 52 61 71 82 93 105 118 132 147 163 179
Board size=64 Depth=3 Initial needed flip power (nfp)=59 Number of pieces=19 Number of theoretical total combinations=1.97337e+026
Piece to number of moves (p2nom): 16 16 16 12 20 20 20 16 25 24 20 30 24 35 35 42 42 42 40
Processing k=18
Processed boardStates/Total boardStates 0/1 Resulting boardStates 0
Added piece 18 to 1 boardStates  resulting in 40 resultingBoardStates.
Duplicates=0
Processing k=17
Processed boardStates/Total boardStates 0/40 Resulting boardStates 0
Added piece 17 to 40 boardStates  resulting in 1680 resultingBoardStates.
Duplicates=0
Processing k=16
Processed boardStates/Total boardStates 0/1680 Resulting boardStates 0
Added piece 16 to 1680 boardStates  resulting in 70560 resultingBoardStates.
Duplicates=0
Processing k=15
Processed boardStates/Total boardStates 0/70560 Resulting boardStates 0
Added piece 15 to 70560 boardStates  resulting in 2962560 resultingBoardStates.
Duplicates=960
Processing k=14 (k==lookupTableSize. Those boardStates will be inversed.)
Processed boardStates/Total boardStates 0/2962560 Resulting boardStates 0
Processed boardStates/Total boardStates 100000/2962560 Resulting boardStates 3499994
Processed boardStates/Total boardStates 200000/2962560 Resulting boardStates 6999994
Processed boardStates/Total boardStates 300000/2962560 Resulting boardStates 10499967
Processed boardStates/Total boardStates 400000/2962560 Resulting boardStates 13999903
Processed boardStates/Total boardStates 500000/2962560 Resulting boardStates 17499838
Processed boardStates/Total boardStates 600000/2962560 Resulting boardStates 20999825
Processed boardStates/Total boardStates 700000/2962560 Resulting boardStates 24499817
Processed boardStates/Total boardStates 800000/2962560 Resulting boardStates 27999725
Processed boardStates/Total boardStates 900000/2962560 Resulting boardStates 31499649
Processed boardStates/Total boardStates 1000000/2962560 Resulting boardStates 34999574
Processed boardStates/Total boardStates 1100000/2962560 Resulting boardStates 38499552
Processed boardStates/Total boardStates 1200000/2962560 Resulting boardStates 41999470
Processed boardStates/Total boardStates 1300000/2962560 Resulting boardStates 45499431
Processed boardStates/Total boardStates 1400000/2962560 Resulting boardStates 48999414
Processed boardStates/Total boardStates 1500000/2962560 Resulting boardStates 52499398
Processed boardStates/Total boardStates 1600000/2962560 Resulting boardStates 55999397
Processed boardStates/Total boardStates 1700000/2962560 Resulting boardStates 59499291
Processed boardStates/Total boardStates 1800000/2962560 Resulting boardStates 62999264
Processed boardStates/Total boardStates 1900000/2962560 Resulting boardStates 66499174
Processed boardStates/Total boardStates 2000000/2962560 Resulting boardStates 69999164
Processed boardStates/Total boardStates 2100000/2962560 Resulting boardStates 73499077
Processed boardStates/Total boardStates 2200000/2962560 Resulting boardStates 76999060
Processed boardStates/Total boardStates 2300000/2962560 Resulting boardStates 80498981
Processed boardStates/Total boardStates 2400000/2962560 Resulting boardStates 83998956
Processed boardStates/Total boardStates 2500000/2962560 Resulting boardStates 87498918
Processed boardStates/Total boardStates 2600000/2962560 Resulting boardStates 90998890
Processed boardStates/Total boardStates 2700000/2962560 Resulting boardStates 94498884
Processed boardStates/Total boardStates 2800000/2962560 Resulting boardStates 97998883
Processed boardStates/Total boardStates 2900000/2962560 Resulting boardStates 101498858
Added piece 14 to 2962560 boardStates  resulting in 103688457 resultingBoardStates.
Duplicates=1143 
Last edited by camel on Wed May 28, 2014 4:41 am; edited 3 times in total 

Sat Mar 08, 2014 9:12 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



Now I got 100mil precomputed valid boardStates for piece 1519, my memory is full and the lookup table is pointless ... derp ... ) Literally a standstill. Maybe a tree is the better choice? Also partial lookup tables (only considering every nth tile of the board) that span more pieces seem to work way better ...


k: 0 Stack: 0                   b: 1000100010202110001111101111102201201020010110002210010102200120 +: 3 8 9 10 11 16 17 18 19 20 24 26 27 34
35 36 r: 1001100021012110112221102122102201012020010110002210010102200120 nfp/rfp: 61/163
goodStates=0 badStates=0
k: 1 Stack: 0 0                  b: 1001100021012110112221102122102201012020010110002210010102200120 +: 0 1 2 3 9 10 11 12 16 17 18 19 20 24 25
32 r: 2112100022120110220001100222102211012020010110002210010102200120 nfp/rfp: 57/147
goodStates=0 badStates=0
k: 2 Stack: 0 0 0                 b: 2112100022120110220001100222102211012020010110002210010102200120 +: 2 3 9 10 11 16 17 18 19 20 26 27 28 34
35 r: 2120100020200110001111100200202211122020010110002210010102200120 nfp/rfp: 54/132
goodStates=0 badStates=0 


Sat Mar 08, 2014 9:50 pm 


eulerscheZahl
Joined: 29 Nov 2012 Posts: 56 Location: Germany 



I resigned, as I could not solve #44 in about 10 hours. But it seems that I have a completely different tactic than you have: my solver has less than 300 lines of code (C#, with webinteraction), uses nearly no memory (except storing the board for all steps of recursive function) and as I saw at Level97 of neopets.com, it has problems with large fields (stoped it after 1 or 2 minutes), while I can solve small fields very fast (level 42 in less than a minute in a virtual machine).


<param name="depth" value="3">
<param name="board" value="1200202,1010101,0021122,2122121,2002222">
<param name="pieces" value="XXX,XXX ...X,.XXX,XX.. XXX,XX.,.XX X..X,XXXX,.X.. ..X.,XXXX XXX,..X X.X,XXX .X.,.X.,.XX,XX. XXXX,.X.. X.,XX,.X ..X,XXX,..X XX,XX XXXX,...X X.,X.,XX,X. .XX,..X,XXX ..X,.XX,XX.,.X. XXX,X.X XXXX,XX..,X..."> 
The only trick I used is not to loop over the stones, like it is done when playing by hand


Thu Mar 20, 2014 6:53 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



What do you mean by saying that you are not loop over stones?
My previous solver did not use much memory as well. It just did depthfirst recursion with an early out based on the inc power (i.e. how many tiles they can "++") the remaining tiles provide. I sort the tiles by size and start with the ones providing the most inc power ... i.e. the tiles with the most fields set to 1. This early out allows to solve that lvl97 in 34 sec because the entire board requires almost as many incs (++) as all the tiles provide. It's a very easy level because of this. Placing the first 34 tiles on wrong spots will result in a board which requires more incs than all the remaining tiles can provide. You limit the search space by like 99% ...
(See the "nfp/rfp: 131/131" part in the code listing above ... the remaining inc power is exactly the same which is actually required ... so there is almost no margin for error.
But this does only get you that far. Level 44 got a huge, huge search space and the early out tactic only removes like 10% or so of the search space because the levels here are much more harder than those on neopets. Tiles get flipped (not just inc'ed until tilepower%depth==0) multiple times (i.e. they will go over the zero state multiple times).
That's why I started working on a solver with a "meet in the middle" logic. I.e. given 20 tiles I precalculate all the valid board states which can be solved with the last 8 tiles (the smallest tiles). Then all I need to do is to combine the first 12 tiles (the largest ones) and I instantly know which combination of the first 12 tiles will can be completed with the remaining 8 tiles by looking up the validBoardStates hash. Unfortunately I have not come up with a small/performant enough data structure for the lookup hash but I have also been busy doing other stuff the last weeks. A good way also seems to be only to consider ever other tile when doing the lookup table.
Maybe you can explain your approach? Maybe it's something I have not yet thought of ...
Last edited by camel on Wed May 28, 2014 4:43 am; edited 2 times in total 

Sat Mar 29, 2014 1:44 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



In the 2nd code listing in this post
http://www.hacker.org/forum/viewtopic.php?p=21536#21536
you see the process of creating the lookup table. I start with a board full of zeros (the solution board) and then add the last (the smallest) tile to it at every possible location. This results in 40 board states. Those are the only valid board states prior to adding piece 18 which are solveable. I continue with the 2nd last (2nd smallest) until piece 14 ... the last piece for my lookup table. This time I not only add the tile but "invert" the resulting board states so that I can just do simple hash lookups and see if any boardstate after the first 13 pieces were added can be solved by adding the last 5 pieces via the lookup table. Pretty straight forward concept. It saves A LOT of processing power as you only need to do recursion through 13 of the 18 tiles but it still would run around 12 days in total using 20 threads (lookup table is created within a single thread then gets shared between 20 threads and every one of those will place the first piece in one of the 20 different locations) which is not what I want. I want to solve lvl 44 in at most an hour.
As said I did not use lookup tables until level 44.
I don't really want to start writing a heuristic based on borders and corners and stuff ... that's probably not worth my time as it is too game specific. I rather stick with improving what I got and think about other approaches.


Sat Mar 29, 2014 1:50 pm 


camel
Joined: 26 Dec 2007 Posts: 50 Location: Austria 



I also thought about only working with half of the board. (Like only use the black tiles from a chess board.) Like using every other tile through the entire process. Then run the entire thing again for the other half of the tiles and combine the solutions.
But this would ruin the inc power early out heuristic totally as pieces would no longer provide a fixed number of incs but incs would vary with every possible offset of the piece.
A piece which incs 3 tiles in a row on the full board would inc 1 or 2 tiles if you only consider every other tile of the board depending on placement of said piece.


Sat Mar 29, 2014 2:10 pm 


eulerscheZahl
Joined: 29 Nov 2012 Posts: 56 Location: Germany 



Sorry for late response, I thought there would be an email notification, seems that I forgot to use the checkbox below the input field.
I also tried using lookuptables up to about level 30, but then memory consumption increased quickly and it became slow after all of my 8GB RAM were used.
Then I decided to completely change my stradegy: I pick one field (in the corner) and calculate the number of stones needed to fix this single field (of course there are more solutions because 2=5=8=... mod 3 for example). Then I choose the needed number of stones out of them, that are able to reach that field (not every stone properly fits into the corner) and recursively fix the remaining fields without touching the previous ones.
Thats why my solver has problems solving the large field, although there aren't many possibilities with early outs.
But I had no idea, how to realise this for my way of solving.
I also tried selecting fields in an intelligent way (less stones fitting there), but selecting the next field was too slow, so my straight forward code was faster although trying more possibilities. Maybe I should select the first fields and do the rest one after the other, but I was too lazy to code it.


Sun Apr 20, 2014 1:13 pm 




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


