kunaajain's blog

Question on Game Theory
By kunaajain, history, 8 years ago, In English

Hi this was a recent coding question asked by a company. Its over, so safe to discuss now. I am interested in strategies approaches for this :)

‘samu’ and ‘vibhu’ are playing a game where there are N integers from 1 to N lying on the table. In each turn, the player gets to pick one integer to mark as visited from among the previously unvisited ones. If in a turn, the player picks a number which completes the picking of three consecutive numbers, he wins. i.e., say at some stage in the game 2 and 4 are already picked(visited) if the player now picks 3, he wins. Assuming samu starts first and both the players play perfectly optimally, who is the winner.

  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think,

each turn samu and vibhu will try not to pick such Integer that has an absolute difference <=2 with a visited one or previously taken.

if they pick such Integer, alternate player will be the winner... so,

if N is <3 nobody will win

if (N+4)/5 is odd samu will win. otherwise vibhu will win

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    umm not sure if it works.. for N = 3 , 4 , 5, 7, 8, 9, 10, 11 Samu wins. For 6, 12, 20 Vibhu wins. I tried with exponential code for these results.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In my opinion, if N <= 4, then nobody will win, because each player will only have max 2 Integer. But if N > 4, I think the result is draw, if Samu start first, and pick Integer X, then Vibhu will pick X+1 or X-1 (which one is unvisited) to prevent Samu to win.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Samu can pick x+2 and win. I think you misunderstood question..

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

Firstly, to make proper analysis of this game, we need to reformulate it in "player who can't make move according to some rules loses". It is quite easy to see that player that is first to create a situation, where there are two numbers with difference  ≤ 2 loses. So we can just forbid moves within 1 or 2 (in both directions) of any already taken number (the game actually has no draws now).

Now, consider a situation where first player has just taken number x as his first move. Then game splits in two independent games of length max(0, x - 2), max(0, n - x - 3) (according to reformulated statement n = 0 is losing for first player and n = 1 or n = 2 is winning) — we forbid taking numbers in [x - 2, x + 2], but taking other numbers is okay and left and right segments are independent because (x + 3) - (x - 3) = 6 > 2.

Now, we succesfully reduced this problem to a Grundy theory problem. This means, that we have already found a way to calculate grundy numbers of game for n = 1, ..., N in O(N2) by usual dynamic programming: dp[n] = mex(x = 1...n | (dp[max(0, x - 2)] xor dp[max(0, n - x - 3)). But actually, sequence of grundy numbers for this game is non-strictly periodic (it consists of two parts: a non-periodic finite prefix and infinite periodic suffix). Actually, periodicity is common quality for sequence of grundy numbers of functions of 1 argument: even when grundy numbers can grow arbitrarily large, sequence is often a sum of arithmetic progression and periodic function).

In fact this is an example of so called octal games.

UPD Actually, I just checked the game for periodicity with small aperiodic part and period and didn't find anything. So I retract (for now) my words that it is periodic. It is still conjectured that all finite octal games are periodic, though.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, do you have code sample for this approach? Asking since you wrote that you checked the game. Using your algo it gives player 1 wins for N = 12, but thats not the case.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Strange, for me it definitely outputs that for 12 grundy number is 0, which means that second player wins.

      Code:
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks :) I was trying to do this without Grundy numbers actually, but I guess now is the time I dive into grundy numbers. Thanks again :)

        → Reply