Game Theory in Competitive Programming

🤔 Ever heard of Game Theory?

Photo by zhang kaiyv on Unsplash

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…