4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a good start, and it’s worth noting that this approach runs in O(kT) where T is the runtime of the algorithm that determines the existence of a forced win. However, not all games have a finite branching factor k. However, depending on the game there can be interaction between k and T. $\endgroup$ – Stella Biderman Aug 2 '18 at 16:23
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was also thinking of games like this. However, can you explain what implications the existence of such games has for the original question? Does it have implications for the existence of a reduction between the two problems articulated in the question? $\endgroup$ – D.W. Aug 2 '18 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.