Introduction to Game Theory.

Ever tried to develop a unique strategy to always win any game regardless of the opponent’s strategy?

If yes, then congratulations on your first step towards Game theory.

Learn how to play games optimally.

Your goal is to play the game optimally, i.e., to find a strategy that you can follow to win the game, no matter what the opponent does, if such a strategy exists.
The condition given is that your opponent is going to use the best strategy to win.

Lets begin with understanding Combinatorial games and the way to win. 

Combinatorial games are the types of games that are:

  • Usually, a two-person game.
  • Win or lose or tie outcome.
  • The game is guaranteed to end regardless of the end condition.

State of the game:

  • Winning state – Player will win the game if he plays optimally.
  • Losing state – Player will lose if the opponent plays optimally.

An Example:

Two players are playing a game of Tower Breakers! The rules of the game are as follows:

  1. Player 1 always moves first, and both players always play optimally.
  2. Initially there are n towers, where each tower is of height m.
  3. The players move in alternating turns. In each turn, a player can choose a  tower of height x and reduce its height to y, where 1<=y<x and y evenly divides x.
  4. If the current player is unable to make a move, they lose the game.
    Given the values of n and m, determine which player will win.

 

Case 1: When n is Even

•  Imagine that the towers are separated into two groups having an equal number of n/2  towers in each group.
•  Whenever player 1 mutates one of the towers from the first group, player 2 can simply copy player 1 ‘s last move and apply it to a tower from the second group.
•  In this way, player 2 will always have move to make, so player 2 will always win.

Case 2: When n is Odd 

•  Player 1 chooses a tower and breaks it down to a height of 1.
•  This results in n-1 remaining breakable towers, which is an even number.
•  Because we know that the first player to make a move when there are an even number of towers always loses, we know that player 1 will always win.

Representing the outcome as a function

Lets name the function func.

int func(int n, int m) {
if(m==1)return 2;
   return 2-(n%2);

}

Let’s move to the next step of Game theory  – nim game.

nim game

Nim game is a mathematical game of strategy in which two players take turns removing objects from distinct heap or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The winner is the player removing the last stick.

The states in nim are of the form [x1, x2,…, xn], where xk denotes the number.

 

Example: States-[3,4,5]

We can solve this problem using many Advanced Mathematical techniques such as the Sprague-Grundy Theorem.

However, there is a simple winning solution for nim games.

The solution: Any position where the xor value of all piles is not zero is a winning position, otherwise it is a losing position. This xor value usually referred to as nim-sum.

What is the reason behind this solution?

Main idea: If the nim-sum is not zero, you always have at least one move which can change the nim-sum into zero. On the other hand, if the nim-sum is zero, you can only change it into a non-zero nim-sum. Note that the end game state (no stones) have a zero nim-sum. Which means, whoever is able to maintain the zero nim-sum for his/her enemy will win this game.

Let x1, x2, …, xn be the size of piles before a move, and y1, y2, …, yn be the size of piles after a move. Let s = x1 ⊕ x2 ⊕ … ⊕ xn (ie., nim-sum before a move) and t = y1 ⊕ y2 ⊕ … ⊕ yn (ie., nim-sum after a move).

t  = 0 ⊕ t
   = s ⊕ s ⊕ t
   = s ⊕ (x1 ⊕ … ⊕ xn) ⊕ (y1 ⊕ … ⊕ yn)
   = s ⊕ (x1 ⊕ y1) ⊕ … ⊕ (xn ⊕ yn)
   = s ⊕ 0 ⊕ … ⊕ 0 ⊕ (xk⊕ yk) ⊕ 0 ⊕ … ⊕ 0
   = s ⊕ xk ⊕ yk

t  = s ⊕ xk ⊕ yk  ——————–  (1)


First, we observe the relation between s and t. In this game, a move consists of removing any number of stones (at least 1) from any one pile. Suppose the chosen pile is pile k, so xk is its previous number of stones in kth, yk is its number of stones after the move, and xk ≠ yk because we have to remove at least 1 stone, or to be precise, yk < xk.

t  = s ⊕ xk ⊕ yk
   = s ⊕ xk ⊕ (s ⊕ xk)
   = 0

We will use equation (1) to proof by taking all the cases.

Case 1: If s = 0, then t ≠ 0 no matter what the move is made.
Proof: From (1) we can see that if s = 0, then any move will produce t ≠ 0 because xk ⊕ yk ≠ 0 (since xk ≠ yk).

Case 2: If s ≠ 0, then it always possible to make a move so t = 0.
Proof: This following strategy will cause t = 0. Find d, the leftmost non-zero bit in the binary representation of s and choose pile k (any pile) which dth bit is also non-zero. Such k must exist, otherwise dth of s must be zero. Then, we can claim that yk < xk for yk = s ⊕ xk since all bits to the left of d is the same in xk and yk, while the dth bit is changed from 1 to 0, and the remaining right bits can only do at most 2d-1 changes. Thus, the respective player can make a move by taking xk – yk stones from pile k.

Example:

Let there be 5 piles in which stones are: {18, 6, 3, 20, 9).

First write the number of stones in each pile in binary form.

18:   1 0 0 1 0
6:    0 0 1 1 0
3:    0 0 0 1 1
20:  1 0 1 0 0
9:    0 1 0 0 1
————- ⊕
s:     0 1 0 1 0   

The leftmost 1-bit of s lies in the 4th. Find any pile which 4th bit is 1, in our case, there’s only one: pile with 9 stones. Change the 4th bit of that pile (with 9 stones) into 0. Because of changing this 4th bit, we already ensure that the value of that pile will be less than its previous value (9) no matter what changes we’ll make in the remaining right bits. So, for the right bits, change all bit positions from 0 to 1 or vice-versa wherever it is 1 in s (we want to make t = 0).

18:   1 0 0 1 0
6:    0 0 1 1 0
3:    0 0 0 1 1
20:  1 0 1 0 0
3:    0 0 0 1 1
————- ⊕
t:     0 0 0 0 0  

If the player always maintains t = 0 for his/her enemy, then at the end he/she will win this game as nim-sum for the end game (no stones) is zero.

This is not the end. There are many impartial games which turn out to be the Nim Game to be discussed in my next post.

 

Author


Niwedita

NITK CSE Student.



References:

https://www.geeksforgeeks.org/introduction-to-combinatorial-game-theory/

https://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/

 https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula/

Leave a Reply

Your email address will not be published. Required fields are marked *