A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position.
Is this problem equivalent under polynomial-time reduction to identifying the best forced outcome of a game, where that outcome might not be a win?
If necessary, assume that it’s a two player zero-sum game that pays out 1 for a win, 0 for a draw, and -1 for a loss.
They are equivalent under Turing reductions, assuming that the game has finite/polynomial-size branching factor (i.e., only that many moves are possible from each position). I don't know if they are equivalent under Karp reductions.
Consider a position $P$. Assume there are $k$ moves that are legal there. Let $P_1,\dots,P_k$ denote the possible positions after making a single move.
Check whether $P$ is a forced win for player #1. If yes, you are done.
Check whether any of $P_1,\dots,P_k$ is a forced win for player #2. If they are all a forced win for player #2, then $P$ is a forced lose for player #1.
Otherwise, $P$ is a forced draw for player #1.
There's a game named "chomp" where it is mathematically proven that the player who starts has a winning strategy, but finding the winning strategy seems to be very hard.
Given is an n x m rectangular board of n x m pieces. The players take turns. Each player choses (x, y) and removes all pieces with coordinates both ≥ x and ≥ y. At least one piece must be removed. The player removing the last piece loses.
The first player can take the one piece at (n, m). This is either a winning move, or the second player has a winning move (x, y). But this produces the same position as if the first player had taken (x, y) in the first place, so (x, y) is a winning move for the first player. In any case, the player going first has a winning move.
