generalizing hex to higher dimensions Hex, Havannah
10 replies. Last post: 20171230
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).