Game Theory in Competitive Programming
🤔 Ever heard of Game Theory?
What if I tell you, you can predict the winner of a game even before playing the game.😮 Yes, you can do that using Game Theory. If you are new to competitive programming, Game Theory might be something new to you. However, Game Theory programming problems are common in most hackathons.
Introduction
Using Game Theory, you can predict winners but only in combinatorial games. Combinatorial Games, are games that will be played by two persons and these games will not have randomization (Ex. Coin Toss). Also, these games will be always finished in either win or lose state.
For example, games like Chess, Tic Tac Toe, and Game of Nim come under the category of combinatorial games.
Game Theory is a quiet considerable topic in Mathematics. That’s why it is rather impossible to understand all the methods in Game Theory (for us programmers of course). That’s why I chose Game Theory in Competitive Programming. With some mathematical theorems, we can solve games like ‘Game of Nim’. However, it is slightly difficult to solve games like Chess or Tic Tac Toe. Through this article, we will discuss how to solve this Game of Nim using Game Theory.
Game of Nim is a combinatorial game and also it is an impartial game. What are impartial games?
Basically we can divide theses games into two categories,
Game of Nim?
The ‘Game of Nim’ is simple. There are ‘n’ piles of coins, (in between two players) each player can take at least one coin from any piles. The player who makes the last move will win. Both players will play optimally. (playing to win)
Example:-
There are two players, John and Kevin. They decided to play this ‘Game of Nim’. So they built 3 piles of coins, each with coins respectively 3, 4, and 5. One player must take either 1, 2, or 3 coins at each round. If John makes the first move, and both players play optimally. This is one scenario that could occur.
