21 счет игры (как игра NIM)

Question

Я хотел бы разработать бота, способного каждый раз побеждать в игре с 21 счетом /NIM.

Правила: Вот правила игры:

• В игре игроки по очереди произносят до 3 цифр (начиная с 1 и заканчивая движением вверх).
• Кто бы ни сказал, что число 21 устранено.

---

Strategie: Победа в игре всегда возможна, если вы знаете правильную стратегию Как выиграть?

• Продолжая, если вы скажете 12, вы выиграете

• если вы скажете 9, вы выиграете,

• если вы скажете 6, вы выиграете,
• если вы скажете 3, вы выиграете
• Итак, если вы идете вторым, вы можете гарантировать, что вы скажете 3, и выигрывать каждый раз.

Мой вопрос: я хотел бы создать бота, используя javascript, который сможет побить пользователя.

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)

Примечание: я не закончил разработку, но, очевидно, есть некоторые проблемы. Я был бы очень признателен, если бы кто-нибудь смог помочь мне найти / исправить их.

Answer 1

Чтобы решить игру NIM, мы рассчитываем Nimbers:

1. проигравшее состояние имеет нимбер 0
2. остальная часть чисел рассчитывается путем просмотра всех достижимых состояний и взятия мекс (минимальный исключающий), который является наименьшим отсутствующим числом в последовательности 0, 1, 2, 3, ...

• Nimber (21) = 0
• nimber (20) = 1, только 0 может быть достигнуто, поэтому 1 - мекс
• nimber(19) = 2, 0 и 1 могут быть достигнуты за один ход, поэтому мекс 2
• нимбер (18) = 3
• nimber (17) = 0, потому что мы можем достичь от 1 до 3, поэтому 0 - наименьшее пропущенное число

и так далее...

Легко видеть, что это повторяется. Таким образом, мы можем рассчитать Nimber, как это (n это текущее состояние): 3 - (n + 2) % 4, Или обобщенно, если мы можем рассчитывать до x цифры и проигрышный номер y: мы хотим добавить z в y, чтобы (y + z) % (x + 1) = x и тогда формула x - (n + z) % (x + 1), Можно также сказать, что y % (x + 1) + z = x (найти самый маленький неотрицательный zдругая формула имеет бесконечное количество решений для z), так z = x - y % (x + 1),

Таким образом, если nimber состояния не равен 0, выигрышный ход - это переход к следующему проигрышному состоянию с nimber 0. Как оказалось, выигрышный ход (сколько чисел считать) в точности равен nimber.

Важно отметить, что 21 обозначает состояние, когда было сказано 20, а 21 еще не было сказано.

Это становится интересным, когда мы играем с несколькими экземплярами, например, с нумерацией карт от 1 до 21 в нескольких стопках, когда вы можете взять от 1 до 3 самых младших карт в стопке. Тот, кто берет самую последнюю карту, проигрывает. Здесь мы можем просто переписать число всех стеков, если оно равно 0, мы находимся в проигрышном состоянии, в противном случае выигрышный ход.