CODEWITHSUNDEEP
algorithm
Leopard
Leopard

Reputation: 161

Optimal strategy for a 2 player game

For example:

n = 13 = b1101

Only possible i=1

k = n - 2^i = 11 = b1011

Again,only possible i = 2

k = n - 2^i = 7 = b111

Since Player A cant make any more moves, Player B wins

I've deduced that at any step,we can only choose an i,such that there is a 0 at the corresponding position in the binary representation of n.

For Example: if n=1010010,then i can only be {0,2,3,5}.

But I cant move any further.A minimax algorithm isnt exactly striking me.I would appreciate any help.Thanks in advance

Upvotes: 6

Views: 2007

Answers (1)

krjampani
krjampani

Reputation: 2982

Assuming n is not too big, we can use dynamic programming to solve this problem. Define an array A[1:n], where A[i] represents whether player i will win on input i. Let's use the interpretation:

   A[i] = 1, if A wins on input i,
   A[i] = 0, if A loses on input i.

Now A can be computed bottom-up as follows:

A[1] = 0, A[2] = 1.
For j=3:n { 
      Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
                              (number of 1's in i >=  number of 1's in j)
      Otherwise  Assign A[j] = 0 
}

Upvotes: 3

Related Questions