Game Theory in Competitive Programming

🤔 Ever heard of Game Theory?

Image for post
Image for post
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 impartial games?

Basically we can divide theses games into two categories,

Image for post
Image for post
Partizan Games vs Impartial Games

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.

Image for post
Image for post
Game of Nim-Example

Kevin takes the last coin. Therefore, Kevin wins the game.

How to Predict the Winner?

Game Theory implies that the winner of this game will surely depend on two factors.

01. Who starts the game.

02. The number of coins in each pile. (not the total coins in all the piles)

This doesn't suggest that the person who is starting the game will win all the time, there can be a state which Kevin will lose at our example. (by changing the number of coins)

Let's make life simpler. Assume that in our example, there is only one pile. This Pile has 5 coins. Two players will take turns and one player can either take 1,2, or 3 coins. Then the winner will be,

If both players play optimally, then the player starting first is guaranteed to win, if the grundy value at the beginning of the game is non-zero. Otherwise, if the grundy value equals to zero, then player starting first will lose definitely.

Yeah, I’m throwing a lot of new things here. So hang in tight and put your geek glasses on. 🤓

We want to calculate the grundy value, at the beginning of our game. Grundy Value is the MEX value of all the possible states you can go to at the beginning. This Grundy Values define each game state. Therefore if total coins are equal to 5,

Grundy(5) = MEX(the possible states that you can go to)

MEX or otherwise Minimum Excludant of a set is the smallest non-negative number which is not present in the set.

Ex:- if S = {0, 1, 3, 8, 12} then MEX(S) = 2

Now, you might think Grundy(5) for the above example as,

Grundy(5) = MEX({4,3,2}) → Grundy(5) = 0

I’m afraid this is incorrect. We are talking about possible game states here. In this theorem, the possible game states are defined using Grundy Numbers. (I told you earlier😜)

Ex:-

  • the state of taking one coin — Grundy(4)
  • the state of taking two coins — Grundy(3)
  • the state of taking three coins — Grundy(2)

Therefore,

Grundy(5) = MEX({Grundy(4), Grundy(3), Grundy(2)})

Now you can clearly see a recursive function here. No wonder why the combinatorial game theory and programming are the perfect match😀. Let's calculate all the Grundy values for our example.

Image for post
Image for post
Grundy Values Table

From the above table, let’s calculate Grundy(5),

Grundy(5)=MEX({ Grundy(4), Grundy(3), Grundy(2) })

Grundy(5)=MEX({0,3,2})→ Grundy(5)=1

Grundy(5) equals to a non zero value. Therefore, if both players play optimally, the player starting first will win. Now, that brings up the question, how to solve when there are more than one piles of coins? That's where Sprague — Grundy Theorem comes in.

We need to calculate the XOR value of the set that can be generated by applying the grundy value for each pile. If the XOR value is non zero, the player starting first will win. If the XOR value is zero, the player starting first will lose.

Please note, we are assuming that both players will play optimally. Let's apply Sprague-Grundy Theorem for our Game of Nim example.

In the beginning, there are 3, 4, and 5 coins at each pile respectively. Now, if we were to calculate the XOR Value,

XOR Value = XOR(Grundy(3), Grundy(4), Grundy(5))

XOR Value = XOR(3, 0, 1) → XOR Value = 2

XOR value is a non-negative number. Hence, we can assume that first player will win. Our example also proves that as well.

Congratulations! 👏 you learned Combinatorial Game Theory. Although, I haven't told you how to implement this using a programming language. Try to do that on your own. Here’s a programming problem that I have created using Game Theory for one of our University Hackathons.

Happy Coding! 😉

If you learned something new, please do not forget to share this post as well.❤️

Written by

Undergraduate | Developer | https://iamsahan.web.app/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store