Recurrence relation for variation of Nim Game

0
votes

I am struggling to get the optimal subtructure to solve the problem i.e. the recurrence that has to be followed and upon which Dynamic Programming Solution can be build for optimizing the Time Complexity.

Suppose A and B have 2 kinds of Stones. There are A stones of the first type and B of the second type. They decide to play a game according to rules such in each turn one of the following valid moves can be done:

  1. Pick some Stones of first type
  2. Pick some Stones of Second type
  3. Pick equal number of Stone of both type

They have to pick atleast one Stone in each turn. Whoever makes the last move wins the game. Both play optimally. However while telling the rules of the competition, Alice cheated a bit to ensure that she wins the game by deciding who will take the first move.

Given the Stones, determine if Alice takes the first move or not.

2
algorithmdata-structuresdynamic-programminggame-theory
If Alice takes all but one stone of A, Bob can take all but two stones from b. 1-2 situation is a loss for a player on turn which is Alice - since 1-1, 1-0 and 0-2 all can be taken in a single turn and you have to take at least one stone. This one is rather tricky though I think the solution wasn't that hard. Just tricky. However I would like to hear more about the OP's thought process and attempted solutions :-). - Shamis

2 Answers

2
votes

You can work backwards from a winning position.

  1. If all remaining stones are of either the first of the second type, or if there are an equal amount of stones from each type, the player whose turn it is wins - by picking all remaining stones.
  2. In any other position, the player whose turn it is can reduce the number of stones of either the first or second type by one or more, or can reduce the number of both types of stones by one or more. If all of the resulting positions are winning, this position is losing. If at least one of the resulting positions is losing, the player can choose that one, so this position is winning.

More formally, for a game with A stones of the first type and B stones of the second type, create a table N[A+1, B+1] of booleans, where true means winning and false means losing.

Then just fill the table like this:

for (a = 0; a <= A; a++) {
  for (b = 0; <= B; b++) {
    if (a == 0 || b == 0 || a == b) {
      // case 1, always winning
      N[a, b] = true;
    } else {
      // case 2, winning if there is a losing position reachable
      if (
        there is an 1 <= i <= a, such that N[a-i, b] is false
        OR there is an 1 <= i <= b, such that N[a, b-i] is false
        OR there is an 1 <= i <= min(a, b), such that N[a-i, b-i] is false
      ) {
        N[a, b] = true;
      } else {
        N[a, b] = false;
      }
    } 
  }
}

After filling the table, Alice should start if N[A, B] is true and let Bob start otherwise.

0
votes

Posting this as a separate answer because it so different from the other. I'll leave that answer too because this technique is probably not very useful for similar problems.

By running an example with 10 stones of each type by hand, I found that the only losing positions are (1, 2), (3, 5), (4, 7), (6, 10). There is a search engine for integer sequences where one can search for known formulas given the start of the sequence, called OEIS

So there is sequence A072061, which matches this one. This teaches us two things:

  1. This is a known problem and the game is more commonly known as Wythoff's game
  2. All losing positions are given by the formula (a(2*k), a(2*k+1)) for some integer k and a(n) = n*(1+(-1)^n)/4+floor((2*n+1-(-1)^n)*(1+sqrt(5))/8)

So to determine if Alice should start, you can compute if (A, B) is a losing position using the given formula.