Euler plays Ingress

In the game Ingress you capture portals (by visiting real world locations), and then you can link pairs of portals together. You get points for doing that. If three portals are mutually linked with three links, forming a triangle, then they make a control field, and that’s a good thing if only because you get a lot of points for doing that. So if you’re trying to level up, one way is to find a lot of portals close together and circulate between them, capturing them and linking them.

One rule of linking, though, is that links can’t cross. If you want to link two portals, and a straight line segment between them intersects some other link, then tough luck: you can’t link them.

(Technically, if the Earth is regarded as a sphere, presumably links are great circle segments and control fields are spherical triangles. But for our purposes we pretend we’re working in a plane. Links are line segments, control fields are Euclidean plane triangles.)

So a question you might ask is, for some collection of portals, is there an optimal way to link them? Can you make more links or more control fields if you do it one way than if you do it another?

Answer: No. If you start creating links, and keep adding links until no more links are possible, then regardless of how you decide which links to make, you always get the same number of links, and the same number of control fields.

And how many is that?

You get the answer using the Euler characteristic. For any convex polyhedron,

F - E + V = 2

where F, E, and V are respectively the number of faces, edges, and vertices the polyhedron has. A cube, for instance, has 6 faces, 12 edges, and 8 vertices:

6 - 12 + 8 = 2 .

What do polyhedra have to do with portals? Well, the same idea applies to any connected planar graph (a graph with non crossing edges), which can be thought of as the shadow of a polyhedron, provided you realize every region of the plane bounded by edges is a face, including the region extending to infinity. So this graph

also has 6 faces, 12 edges, and 8 vertices, if you count as faces the central quadrilateral, the four quadrilaterals surrounding it, and the infinite region surrounding them.

Viewed as linked Ingress portals, though, it’s not maxed out; in fact, there are no control fields because none of the polygons are triangles. So you can add more links until you have, for instance

and now there are 11 faces, 17 edges, and 8 vertices; 11-17+8=2.

But to maximize links and control fields, all the polygons in the graph, except the external one, must be triangles. Each of the F-1 triangular faces has 3 edges. But E\ne 3(F-1), because where two triangles adjoin, a single edge is one of the bounding edges of both triangles. It serves as two edges, in a way. On the other hand, edges of triangles along the boundary are shared with the external polyhedron. So if we regard the external polyhedron as contributing zero edges then each internal triangle (not along the boundary) contributes 3/2 edges, and each boundary triangle contributes 2 edges. Or

E = \frac{3}{2}N + \frac{1}{2}N_b

where N=F-1 is the number of triangles and N_b is the number of boundary triangles, which is the same as the number of edges or vertices in the bounding polygon (which is the convex hull of all the vertices). Solving for N,

N = \frac{2}{3}(E-\frac{N_b}{2})

Then combining with the Euler characteristic,

\frac{2}{3}(E-\frac{N_b}{2})+1-E+V = 2

or

E=3V-N_b-3

In the above diagram, V = 8 and N_b = 4 so E = 24-4-3 = 17, which is what we see. This tells us no matter how we link portals, once we’ve made all possible links, the number of links we end up with is the same. And the number of control fields, N, is

N = \frac{2}{3}(3V-N_b-3-\frac{N_b}{2}) = 2V-N_b-2

And again in the above diagram, N = 2\times 8-4-2 = 10 which is correct. No matter how we link a given set of portals, we end up with a fixed number of control fields. All that matters is the number of portals, and the number in the convex hull.

Holographic Fifteen

Here’s a pretty good, simple discussion of the holographic principle. Its main failing is that it conveys the impression that the holographic principle is true! And maybe it is, but it’s only been proved for certain particular cases… not for the universe we live in.

For more on the concept of duality, think about the following game which I’ll call “Fifteen”. (I’ve forgotten where I first read about this. Anyone know of where this has been written up before?) We have nine cards bearing the numbers 1 through 9. Deal them out face up, and then you and I take turns picking up one card at a time. If at any point one of us has three cards in hand that add to 15, that person wins. (If we pick up all nine cards and neither of us has three that add to 15, it’s a draw.)

So for instance:

  1. I take 5.
  2. You take 1.
  3. I take 6.
  4. You take 4.
  5. I take 7.
  6. You take 2.
  7. I take 3 and win, because I have 5 + 7 + 3 = 15.

Is this game a win for one player or the other, and what’s the optimum strategy? Think it over before continuing.

Time’s up!

Okay… think about it like this. I said “Deal [the cards] out face up” but didn’t specify how. It doesn’t matter how, but suppose you do it like this:

8 1 6
3 5 7
4 9 2

That of course is a magic square of order 3. Each row, each column, and each diagonal sums to 15. In fact, as you can easily figure out, those are the only eight sets of three distinct integers in the range 1 to 9 that sum to 15.

So when you’re alternating picking up cards, the first to take all the cards a line of three — row, column, or diagonal — wins. Sound familiar? Right: Tic-Tac-Toe (or Naughts and Crosses, or, as someone once told me they call it in Norway, Swedish Chess). Fifteen and Tic-Tac-Toe are not the same game, but there’s a duality between them: The rules of either one map onto the rules of the other, and given a situation in one game, there’s a corresponding situation in the other. For example, the penultimate situation in the example game above (I hold 5, 6, and 7, you hold 1, 2, and 4, and it’s my turn) corresponds to the Tic-Tac-Toe position

   | O | X
-----------
   | X | X
-----------
 O |   | O

and the winning Tic-Tac-Toe move corresponds to my taking 3. So there’s a winning strategy in Fifteen for the first player, which is dual to the winning strategy in Tic-Tac-Toe.

Likewise the holographic principle asserts that a three dimensional universe is dual to its two dimensional surface (let’s not get into what “surface of the universe” actually means… good question but not for here and now); different mathematics describes the physics of the volume and the surface, but there is a mapping from either onto the other, and given a configuration of the volume, there’s a corresponding configuration of the surface, and vice versa. Knowing what happens on the surface, you can map that onto the volume to find what happens there, and vice versa.

 

2048

Lately I’ve been spending way too much time playing 2048 by Gabriel Cirulli. It’s a ridiculously simple (to play; not to win) puzzle game: you use the arrow keys to slide numbered tiles around on a 4 by 4 grid; tiles with the same number merge when they collide to form one tile with double the number; a 2 or 4 tile drops randomly on each turn. You “win” if you make a 2048 tile, but you can then go on to try to increase your score after that.

Given the random element there’s no guaranteed winning strategy. But some general principles tend to work for me:

I try to keep my highest numbers in the bottom row, with the highest one in the lower right corner. The point is that, say, a 512 can’t merge with anything but another 512; if there’s a 512 next to a 2, the 2 gets “starved” because you can’t “feed” it from that direction until you’ve built it up to 512 (or you move the 512 and 2 apart). On the other hand, it’s great to have a 256 next to a 512 because once you “feed” the 256 and turn it into a 512, you can then merge the two 512s right away.

Keeping the high numbers in the bottom row means I almost never  use the up arrow. Lift the bottom row and you’re likely to get a 2 or 4 placed under it! Where it’ll starve, taking up space; meanwhile the high number it’s shoved up is starving low numbers around it.

I also try not to use the left arrow unless the bottom row is filled, or there are no legal right arrow or down arrow moves. Again, if you move the bottom row left, you run the risk of getting a 2 or 4 shoved in on the lower right next to your biggest number. It’s not likely, unless there are few vacant spaces in the grid, but it can happen.

If the bottom row is full (and there are no pairs to merge in it) then the left arrow is safe, of course.

So most of my action happens on the lower left. I build up a number on the left side (first or second position from the left) of the second row I can merge with the number below it. Then merge. Repeat until there’s a mergeable pair in the bottom row. Arrow right to merge them… and now things are dangerous, the bottom row’s not full and I try to avoid left arrows until a tile appears in the left column and I can drop it to the bottom. Occasionally I run out of right and down moves in that situation and have to hold my breath, hit the left arrow, and hope the new tile doesn’t show up in the bottom row. If it does it’s hard to recover the game, once you’ve built up the highest number to 256 or so. If it doesn’t, of course I always move right on the next move.

Of course it’s good to have numbers in a powers-of-two sequence orthogonally connected. Then when you get two of the lowest number next to one another you can merge them, then merge that with the next, merge that with the next, and so on, eating up the whole sequence at once.

Other than that, I pretty much play by learned instinct based on previous games. Lately if I can avoid stupid moves (like an ill-conceived up, or left with the bottom row unfilled) I find I can get to 2048 a fair fraction of the time. Maybe more than half.

An easier version of the game is here: http://siva1456.github.io/2048/ (thanks, Louis Nick) (Actually it’s easier to win, but about as hard to play once you keep going.) Another version, very doge, such hard, is here: http://doge2048.com/

I’m going to brag by putting up an image of my best game. Feel free to avoid looking at it if it’ll just irritate you. Feel free not to rub my face in it if you’ve done better.

Screen Shot 2014-03-18 at 3.44.42 PM

Update: Of course my best has gotten better this past week, and the other day I astonished myself with this result:

Screen Shot 2014-03-24 at 11.03.02 AM

I’ve now retired from 2048. No really.