generalizing hex to higher dimensions Hex, Havannah
12 replies. Last post: 20180305
Reply to this topic Return to forum
lazyplayer at 20171229
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 20171229
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 :)

lazyplayer at 20171229
Arek, there are two “obvious” ( :D
hahaha
References:
https://en.wikipedia.org/wiki/Trapezorhombic_dodecahedron
https://en.wikipedia.org/wiki/Rhombic_dodecahedral_honeycomb
https://gamedev.stackexchange.com/questions/18608/istherea3dequivalentofhextilemaps 
Ignatius J Reilly at 20171230
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 2ndimensional ball into polyhedra. (i.e. choose a tiling of the 2nball, 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 Poincaredual to a highdimensional 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, 7gons, etc. are fine, so long as only three polygons meet at each vertex.)
* The boundary of the 2ndimensional 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 3dim’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 2nball is black, part is white, and part is still empty. A winning board state for black is one in which a core (n1)sphere inside the black part of the boundary bounds an ndimensional hypersurface inside the black part of the 2nball. 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 4ball.
* 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 2nball) symmetric between black and white. Unfortunately, neither the rhombic dodecahedron nor the trapezorhombic dodecahedron will work, since neither of these tilings is generic in the soapfilm sense.

lazyplayer at 20171230
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 20171230
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 20171230
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 4dimensional 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 20171230
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 warmups for the 4d, 6d, etc. examples.

Ignatius J Reilly at 20171230
Two additional remarks:
(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 3dimensional tiling of the box to be generic (in the soap film sense).

David J Bush at 20180128
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 20180305
Y can be generalized to any evennumbered dimension using microreduction:
First, let’s restate the game of Y in 2d in more abstract terms. Imagine the board as an upwardpointing 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 lowerleft of it is (x+1,y) and the one to the lowerright (x, y+1).
Now, to perform microreduction on a filled board of size n, on a new board of size n1 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 n1. Repeat the process to end up with a size 1 board with a cell of the winning color.
Using microreduction as a defining feature of Y, we can extend the game to be played on a simplex of any evennumbered dimension. Using ordered ntuples, 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 microreduction 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 ntuple) 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 prefilling 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