BrainMeta'   Connectomics'  

Welcome Guest ( Log In | Register )

2 Pages V  1 2 >  
Reply to this topicStart new topic
> Eternity2, $2 million prize
trojan_libido
post Oct 24, 2007, 02:09 AM
Post #1


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



I wanted to discuss some techniques for solving this monster NP Complete puzzle. The details of it can be found easily with a search on Eternity 2, the first person to solve it gets $2,000,000.

Basically its a tiling puzzle. Each square tile has 4 patterns at each edge, and you have to match all the edges in a giant 16x16 square to solve it. A tile can be in any of four orientations, except if its an edge pattern which is grey and must be around the edge, or corner which is basically two edges.

There is anywhere between 1 and 20,000 solutions, the exact amount is still being debated as different media have reported different things.

I am looking for a discussion on implementation of a solver, I've already completed a working solver but it can only place 70,000 tiles a second, but tests over 17.8 million in the same time. The solver is written in C# after my vb prototype proved a little slow. Problem is other developers are managing over 25million tiles placed a second, and their calculations still say it'll take around 500 years to brute force the answer. My solver can create its own puzzles, solve borders, graphically display whats going on, and can solve "some" puzzles instantly.

So I wondered if anyone wants to discuss ideas, help me along, and if I feel the person has been helpful enough or is intelligent and passionate enough I will share everything I have so far. It's very interesting work and even without the prize its a mental workout.

Hopefully I'll get some interested parties and some clever discussion.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Enki
post Oct 24, 2007, 10:00 AM
Post #2


Supreme God
*******

Group: Basic Member
Posts: 2794
Joined: Sep 10, 2004
From: Eridug
Member No.: 3458



Whau! 2,000,000 USD! I can buy a dish washing machine, all dreams can come true.

Are you sure they will pay?
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Enki
post Oct 24, 2007, 10:03 AM
Post #3


Supreme God
*******

Group: Basic Member
Posts: 2794
Joined: Sep 10, 2004
From: Eridug
Member No.: 3458



About 30 Pounds + 50 USD shipping ...
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 24, 2007, 12:07 PM
Post #4


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



Regardless of if they will pay, it would be fun to figure out just for the hell of it.

Brute forcing the answer is dumb, the only way your going to solve it is with abstractions and geometry.

By the way, the 2 million dollar prize is 256x256 not 16x16.

http://uk.eternityii.com/available-puzzles/
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 24, 2007, 12:55 PM
Post #5


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



Nah its not Max, I have all the clue puzzles and the monster puzzle here in front of me. It states [piece]x256, which is the 16x16 grid. I also have all the pieces electronically and my application can get 75-80% done before it begins to backtrack seriously. Obviously this is a poor result because it could quite easily get 255 tiles placed and be left with the odd one, which is just as incomplete as 80% lol.

I've managed to double the speed of my tile placements with some presorting, now I just need to implement some clever checks to end search branches earlier.

I'd be very interested in sharing the code with the regulars in brainmeta, I'm not sure how much you guys know about coding, but you can get C# express for free from MS site. Regardless whether you can code or not, the program is complete in that it will solve it, eventually lol. Just watching how its working and some heavy thought may result in some good ideas that I can then implement.

I very much doubt I will be the first to complete it, but if I did any contribution would be well paid smile.gif But realistically, I want to just to say I did.

Oh, but I couldn't give you the actual 256 tile puzzle, because that would immediately disqualify me, unless you purchased it of course wink.gif
The program can generate equally difficult puzzles with a few button clicks that you can subsequently run on it.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 24, 2007, 01:26 PM
Post #6


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



I'll explain how I broke the problem down, which actually worked out great because it seems everyone else is using the same method for brute forcing it.

Patterns are numbered 0-19, 0 being the edge pieces.
Tile edges are numbered 0 to 3, thats North East South West.
I get the position on the board, and work out the pattern I'm looking for (NESW again), so a typical corner search pattern would be 0 0 -1 -1 (-1 is any pattern). From this pattern I search all tiles and create a shortlist of tileIDs.

I randomly select a starting point in this list to add a luck factor that I wouldn't otherwise get. Thats about it in a nutshell, I was using recursion but it became cumbersome to pass information to certain board tiles and so I now store each shortlist at each board position. Unfortunately once it backtracks it loses any information it previously had and will place the same old "wrong" tiles futher down because it "forgot" those tiles cant sit together, despite the beginning of the board changing.

Aparently binary search tree's are the way to go, but I've no idea on implementation when your dealing with a four sided tile.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 24, 2007, 04:03 PM
Post #7


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Brute forcing it is out of the question. The number of possible configurations is greater than 10^108. So you need to use a heuristic to help find solutions.

There are four corner pieces and 4! = 24 configurations for those, and each one probably is part of a solution. So first, select a configuration of the corner pieces and solve the remaining 56 edge pieces. There are probably many solutions for the edge and corner set, so pick one and then solve the interior tile configuration by building inward from the edge.

Do that by taking the 196 interior tiles and making 98 matched pairs out of them. Then take the matched pairs and make 49 quartets. See if the quartets have a 24-quartet set that matches the established perimeter. If so, continue to build inward in that manner. If not, re-assemble the quartets in a different way and try again.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 24, 2007, 11:54 PM
Post #8


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



I believe that if you stored the information to make up those quartets, considering rotations, you'd end up with well over a terrabyte of information. Some others have tried to implement this method and have had mixed results, none of them better than a brute force attack.

Something clever has to be done with the patterns within the tiles, remembering how useful tiles are, or constrained.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 25, 2007, 12:10 AM
Post #9


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



QUOTE(Rick @ Oct 24, 2007, 06:03 PM) *

Brute forcing it is out of the question. The number of possible configurations is greater than 10^108. So you need to use a heuristic to help find solutions.

There are four corner pieces and 4! = 24 configurations for those, and each one probably is part of a solution. So first, select a configuration of the corner pieces and solve the remaining 56 edge pieces. There are probably many solutions for the edge and corner set, so pick one and then solve the interior tile configuration by building inward from the edge.

Do that by taking the 196 interior tiles and making 98 matched pairs out of them. Then take the matched pairs and make 49 quartets. See if the quartets have a 24-quartet set that matches the established perimeter. If so, continue to build inward in that manner. If not, re-assemble the quartets in a different way and try again.


Rick is right, brute force will get you know where. There is way to many possibilities, someone smart enough to come up with a more sophisticated method will solve the puzzle long before the brute forcer's do.

You may not be able to do computer calculations with such a method. However, its like people who try to brute force cryptology. The amount of time for such a brute force method would extend into hundreds of years, which is just not practical.

Instead you need to think smarter than everyone else. If you do what everyone else is doing, then you are giving yourself a very low chance of success. A. since other people have started the brute force method before you, they have a higher probability of solving the equation first. B. Since everyone is using the same brute force method, someone may get lucky and solve the equation right away.

You might as well play the lottery.

Think geometry and patterns, because thats what your really dealing with. Think also of the facts you know. You know that gray pieces have to go along the outside. Which reduces the number of pieces you have to deal with.

Then take your hints, you can deduce even further the number of possibilities. If you simply use the laws of deduction applied with sound logic, you will greatly increase the probability of success by reducing the number of required calculations.

This will require some inventive thinking. Once you have the calculations down to a bare minimum, you can begin putting the pieces together...
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 25, 2007, 01:06 AM
Post #10


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



I ran the brute force method on the border only, it came up with over 10,000 variations in less than 2 minutes, and it had only backtracked over half the border patterns. I deemed this attempt to solve the borders first essentially futile.

Take this example (o = placed for a while, x = currently processing)

oooooooo
oooooooo
ooooxxx

If those last three pieces can't be placed because of the row above, once it backtracks past the first x it will attempt to place those three in identical places. It would have to though, because previous pieces would have changed and that would mean there may be a new piece to place.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 25, 2007, 10:57 AM
Post #11


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



Try thinking of the big picture, its possible to brute force ANY puzzle, but if you look at the whole.. you might be able to see the patterns.

Would you use a computer to help you figure out a puzzle with a picture of a kitty? of course not. This is the same thing, except it is geometric patterns instead of a picture. Think of the big picture and the patterns as a whole.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 25, 2007, 03:43 PM
Post #12


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



Do we have any coders here amongst the regulars?
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 25, 2007, 04:26 PM
Post #13


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Yes. See for example:

http://teamster.usc.edu/~dteam/images/tictac/index.html
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 26, 2007, 12:50 AM
Post #14


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



QUOTE(trojan_libido @ Oct 25, 2007, 05:43 PM) *

Do we have any coders here amongst the regulars?


Yes.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 26, 2007, 01:05 AM
Post #15


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



Ok then, doesn't anyone want to collaborate on solving this beast? smile.gif
What languages do you guys use?
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 26, 2007, 08:50 AM
Post #16


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



QUOTE(trojan_libido @ Oct 26, 2007, 02:05 AM) *

Ok then, doesn't anyone want to collaborate on solving this beast? smile.gif
What languages do you guys use?

I suggest C++ for this. Every square has an edge-matching relationship with approximately 256 / 22 = 12 or so other squares. Start with the required fixed tile and build a tree of 4 * 12 = 49 matching tiles on the edges and solve for the corner tiles that can fit to produce a set of nuncets (3 x 3 squares of tiles). Take that set of nuncets, one at a time and try building outward by expanding square frames of tiles.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 26, 2007, 09:52 AM
Post #17


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



You ar correct, the most I've seen the shortlist get to is 11 tiles left from the bag that match.
QUOTE
Start with the required fixed tile and build a tree of 4 * 12 = 49 matching tiles on the edges
I only know VB and C#, why should you use C++ over C#? I'm also not sure what you mean by a tree of 4 * 12?

The variations on the sets of 9 possibilities will be huge. If you take a single tile in position, then you still have to solve every 3x3 square possible. I suppose then you could cross reference the 3x3 tiles to make sets of coexisting configurations for all nuncets, then you could possibly end up with a reduced processing time.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 26, 2007, 11:16 AM
Post #18


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



Because

A. C# was made for the web. Its original purpose was to cut out Java from the market. When that didn't work out so well they tried to replace C++. Which also failed.

B. Its made by microsoft and microsofts software sucks.

C. C++'s low level memory management and it's ability to use every speck of computing power makes it the best choice.

You shouldn't have much difficulty using C++ if you know C# anyways. Microsoft is just trying to build a cutthroat little moat around programming languages. C++ will dwarf C# any day of the week, its ability to maximize processing power is unsurpassed.

When you are trying to do hundreds of millions of calculations, you need very tight programming, memory and processor usage. C++ is the stingiest, most ruthless programming language known to man and it will not give one spec of memory unless it absolutely has to.

Which means it process more, better and faster than anything else. Just a pain in the ass to program though - since everything must be done by hand.

Also, did you guys think of just building a minicomputer designed to calculate this puzzle? One could even go so far as to build a NN with the specialty NN processor to solve this puzzle.

Or you could also try coming up with a mathematical equation that could deduce which puzzle combinations are possible and which are not, based off of the clues and gray borders. Rather than brute forcing it, one could start off by eliminating combinations by the millions.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 26, 2007, 11:42 AM
Post #19


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



QUOTE(trojan_libido @ Oct 26, 2007, 10:52 AM) *
... I'm also not sure what you mean by a tree of 4 * 12?

Four times twelve is 48. The 49 was a typo. What I mean is that each tile in the puzzle is connected to a tree of possible neighbor configurations (4 tiles) with a branching factor of about 48. However, most of those four tiles on the edges will not fit with any tiles on the corners, so every nuncet (3 x 3 square) found has already filtered out a lot of non-solutions, so it should result in a speedup. We could establish one nuncet, then move our attention from the center of the nuncet to one of its boundary squares and continue building in that fashiom.

I think Max pretty well answered the question of choice of programming language. However, the purists will tell you that C is quite a bit faster than C++, but I avoid it because it doesn't support the object oriented paradigm (OOP) and so it makes programming complex problems very difficult. I don't even want to think about developing special hardware for this.

A neural network (NN) approach could be interesting. We could train it to solve nuncets, then go to 4 x 4, and so on. Maybe it could learn enough that way and just keep expanding until we get to 16 x 16.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 26, 2007, 11:55 AM
Post #20


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



Yea a NN might work out better, especially if we coded some sort of pattern recognition and get it to learn how to see in patterns rather than the normal calculation method.

I think we would need to do supervised learning for it. Say have the completed pattern for the small grid like you were talking about, then get it to solve the puzzle and use its newly learnt skill to solve the more difficult puzzle ;D.

I have a paid host with an FTP server if we need somewhere to host the code.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 26, 2007, 12:02 PM
Post #21


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Better to decide on a software design before we waste time coding.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 26, 2007, 12:06 PM
Post #22


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



Hm, well if we do NN it has to be able to do pattern recognition and be able to create the patterns as well. A NN would be much more efficient although it would also require more time training. If we put the learning rate too high then it will lose its effectiveness.

If we try to do some sort of pseudo brute force, it will take longer but require less time coding and no training time. So I suppose the first decision to make is pseudo brute force or NN?
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 26, 2007, 12:08 PM
Post #23


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Or we could just join Eternity2.net

http://eternity2.net/
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maximus242
post Oct 26, 2007, 12:14 PM
Post #24


God
******

Group: Basic Member
Posts: 1755
Joined: Jan 24, 2006
Member No.: 4768



Well if they get enough people they could solve it. No way we would solve it before them using computers, they just have too much processing power.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 26, 2007, 12:24 PM
Post #25


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Yep. I used to be a part of the SETI-at-home processing brigade. It's a nice setup. Idle CPU being put to work.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 26, 2007, 01:23 PM
Post #26


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



I dont want to use anothers engine, wheres the fun in that! smile.gif I already have a brute force method that works, would only require a bit work to make it distributed, but again its the challenge not the processing power.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 26, 2007, 01:52 PM
Post #27


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



In 30 years we will have quantum computers that will solve the puzzle instantly (if the technological pundits are correct). Why not just wait?
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 30, 2007, 12:23 PM
Post #28


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Over the last few days I figured out a way to solve the puzzle. The fact that there are many solutions, perhaps millions of them, allows us to use simulated annealing, a classic algorithm for search in complicated topographical spaces. See this reference for standard software implementations:

http://www.cs.sandia.gov/opt/survey/sa.html

To build an implementation for the Eternity II problem, consider that each tile can occupy one of 256 positions in the puzzle with one of four orientations, a possible configuration space of about a thousand.

Consider a solved puzzle to be at the lowest energy (temperature) state (all edges have a mate). Unmatched edges raise the energy level. The annealing algorithm seeks to minimize the energy level of the puzzle.

Assign each tile to a configuration point randomly to initialize (highest temperature). Then follow the algorithm to "cool" the puzzle as it settles automatically into a low energy state, one of many "solved" configurations. A successful implementation of the simulated annealing algroithm for Eternity II should have a running time of under an hour.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
trojan_libido
post Oct 30, 2007, 03:13 PM
Post #29


God
******

Group: Basic Member
Posts: 1351
Joined: Sep 19, 2006
From: UK
Member No.: 5681



That sounds very interesting. Do you place all 256 tiles before beginning the solution? I'll read that article tomorrow.
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rick
post Oct 30, 2007, 04:17 PM
Post #30


Supreme God
*******

Group: Basic Member
Posts: 5916
Joined: Jul 23, 2004
From: Sunny Southern California
Member No.: 3068



Yes, you start with a random placement (high energy) and let it seek a minimum energy solution. The set of the million or so zero energy configurations is the set of solutions.

See also:

http://mathworld.wolfram.com/SimulatedAnnealing.html

http://www.heatonresearch.com/articles/64/page1.html

http://www.taygeta.com/annealing/simanneal.html
User is offlineProfile CardPM
Go to the top of the page
+Quote Post

2 Pages V  1 2 >
Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 



Lo-Fi Version Time is now: 18th November 2017 - 05:20 PM


Home     |     About     |    Research     |    Forum     |    Feedback  


Copyright BrainMeta. All rights reserved.
Terms of Use  |  Last Modified Tue Jan 17 2006 12:39 am

Consciousness Expansion · Brain Mapping · Neural Circuits · Connectomics  ·  Neuroscience Forum  ·  Brain Maps Blog
 · Connectomics · Connectomics  ·  shawn mikula  ·  shawn mikula  ·  articles