21 counting game (like nim game)

Question

I'd like to develop a bot that is able to win the 21 - counting game/NIM - game every time.

Rules: Here are the rules for the game:

In a game players take it in turns to say up to 3 numbers (starting at 1 and working their way up).
Who every say's the number 21 is eliminated.

Strategie: Winning the game ever time is possible if you know the right strategy How to win?

Continuing on, if you say 12 you win
if you say 9, you win,
if you say 6, you win,
if you say 3, you win
So, if you go second, you can guarantee that you will say 3, and win every time.

My question: I'd like to create a bot using javascript that is able to beat the user.

let _ = function(call, int) {
  setTimeout(call, int)
}



class game {
  constructor() {
    this.number = 1;
  }
  user(val) {
    console.log(`Userinput: +${val}`)
    for (let i=0; i<val; i++)
       console.log(`number: ${this.number++}`)
    this.checkWin("bot")
    console.log("\n\n\n")
    this.bot()
  }
  bot() {
    let val = (this.number === 3) ? 3 : parseInt(Math.random()*2)+1
    console.log(`Botinput: +${val}`)
    for (let i=0; i<val; i++)
       console.log(`number: ${this.number++}`)
    this.checkWin("user")
    console.log("\n\n\n")
  } 
  checkWin(looser) {
    if (this.number >= 21) {
      console.log(`${looser} lost the game.`);
    }
  }
}


let instance = new game()


_(function() {
  instance.user(3)
},0)
_(function() {
  instance.user(2)
},100)
_(function() {
  instance.user(3)
},200)
_(function() {
  instance.user(3)
},300)
_(function() {
  instance.user(1)
},400)

Note: I did not finished the development but obviously there are some issues. I would really appreciate if somebody is able to help me finding/fixing them.

Are you talking about NIM game: https://riverbendmath.org/modules/Nim_Games/? — NiVeR, Sep 15 '18 at 16:40
I don't understand the logic of `if you say 18, you win`. It seems that if you say `18`, I say `19, 20` forcing you to say `21 `and loose. What am I missing? — Mark, Sep 15 '18 at 16:58
Hm, I edited to add the [tag:nim-game] tag and it seems I messed up an edit you were doing at the same time. — m69's been on strike for years, Sep 15 '18 at 17:02
From the NIM link: "The object of the game is to be the **first one to say** [some target number]". So you'd like to force your opponent to say the target number less 1, 2, or 3. This suggests a solution that could be compactly written as a recursive function. — danh, Sep 15 '18 at 17:14

maraca · Answer 1 · 2018-09-16T12:42:02.640

To solve a nim game we calculate the nimbers:

the losing state has nimber 0
the rest of the nimbers is calculated by looking at all the reachable states and taking the mex (minimal exclusive) which is the smallest missing number in the sequence of 0, 1, 2, 3, ...

nimber(21) = 0
nimber(20) = 1, only 0 can be reached, so 1 is the mex
nimber(19) = 2, 0 and 1 can be reached within one move, so mex is 2
nimber(18) = 3
nimber(17) = 0, because we can reach 1 to 3, so 0 is the smallest missing number

and so on...

It is easy to see, that it is repeating. So we can calculate the nimber like this (n is the current state): 3 - (n + 2) % 4. Or generalized if we can count up to x numbers and the losing number is y: we want to add z to y, so that (y + z) % (x + 1) = x and then the formula is x - (n + z) % (x + 1). We could also say that y % (x + 1) + z = x (to find the smallest non-negative z, the other formula has an infinite amount of solutions for z), so z = x - y % (x + 1).

So if the nimber of a state is not 0, the winning move is the one going to the next losing state with nimber 0. As it turns out the winning move (how many numbers to count) is exactly equal to the nimber.

It is important to note, that 21 denotes the state when 20 was said, 21 itself wasn't said yet.

It gets interesting when we play with several instances, like having cards numbered from 1 to 21 in several stacks where you can draw 1 to 3 of the lowest cards in a stack. The one taking the very last card loses. Here we can just xor the nimbers of all stacks, if it is 0 we are in a losing state, otherwise there is a winning move.

21 counting game (like nim game)

1 Answers1