### generalizing hex to higher dimensions Hex, Havannah

12 replies. Last post: 2018-03-05

generalizing hex to higher dimensions
• lazyplayer at 2017-12-29

hi guys

do you have any idea how it can be done while preserving property of exactly one winner?

i think winning paths have to become winning surfaces, but it’s not clear to me how to make it work...

• Arek Kulczycki at 2017-12-29

1 question... In 3d, instead of hexagons, what blocks should we use? Cubes, dodecahedrons or icosahedrons? This question makes one realize how complex the subject is :)

• Arek Kulczycki at 2017-12-29

Oh, sorry, I realized only cubes are possible :)

• lazyplayer at 2017-12-29

Arek, there are two “obvious” ( :D
hahaha
References:

https://en.wikipedia.org/wiki/Trapezo-rhombic_dodecahedron

https://en.wikipedia.org/wiki/Rhombic_dodecahedral_honeycomb

https://gamedev.stackexchange.com/questions/18608/is-there-a-3d-equivalent-of-hex-tile-maps

• Ignatius J Reilly at 2017-12-30

There are some relatively obvious and straightforward generalizations of hex to even dimensions:

* Let n be a positive integer.  (e.g. n=1 for standard Hex)

* Subdivide a 2n-dimensional ball into polyhedra.  (i.e. choose a tiling of the 2n-ball, perhaps an irregular one.)  In order to prevent tied games, this subdivision should be generic, in the sense that the strata locally look like (high dimensional) soap films.  (Another way of saying this is that the subdivision is Poincare-dual to a high-dimensional triangulation.)  When 2n = 2, then this means that every vertex is trivalent (so a square or triangular tiling is not allowed, but a hexagonal tiling (as in standard Hex) is allowed.  The subdivision need not be translationally invariant; irregular arrangements of pentagons, hexagons, 7-gons, etc. are fine, so long as only three polygons meet at each vertex.)

* The boundary of the 2n-dimensional ball is a 2n – 1 dimensional sphere.  This sphere can be divided into two thickened n – 1 dimensional spheres, one for the black player and one for the white player.  When n=1, a 0 dim’l sphere is a pair of points, and a thickened pair of points is a pair of intervals.  These are the two black (or white) sides in standard hex.  When n=2, we have a 3-dim’l sphere divided into to thickened circles (also known as “solid tori”).

* Players take turns coloring polyhedra.  After several moves have been played, part of the 2n-ball is black, part is white, and part is still empty.  A winning board state for black is one in which a core (n-1)-sphere inside the black part of the boundary bounds an n-dimensional hypersurface inside the black part of the 2n-ball.  When n=1, this means that a pair of points (one in each component) in the black part of the boundary of the disk can be connected by an arc.  When n=2, this means that a circle inside the black solid torus bounds a surface inside the black part of the 4-ball.

* Ties are not possible.  This follows from standard homological arguments (Alexander duality (https://en.wikipedia.org/wiki/Alexander_duality), more or less).  Since moves cannot hurt one, it follows that the first player has a winning strategy.

* There should be various ways to make the board (the 2n-ball) symmetric between black and white.  Unfortunately, neither the rhombic dodecahedron nor the trapezo-rhombic dodecahedron will work, since neither of these tilings is generic in the soap-film sense.

• lazyplayer at 2017-12-30

Ignatus, thank you very much, i’m still trying to understand the terminology of your reply. Can you provide a clear example with N=1?

• lazyplayer at 2017-12-30

Perhaps you can “show” us by drawing it (the N=1 case) in a board like this: http://www.trmph.com/havannah/board#10,

• Ignatius J Reilly at 2017-12-30

The n=1 case is a family of board games, all of which are similar to (or in some cases identical to) standard Hex.  I’ll try to draw a picture to illustrate this with some example boards and post that in a separate message.

The n=2 case is the first interestingly new example.  It’s played on a 4-dimensional board.  With a computer interface, I think it would be playable.  The computer could present 3d slices of the 4d board from various angles.

• Ignatius J Reilly at 2017-12-30

Here are some examples of the n = 1 case: http://canyon23.net/perm/2d_generalized_hex_examples.pdf

I’m not claiming that these 2d cases are interesting — I’m sure many instances have already been described elsewhere.  They are just meant to be warm-ups for the 4d, 6d, etc. examples.

• Ignatius J Reilly at 2017-12-30

(1) I claimed that the first player has a win (above), but this was assuming (implicitly) that there was a symmetry of the board which interchanges black and white.  During most of the discussion I have not been making this assumption.

(2) If we are willing to tolerate even greater asymmetry between the roles of black and white, then it is possible to construct examples in odd dimensions, and in particular in 3 dimensions.  For purposes of illustration, assume the board  is the shape of a rectangular box with lattice dimension H x W x L (height x width x length).  Black’s goal is to build a string connecting the top and the bottom of the box.  This will require at least H moves.  White’s goal is to build a surface separating the top and the bottom of the box.  This will require at least W*L moves.  By adjusting the parameters H, W and L, we can tune the game so that it is balanced between black and white.  (The first guess would be that we need H = W*L, so that the minimal winning configurations for black and white have roughly the same number of moves.)  In order for ties to be impossible, we must choose the 3-dimensional tiling of the box to be generic (in the soap film sense).

• David J Bush ★ at 2018-01-28

Lazo does not preserve winner exclusivity, but it is a 3D path connection game from a topological standpoint. The pieces stack on top of each other like cannonballs. The shape of the tiles ensures that each new layer must be formed in only one way. The lattice of cells that results comprises the framework for defining the game object. A winning path is a loop of same color pieces (which might include the board surface as part of the loop.) There must be a hole passing through this loop consisting of vacant spaces in the lattice or opposing tiles. So, this hole path must also be part of the lattice. As in Havannah, counting moves is necessary. At the moment, the only way to play this online or against the computer is with the Zillions of Games software, which is not free. I don’t recommend you buy ZoG just to play this one game. But the computer opponent does play a decent game. The module is called "Loop Game." You can play online in real time with someone who knows your IP address.

• HexNash at 2018-03-05

Y can be generalized to any even-numbered dimension using micro-reduction:

First, let’s restate the game of Y in 2d in more abstract terms. Imagine the board as an upward-pointing triangle of hexagonal cells. Label the topmost cell with the coordinates (0,0). Now label the two adjacent cells below it (1,0) and (0,1). Continue labeling all the cells such that for any cell (x,y) the one to the lower-left of it is (x+1,y) and the one to the lower-right (x, y+1).

Now, to perform micro-reduction on a filled board of size n, on a new board of size n-1 color in cell (x,y) with the majority color of cells (x,y), (x+1,y), and (x,y+1) on the filled board. Do that for every cell except the very last row to end up with a filled board of size n-1. Repeat the process to end up with a size 1 board with a cell of the winning color.

Using micro-reduction as a defining feature of Y, we can extend the game to be played on a simplex of any even-numbered dimension. Using ordered n-tuples, label the “topmost” cell as all 0s, and each cell under it as +1 in a single element. For example, in four dimensions, the topmost cell would be (0,0,0,0) and the cells adjacent to it “below” would be (1,0,0,0), (0,1,0,0), (0,0,1,0), and (0,0,0,1). Note that one can easily check if cells are adjacent if their coordinates differ from another by +1 or -1 in a single element, or differ by +1 and -1 in exactly two different elements.

To perform micro-reduction in this generalization, simply take the majority color of a cell and its children (in other words, the majority color of the set containing a cell and the cells one gets by adding 1 to each element in its n-tuple) and put that color in the corresponding cell of a board of one smaller. In even dimensions, there will be an odd number of cells in each of these sets, so a majority color will unambiguously be chosen. Just like with 2d Y, repeat this step with every smaller board until you get a board of size 1 with a single, winning, color.

Unfortunately, I have no idea how to visualize what a winning state would look like on a large board in such dimensions (other than 2, of course), but I assume it still connects facets of the polytope in some way.

I suspect that it might be able to generalize Hex as well by pre-filling in certain cells in these Y boards, just like how 2d Hex can be played within a 2d Y board, but I’m not sure what that would look like in dimensions greater than 2 either.

I originally posted this discovery in a much altered form on the BoardGameGeek Abstracts forum:
https://boardgamegeek.com/article/18020001

#### Reply to this topic

Include game board: [game;id:123456] or [game;id:123456;move:20] or [game;id:123456;move:20;title:some text]