In its early years, the rigorous study of games (game theory) looked only upon games of so-called perfect information, in which each player knows the moves carried out by all players. Such games laid the foundation for early economic models of perfect competition, wherein consumers have full knowledge of both market conditions and each others’ consumer tendencies.
Of course, perfect competition — taken literally — cannot exist, and the failure of this model and others prompted economic theorists to study a more-general class of games, games of limited information (also known as games of imperfect information).
In this post, we’ll look at one-player games of limited information (sometimes classified as puzzles, not games) through a topological lens, and create for each game a poset of topologies under which topologically indistinguishable points correspond to outcomes that are indiscernible in a limited-information context. Expanding this dictionary, we’ll describe a topology on the outcome space under which the “safe” or “warranted” extension of one’s limited information relates to the continuity of certain maps.
— PART I (THE DICTIONARY)–
Our discussion will be modeled around Minesweeper-type games, a game archetype that includes in addition many grid-based logic puzzles. In this setting, the “limited information” is encoded in the set of revealed grid tiles, which — depending on the rules of the game — may (or may not) conform to particular patterns. In this sense, a round of the game is a map
in which is the game-space (e.g. the set of grid tiles) and is the space of outcomes (e.g. the numbers 0-9, union “the mine”), and is consistent with the rules of . Let
denote the set of valid rounds to the game . For each subset , we define an equivalence relation , such that precisely when identically. Following this, we define (for fixed ) a topology on , with basis the cosets of . (In other words, the open sets are precisely the (possibly empty) unions of cosets in .)
In general, two sets in a topological space are said to be topologically indistinguishable if they are contained in exactly the same open sets (equivalently, in the same closed sets). One motivating property of our construction is that two games are topologically indistinguishable with respect to if and only if they agree on the tiles of . (You may want to pause and verify this.)
Example 2: (A continuation of Example 1.) In the trivial topology, each pair of points is topologically indistinguishable (hence no two games are differentiated). On the other hand, all points are distinguished in the discrete topology, i.e. this space is . (Of course, totally disconnected spaces satisfy not just one, but all of the separation axioms.)
A second, subtler advantage to our construction is its naturality: an inclusion of sets induces an “inclusion” of topologies, in the following exact sense:
For two topologies over a single topological space, we say that if all open sets in are open in . If so, is said to be coarser than , while is said to be finer than . We remark that the relation “” defines a poset on all topologies over a given space.
We have the following:
Proposition: The surjection
given by is inclusion-preserving.
Proof: If are subsets of , let denote the coset class of under the equivalence . To show that , it suffices to prove that can be written as a union of cosets in . But this is clear, as
in which the union runs over all cosets such that .
Whereas is by construction surjective, it will rarely inject. Minesweeper, as a typical example, yields a non-injective map . (See the Exercises.) Nevertheless, we give now (for completeness) a criterion equivalent to the injectivity of :
Theorem: The map is an inclusion-preserving bijection if and only if the following condition holds:
() For all , there exists a coset that splits non-trivially (i.e. into multiple cosets) under .
Proof: Necessity of the condition () is clear: if for two sets this condition does not hold, then all open sets under are open under , giving . Thus by our Proposition, i.e. .
On the other hand, suppose that fails to inject, and take for two sets . Then , so is a non-empty union of cosets under . Any coset in this union is open in (hence a union of -cosets). But the only open set (with respect to ) contained in is , so we have for all . Suppose by symmetry that . It follows from definition alone that . Taking and , we find a contradiction to criterion ().
— PART II (REFINEMENT)–
In Part I, we discussed at length the ways in which an increase in limited information can be modeled by a refinement of topologies over the space of rounds . In this section, we focus on the process of extending one’s limited information, in relation to the existence of continuous maps into (and its powers).
To set the stage for our work this section, suppose that a game has been determined mod (i.e. the outcomes of on are known). The simplest of all scenarios occurs when the map fails to inject; specifically, when for some . Here, it’s simple to show that (regardless of ), hence defines a unique function mod .
More follows if we specify beforehand, as would happen in practice. In this case, we obtain a unique extension of to containing if and only if; that is, if forms a single coset mod . (To borrow from algebraic number theory, one might say that is “inert” with respect to .)
Inertness has an equivalent formulation in the continuity of certain maps. To keep things simple, let us first assume that is obtained from with the inclusion one additional element . If is given the discrete topology, then the map
given by evaluation at is continuous if and only if it is constant (i.e. when). In greater generality, we have (for ) if and only if
is continuous. (Here is given the product topology.)
It turns out that this second formulation is more useful. To see why, let’s consider again the case of Minesweeper:
Example 3: In the familiar case of Minesweeper, our outcome set consists of the integers 0-9, as well as the mine . If our game is known on and lies outside of , we need not have full knowledge of on to expand our limited information. Rather, it suffices to know whether or not is a mine, i.e. which component of the partition
of that lies in. If this component is fixed as varies over , then we are justified in expanding our limited information to include the value of on . But this happens precisely when the map is continuous with respect to the partition topology on .
All together, we’ve stumbled upon an “algorithm” for justifiable and/or safe play:
- Partition into the minimal number of components required to inform safe play under general conditions.
- Given knowledge of on , let be maximal such that is continuous with respect to the partition topology on (whence the product topology on ).
- This justifies knowledge of on ; now repeat step 2.
If is finite, the procedure above will terminate (in finite time) with knowledge of on some subset . Dependent on we have two cases (here, we assume finite):
- , in which case we have won our game.
- , in which case we reveal some such that the Bayesian probability of winning (given knowledge of on weighed against the risk of guessing ) is maximized.
Combined with our earlier procedure, this gives an optimal (probabilistic) strategy for , which need not be a winning strategy. (This result, we remind the reader, relies upon the finiteness of .)
— PART III (GENERALIZATIONS) —
If our game space is infinite, far less can be said. For instance, it could very well be that our “algorithm” above may never terminate (although these “infinitely long games still hold interest for certain game theorists; see determinacy).
A second means of generalization comes from relaxing our assumptions on (while keeping finite). Here, our algorithm for careful play proceeds without a hitch, while admitting the novel possibility of an infinite number of different rounds . Indeed, the only sticking point in this more general setting is our reliance upon Bayesian probability.
Working over a finite set of rounds allows us to (implicitly in the previous) make use of a uniform distribution on . Without this standard, invocation of Bayesian probability requires a priori knowledge of the distribution of rounds in . Alternatively — if the distribution of rounds is not known — we could employ a frequentist approach, hopefully converging upon optimal play (using a machine-learning algorithm, say).
Simple examples of this more general behavior are included in the Exercises.
— EXERCISES —
Exercise: Show that the function given by associated to the game of Minesweeper is not injective. (Hint: consider at which point the round is determined.)
Exercise: Let be a region, and let be a closed, measurable set with finitely many components. We define
in which is the volume of the -dimensional unit ball and is the indicator function of . Fix some . We define a game of limited information as follows: the player chooses such that . If, the player loses (immediately). Otherwise, play continues until the player can ascertain the number of connected components of . Prove that this game has a winning strategy if and only if
- We do not lose on the first turn.
- is pre-compact (equivalently, totally bounded).
- The connected components of are simply connected.
Prove that (2) can be dropped if we are allowed to take countably many turns. (This might be called a “-winning strategy.)
Exercise (The Secretary Problem): Let be a list of real numbers (unknown to the player). We define a game of limited information as follows: the player views the elements of sequentially, and may stop at any point. If the player stops at , the round ends and the player wins if and only if . What is the optimal (probabilistic) strategy, as ? How does this problem change if is known to be sampled from a given distribution?