principleMinor
Determining the existence of a forced win vs determining the best outcome
Viewed 0 times
windeterminingtheexistenceoutcomeforcedbest
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#95880, answer score: 3
Revisions (0)
No revisions yet.