Rmg_'s blog

By Rmg_, 10 years ago, In English
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Just ignore P and solve the problem with an ordinary minimax DP. Then add 2 * P to the answer.

Very short sketch of proof:
If a player in a winning position passes, he'll obviously lose the game. If the losing player passes, he can let the winning player end the game in a smaller amount of moves (or the winning player will pass the move back), so passing only makes sense when no such shortcut exists (for example, when any loser's move will lead to an immediate victory of his opponent).