Let me first of all be more clear by explaining what a unsolvable game is.
An unsolvable game is a game which can never be solved, not even hypothetically, because no strategy can force a win if the other player plays perfectly.
More precisely, an unsolvable game is a game that:
-
Has computable rules. Meaning that some algorithm can determine what the next possible moves for each player are, what they will result in, and can compute the game tree up to an arbitrary length.
-
The path for either side to avoid a loss is uncomputable and every computable strategy will lose with optimal play from the other player at the start of the game.
In other words:
A perfect game is a game in which the rules can be fully understood, all possible moves and their consequences, but there is no computable strategy that will prevent either player from losing.
While a strategy may result in victory, it is only due to the other player playing imperfectly, and not because the strategy was unbeatable.
What is an explicit example of such a game, if any?
Now, this is the core of the question, but I also want to share some motivation and the progress on this question I have made so far.
When designing a game like Chess or Go, a game of pure strategy, we want the mechanism of play to be knowledge of the game mechanics and superior ability to outwit one's opponent. Games with perfect information, games where all players know exactly what moves are possible and what the result of each will be, fulfill this requirement, and are called in mathematics combinatorial games. Another way to understand what a combinatorial game is, which is maybe a little more precise, is that it is a game in which the game tree for either player's moves is computable up to n moves deep, from any given position in the game, where n is any integer. I will only be talking about combinatorial games from now on. Otherwise my question would be easily answerable in the affirmative by simply playing a game in which the outcome of every move is randomly losing or not losing.
Now, ideally, a combinatorial game has a high skill ceiling, meaning that even if a player is really good, there will be room for players who are truly masters to play at an even higher level. A great example of such a game is Chess. A very low-skilled player can understand basic rules and look a few moves ahead to avoid losing, but a high-skilled player can outwit them who has better knowledge, and an expert can easily defeat most players he plays. Importantly, Chess is not currently solved, meaning that no one, not even an advanced AI database, has been able to deduce a strategy by which the game can always be won by one side, and it is not currently known which side is "winning." However, for most games, even those with high skill ceilings, these games can hypothetically be solved. Chess has 12 types of pieces, 6 for each side, and only 64 squares. This places a finite upper limit on the number of possible game states. Since most combinatoric games are played on a finite board or with finite cards or chips, these games are solvable, meaning that a sufficiently advanced AI, even if it doesn't fit in this universe, can always win these games and exhaust every possible strategy. However, an unsolvable game can never be solved by any Turing complete machine, making it in a sense the "perfect" game.
We can infer several facts about such a type of game immediately. Firstly, such a game can not have finite possible moves in a turn and also necessarily terminate in a finite amount of time. Otherwise it would have finite game states and its tree could be solved.
Instead of worrying about games in which there are infinite moves in a turn, I will just note some things about the ones in which there are only finite moves per turn.
In such a game, optimal play means a game would last forever. If optimal play terminates, the game is solved for one player, since even with optimal play they still win over their opponent in finite time, and any finite strategy of finite possible moves is computable. So, optimal play must never terminate. However, no path that results in a perpetual stalemate can be computable, since no strategy can guarantee that either player never loses, so no computable strategy will result in a perpetual game, even though an uncomputable strategy exists which will result in a perpetual game.
We can consider 3 types of game states then which we will find in the game tree of all possible game states and moves for each player. First are neutral states, in which neither player will win with optimal play. Such a state must be at the beginning of the game, and every neutral state must have another neutral state as a possible move in the game tree. There are also 1 states, and 2 states, in which player 1 or 2 will win with optimal play, respectively. If it is a neutral state and it is 1's turn, every move will be to another neutral state or a 2 state, since 1 can not win with optimal play, only lose with suboptimal play, and likewise vice versa for 2. If it is 1's turn on a 1 state, it will always have access to another 1 state, (since it can win with optimal play) but may have access to other states. If it is 2's turn on a 1 state, than 2 can only move to a 1 state, since it always loses with optimal play, or 2 can move to nothing, in which case 1 wins. This is also the case if you switch 1 and 2's roles.
In addition to these rules for generating such a game, we can also know a few more things. The subtrees of the game tree which consist of only winning strategies for one player when the other has played a suboptimal move, have finite length (since one player forces a victory) and lengths which increase at a rate exceeding any computable function. This is because otherwise a strategy could be to apply some function at every turn t of looking C(n) moves deep to avoid losing moves, where C is a computable function. The game length of a subset of the strategies that eventually lose, will get longer and longer as the game progresses, so that no C(n) will outpace L(n), which is the longest tree of losing moves at that turn. In summation, the actual moves that are part of a perpetual stalemate can never be determined by any algorithm, only that there is such a game which lasts forever.
So how might we go about finding a game like this? In designing an unsolvable game, it seems like we need to find a game where a process or structure, perhaps a formal language of some kind, is continued as long as is possible. For example, a game could be constructed in which both players place Wang tiles, and when it is no longer possible for a player to place a Wang tile, they loose. Wang tiles are Turing complete already, meaning that it is undecidable if certain Wang tiles can tile the plane. In other words there may be aperiodic tilings that exist, but which can not be computed. It is possible such tilings with a certain set of tiles can always be constructed so long as neither player makes a losing move, but this is conjecture. This is merely an example of the sort of discovery that would seem to be necessary to construct an unsolvable game.
I know this is a very long question, but I thought all this additional information would help clarify what I mean and also help anyone who wants to take up my question. I don't think it is easy since no one has been able to come up with such a game before. Maybe it is impossible. Either way I look forward to your feedback.
Best Answer
Here is a simple example of a "computable but non-computably-determined" game. Even better, each play lasts at most three moves. Below, "$\Phi_e(c)[s]\uparrow$" (respectively, $\Phi_e(c)[s]\downarrow$) denotes "the $e$th Turing machine on input $c$ does not halt in $\le s$ steps" (respectively, "does halt in $\le s$ steps:)
Player $1$ plays some natural number $n$.
Player $2$ responds with either a natural number $m$ of their own, or the word $\mathsf{never}$.
If player $2$ played a natural number, then the game stops; if player $2$ played the word $\mathsf{never}$, then player $1$ plays a natural number $k$.
Player $1$ wins iff $(i)$ player $2$ played a natural number $m$ but $\Phi_n(n)[m]\uparrow$, or $(ii)$ player $2$ played $\mathsf{never}$ but $\Phi_n(n)[k]\downarrow$. Player $2$ wins otherwise. Note that the rules and win conditions are computable. Also, there are no ties or infinite plays, so "non-losing strategy" is the same as "winning strategy" here (which simplifies things a bit).
Essentially, in this game player $2$ is trying to guess the halting problem. Obviously player $1$ has no winning strategy, computable or otherwise; however, any winning strategy for player $2$ has to be non-computable (and indeed must compute the halting problem).
Note that there is a kind of "infinite branching" here: specifically, the game tree is infinitely branching since there are infinitely many legal moves. This is necessary if we want to keep our game of bounded length: any computable game on a finite move set where all plays have length $\le n$ for some fixed $n$ must have a computable winning strategy (just via brute-force analysis).
Something a bit more interesting happens if we require a finite move set but don't require a uniform bound on the length of plays, and merely require that all plays be finite. While Konig's lemma implies that any such game does in fact have a uniform bound on the length of plays, that result is not computably true. On the other hand, it's also not as powerful as the halting problem (in a precise sense).
To make the picture somewhat more complete, there are four different ways we might make sense of the claim "Every finite-length game is determined," and these give rise to four different "levels of non-computability" as measured by reverse mathematics. This is all extremely technical, but I think it's worth putting these facts down for ease of reference even if they're getting beyond the context of this question:
"Every uniformly-finite-length game on a finite move set is determined" is at the lowest level $\mathsf{RCA_0}$ (= no noncomputability at all).
"Every non-uniformly-finite-length game on a finite move set is determined" is one level up, at $\mathsf{WKL_0}$.
"Every uniformly-finite-length game on an infinite move set is determined" is one level above that, at $\mathsf{ACA_0}$.
Finally, "every non-uniformly-finite-length game on an infinite move set is determined" - called clopen determinacy - is even higher, at the level of $\mathsf{ATR_0}$.
Infinitely-long games are also extensively studied, but more so in set theory than in reverse mathematics. That said, one of the earliest serious results in reverse mathematics was the surprising equivalence between clopen determinacy (= $\mathsf{ATR_0}$) and a particular infinite-length determinacy principle (basically, player $2$ wins if the game goes on forever). I've said a bit about this here.
Finally, this blog post of Hamkins may be of interest.