Games with the computable-play paradox

The_Chess_Game_-_Sofonisba_AnguissolaLet me tell you about a fascinating paradox arising in certain infinitary two-player games of perfect information. The paradox, namely, is that there are games for which our judgement of who has a winning strategy or not depends on whether we insist that the players play according to a deterministic computable procedure. In the the space of computable play for these games, one player has a winning strategy, but in the full space of all legal play, the other player can ensure a win.

The fundamental theorem of finite games, proved in 1913 by Zermelo, is the assertion that in every finite two-player game of perfect information — finite in the sense that every play of the game ends in finitely many moves — one of the players has a winning strategy. This is generalized to the case of open games, games where every win for one of the players occurs at a finite stage, by the Gale-Stewart theorem 1953, which asserts that in every open game, one of the players has a winning strategy. Both of these theorems are easily adapted to the case of games with draws, where the conclusion is that one of the players has a winning strategy or both players have draw-or-better strategies.

Let us consider games with a computable game tree, so that we can compute whether or not a move is legal. Let us say that such a game is computably paradoxical, if our judgement of who has a winning strategy depends on whether we restrict to computable play or not. So for example, perhaps one player has a winning strategy in the space of all legal play, but the other player has a computable strategy defeating all computable strategies of the opponent. Or perhaps one player has a draw-or-better strategy in the space of all play, but the other player has a computable strategy defeating computable play.

Examples of paradoxical games occur in infinite chess. We described such a paradoxical position in my paper Transfinite games values in infinite chess by giving a computable infinite chess position with the property that both players had drawing strategies in the space of all possible legal play, but in the space of computable play, then white had a computable strategy defeating any particular computable strategy for black.

For a related non-chess example, let $T$ be a computable subtree of $2^{<\omega}$ having no computable infinite branch, and consider the game in which black simply climbs in this tree as white watches, with black losing whenever he is trapped in a terminal node, but winning if he should climb infinitely. This game is open for white, since if white wins, this is known at a finite stage of play. In the space of all possible play, Black has a winning strategy, which is simply to climb the tree along an infinite branch, which exists by König’s lemma. But there is no computable strategy to find such a branch, by the assumption on the tree, and so when black plays computably, white will inevitably win.

For another example, suppose that we have a computable linear order $\lhd$ on the natural numbers $\newcommand\N{\mathbb{N}}\N$, which is not a well order, but which has no computable infinite descending sequence. It is a nice exercise in computable model theory to show that such an order exists. If we play the count-down game in this order, with white trying to build a descending sequence and black watching. In the space of all play, white can succeed and therefore has a winning strategy, but since there is no computable descending sequence, white can have no computable winning strategy, and so black will win every computable play.

There are several proofs of open determinacy (and see my MathOverflow post outlining four different proofs of the fundamental theorem of finite games), but one of my favorite proofs of open determinacy uses the concept of transfinite game values, assigning an ordinal to some of the positions in the game tree. Suppose we have an open game between Alice and Bob, where the game is open for Alice. The ordinal values we define for positions in the game tree will measure in a sense the distance Alice is away from winning. Namely, her already-won positions have value $0$, and if it is Alice’s turn to play from a position $p$, then the value of $p$ is $\alpha+1$, if $\alpha$ is minimal such that she can play to a position of value $\alpha$; if it is Bob’s turn to play from $p$, and all the positions to which he can play have value, then the value of $p$ is the supremum of these values. Some positions may be left without value, and we can think of those positions as having value $\infty$, larger than any ordinal. The thing to notice is that if a position has a value, then Alice can always make it go down, and Bob cannot make it go up. So the value-reducing strategy is a winning strategy for Alice, from any position with value, while the value-maintaining strategy is winning for Bob, from any position without a value (maintaining value $\infty$). So the game is determined, depending on whether the initial position has value or not.

What is the computable analogue of the ordinal-game-value analysis in the computably paradoxical games? If a game is open for Alice and she has a computable strategy defeating all computable opposing strategies for Bob, but Bob has a non-computable winning strategy, then it cannot be that we can somehow assign computable ordinals to the positions for Alice and have her play the value-reducing strategy, since if those values were actual ordinals, then this would be a full honest winning strategy, even against non-computable play.

Nevertheless, I claim that the ordinal-game-value analysis does admit a computable analogue, in the following theorem. This came out of a discussion I had recently with Noah Schweber during his recent visit to the CUNY Graduate Center and Russell Miller. Let us define that a computable open game is an open game whose game tree is computable, so that we can tell whether a given move is legal from a given position (this is a bit weaker than being able to compute the entire set of possible moves from a position, even when this is finite). And let us define that an effective ordinal is a computable relation $\lhd$ on $\N$, for which there is no computable infinite descending sequence. Every computable ordinal is also an effective ordinal, but as we mentioned earlier, there are non-well-ordered effective ordinals. Let us call them computable pseudo-ordinals.

Theorem. The following are equivalent for any computable game, open for White.

  1. White has a computable strategy defeating any computable play by Black.
  2. There is an effective game-value assignment for white into an effective ordinal $\lhd$, giving the initial position a value. That is, there is a computable assignment of some positions of the game, including the first position, to values in the field of $\lhd$, such that from any valued position with White to play, she can play so as to reduce value, and with Black to play, he cannot increase the value.

Proof. ($2\to 1$) Given the computable values into an effective ordinal, then the value-reducing strategy for White is a computable strategy. If Black plays computably, then together they compute a descending sequence in the $\lhd$ order. Since there is no computable infinite descending sequence, it must be that the values hit zero and the game ends with a win for White. So White has a computable strategy defeating any computable play by Black.

($1\to 2$) Conversely, suppose that White has a computable strategy $\sigma$ defeating any computable play by Black. Let $\tau$ be the subtree of the game tree arising by insisting that White follow the strategy $\sigma$, and view this as a tree on $\N$, a subtree of $\N^{<\omega}$. Imagine the tree growing downwards, and let $\lhd$ be the Kleene-Brouwer order on this tree, which is the lexical order on incompatible positions, and otherwise longer positions are lower. This is a computable linear order on the tree. Since $\sigma$ is computably winning for White, the open player, it follows that every computable descending sequence in $\tau$ eventually reaches a terminal node. From this, it follows that there is no computable infinite descending sequence with respect to $\lhd$, and so this is an effective ordinal. We may now map every node in $\tau$, which includes the initial node, to itself in the $\lhd$ order. This is a game-value assignment, since on White’s turn, the value goes down, and it doesn’t go up on Black’s turn. QED

Corollary. A computable open game is computably paradoxical if and only if it admits an effective game value assignment for the open player, but only with computable pseudo-ordinals and not with computable ordinals.

Proof. If there is an effective game value assignment for the open player, then the value-reducing strategy arising from that assignment is a computable strategy defeating any computable strategy for the opponent. Conversely, if the game is paradoxical, there can be no such ordinal-assignment where the values are actually well-ordered, or else that strategy would work against all play by the opponent. QED

Let me make a few additional observations about these paradoxical games.

Theorem. In any open game, if the closed player has a strategy defeating all computable opposing strategies, then in fact this is a winning strategy also against non-computable play.

Proof. If the closed player has a strategy $\sigma$ defeating all computable strategies of the opponent, then in fact it defeats all strategies of the opponent, since any winning play by the open player against $\sigma$ wins in finitely many moves, and therefore there is a computable strategy giving rise to the same play. QED

Corollary. If an open game is computably paradoxical, it must be the open player who wins in the space of computable play and the closed player who wins in the space of all play.

Proof. The theorem shows that if the closed player wins in the space of computable play, then that player in fact wins in the space of all play. QED

Corollary. There are no computably paradoxical clopen games.

Proof. If the game is clopen, then both players are closed, but we just argued that any computable strategy for a closed player winning against all computable play is also winning against all play. QED

8 thoughts on “Games with the computable-play paradox

  1. The painting is by Sofonisba Anguissola, ‘The first great woman artist of the renaissance,’ of her sisters playing chess (painted 1555). I noticed that the color of the squares on the board is the opposite from what is usually used in modern games (light on the right), and I wonder whether this convention was less used at that time or whether this was an imaginary scene or what. I posted a question about this on chess.stackexchange: http://chess.stackexchange.com/q/17104/3454.

  2. This is very interesting, no doubt. But I wouldn’t go as far as calling this a paradox. If you change the rules, you can change who’s winning. I do agree this is somewhat surprising. But not “Banach–Tarski level of surprising”.

    • I wouldn’t say the rules of the game have changed, since it is the same game tree in both cases. What has changed is the space of allowed strategies. It would be similar to having a game where one player had a winning strategy in one model of set theory and the other player in another model of set theory. There are limitations on that phenomenon, in light of Shoenfield absoluteness (since existence of strategies is essentially $\Sigma^1_2$, unless the payoff set is complicated), but I would still call this situation paradoxical.

        • It seems that you want to use the word paradox only for extreme cases. That is fine, but then I wonder why you would call the Banach-Tarski paradox a paradox or the Russell paradox.

          My perspective is that we use the word paradox only when a result goes against what might be naive intuitions on the topic. Most of the so-called paradoxes in set theory (Banach-Tarski, Russell, Burali-Forti) are not paradoxical or even confusing to someone with a more sophisticated understanding of the topic. The paradoxes evaporate with a more informed understanding. (One exception might be the liar paradox, whose confounding nature seems to be more enduring.) For this reason, I prefer a more relaxed use of the word ‘paradox’.

          In the instance of my post, I find the result paradoxical in that someone with a naive understanding of game theory might not expect that it would matter for the purpose of having a winning strategy, whether one insisted on computable play or not, especially since the game tree is computable. Indeed, I find the fact that there is a computable tree with no computable branch to itself be similarly paradoxical.

          Similarly, I do find it paradoxical that CH can be true in some models of set theory and false in others, especially when those models have the same real numbers.

          • Well, that’s just taking my words to the extreme. I certainly agree that a paradox can be any result which defies naive intuition.

            But I the problem is that naive intuition is not something concrete. The Banach–Tarski Paradox is indeed paradoxical to the naive intuition, since the naive intuition certainly does not expect it. And only a handful of people who might disagree with that naively.

            Russell’s paradox is also a bit paradoxical, but mostly because we usually present comprehension as “the naively correct intuition” (which may have been true back in the 19th century, but I argue that 120 years later, our intuitive sensitivities in logic may have already got to the place where this naive intuition is no longer that common).

            But in this case? I just don’t know if I agree. Maybe because I’m a set theorist and I’m more used to the whole “move to a different universe” thing. Maybe it’s just my philosophical views that give me that point of view. But I am certainly someone not versed in game theory at all.

            As far as CH goes, though, here I think that you’re just missing the point. CH is not about reals, it’s about sets of reals. Different models with the same reals which disagree about CH, will invariably disagree about the sets of reals as well.

  3. How about this game: each turn, each player names an integer.
    If black always names a busy beaver number he never named before,
    then black wins. Otherwise white wins.
    Obviously, black has a forced win but not if he has to
    use computable strategies.
    Also note: This game can be made to have finite length,
    in the sense that Yedidia and Aaronson recently proved
    that a turing machine with some exact number of states (I forget
    their number, but it was about 8000; they constructed the machine
    fully explicitly) cannot be proved in ZFC not to
    halt; and it halts if and only if ZF is inconsistent. Which tells
    us that BusyBeaver(n) is uncomputable for every n>8000.
    Which means black can force a win in a finite length version of this game,
    e.g. with 10000 turns — but only using uncomputable strategies.

Leave a Reply to Warren D SmithCancel reply