Eternity II is here!!
Last week, the Eternity II puzzle (which I’ve talked about here and here) went on sale. I can finally wipe up the drool-puddle-of-anticipation that’s been forming on my desk and get to work cracking this nut.
Unfortunately for those of us in the United States, the puzzle is not available here, and there are very few online retailers willing to ship the puzzle to the USA.
But I did track down the puzzle at Hamley’s and placed my order. Their online shopping cart is a little bit crappy (it got confused verifying my non-European billing address), so I had to call them on the phone ( (+44) 800 2802 444) and a very friendly girl with an Irish accent took my order.
I placed the order at noon last Wednesday, and the package was delivered (in Boston, MA) by about 2:00 pm on Friday.
Holy crap.
At first, I thought they must have used an American order-fulfillment location, but the package had international shipping stickers and a return address in the UK, so it seems to be an actual international delivery. Fulfilled in just two days. I’m very very impressed. I had no idea that it was even possible to ship something overseas so quickly.
The puzzle cost £35, plus another £25 for shipping. With today’s lousy exchange rates and the weak dollar, that’s a total of $120. Unfortunately, when I win the $2 million prize, that means I’ll really only be netting $119,999,880.
Bummer.
Anyhow, if any of you American algorithm enthusiasts have been sulking because you can’t get Eternity II here, sulk no more!!
August 7th, 2007 at 6:03 pm
So, Benji, I’ve got a few ideas for ways to attack this problem. Are you or anybody else going to publish the list of pieces online for those of us too cheap to buy the game? Or should I offer to help you for only $999,940 of the prize money?
August 8th, 2007 at 9:19 am
Hey, Robby! How’s things?
Unfortunately, I won’t be publishing a list of the pieces. The E2 rules make it very clear that anyone sharing a list of piece descriptions (with or without the official graphics) is subject to immediate disqualification.
After I placed my order (thinking it’d be a few weeks before it arrived), I started hunting around on the E2 Yahoo! Group, asking for a list of pieces. I was quickly informed about the strictness of the rules.
Just a few days ago, in fact, Lord Christopher Monckton, the third Viscount of Brenchley (the game’s creator), posted on the Y! group threatening ALL of us with disqualification simply for posting to the group.
So anyone who wants to play has to buy the puzzle. That’s fine by me. I was always planning on buying it.
But, after opening the box, I had to manually key all of the pieces into some sort of file format. (A process almost as error prone as it is mind-numbing, as you try to remember that “blue box with green circle with an X-shape” represents “edge 12″, or whatever.)
Someone on the E2 Y! group posted a checksum of the official pieces, so I was able to determine that my pieces had at least one error. But I couldn’t figure out *where* the error was. So I started from scratch, spending another 2 hours punching in the orientations of 1024 different edge patterns. Again.
After the second try, I did a diff between the two data files and found my errors. What a pain in the ass. Even if I had found a description of the files online, I would have still bought the puzzle, but at least I wouldn’t have had to do all that data entry.
I have considered posting a little script that people could use to check their data entry a little more thoroughly (using row checksums and column checksums, rather than a single checksum, so that the script could tell you *where* you made your errors). But no, sadly, I won’t be publishing the pieces.
August 9th, 2007 at 10:59 pm
Hi Benji
There is some free software at http://eternity2.net to allow anyone who owns the eternityii puzzle to use their computer to try to solve the puzzle. You can read all about it there.
More importantly, perhaps, for you, would have been the utility program at http://eternity2.net/e2editor.php, which is a graphical editor to help you create the definition of the pieces. This utility program shows you simply (with red/green colour coding) which pieces you have entered correctly, and which have a typo.
Cheers,
Dave Clark
August 10th, 2007 at 9:34 am
Ah, very clever, Dave. A few of my friends have offered me their spare computing cycles, if I send them a distributed solver. This seems rife for trouble, though.
Let’s say 10 people run your distributed solver. Each of them navigates a different part of the search tree, and eventually one of them finds a solution. What about the other nine people? None of those nine people contributed anything less than the guy whose computer stumbled upon the solution. I think you’re in dangerous waters. I know I’d hate to be the one to explain to those other people that they were a part of a victorious team but don’t get any of the spoils.
Thanks for making the e2editor available. I actually used it to do my first round of data entry, and I found it very helpful. Unfortunately, I made a few errors, so the checksum failed. After that, I used Malcolm Bailey’s javascript tile inputter, available in the Y! group files section, and was subsequently able to do a diff between the two files to find my errors. (I made *nine* data entry errors in e2editor. Yikes! Curiously, I only made one error with the JS inputter.)
In the off chance that you’re actually still tinkering with e2editor, here are a few feature requests:
* Create a mode where the cursor automatically advances (clockwise, starting on the south edge) around each tile, and from tile to tile. Having to click back and forth between the board and the edges, and having to manually select each edge was actually the cause of several of my data entry errors.
* Rather than just supporting a single checksum, generate a set of checksums on the rows and columns (and possibly the diagonals). A user could load a set of checksums from a text file (much like the piece list is currently loaded). Validating the board against row, column, and diagonal checksums would allow the software to triangulate the *location* of errors rather than just reporting pass/fail. This would have saved me about two hours.
* Support a mode where GIF images are loaded for each of the edge types (if people prefer to create their own images, in lieu of using the palette settings). I think the reason I had more success with the JS inputter is because it had the actual images of the E2 tiles.
Of course, I don’t actually need any of those features anymore, now that I’ve confirmed the accuracy of my piece list. I know if I were in your shoes, I wouldn’t spend much time adding feature enhancements to what’s basically a one-time-use, freeware piece of software. Then again, if a better tile inputter increases adoption of your distributed solver, it might be a good idea.
Anyhoo… thanks Dave!! Your tool was a huge help for me. Good luck with your solver!
August 13th, 2007 at 9:13 am
Hi Benji
What would you say are the odds of someone solving this puzzle manaully without any computer model?
Monde
August 13th, 2007 at 9:49 am
Zero.
August 16th, 2007 at 7:59 am
Hi Benji,
I am kind of on the same page as you regarding the reward system of eternityii.net’s distributed computing effort. I programmed a solver a few weeks ago (before the game came out) that does about 20M piece placements per second with lookahead (checks whether there is any empty board cell with zero playable pieces to avoid wasting time). I was considering setting up a distributed computing project where rather than two people splitting the prize, it would actually be distributed quite a bit more. Something like this:
1) $400K goes to the developer of the distributed application
2) $400K goes to the person that actually finds the solution, if applicable :-)
3) $400K gets split among the people that complete the most work units (i.e. the more work you do, the more you get)
4) $400K goes to a charity selected by the folks that do at least one or two work units.
5) $400K gets split at random among people (say, 400) that do at least one or two work units (e.g. like a lottery)
OK, this payout scheme certainly way more complicated than a simple 50/50 split, but it provides an incentive to a lot of people to participate that wouldn’t otherwise. #3 provides an incentive to folks with lots of computing resources to work the problem even though their chances of finding a solution themselves is still quite small. #4 would be great for generating publicity and rallying folks who’d rather see their computer cycles going toward helping a worthy cause. #5 gets people with less computing resources involved because they know that they still have a chance at getting $1000 or whatever just for participating minimally.
Of course the amounts could be shuffled around and a tax attorney would have to weigh in to ensure that things aren’t taxed a zillion times as the money is divided, but in principle, it seems like a more “fun” way to work the problem. I think it would just be cool to watch the online graphs change over time, showing how many work units different people have done and stuff like that :-) I was looking at just using BOINC, but hadn’t really gotten that far.
The issue with requiring folks to enter in their own piece definitions makes things a bit more burdensome on wouldbe participants. CM’s threats aside, I don’t really know what the copyright laws would prevent as far as including an encoding of the game pieces in the software (to what extent would that be a derived work, especially if the internal encoding is nothing like 256 pieces with four edges). But regardless it seems reasonable that the judges could disqualify you for whatever reason they want to, so even if no laws are broken, you lose the prize if they somehow “found out”. Makes it all less conducive to a public distributed computing effort.
Anyway, you probably know now that Toy R Us in the US has it for quite a bit less than $120, but maybe those few extra days let you find your solution? :-)
Cheers,
Bill
August 20th, 2007 at 4:45 pm
Kinda lame they don’t give you a relatively simple means of obtaining the dataset, but at the same time it’s understandable. Copyright protection schemes only keep honest people honest, someone will leak it eventually, but the more honest bunch would’ve been the majority of their revenue anyway.
Good luck on the puzzle, Benji. Keep us posted on how your endeavors are going.
-Brian
August 23rd, 2007 at 5:30 pm
Eternity II is now available in the US from TOYSRUS.COM!
September 6th, 2007 at 11:25 pm
Hi Benji,
Well, it’s been quite a while since the puzzle was published. I haven’t dug around too much but I imagine someone has sent in a valid solution by now. But if not, or if you still want to hear my weird ideas for attacking it, drop me an email.
Hope all is well in beantown,
Robby
September 22nd, 2007 at 7:33 pm
Hi Benji,
I’m just curious, how large is your search space at the moment (with your current heuristics)? Have you calculated anything on computing time / position?
Whats your general approach? Which algorithms have you discarded? Have you tried any genetic algorithms? I heard saw someone mention simulated annealing as something interesting to try.
I’m working on a solving engine written in c++ using stl/boost and a java gui on the eclipse platform which connects to the engine via jni.
My goal is to have a platform to try out different heuristics and compare them against each other at various board sizes to get a feel of their strengths and weaknesses. I’m setting up a testbench for the engine which can generate random boards of any size - both solvable and none solvable, so I can verify my code.
I do not think I will take home the money though, the eternity2 project at eternity2.net has probably already a solution to this, or will have in the coming months - at least before me.
Regards,
Daniel
September 28th, 2007 at 4:35 pm
INFINITY2 FREE DEMO VERSION
Find the Eternity`s solution!!!
FREE DOWNLOAD
http://rapidshare.com/files/58807680/setupInfinity2-Demo.exe
WEB PAGE
http://www.infinity2game.blogspot.com
October 19th, 2007 at 3:07 pm
Daniel,
For Eternity I, I seem to recall that the winner took 18 months to get a solution. The puzzle has only been out for ~4 months.
“To the proper military authority: I’m calling to the commandant’s attention the recent changes noticed in the attitude towards fighting of soldier Daniel. He has attempted on several occasions to escape his duties … and made defeatist comments in public.”
:)
-Brian