Note: this is basically a more precise restatement of this question, which didn't get proper answers because it was vague.Most two-player perfect information games can be represented as a finite directed graph, because although the games could theoretically go on forever, there are only finitely many possible states for the game. Chess fits into this category, for instance. Here we'll consider states to be distinct even if the only difference between them is whose turn it is, thus our directed graph is always two-colorable with the colors White's turn and Black's turn.Given a directed graph $G$ with such a two-coloring, with one priveleged node called the initial node, a strategy for a player $P$ is a partial function $s:N(G)\to N(G)$ such that:$s$ is defined only on nodes at which it is $P$'s turn.If $s$ is defined at a node $A$, then $s(A)$ is a child of $A$.If $s$ is defined at a node $A$, it is defined at all children of $s(A)$.$s$ is defined on the initial node, or on all children of the initial node if $P$ goes second.Now, I'll call a complete path through $G$ a path through $G$ starting at the initial node which either goes on forever or ends at a node with $0$ out-degree, such nodes are called endstates. If $S$ is some set of complete paths, we will say that player $P$ can force $S$ iff there exists a strategy for $P$ such that any complete path which obeys that strategy (I think it's obvious what this means) is in $S$.Some endstates are marked as victories for White, some are marked as victories for Black, some are marked as draws. Let $W$ be the set of all complete paths ending in a victory for White, $B$ be the set of all complete paths ending in a victory for Black, and $D$ the set of complete paths ending in a draw. Let $I$ be the set of all infinite complete paths, which we will also conceptually think of as draws.It is then a theorem that either White has a strategy that forces $W\cup D \cup I$, or Black has a strategy that forces $B\cup D \cup I$, or both.Is there an algorithm which, given such a description of a game, outputs which players have such a strategy, along with the strategy itself?I don't mind if no such algorithm is actually known, but is there an existence or impossibility proof?
Is there an algorithm that can solve any two-player game?
board games