Topological Tic Tac Toe 3: Hypergraph Games

I keep telling myself that I’m a geometer/topologist, but I keep acting otherwise. I’ve been attending lectures by Imre Leader at Cambridge on Hypergraph Games. I attended the first lecture on a whim, having never thought about games or graphs or combinatorics in my life (other than my odd fascination with topological tic tac toe). Five minutes into the lecture, I realized that topological tic tac toe is a hypergraph game! Moreover, I found the lecture thoroughly entertaining, and I’ve been following the course attentively since. So in this post, which is sort of an appendix to my previous posts (1, 2) on topological tic-tac-toe (henceforth called T4 for short), I will discuss the wider context of hypergraph games. Much of the general presentation here follows Leader’s lectures.

Although I’ll briefly indicate how T4 fits into this larger picture, let me give the short answer up front: game-theoretically, it’s a fairly boring and straightforward example. But as a visualization exercise or as a gimmick, I still think it’s groovy.

Throughout this post, all sets will be taken to be finite; this isn’t essential everywhere, but it simplifies certain things. The data of a hypergraph game are a set called the board and a collection of subsets of which are called the winning lines of the game. Two players (P1 and P2) take turns marking elements of ; each element can only be marked once. The game ends when one player has marked all the elements of a winning line; if the board is exhausted with neither player winning, then the game is a draw. A particular state of the game is called a position; precisely, it is a choice of two disjoint subsets of —those marked by P1 and those marked by P2—such that P1 has marked either one or zero more elements than P2 has. Note that this necessarily encodes whose turn is next.

We are most interested in what happens when P1 and P2 both play with perfect strategy. A winning strategy (for P1) is a function from the set of positions on the board to the set of possible moves such that in any play of in which P1 plays according to , P1 will win. A drawing strategy (for P1) is the same, except the guaranteed result is that the game is a draw or P1 wins.

Proposition 1: For any hypergraph game , exactly one of the following holds:

1. P1 has a winning strategy
2. P2 has a winning strategy
3. both P1 and P2 have a drawing drawing strategy

Proof: The proof is by “backtracking.” We say a position is a P1 winning position if whenever the game is played from this point (with perfect strategy), P1 wins; define similarly the notions of a P2 winning position and a drawing position. (We allow such positions to be such that the game is already finished.) Let . Then every position in which all elements are marked is one of these three possibilities: winning for P1 or P2, or drawing.

Inductively, suppose all positions with at least elements marked is either winning for P1 or P2, or drawing. Let be a position with elements marked; without loss of generality, suppose P1 is next to move. There are finitely many possible resulting positions after P1 moves. If any of these are P1-winning, then is P1-winning. If all are P2-winning, then is P2-winning. If none are P1-winning and not all are P2-winning then by the inductive hypothesis at least one must be drawing. Hence P1 will play for a draw and is drawing. Hence, by induction, the initial position in which no elements of are marked is either P1-winning, P2-winning, or drawing; the Proposition follows, as the status of the initial position is the status of the game itself. Q.E.D.

Hence we can refer to a given game as either a P1 win, a P2 win, or a draw. In fact, we can improve on this. You may wish to try and prove this yourself before reading the given proof.

Proposition 2: No hypergraph game is a P2 win. In particular, if a hypergraph game can never end in a draw, then it is a P1 win.

Proof: We use the technique of “strategy stealing.” Let be a winning strategy for P2; we will find a winning strategy for P1, yielding a contradiction. Note that for either player an extra move can never hurt (think this through!). P1 begins by playing anywhere, say . Then it is as if P1 were the second player with an extra element marked. So playing according to is a win for P1; if at any point says P1 should play at , then P1 plays anywhere unmarked, say , and on his next turn resumes play according to . In the future, if calls on P1 to play at , then P1 plays anywhere unmarked and then resumes , and so forth. Hence P1 has a winning strategy. Contradiction! Q.E.D.

Note that the strategy-stealing proof of Proposition 2 is completely non-constructive! One theme in the theory of hypergraph games is the search for explicit winning strategies to particular games. This is very hard! Many (most?) of the known winning strategies for small games are by case analysis. If you constructed winning strategies to the various flavors of T4 similarly to the way that I did, then you were essentially doing clever case analysis, in which you used observation and/or symmetry to cut down the number of cases considered. This quickly becomes unwieldy for larger boards.

While there seems to be a dearth of general techniques for constructing winning strategies, there is one which helps for constructing drawing strategies—the technique of a pairing strategy. Let be a hypergraph game. Suppose one can choose exactly two elements from each winning line such that all elements are distinct; we call this a splitting of the board. Then P2 has an easy drawing strategy: whenever P1 plays by marking one member of a given pair, P2 responds by marking the other member. Since by Proposition 2 a P2-winning game is impossible, it follows that any hypergraph game which admits such a splitting is a draw. Exercises 1-3 below give some practice with splitting strategies.

We conclude with what may be a surprising fact to some.

Warning: Based on our intuition and what we have seen in the various flavors of T4, one might conjecture the following: if a hypergraph game is a P1 win and is a collection of subsets of which contains as a subset, then the hypergraph game is a P1 win as well. This is false, and the phenomenon is known as non-monotonicity. Exercises 4 and 5 below are a do-it-yourself example.

Exercises:

1. Use case analysis to show that the games of 3×3 tic-tac-toe and 4×4 tic-tac-toe are draws.

2. Construct pairing strategies for 5×5 and for 6×6 tic-tac-toe, showing both are draws.

3. Given a pairing strategy for x tic-tac-toe, construct one for x tic-tac-toe. Conclude that for , the game of x tic-tac-toe is a draw. Why wouldn’t this work for x tic-tac-toe?

4. Let be the set of vertices of a binary tree of depth ; that is, and the bottom row has leaves. Let consist of the subsets of which are direct paths to leaves along the tree; there is one of these for each leaf. (By direct, we mean each step descends one level.) Show that the hypergraph game is a P1 win in moves.

5. Let be the game of the previous exercise on a binary tree of depth . Add one winning line to the set such that the resulting game is a draw, proving that non-monotonicity can occur.

About these ads