If a game ends after finite number of moves, does it mean that at least one of the players has winning strategy?

Question

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.

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.

Answer 1

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.