algorithmdata-structuresdynamic-programminggame-theory

Recurrence relation for variation of Nim Game


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.


Solution

  • 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.