In an earlier examination of games, we ran into some trouble when Hypergame, a “game” we defined, led to a contradiction. This ended up being a positive development, as the ideas we developed there led us to a (non-contradictory) proof of Cantor’s Theorem, but it indicates that, if we are going to be serious about our study of games, we need to be more careful about our definitions.
So, what is a game? Here’s what Wittgenstein had to say about the question in his famous development of the notion of language games and family resemblances:
66. Consider for example the proceedings that we call “games.” I mean board-games, card-games, ball-games, Olympic games, and so on. What is common to them all? Don’t say: “There must be something common, or they would not be called ‘games’” but look and see whether there is anything common on all. For if you look at them you will not see something that is common to all, but similarities, relationships, and a whole series of them at that. To repeat: don’t think, but look! Look for example at board-games, with their multifarious relationships. Now pass to card-games; here you find many correspondences with the first group, but many common features drop out, and others appear. When we pass next to ball-games, much that is common is retained, but much is lost. Are they all ‘amusing’? Compare chess with noughts and crosses. Or is there always winning and losing, or competition between players? Think of patience. In ball-games there is winning and losing; but when a child throws his ball at the wall and catches it again, this feature has disappeared. Look at the parts played by skill and luck; and at the difference between skill in chess and skill in tennis. Think now of games like ring-a-ring-a-roses; here is the element of amusement, but how many other characteristic features have disappeared! And we can go through the many, many other groups of games in the same way; can see how similarities crop up and disappear. And the result of this examination is: we see a complicated network of similarities overlapping and crisscrossing: sometimes overall similarities, sometimes similarities of detail.
-Ludwig Wittgenstein, Philosophical Investigations
This is perhaps the correct approach to take when studying the notion of “game” as commonly used in the course of life, but that is not what we are doing here. We want to isolate a concrete mathematical notion of game amenable to rigorous analysis, and for this purpose we must be precise. No doubt there will be things that many people consider games that will be left out of our analysis, and perhaps some of our games would not be recognized as such out in the wild, but this is beside the point.
To narrow the scope of our investigation, let us say more about what type of games we are interested in. First, for simplicity, we are interested in two-player games, in which the players play moves one at a time. We are also (for now, at least) interested in games that necessarily end in a finite number of moves (though, for any particular game, there may be no a priori finite upper bound on the number of moves in a run of that game). Finally, we will be interested in games for which the game must end in victory for one of the players. Our theory can easily be adapted to deal with ties, but this will just unnecessarily complicate things.
One way to think about a move in a game is as a transformation of the current game into a different one. Consider chess (and, just so it satisfies our constraints, suppose that a classical “tie” counts as a win for black). A typical game of chess starts with all of the pieces in their traditional spots (for simplicity, let’s be agnostic about which color moves first). However, we can consider a slightly different game, called chess_1, that has all of the same rules as chess except that white’s king pawn starts on e4, two squares up from its traditional square. This is a perfectly fine game, and white’s opening move of e2-e4 can be seen as a transformation of chess into chess_1.
With this idea in mind, it makes sense to think of a game as two sets of other games: one set is the set of games that one player can transform the game into by making a move, and the other set is the set of games that the other player can transform the game into by making a move. We will refer to our players as Left (L) and Right (R), so a game can be thought of as a pair , where and are sets of games. This in fact leads to our first rule of games:
First Rule of Games: If and are sets of games, then is a game.
Depending on one’s background assumptions, this rule does not necessarily rule out games with infinite runs, or pathological games like Hypergame. We therefore explicitly forbid this:
Second Rule of Games: There is no infinite sequence of games such that, for all , .
And that’s it! Now we know what games are…
The skeptics among you may think this is not enough. It may not even be immediately evident that there are any games at all! But there are. Note that the empty set is certainly a set of games (all of its elements are certainly games). Therefore, is a game. It is a boring game in which neither player can make any moves, but it is a game nonetheless. We can now begin to construct more interesting games, like , or chess.
There’s one crucial aspect of games we haven’t dealt with yet: who wins? We deal with this in the obvious way. Let us suppose that, in an actual run of a game, the players must alternate moves (though a game by itself does not specify who makes the first move). During a run of a game, a player loses if it is their turn to move and they have no moves to make, e.g., the game has reached a position , it is R’s turn to move, and .
Let us look now at a simple, illustrative example of a game: Nim. A game of Nim starts with a finite number of piles, each containing a finite number of objects. On a player’s move, they choose one of these piles and remove any non-zero number of objects from that pile. The loser is the first player who is unable to remove any objects.
Let us denote games of Nim by finite arrays of numbers, arranged in increasing order. For example, the game of Nim starting with four piles of, respectively, 1,3,5, and 7 objects will be represented by [1,3,5,7]. The trivial game of Nim, consisting of zero piles, and in which the first player to move automatically loses, will be represented by .
Let us see that Nim falls into the game framework that we developed above. The trivial game of Nim is clearly equivalent to the trivial game, . We can now identify other game of Nim as members of our framework by induction on, say, the total number of objects involved in the game at the start. Thus, suppose we are trying to identify [1,3,5,7] as a game and we have already succeeded in identifying all instances of Nim with fewer than 16 objects. What instances of Nim can [1,3,5,7] be transformed into by a single move? Well, a player can remove all of the objects from a pile, resulting in [1,3,5], [1,3,7], [1,5,7], or [3,5,7]. Alternatively, they can remove parts of the 3, 5, or 7 piles, resulting in things like [1,3,4,5], [1,1,5,7], etc. All of these Nim instances, clearly, have fewer than 16 objects, so, if we let denote the set of Nims that can result after one move of [1,3,5,7], then we have shown that is a set of games, in the sense of our formal framework. We can therefore define a game , which is clearly equivalent to [1,3,5,7].
In the next post, we’ll look at strategies for games. When can we say for sure which player wins a game? How can we derive winning strategies for games? And what does it all mean?
Cover image: Paul Cézanne, “The Card Players”