Блог пользователя Rmg_

Автор Rmg_, 10 лет назад, По-английски
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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).