# Optimal Strategy for a 2 player game

• 2 players A & B are playing a game involving a number n
• Player A makes the first move & both players play alternately.
• In each move the player takes the number n,chooses a number i such that 2^i < n and replaces n with k = n - 2^i iff the number of 1s in the binary representation of k is greater than or equal to the number of 1s in the binary representation of n
• Game ends when no player can make a move, ie there does not exist such an i

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

-

It’s a disguised version of Nim. Each block of consecutive $0$’s in the binary representation of $n$ is a pile. For example, from $10000_2$ you can subtract $8$ to get $1000_2$; $4$ to get $1100_2$; $2$ to get $111_2$; or $1$ to get $1111_2$. These moves correspond to reducing a pile of $4$ stones to $3$, $2$, $1$, or $0$ stones, respectively. I’ll leave it to you to fill in the details. You probably already know the strategy for Nim.
This doesn't seem right, since the removal of zeroes from one block will create new zeroes in the next block to the left. The value of $1010_2$, for instance, is $*$, not $0$, even there are two equal "piles" of zeroes in that number. – Théophile Sep 24 '12 at 23:50
@Théophile: You’re right: I was concentrating so much on the case of adjacent $1$’s that I forgot that the piles get amalgamated in the basic case! – Brian M. Scott Sep 25 '12 at 0:03
It seems that every position has value $0$, $*$, or $*2$. – Théophile Sep 25 '12 at 0:31