Any hints?

camel · Post by **camel** » Wed May 28, 2014 4:33 am

I even tried using a machine with 300gig of memory and 100cpus. Precalculating a lookup table for the smallest 5-6-7 pieces and using the inc-power based early out does not seem to be enough. At least not when you use every tile instead of using a tiles%2 or tiles%3 approach.

I am currently busy with socioeconomic activism (capitalism is a bitch to overcome) but I will look into this later this year and share a few thoughts.

camel · Post by **camel** » Tue Sep 16, 2014 6:12 pm

After talking to 2-3 people I can confirm that they managed to solve levels beyond 44 using a totally different approach than iteration/recursion with pruning/backtracking/early outs. I expected something like that because even with a heuristic that prunes 2/3 of the entire search space lvl 44 already comes with 4.81761e+026 possibilities and would take around 2-3 weeks on 16 cores.

So it's time to learn something new and approach this challenge in a totally new way ...

Hippo · Post by **Hippo** » Sun Oct 26, 2014 10:31 pm

I have started today with meet in the middle, what was OK for levels upto 30 and with some luck I got to solve even 33. I have looked at level 34 and it's absolutely out of reach of this approach. Fortunately the meet in the middle could be recoded to just provide middle stops. The board 34 clearly provides better methods for early stops (large board*depth). Seems one should find a lot of possible fast stops methods to be able to solve further levels.

Hmmm. I have expected there would be much earlier cuts on level 34 based on number of remaining squares ... or I coded something wrong ... hmmm, I have read the board wrongly:( I tought the depth is 5

. With the depth 3 its natural

.

Hippo · Post by **Hippo** » Sat Nov 01, 2014 12:09 am

camel wrote:

Code: Select all

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" />';

My solver did it in 1716 ms (when meat in the middle disabled). (With meet in the middle allowed it solves the same board in 1452ms ... after 173957ms filling the meet in the middle tables).

But I am stuck on 38

Code: Select all

3
02121020,11200002,20012211,02100020,22220220,00011120,22110110,01100120
X..,X..,XXX,X.. X..,XX.,XXX,X.X,XX. XX..,.XXX,.XX.,..X.,..X. ...X.,..XX.,..XXX,.XX..,XX... XX..X,XXXXX,.X.X. .XX,XXX,.XX,.XX .XX,XXX,.X. X..,X..,XX.,XXX X...,XXXX,.XXX,XXX.,..X. ..XX.,..XXX,..XXX,XXXXX,.XX.. ...XX,XXXXX,..XXX,..XXX,.XX.. ..XXX,..X..,XXX..,.XX.. ..XX.,.XXX.,XXXXX,XXX.X,..X.. ..XX,XXX.,XXXX,..X. .X...,.XXX.,XXXXX,XXX..,..X.. X.X..,X.X.X,XXXXX,XXX.. X...X,XXXXX

anyways

.

For meet in the middle I have tried to maximize the possible table size ... I use zobrist hashing and I just set corresponding bit in the table. (Several board states could address the same bit, but when bit is not set I am sure the position is not solvable). I use 7 tables with halving size each next, addressing by different bits of 64 bit zobrist key. First table (the largest) is for level having about half possible options as is its size. There is probability about 1/2 of false match on the first level, but the probability goes quickly to 0 on next levels as the level sizes decrease much faster than the table sizes.

I am not sure the adressing overhead is worth it and heuristic counting how many squares are opened seems cuts good enough anyways. ... OK seems in levels where more than say 15 squares are left to open the meet in the middle helps.

After really long search I have solved

Code: Select all

3
02121020,11200002,20012211,02100020,22220220,00011120,22110110,01100120
X..,X..,XXX,X.. X..,XX.,XXX,X.X,XX. XX..,.XXX,.XX.,..X.,..X. ...X.,..XX.,..XXX,.XX..,XX... XX..X,XXXXX,.X.X. .XX,XXX,.XX,.XX .XX,XXX,.X. X..,X..,XX.,XXX X...,XXXX,.XXX,XXX.,..X. ..XX.,..XXX,..XXX,XXXXX,.XX.. ...XX,XXXXX,..XXX,..XXX,.XX.. ..XXX,..X..,XXX..,.XX.. ..XX.,.XXX.,XXXXX,XXX.X,..X.. ..XX,XXX.,XXXX,..X. .X...,.XXX.,XXXXX,XXX..,..X.. X.X..,X.X.X,XXXXX,XXX.. X...X,XXXXX

instead. ... Oops ... have I finally solved the original task?

And 39 was trivial ... ForwardTime: 126ms (after BackTime: 54881ms preprocessing).
Probably main reason is ... there exists a lot of solutions ...

I have cheated a bit by choosing easier level when the original looked difficult

. So finally I went among 43 level solvers ...

Level 44 is difficult especially because it has only one solution with very high probability. (It has statistically no solution, but one is guaranted by puzzle generator (I hope;)). I have chosen among given boards to have good chance to finish the computation. On previous levels, I have chosen manually from about at most 4 tasks by feel. On level 44 I have chosen from more tasks, I have used some statistics to allow the decision. Seems the chosen task is solvable in less than a day.

Yes ... it was 8h 9m 7s 428 ms forward time, 31s 30ms preprocessing. I have searched more than half of the search space.

Wow second seen task on 45 ... ForwardTime: 13s 191ms, preprocessing time 38s 657ms.

First task on 46 level estimated time 3h ... it is not worth a risk to try other tasks.

After solving 46 (in 56 minutes), I have returned to 38

Code: Select all

3
00220100,22000000,22120100,00211002,22210120,22200010,00011002,00222220
..X,XXX,.X.,.XX,XXX XX.,.XX,XX.,.X. XXXXX,XXX..,XXXX.,.X...,.X... ..X,..X,XXX,.X.,.XX X.X..,XXXX.,.XXXX,.XXXX .XXXX,.XXX.,XXX..,..X.. XX..X,.XXXX ..X..,.XX..,XXXX.,.XXXX,...X. X..,XXX ..XX,..X.,X.X.,XXXX,.XX. X.X,XXX,.X.,.XX,..X .XX..,XXXXX,..XX.,...X.,...X. .X..,XXXX XXXX.,XXXX.,XXXXX,.X... X.X..,XXX..,.XXXX,..XX. ..X..,XXX..,.XXX.,XXXXX,..X.X ..XX,..X.,XXX.

was under 8min ...

And now I can see my solution of 46 was not accepted ... and tasks are much harder now

... OK it was 45 rather than 46.

I have automated task selection ... but I have bug in level selection ... and therefore I have solved levels 47 and 48 several times

.

Level 50 seems to be next crucial level?!

Seems I should implement active border size reduction to be able to pass level 55.
... I had already 1/48 of level 55 solved ... and I have decided to restart the search ...

Wow good decision

I did it

.

But level 56 seems to bee too much ... may be using something faster than java? (Days->Hours would help...)
My attempt on level 56 is to reduce borders by placing several pieces and the task is chosen if the resulting expected solution time is reasonable. This selects one of about 80 tasks ... but the solution times are underestimated as always till now there was no solution in the reduced puzzle:(.
Task selection is much faster than task solving ... may be I should be more strict in the selection process.

Hippo · Post by **Hippo** » Mon Feb 16, 2015 6:40 pm

After 100 days of permanent single thread trying to find good reduced task (for level 56) and solving still solution not found (about 60 tasks tried).

Valar_Dragon · Post by **Valar_Dragon** » Mon Feb 16, 2015 11:48 pm

Holy cow, thats quite some dedication. I can't imagine leaving a program running on my computer for 100 days o_O

Hippo · Post by **Hippo** » Wed Feb 18, 2015 10:56 am

Fortunately it's in office I am not visiting daily

, ... not on my laptop.

Actually I have misestimated ... 100 days anniversary is about 25.2.2015.

Wed Feb 18, 2015 8:53 pm

That's still insane.

Hippo · Post by **Hippo** » Tue Feb 24, 2015 6:49 pm

camel wrote:After talking to 2-3 people I can confirm that they managed to solve levels beyond 44 using a totally different approach than iteration/recursion with pruning/backtracking/early outs. I expected something like that because even with a heuristic that prunes 2/3 of the entire search space lvl 44 already comes with 4.81761e+026 possibilities and would take around 2-3 weeks on 16 cores.

So it's time to learn something new and approach this challenge in a totally new way ...

Hmmm, I am still fighting with 56 level, and I don't think I have more than early outs combined with meet in the middle and task selection process. I am curious what else the top 3 guys did (exept of massive paralelism?) I still hope they were lucky with task selection on level 56

and remaining levels till 61 are easy.

Hckr · Post by **Hckr** » Wed Feb 25, 2015 10:09 pm

If i am right, it has nothing to do with massive parallelism. Should be a property of the puzzle, you can make use of. Its just an idea at this point, but i hope i can overcome my lazyness soon to try it out

lvhao945 · Post by **lvhao945** » Fri Feb 27, 2015 10:18 am

level 44

Fettpet · Post by **Fettpet** » Mon Apr 06, 2015 9:24 pm

Hi hackers,

a question about level 38. How long do it calculate to generate a solution? I translate the modulo puzzle into sat and start a sat-solver. In level 38, I test 100 instances with 10h timeout. Zero are solved.

mfg
Fettpet

eulerscheZahl · Post by **eulerscheZahl** » Tue Apr 07, 2015 3:48 pm

Hi,
I don't want too run it again, but as far as I know, it took about 8 hours (C#, 64bit single-core application, Intel i7). I tried two or three different puzzles until I found a solution, as I didn't want my computer to run during the night.

I have an idea, how I could probably speed it up a little bit, but I was too lazy to code it until now.

Hckr · Post by **Hckr** » Wed Apr 08, 2015 10:53 am

Mine too (about 8 hours). If you choose a good level instance you should be able to solve it in reasonable time.

Hippo · Post by **Hippo** » Wed Apr 08, 2015 10:09 pm

Fettpet wrote:Hi hackers,

a question about level 38. How long do it calculate to generate a solution? I translate the modulo puzzle into sat and start a sat-solver. In level 38, I test 100 instances with 10h timeout. Zero are solved.

mfg
Fettpet

Unfortunately I cannot test it as my code is still running on level 56 ... on faraway computer.
May be I will interrupt it to make a test. But I remember level 38 was one of worst.

But I have logs ... it took me 800s on the well chosen task.
It took 1400s on another one. But I think this was the level I start chosing the tasks ... Seems I coded the task selection on level 44, but I have tested it on level 38 (the 800s run).

The code is single threaded java, it was run on intel core i5 laptop. 2.5GHz, 4GB RAM.