Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let us consider a game played by two players and if the game reaches some of the ending positions, one of the players is declared a winner. Let us assume that the game has to end after finitely many moves (i.e., players cannot make an infinite sequence of moves without reaching any of the ending positions). This means that for each legal run of the game one of the player wins.

Now if there is some number $N$ such that the game ends after at most finite moves, it is clear, that one of the players has a winning strategy. (See Does a finite game that cannot be drawn imply a winning strategy exists?)

Entirely different type of games are games which end after infinitely (countably) many steps. Such games are studied, for example, in topology. It is known that there are games of this type where none of the two players has winnings strategy, at least if we believe axiom of choice. (This is related to Axiom of Determinacy.)

What can be said about "the middle case" between two types of games I mentioned above?

Consider a game of two players, which will end after finitely many moves, but the number of moves can be arbitrarily large. Is it true, that for a game of this type at least one of the two players must have a winning strategy?

We know from König's lemma that this is only possible if the tree representing all possible runs of the game is not finitely branching. In game theoretic terms, we must have positions in which there are infinitely many legal moves. To illustrate this, I will include a picture of such tree, which is taken from here.

enter image description here

Of course, in the game corresponding to that picture the end result is decided by the first move of the first player. This picture is here merely to illustrate that it is possible to have a game, which always ends after finitely many moves, but there is not a uniform bound for number of moves.

share|improve this question
    
@xavierm02 Why do you think there is such an $M$? –  bof May 15 at 11:53
    
@xavierm02 Sure it's finite. I thought you were claiming that it was bounded. –  bof May 15 at 12:18
    
@xavierm02 Yes, we're talking of the number of steps before you enter a subgame which is finite. What makes you think that it's bounded? –  bof May 15 at 12:30
    
@xavierm02 Imagine the following construction. Let us call the tree from the picture in my post $T$. Let us create a new tree $T'$ by replacing each leave of $T$ with a copy of $T$. The new tree $T'$ will still have no infinite branch. (Every game will end after finitely many moves.) Bud if the first play plays the $n$-th move from the left in the first step, it will take $(n+1)$ moves until we reach a finite "subgame". So the number of steps before reaching some finite subgame is not bounded. –  Martin Sleziak May 15 at 13:05

1 Answer 1

up vote 2 down vote accepted

Yes. I recall seeing such digraphs (or games) called "progressively finite" in one of Claude Berge's books on graph theory [1]. The determinacy of finite positional games is attributed to Zermelo; I don't know if he also discussed this generalization.

Call a node "bad" if the subgame starting from that node is undetermined. It is easy to see that a node is determined if all its immediate successors are determined, in other words, a bad node must have at least one bad successor. It follows that, if the initial node is undetermined, there is an endless play. Contrapositively, if no unending play is possible, the game is determined.

An interesting example of such a game is transfinite nim. The number of piles is finite, and each pile is a well-ordered set, not necessarily finite; i.e., a position is described by a finite sequence of ordinal numbers. A move consists of removing a nonempty final segment from one pile, i.e., diminishing one of the ordinals. The game is determined, and its analysis is a straightforward generalization of the analysis of ordinary nim, using the representation of an ordinal number in the binary form $$2^{\alpha_1}+2^{\alpha_2}+\cdots2^{\alpha_n}$$ where $\alpha_1\gt\alpha_2\gt\cdots\gt\alpha_n$.

By the way, the games you are asking about can be turned into games of length $\omega$ by making the players keep on making irrelevant moves after the real game is over. That is, we're talking about the subclass of games of length $\omega$ consisting of games in which every possible play is decided after a finite (but unbounded) number of moves. Topologically speaking, these are the "clopen games".

[1] Claude Berge, The Theory of Graphs and its Applications, translated by Alison Doig, Methuen & Co. Ltd., London, 1962; especially Chapter 6, Games on a Graph.

share|improve this answer
    
This argument seems to be much easier than I expected. But I am glad that I have learned from your answer not only the solution to the question I have asked but also some new keywords. (The terminology I have learned here might help me to find more related things and learn about them.) –  Martin Sleziak May 15 at 13:07
    
Here is Google Books link the the 2001 Dover reprint of the Berge's book you mention. –  Martin Sleziak May 15 at 13:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.