Game Theory with examples

Game Theory with examples

Introduction

In this article I will be covering problems related to two players game in which it is assumed that both players play optimally and we have to find out the winner of the game.

First we will look at the basic division of positions to winning and losing. Then we will see the Game of Nim and then see how it will be used to solve the Composite games .

Basic Division of positions to winning and losing

Problem Statement: Consider a simple game played by two players A and B . There are n stones on the table. Each player can pick 1 , 2 or 5 stones in each turn. Both players pick the stones alternately until the total number of stones left on the table is 0. The player unable to make the move will lose. Assuming that both the players play optimally, output the winner of the game.

Solution: As you can see positions 1 , 2 and 5 are winning positions since the player can pick up all the stones and other player will not be able to make a move . 0 is a losing position since the player can not pick any stones. Also 3 is a losing position as there is only two options that is to pick 1 stone or two stones . In both the cases the other player will pick the remaining stones and win.

So , from the following observation we can conclude that :

· Terminal positions are losing positions.

· If a player can move to a losing position the he is on a winning position.

· If a player can only move to a winning position than he is on a losing position.

This can be implemented using simple 1-D dp code.

bool dp[n]; 
dp[0] = dp[3] = 0; 
dp[1] = dp[2] = dp[4] = dp[5]=1; 
for(int i=6;i<=n;i++){ 
	if(dp[i-1] == 0 or dp[i-2] == 0 or dp[i-5] == 0) 
		dp[i]=1; 
	else 
		dp[i]=0; 

Here ‘1’ represent winning position and ‘0’ represent losing position.

The Game of Nim

Problem statement: There are k piles of stones . In each turn a player chooses a pile and takes out atleast one stone from it. If someone is unable to make a move , he loses .

Solution: Let there be n1,n2,n3….nk no. of stones in the 1,2,3….kth pile respectively. Now, a player is in a losing position if n1 xor n2 xor n3 xor…..nk = 0 . Else he is in a winning position .

Composite Games - Grundy numbers

Problem Statement(link):

Bob recently invented a new game. The game is played on an

chessboard. The rules of the game are:

• Initially, there are k kings in some of the cells. A cell can contain more than one king.
• A king is only allowed to move in one of three directions: up, left or up-left.
• Some of the cells on the board might be damaged. A king is not allowed to move to a damaged cell.

• A king cannot be moved outside the board.
• There are two players in the game. They make moves alternately.
• In a single move, a player must choose a single king and move it to a new cell.
• If a player can't make a move, they lose the game.

Bob is playing the game with his friend Alice. Bob always makes the first move. Given the configuration of the board, Find the number of ways Bob can make the first move to ensure that he will win the game, assuming that both players will play optimally.

Solution: This is same as if we have k different chessboards each having exaxctly one king. Now , we can solve the k sub problems independently. Each sub problem can be solved using grundy numbers. Algorithm for finding grudy numbers is as follows:

int grundyNumber(position pos) { 
    moves[] = possible positions to which I can move from pos 
    set s; 
    for (all x in moves) insert into s grundyNumber(x); 
    //return the smallest non-negative integer not in the set s;     
    int ret=0; 
    while (s.contains(ret)) ret++; 
    return ret; 
} 

Through this algo we can compute grundy number for each position of the chess board. Now, this problem can be solved using the Game of Nim concept. The player is in a losing position if the xor of all values at the positions of kings is 0. Else , he is in a winning position.

You can find the code for above problem here.

How these two problems are equivalent?

• In the game of nim we can take any number of stones out of the pile (atleast one) , same is the case with king problem as we can move to index with less grundy number than that index.
• Also, if we move the king to any other index , that index must have grundy number less than the the previous index , which is same as decreasing number of stones from a pile.

Practice problem: SNACK01