Seems there is a solution that could yield even larger numbers should you be able to go from the 3rd ring to the 1st ring and back on every step on your final move. Wouldn’t that generate an even higher score?

@bmvaughn – There are 169 lengths of path on the board that you can use, 35 of which you must use in the first 35 moves, leaving at most 134 for the final move. If you count the length of the blue path on the posted image, you’ll see it has length 134 and so it is indeed optimal — there is no way to do better.

Of course, there may be many, many other optimal boards out there. It doesn’t really matter *how* the final blue line crosses over the rest of the image — we could have crossed from the 3rd ring to the first and back repeatedly. But as you can see the posted image already uses all 12 entrances/exits of each tile, so there’s no way another strategy could do better.

here’s a different optimal path i found yesterday! nice mathematical analysis! http://twitpic.com/3sg374

@Michael – Awesome, thanks for sharing 🙂 It would be neat to somehow derive the number of optimal paths that exist, but it seems like a rather messy problem so I haven’t had the nerve to try my hand at it yet.

The odds are extremly high against an actual game resulting in an actual optimal path. The hexagons dealt to you are random, not all the same type as in your optimal path. There is no look-ahead either, so you can’t really plan your path out to the end.

However, the actual all-time high score for path length is 134, which is amazing, only 35 short of the optimal 169.

impossible — my highest score was 227 with 85 segments

Hi,
Hey, very nice analysis!
I think the question about the number of optimal paths is interesting, and as said, very difficult. However, once an optimal path is found (like the one here) one could ask what the chance of getting the right pieces in the right sequence if they are selected at random. Given the regularity of the optimal path found here (you need to get many long sequences of the same path!), the probability is pretty low.

Is anybody able to find the most non-regular optimal path? By regular I mean that it requires the shortest sequences of the same path for its construction.

Keep going!

@Nic
Wouldn’t that be a path length of 85, far less than 169?

Hello.

I am pretty sure your path is THE best if the scoring system was points= 1*2*3*….*n (where the best thing to do would be to score big on the last one, obviously). Im also pretty sure your path is optimal for each scoring system where having a long path is favoured more than having a ton of smaller paths. In short, there is some kind of “sur-optimality” in that path. Have to work on that.

Hey, for a game that’s simple on the surface and a heck of a lot of fun, it sure is complex! They should include this Entanglement in mathematics courses.

You should publish the sequence of maximal scores per game radius on OEIS, they don’t seem to have it. 🙂

Great work!

@JuanPi
Gotta be some hell’s combinatorics problem using Bernoulli and the fitness function T you derived.

@JuanPi
Wrong address, “Nathaniel derived” the T function.
Probability of one given path is pretty straight forward (1/6)^(3n(n+1)), n being field radius.
6 possible positions to every tile, probability of getting one specific position for each is 1/6. For k tiles it’s 1/6 at power of k.

It’s over 9000!

@Nic
Get Smart 😀

Finely people who proses the world the world the way i do

I’m fairly certain that it is written into the game that the same piece will never appear 4 times consecutively, thereby rendering this “Optimal path” nonexistent. I have not done the math, but based upon actually observing the game and how the pathes of the tiles are chosen, the highest score possible is in the 4000 range. Of course, we could always just ask the developers for a definitive solution.

@Dsplayname
I think you are wrong. the pieces are chosen randomly, there isn’t much sense in preferring one piece over another, though the probability of the same piece to appear in 4 consecutive times is (really) small.
Plus, I don’t think the developers care much about what is the highest score possible, they probably got more important things to do.

My best is only 235 and 96. And this so called highest score is flat impossible. Since there is no way of controlling which tile comes up next for you to use it cant be done. Besides that the funky patterns on the tiles used to show your “highest score possible” don’t exist in the first place. At least I’ve never seen any with any of those patterns to choose from. I would just like to see a screen shot of the final pattern for those scores shown that are over 1000. I’d really like to see the final pattern for today’s high of 1856 that’s listed, cuz I don’t belive that’s possible without some way of changing the tile selections, so that you have more than just the 2 to choose from, and being able to back up a move and change it.

@ColoradoHermit (and everyone else who mistook this post as meaning that 9080 is easily-attainable or some such thing) – I got all of the tiles from the game itself. Each and every tile in the image above is from a screenshot of the game; they all exist. I’m not so good at image manipulation that I was able to recreate them myself.

The reason that you perhaps don’t recognize some of them is because there are hundreds of different tiles in the game (there are lots of ways to arrange 6 paths between 12 nodes). This is also the reason why in most games you don’t see the same piece appear multiple times in a row. As far as anyone can tell though, they are indeed randomly-generated on the fly as the game is played (though feel free to e-mail the developer and ask if you believe otherwise).

Also, this post is about the mathematically best-possible score. Not the best score that you expect to attain on a given playthrough, or the best score that a “good” player will get, or the best score that you will see on the high-score boards. It is about the best *possible* score that you could ever, ever see, assuming someone got extraordinarily lucky. It means that if someone said “I bet you $1 trillion that I got a score of 9081 on Entanglement”, you should take that bet, whereas if they said “I bet you $1 trillion that I got a score of 9080” then you should maybe think twice.

It’s just like how the best possible score in Jeopardy! is $566,000. Of course no one has actually ever won that much, but that’s the most that anyone could ever hope to win in a single episode.

As for how likely it is to get a string of tiles that could potentially lead to an optimal game with a score of 9080, I simply don’t know. The image included in this post is not the only optimal board – it is just one that is particularly “nice”, has relatively easy-to-see optimality, and is easily generalized to boards of different radius. There are plenty of optimal boards out there that use very different tiles and have no apparent symmetry, but they’re not particularly fun to draw or come up with, and they’re not particularly enlightening to look at either.

Anyway, I’m glad that so many people found this post interesting. Cheers 🙂

dig the math, brother. based on the first few games i have played….i wondered about the highest possible score.

ftl, heavyier than a planet, and way past the point of know return….

rock on!

@Nic i scored 319 on my 15th attempt with a path length of 89.i think much higher score can be attained.I can share my scrrenshot if you want.

@Everyone
So now we know that for a given set of random hexes(for one full game), that the computer dishes out one by one, there are many optimal paths with maximum score. What do we try to achieve in each step to get as close to the maximum score as possible?

@Nic
possible, mine was 304 with 95

My highest score is: 391 with Path: 87.

http://www.facebook.com/photo.php?fbid=1736516665043&set=a.1735016867549.95475.1602415814&theater

I did some quick work, and there are 12 connections on each tile. for the first connection there are 11 possible positions, for the second there are 9, third 7, fourth 5, fifth 3, and sixth 1. 11*9*7*5*3=10395 possible combinations of paths through a tile. unfortunately I’m not mathematician enough to know if this number includes non-unique rotated paths or not. if it does, then I’m not sure how to find the number of unique paths, because 10395/6 doesn’t give an integer quotient

I started playing Entanglement a few weeks ago, and while I can’t seem to break my score of 673, I don’t think I should be ashamed about “only” getting 16th on the daily top 100. It did take a lot of luck to get that far.

Anyway, I was actually thinking about this subject while I was playing earlier today, and the equation that I came up with is a lot simpler than anything I’ve seen on this page. I got the same total as you, so here’s my theory for any move in the game–

(n+1)(n/2)

If you take that and apply it to the “maximum possible score” question, it looks like this–

35+(134+1)(134/2)
35+(135)(67)
35+9045
__________________
9080

As you know, that 35 is the initial 35 that’s used to fill up the board, and the 134 is that epic final move.

I’ve tried it with a lot of path lengths, and it seems to work in all cases. So if anyone’s brain starts to hurt when they’re thinking about points, it’s (n+1)(n/2)

Actually sorry- I found that equation up there right before the beginning of the comments@Derek

There are pieces in your solution that never appear in the game, is there an optimal solution with only possible pieces ?

You should calculate the probability of getting all of those tiles (assuming the piece generator is truly random)

A good solution. A somewhat more difficult problem will be, what is the highest attainable score in the Sakura Grove mode. When I have some more time next week I will give that a shot.

@Nick
None of the pieces used in this path are made up. The board is made entirely of possible game pieces. Of course, it is very unlikely that a person is given these pieces in the correct order, but it is still possible.

The highest score to date is 3551. I had a personal best score of 951 with 41 path segments on the last move, on a different game with a lower score I got 92 as the longest path. To get a high score you must construct a very long path separate to the one you are currently on which you then use in your last move.

I have been dabbling in this game a bit, and it is certainly addictive. My all time best is only 359 with longest path of 98. Nowhere near a record.

I tend to build huge paths, but then get screwed and lose out when I can’t get the final piece needed to connect to it! Oh well. Would be interesting to play on a larger board too bad you cant just adjust it in options or something.

I was intrigued by the comment:

“The reason that you perhaps don’t recognize some of them is because there are hundreds of different tiles in the game (there are lots of ways to arrange 6 paths between 12 nodes).”

So I thought I would try and work out how many different tiles there were. After several hours and much hair-pulling later, I eventually came up with an answer of 1,799! Can this really be correct?

@Jof – Yep, 1799 is correct 🙂 That number can be computed using Burnside’s lemma or via brute-force (I’ve done it both ways just to be extra sure). It’s also worth pointing out that not all of the tiles are equally probable — tiles with lots of rotational symmetry occur less frequently. For example, the tile in the top-left corner with six half-loops on it only has probability 1/10395 of occurring (and no, it’s not a coincidence that 10395 showed up in Jon’s comment as well).

@Nathaniel
I went the brute-force route. Wrote a program to create all the different sets of paths (yes, I got 10395 of these). Then came up with a notation that would allow me to ‘rotate’ these tiles to see if they matched any of the others and used this to eliminate the duplicates. Good to know my logic was correct. Thanks for the very interesting blog.

@Nathaniel

Maybe I’m just stating the obvious here (or using fancy names for something obvious), but it seems to me that if we consider the board (excluding path ends facing walls/the central hexagon) an undirected graph, regarding hexagons as nodes and connections as edges, every Eulerian cycle (a cycle using all edges exactly once) whose first 35 edges form a Hamiltonian path (a path that visits all nodes exactly once) would be an “optimal path”.

I might not really constructively be getting us closer to the number of optimal paths, but since counting Eulerian cycles is known to be #P-complete (http://en.wikipedia.org/wiki/Eulerian_path#Complexity_issues), at least I hope to substantiate that it’s hard! Not sure how the regularity of the graph and the restriction that the first 35 edges have to be Hamiltonian adds to/subtracts from the complexity, though.

Not sure if anyone has noticed and/or agrees, but it seems to me that Entanglement is at least partly based on chess. You can move only one “square” (well, hexagon) the first move. Later, you can create a Knight-move (2 and a half steps). Obviously, you cannot create a Bishop or Queen move (diagonally) because you would hit the centre, but you can definitely make a Rook move. The walls are angular, no doubt, but it IS possible to move in a kind of a “straight line” and “connect the dots” if you see what I mean. Aside from the moves, the logic is also chess-like. The centre (King) can never be compromised. The longer you control the centre (the line of hexagons between the line closest to the centre and the line closest to the wall) you increase your chances of maximizing your score. I just thought it was interesting that there were so many similarities between chess and Entanglement.

Great analysis Nathaniel! Being like-minded, I had been thinking of figuring this out myself, but couldn’t find the time due to time spent playing the game instead. 🙂 Just scored my best score to date, 754, path length 131. I’m not sure that I’ll beat that too often…

1821. 128 length. Gotta quit… I’d love to see a breakdown of the probabilities of getting different kinds of tiles, e.g. the oh-so-valuable non-intersecting types good for the outer ring, or of horribly intersecting (i.e. six straight lines).

Okay, I will accept (because I’m lazy) that there are 1799 distinct organizations of 6 non-intersecting paths connecting 12 nodes. Now, like most players, we sometimes have to gamble that in the next tile we will get at least one path configuration that we desire. What is the probability of that? Release the Mathletes!

@Nathaniel

Okay, I will accept (because I’m lazy) that there are 1799 distinct organizations of 6 non-intersecting paths connecting 12 nodes. Now, like most players, we sometimes choose to gamble that in the next tile we will get at least one path configuration that we desire. What is the probability of that? Release the Mathletes!

Would someone mind computing, then posting the probabilities of each path configuration? Nathaniel, that sounds right up your alley! 😉 Thanks!

@Pythius Jang – Each tile has either a 1/10395, 2/10395, 3/10395, or 6/10395 probability of appearing at any given stage, depending on the rotational symmetry of that tile. Tiles that are completely rotationally symmetric (e.g., the piece at the top-left of the image in this post that has the six U shapes on it) are the least likely to occur (i.e., probability 1/10395). Shapes that are 120-degree rotationally symmetric have probability 2/10395. Shapes that are 180-degree rotationally symmetric have probability 3/10395. Finally, shapes that have no rotational symmetry are most common, with probability 6/10395 each.

The high scores I’ve seen published could only be achieved by someone who had hacked into the program to make manipulation possible.

Givin’ a try to at least guess the number of routes leading to the optimum score (a bit over midnight, so I’m not too sharp, but I think I’m right; please comment if I’m making any mistakes.)

Starting the first path passing all tiles (the green one above), the first step is irrelevant (due to symmetry), the next gives you 5 possible moves, and after that, following the inner ring and then the second gives you 16 moves where each moves gives 4 possible directions (going directly outwards will lower that, but I’ll ignore that for the guess). The outer ring leads only to two possible ways to pass all consecutive tiles: clockwise and counter-clockwise. That gives 5 x 2^16 x 2, comes down roughly to 10^10.

Then ‘entangling’ the way back passing all 134 possible steps that are left (the blue line). Let’s first look at the number of possible paths to follow per tile: for the tiles in the second circle, that’s 9 (12-2-1=9: -2 are the points where the green line runs through, -1 for where you enter the tile). Similarly, the number of paths per tile are 3 for the corner tiles, 5 for the outer ring, and 7 for the center ring. I hope you get where I’m going so cutting my story short would yield a final number of (9!)^12 x (7!)^6 x (3!)^6, and that multiplied by the 10^10 I mention above, which comes down to 4 x 10^103.

Even if this guess is over-estimated, it will still give an increadibly high number. It must be possible to get one of these possible solutions with the random tiles given 🙂

But, to disencourage you all from trying, there must be roughly 11^(12*36) = 10^450 routes possible that give any lower score.

Just today, 2013-04-13, “Smart Familiar Mandolin” has posted two impossible scores: 1234567 (which is clearly hacked) and 10,119 (which must be a cheat, thanks to Nathaniel’s theorem). Also, “Free New Flag” has posted 6972 today. This is also suspicious, since it occurred today, and since the 4th all-time high score is 5353.

Have such fake scores appeared before, and been erased?

Continued…
I have checked and “Free New Flag”‘s score was not posted today. It was posted this week.

Great maths there! I miss the days when I understood what you said.

on a side note: Lofty Prancing Llama currently holds 39 of the top 100 all time scores. Sadly s/he peaked at 8th a mere 1111 points from the current highest of 5195.

My record is 191 on 83. Long way to go yet.

My best is 263, my wife’s is 243, my 9 yr old son got 288 on his 3rd game. Scary thing is the wife and I both have 130+ Iq, scares me to think what his might be. He’s even smart enough to sit back and watch his frustrated parents try to best his score rather than try to show off and go higher.

I was going to leave a comment congratulating you on your analysis, empathising over those who had to complain about what they had misinterpreted, and laughing at all the people who feel the need to show off how much maths they don’t quite understand, but have heard of.

Then I spotted the “Assistant Professor” and saw that at the time of this post you were working on your Ph.D. in mathematics.

My kudos on your analysis seem somewhat trite now, so, may I say, congratulations on your appointment 😀

@Jon Not sure if anyone answered this, but you have to divide by n-1, if n is the number of unique node to node paths with a turnable tile, or 5 and not 6, making 2079 possible turnable tiles. But I seem to know so many of the tiles that show up, so maybe the programmers picked somewhat less than 2079 to put in the game.

@JDarc Oh well, I wasn’t taking symmetry into account. Darn. Back to my cut out tiles to test my math. 🙂

@JDarc
Why am I staying up so late for this? I find patterns irresistible – that has to be it.

In my preliminary research on symmetry, I’m finding the math will be much more complex when limiting tiles that look completely different to a human.

For example, let’s say 4 paths will use this algorithm (node-x + 4). The 4 paths are identified as nodes 1-5, nodes 2-6, nodes 3-7, nodes 4-8. Then the two remaining paths could have their own repeatable pattern of (node-x + 1) or they will not follow any repeatable algorithm. Those remaining two paths can only be situated in two ways. For the example, I’ll say the paths are nodes 9-12 and 10-11. If you turn the tile and write down the new resulting paths, mathematically there will be 4 unique path sets. But the tile “looks” the same to a human, so there is only 1 tile that will be used in the game. Even if you look at the mirror image of this tile, it’s the same, again leaving only one tile.

Now for an example where the mirror image is different. The tile is not symmetrical, yet some paths will use the same algorithm. For 4 of the paths, I used two different repeatable algorithms (node-x + 1 and node-x + 5) and the 2 remaining paths had non-repeating algorithms. The first set of these paths are:
Nodes 1-2
Nodes 3-4
Nodes 5-10
Nodes 6-11
Nodes 7-9
Nodes 8-12

Mathematically there are 6 sets of unique paths in that example. But the tile looks the same any way it’s turned. Because the tile is not symmetrical, the mirror image looks slightly different – this results in 6 more unique path sets. So there will only be two tiles used in the game, not 12 as math would suggest.

Math calculations for the true number of tiles in the game can be found based on these 3 dynamics:
-The number of paths that use the same algorithm
-The number of paths that use different algorithms than any other path
-The decision about symmetry (the mirror image thing)

However, I have not figured out the math. I have only played with little hexagonal cutouts and noted my human-view findings. 🙂