A Hyperbolic Variant of Tic-Tac-Toe

Year: 2023 Authors: Sarah Chen; Manil Suri

Core claim

With modified rules, hyperbolic tic-tac-toe and a spherical variant both allow either player to force a draw, and a cell-based criterion helps choose optimal moves.

Topics

tic-tac-toe variants, hyperbolic geometry, game strategy, pedagogy, crochet geometry

Domains

combinatorial games, non-Euclidean geometry, hyperbolic plane, spherical geometry, crochet, mathematical visualization, craft-based modeling, educational game design

Methods

case analysis, move-tree reasoning, symmetry arguments, strategy evaluation

Media

crocheted board, 13-cell hyperbolic board, six-cell spherical board, paper diagrams

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2023 Conference Proceedings

A Hyperbolic Variant of Tic-Tac-Toe

Sarah Chen ${}^1$ and Manil Suri ${}^2$

${}^1$ Honors College and Dept. of Psychology, UMBC, Baltimore, MD, USA; schen8@umbc.edu ${}^2$ Dept. of Mathematics and Statistics, UMBC, Baltimore, MD, USA; suri@umbc.edu

Abstract

We consider a variation of tic-tac-toe played on a truncated hyperbolic plane, the inspiration for which arises from using crochet to create hyperbolic geometry. Instead of a $3\times 3$ grid, we now have 13 cells. We show that using some modified rules, each player can again force a draw, as is the case for the usual flat version. We briefly consider tic-tac-toe on a sphere as well, for which we show that the same outcome of a draw holds. Finally, we present a strategy that can be used to choose the best move. Our game variations can be used pedagogically to engender more familiarity with non-Euclidean geometry.

Variations of Tic-Tac-Toe

The game of tic-tac-toe on a $3\times 3$ plane grid is well-known, and several variations have been proposed and mathematically investigated over the years, see e.g. [2][3][4]. These variations are often over a grid drawn on a flat (Euclidean) plane or its higher-dimensional versions. Our primary purpose in this paper is to present and analyze the case when the underlying surface is a hyperbolic plane. This technically fits into the general problem of tic-tac-toe games defined on hypergraphs, see [1].

Our hyperbolic variation was developed by the first author as a class project while she was enrolled in an Honors Seminar taught by the second author, based on his book [6]. In particular, Chapter 13, drawing on the work of Taimina [7], shows how non-Euclidean versions of the plane can be represented in three-dimensional space through the use of crochet. This led to two crocheted versions of non-Euclidean tic-tac-toe “boards” - the first a truncated hyperbolic plane with 13 cells, and the second a sphere with six cells, as shown in Figure 1.

Figure 1: The crocheted hyperbolic and spherical boards

Taken along with the standard 9-celled flat board, this set of three games can be used as a pedagogical tool to foster more familiarity with geometries that have negative, positive and zero curvature. In each

Chen and Suri

case, the goal is to occupy three cells in a “line.” The spherical board turns out to be trivial to play and analyze, so we concentrate mainly on the more interesting hyperbolic case here.

Description of Hyperbolic Tic-Tac-Toe

Recall that the hyperbolic plane has more “area” than the flat plane (while the sphere has less). We manifest this in our hyperbolic board by adding an extra cell at each corner. As a result, there are now five cells that meet at each vertex, instead of four in the flat case and three in the spherical case (at least for the way we have chosen to tile these geometries). For representational purposes, we project these cells onto the plane of the paper and number them from 1 to 13, as shown in Figure 2. Keep in mind, though, that the cells are all congruent quadrilaterals.

Figure 2: Numbering of cells on the hyperbolic board

We will designate 1-2-3, 11-13-5 and 9-8-7 to be winning “horizontal” lines and 12-11-10, 2-13-8, 4-5-6 to be winning “vertical” ones. As for diagonals, the addition of the extra corner cells has the effect of creating more of them, which in turn makes the central square too powerful. We therefore add two rules to those of flat tic-tac-toe, to diminish this power:

1. We allow the diagonals 1-13-7, 3-13-9, 4-13-10 and 6-13-12 as winning configurations, but disallow the others (1-13-6, 3-13-10, 4-13-9 and 7-13-12). So now we have only two extra diagonals compared to flat tic-tac-toe.
2. We disallow the first player (who will always be X) from claiming the center space (cell 13) on the first turn. Otherwise, as shown below, this always leads to a victory for X. This is because the center still has two extra winning lines passing through it compared to flat tic-tac-toe, so it remains more powerful.

Totaling the allowable horizontal, vertical and diagonal lines specified above, we now see that hyperbolic tic-tac-toe has a total of 10 winning configurations, compared to 8 in the flat case.

Analysis

We know that for flat tic-tac-toe, if X and O both play their best game, then each can force a draw. A complete analysis is available in [2], where a comprehensive tree of all possible moves is plotted out. Our main goal here is to check whether the spherical and hyperbolic variants share this “draw” property.

The spherical case is easily dispensed with. If X claims any cell, then O just needs to claim the diametrically opposite cell to safeguard against a loss. If O doesn’t claim this cell, then by claiming it on the next move, X ensures victory. Overall, both X and O can clearly force a draw.

For the hyperbolic case, the answer is not obvious. There are more possibilities than regular tic-tactoe, which sparks new interest in the game. Players may need to engage in it several times before they can

A Hyperbolic Variant of Tic-Tac-Toe

figure out good strategies. Only after this might they be able to intuit that like the flat case, either player can once again force a draw.

Let us prove this. We will do this by using a similar technique as in [2], i.e. by essentially running through appropriate lists of possible moves. X’s moves will be denoted as $\mathrm{X}k$ , and O’s as $\mathrm{O}k$ , where $k$ is one of $\{1,2,\dots ,13\}$ . We begin with the following theorem.

Theorem 1: If $\mathrm{X}$ is allowed to start with cell 13, then for any subsequent move by $\mathrm{O}$ , $\mathrm{X}$ can force a win.

Proof: Consider first X13,O1. Then X can move X4, forcing O10, after which X5 gives X two avenues for victory, only one of which can be blocked by O in the next move. Next, consider X13,O2. Then X4 again precipitates O10, and X5 again leads to X’s victory. The other possibilities for O’s second move all have similar outcomes by symmetry. $\square$

As stated earlier, we will therefore disallow X from taking the center in the first move.

Theorem 2: Suppose O fails to claim the center on O’s first move. Then X can always force a win.

Proof: To win, X will claim X13 on X’s second move. Suppose $\mathrm{X}k$ is X’s first move, then the game’s conclusion would be exactly the same if these two moves were interchanged (i.e. X13 became X’s first move, and $\mathrm{X}k$ was X’s second). Due to the same symmetry noted in the previous proof, we therefore only need to consider the scenarios X13,O1,Xk and X13,O2,Xk.

For X13,O1,Xk, it is easily seen that for $k=5,6,10,11,12$ , the game proceeds analogously to the case $k=4$ detailed in the proof of Theorem 1, resulting in a win for X. The case $k=2$ forces O8, after which X4 forces O10 and then X5 gives X a win. Similarly, $k=3$ forces O9, after which X4 leads to a win as before. The case $k=8$ forces O2, which forces X3, which forces O9. Then X4 leads once more to a win. Similarly, $k=9$ forces O3, which forces X2, which forces O8, after which X4 leads to a win. Let’s now consider $k=7$ followed by Om. The case $m=2$ forces X3, which forces O9, and then X4 leads to a win. A similar scenario prevails for $m=3$ . For $m=4,5,6,10,11,12$ , X can play X9 to win. Finally, for $m=8$ or 9, X plays X4 to lead to a win.

For X13,O2,Xk, the cases $k=3,4,5,6$ don’t force X, who can easily win. The case $k=7$ is equivalent to the case X13,O1,X7,O2, which we have just seen gives X a win. The cases $k=1,9,10,11,12$ all follow by symmetry. This leaves $k=8$ . Suppose it is followed by Om. The case $m=1$ reduces to the case X13,O1,X8,O2 which we have seen gives X a win. The case $m=3$ follows by symmetry. The remaining values of $m$ don’t force X, who can then easily win.

From the above, we see that the first two moves have to be $\mathrm{X}k,\mathrm{O}13$ . By symmetry, we only need to consider X1, O13 and X2, O13. We now state the following theorem, whose proof we omit, because it is similar to that of the above theorem.

Theorem 3: (a) Let the first three moves be X1,O13,Xk. Then for $k=2,3,7,8,9$ , O can force a win. For $k=4,5,6,10,11,12$ , X can force a draw..

(b) Let the first three moves be X2,O13,Xk. Then for $k=1,3,7,8,9$ , O can force a win. For $k=4,5,6,10,11,12$ , X can force a draw.

Remark: For part (b), only the cases $k=5$ and 8 need to be considered, since the rest can be verified to follow from part (a) and symmetry.

From the above theorems, it is clear that X always has several choices with which to force a draw, with X’s second move being the crucial one. We can also easily show that O can always force a draw. So the situation is the same as in flat (and spherical) tic-tac-toe.

Strategy

Theorem 3 gives us all possible ways (up to symmetric equivalents) to launch the game, together with corresponding final outcomes, when players continue with their best plays. Let us try to find a

Chen and Suri

mathematical characterization that will allow us to differentiate the cases for which O can force a win from those where X can force a draw. In other words, a rule that will instruct X on which cell to occupy on X’s second move. To fix things suppose we are at the juncture X1,O13,Xk. We’ll look for a rule that tells X to pick any cell $k$ for which $V(k)$ (an appropriately defined value assigned to each open cell $k$ ) is maximized.

Intuitively, the best cells for X to occupy would be those that lie on the maximum number of lines, since this can both block the line for O and open up a potential victory for X. We might therefore want to simply define $V(k)$ to equal the number of lines passing through cell $k$ . However, this doesn’t work, since $V(k)=2$ for all $k$ that are unoccupied.

A more promising definition, given in [3], is based on the work of Erdős and Selfridge for tic-tac-toe games set on $n^d$ boards (i.e. Euclidean $d$ -dimensional boards with $n$ cells in each dimension). Now we weight the contribution to $V(k)$ of each line passing through cell $k$ differently: If this line already has an X on it, the contribution is 0, if the line is empty, the contribution is 1, and if the line has an O on it, the contribution is 2. This gives $V(7)=1$ , $V(2)$ , $V(3)=2$ , and $V(k)=3$ for other $k$ . Since $V(k)=3$ for both the case $k=4$ (draw) and $k=8$ (win for O), this definition also doesn’t work. Using the variation in [5] to define $V(k)$ also fails.

What does work is if we count cells rather than lines. More precisely, consider all lines that pass either through cell $k$ or any cell already occupied by $X$ (in this case, cell 1). Define $V(k)$ to be the total number of distinct unoccupied cells in the aggregate of such lines. Then it can be verified that $V(k)$ equals 3 or 4 for any $k$ which O can win and equals 6 for any $k$ which X can draw. The same holds when we consider X2,O13,Xk. Hence, to make the right choice on the second move, X should pick any $k$ that maximizes $V(k)$ .

This criterion gives the best moves further along in the game as well, so can be used to determine an optimal strategy. Moreover, this strategy also works for flat $3\times 3$ tic-tac-toe. We will examine this criterion and its applications in more detail in the future.

Summary and Conclusions

A variant of tic-tac-toe where the $3\times 3$ flat board is replaced by a 13-cell board on a hyperbolic plane injects new interest into the game, while also giving players more insight into non-Euclidean geometry. It turns out that either player can force a draw in the new game proposed, just like in the case of flat tic-tac-toe. A mathematical criterion can be used to choose the best moves, but we recommend playing the game often enough to discover such strategies the fun way.

References

[1] J. Beck. Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008. [2] E. R. Berlekamp, J. H. Conway and R. K. Guy. Winning Ways for your Mathematical Ways, vol. 3, 2nd edition, pp. 733-736. A. K. Peters/Circ Press, 2003. [3] R. C. Gammill. “An Examination of Tic-Tac-Toe Like Games.” AFIPS ‘74: Proceedings of the May 6-10, 1974, national computer conference and exposition, May 1974, pp. 349-355. https://doi.org/10.1145/1500175.1500249 [4] M. Gardner. Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games, pp. 37-46. University of Chicago Press, 1988. [5] P. Glynn-Adey. “A Potential Strategy for Huge Tic-Tac-Toe.” Math Horizons, Vol. 30, No. 2, 2022, pp. 16-19. https://doi.org/10.1080/10724117.2022.2113682 [6] M. Suri. The Big Bang of Numbers: How to Build the Universe Using Only Math. W. W. Norton, 2022. [7] D. Taimina. Crocheting Adventures with Hyperbolic Planes. 2nd Edition. A. K. Peters/Circ Press, 2019.