The Minimax Principle

When the game involves scores (not just win/lose), use minimax: I find the largest my score, you find the largest yours. Since your gain is my loss, you reducing my outcome is the same as you finding the largest yours. The trick: track the score difference. Let $dp[\text{state}]$ = best (my score $-$ opponent's score) from this state.

When I move, I pick the max. When opponent moves, they pick the min (which flips signs). Result: $dp[\text{state}] > 0$ means I win, $dp[\text{state}] < 0$ means I lose, $dp[\text{state}] = 0$ means tie.