Game Theory
- In all game theory related problems, it is pre-assumed that all players will play optimally (i.e. meaning players will not make a move that causes them to lose the game if a winning move exists.)
P: Given there are two players, Alice and Bob and a number with value 0. In a single turn a player can add 1 or 2 to the number. Players taking alternate turns and first person to make given number's value to x will be considered as winner. consider alice will take the first move.
for example x = 5 A: 2(total=2), B: 1 or 2(total: 3, 5), A: 2 or 1(total:5) so in case of x = 5, player 1(with first turn) will always win.
example x = 6 A: 1 or 2 (total: 1 or 2), B: 2 (total: 3), A: 1 or 2 (total: 4 or 5), B: 2 or 1(total: 6) so in case of x = 6, player 2 will always win -
Here in this case, for any x, if x%3 == 0, player 2 wins, else player 1 will win
P2: Given x number of coins, in a single turn the player can take 2, 3 or 5 coins out of the total, player who makes last possible move will be called a winner. (or if a player cant make a move, player will lose)
- for x = 2, 3, 5 player 1 will win
- for x = 4, alice can take 3 coins, so no move possible for bob, i.e alice made the last move and won
- for i in range(9), for player 1: [❌, ❌, ✔, ✔, ✔, ✔, ✔, ❌, ❌, ✔] where ✔: will win
P3 Given N number of coin piles, a player can take any number of coins from any single pile. player who cannot make a move will lose.
- [x, x] >> player 2 will win
- [x] >> player 1 will win
- [x, y] >> player 1 will win, player 1 can take (y-x) from y and make piles look like [x, x], similar condition as first for player 2.
- If for any move a mirror move(same move as the prev move) available, player 2 will win, wlse player 1 will win.
-