generalizing hex to higher dimensions Hex, Havannah

10 replies. Last post: 2017-12-30

Reply to this topic Return to forum

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

    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 3-dimensional tiling of the box to be generic (in the soap film sense).

Return to forum

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]