Tag Archives: game theory

game-theory1

Knight and Queen // HackerRank Lambda Calculi

It's been a while since my last post here. I've been busy working with my team on a brand new game for Android and iOS.

Anyway, I'm back with a very interesting problem. I was asked to test some problem for HackerRank Lambda Calculi Contest. The one which I want to write about is Knight and Queen. The original problem is available here:

https://www.hackerrank.com/contests/lambda-calculi-10/challenges/knight-and-queen

Problem statement

Two players are about to play a game on a chessboard of size n x n, where the bottom-left cell has coordinates (0, 0). There are only 2 figures on the board: the Knight and the Queen. Both figures moves like in a classic chess game, but with a restriction that they cannot move right or up, so every legal move is left, down or left and down. For example, the Knight standing on a field (5, 4) can move to (4, 2) or (3, 3) but cannot move to (6, 6). Also note that both figures can be a the same cell in the same time.

Players takes moves alternately. Player who is about to make a move can pick the Knight or the Queen and make any valid move with in. A player who is not able to make a move is declared a looser.

Your task is to decide who is a winner knowing the initial positions of both figures and the fact that both players plays optimally.

You will be given many testcases, so the best you can do is to be able to provide the answer for any given initial positions fast.

Solution

If n is quite small, you can consider a dynamic programming solution where we have n^4 positions: n^2 possible positions of the Knight multiplied by n^2 possible positions of the Queen. For each such position, you can compute the best possible move in O(n) time, so a total time will be O(n^5), but since we have n = 50, this is way to much.

We need a faster solution.

Game of Nim

Let's consider a simpler game called Nim first. In the Nim game, there are N distinct heaps. Each heap has a positive number of objects. Players takes moves alternately. Player who is about to make a move, can choose any non-empty heap and remove any positive number of objects from it. A player who is not able to make a move is declared a looser and a player is not able to make a move if and only if all heaps are empty.

This is a very classic game, a fundamental one in game theory. There is a famous theorem which can be used to determine who has a winning position in Nim at the beginning of the game if both players plays optimally. If you haven't heard about it yet, you should be amazed at least a little bit.

Theorem

Let a_1, a_2, ..., a_N be current sizes of heaps i.e. a_i is the number of objects in the i-th heap before the next move. Let X = a_1 xor a_2 xor ... xor a_N, where xor is a binary xor operation.

A player who is about to make a move has a winning position if and only if X != 0.

In other words, if X != 0 and you are about to make a move, you can win no matter what, and if X == 0 and you are about to make a move, no matter what will you do in that move, your opponent can always win.

Sounds great! Let's make a sketch of a proof.

Let X == 0 before the next move. There are two possibilities:

  1. All heaps are empty, so the current player is a looser
  2. There is at least one non-empty heap

Since the first situation is clear, let's consider the second one. The current player has to remove at least one object from a non-empty heap, so no matter what will he do, the xor of sizes of all heaps after his move will be non-zero.

On the other hand, if X != 0 before the next move, the player who is about to make a move can always choose a valid move leading to a situation that the xor of sizes of all heaps after this move will be 0.

If you want to more detailed explanation, check it here or do it on your own considering binary representation of heaps sizes.

Our problem

Let's think of our problem as of a special game of Nim where we have only two heaps, the first one for the Knight and the second one for the Queen and let's consider these two heaps separately. For each of these two heaps, we will assign a single number to any position of the figure corresponding on the board. This number will correspond to the number of objects in a game of Nim on a single heap.

Knight's heap

Let's consider any position of the Knight such that there is no valid move with this figure. Any such position is equivalent to an empty heap, so we will assign 0 to any such position. Next let's consider any other position P, and let M be a set of numbers assigned to all positions reachable from P. We will assign the smallest non-negative integer which is not in M to the position P.

Queen's heap

We will do the same as above with respect to Queen's valid moves.

After making these two above computations, we have assigned numbers to any valid position of each figure on a board. We can think of these numbers as of the number of objects in the corresponding heap in a Nim game - just note that in Nim if you have k objects on a heap before your move, you can reduce the number of objects in this heap to any non-negative number less than k. The same is true in our game. If you decided to move the Queen in your turn, and it is currently in a cell with number k assigned to it, you can move it to a different cell with any assigned non-negative number less than k.

So in order to solve our problem, just assign the numbers as described above to both Knight's and Queen's positions. Let X be the xor of assigned numbers corresponding to the initial position of both figures. The player who starts the game has a winning strategy if and only if X != 0.

Time complexity

For a board of size n x n, you have to compute two tables of size n x n and computing a single position in any of these tables takes at most O(n) time, so the total complexity is O(n^3) if you use memoization or dynamic programming and here we have n = 50, so it will be very fast.

Related problems

One interesting thing is that many simple games can be reduced to Nim. I encourage you to read about that here.

 

Hackerrank Weekly Challenge #7 // Problem 2: Chocolate in Box

If you want to me write an editorial to problem 3, 4 or 5 from Hackerrank Weekly Challenge #7, let me know in the comment section down below.

Problem statement

The problem is available here.

There are 1 \leq n \leq 10^6 stacks numbered from 1 to n. The i-th stack contains 1 \leq a_i \leq 10^9 objects. Two players are playing the following game with the stacks:

Players takes turns. Player 1 starts. In each turn, the current players can remove any number of objects from any single non-empty stack and he has to remove at least one object. The player who is unable to make a move loses. The task is to decide, how many different moves players 1 can take in the first turn in order to win a game. Both players play optimally.

Solution

If you've hear about the game of Nim, you probably already recognized it here. If not, read about it and remember, because this is one of the most fundamental games in game theory.

The theorem says:

The player making the first move has a winning strategy if and only if XOR of the binary representations of sizes of the stacks is nonzero.

In order to solve the problem, you have to decide, how many ways are to select the stack and take some number of object from it, in such a way, that the XOR of sizes of the remaining stacks equals 0, because then player 2 loses and you win. Let \oplus be the symbol of XOR operation.

The first basic observations is that:

a\oplus b = 0 if and only if a = b.

In order to get the answer for the problem, we have to examine every stacks and add 1 to the result, if we can make a move on this stacks. The fact is that in one move, we can take some objects only from one stack, so the other stacks remain the same. We will examine every stack separately.

Let's assume that we examine the i-th stack and let L = a_1 \oplus a_2 \ldots a_{i-1} \oplus a_{i+1} \ldots a_n - the XOR of sizes of all stacks without stack i. Based on above observation, we are interested in taking some number of a_i objects is such a way, that the number of remaining objects on this stack equals L. Obviously, we can do it if and only if L < a_i , because we have to take at least one object, so we can make the XOR of all stacks equal 0 for any 0 \leq L < a_i.

The time complexity of this solution is O(n). You can compute L for every stacks using prefix/suffix sums for XOR or by "unxoring".