algorithm - Tower Breakers - 带有除数的 nim 游戏变体

Question

我遇到过一款名为 Tower Breakers 的游戏，它似乎是 nim game 的变体。 .

• 有两个玩家，玩家 1 和玩家 2。
• 最初有 n塔，每个塔的高度m , 两者 n和 m正整数。
• 玩家 1 开始，然后他们轮流移动。
• 在每个回合中，玩家可以选择高度为x > 1 的塔。并将其高度减小为正整数 y , 其中1 <= y < x和 y平分x .
• 如果当前玩家无法做出任何 Action ，则输掉游戏。

有什么制胜法宝吗？如果一开始塔的高度不相等怎么办？

Answer 1

一般情况

这确实可以像 nim game 一样解决, 但使用不同的数字定义。

在原始游戏中，塔的数量简单地定义为其高度。

在这个变体中，塔的数量 T高度h(T) = x = p₁ˢ¹ … pₖˢᵏ , 与 pᵢ质数，是

n(T) = s₁ + … + sₖ

n的列表编号塔L = (T₁, …, Tₙ)是平常的

n(L) = n(T₁) ⊕ … ⊕ n(Tₙ)

如果你的回合开始时数字为 0，假设其他玩家玩得很好，你将失去你所做的一切。

否则，你只需要做一个让数字变为零的 Action 。

你可以这样做，因为如果 n(L) > 0然后有一座塔，我们假设它是Tₙ，不失一般性。 , 这样 n(Tₙ) ⊕ n(L) < n(L) .

存在这样的塔:n(L) 的最左边位是1那是因为一些塔Tₙ在该位位置有一个 1。做n(Tₙ) ⊕ n(L)你杀死那个 1 并且不改变 n(Tₙ) 的更重要的位因为它是 n(L) 的最左边位.所以n(Tₙ) ⊕ n(L)更小。

那么只需要修改Tₙ即可至 Tₙ'这样 n(Tₙ') = n(Tₙ) ⊕ n(L) ，因此

n(L') = n(T₁) ⊕ … ⊕ n(Tₙ') = n(T₁) ⊕ … ⊕ n(Tₙ) ⊕ n(L) = n(L) ⊕ n(L) = 0

此移动总是可能的，例如将高度降低到 x' = p₁ˢ¹ … pₗ₋₁ˢˡ⁻¹ pₗᵈ , 与 l <= k和 0 < d <= sₗ , 这样 s₁ + … + sₗ₋₁ + d = n(Tₙ) ⊕ n(L) . x'划分 x通过 build ，和x' < x所以它们是不同的。

一旦数字为零，无论其他玩家做什么 Action ，都会影响该塔的数字，然后是总异或n(L)。将不再为零。然后重复相同的策略。

特殊情况

在所有塔具有相同高度的特定情况下，

• 如果有偶数个塔或高度为 1 的塔，则总数将为零，因此玩家 2 如果发挥最佳，将获胜。
• 否则，总人数将不为零，因此如果玩家 1 发挥最佳，他将获胜。

这实际上可以在不使用数字的情况下显示:

• 如果塔的数量是偶数，玩家 2 可以将它们分成两对。他想要保持不变的是每对塔的高度相同。每当玩家 1 采取行动时，这个不变量就会被打破。然后玩家 2 只需要对另一座塔进行相同的移动(这将是一个有效的移动，否则玩家 1 无法完成)。最终，所有塔的高度都将达到 1，玩家 2 将获胜。

• 如果有奇数个塔(高度 > 1)，玩家 1 可以将最后一个塔的高度降低为 1。实际上，这就像消除那个塔。所以现在轮到玩家 2 了，但可玩的塔的数量将是偶数。所以前面的情况适用，玩家 1 将获胜。

播放

您可以在以下片段中播放:

function nimber(num) {
  var n = 0;
  for (var i=2; i<=num; ++i)
    while(num % i == 0) {
      ++n;
      num /= i;
    }
  return n;
}
function change(tower, newHeight, oldHeight, txt) {
  tower.textContent = newHeight;
  totalNimber ^= tower.dataset.nimber;
  tower.dataset.nimber = nimber(newHeight);
  totalNimber ^= tower.dataset.nimber;
  log.textContent += "    " + txt + " the height of the " + tower.getAttribute('data-index')
                     + "-th tower from " + oldHeight + " to " + newHeight + ".\n";
  if (newHeight == 1) tower.removeEventListener('click', playerMove);
}
function end(txt) {
  log.textContent += "    " + txt;
  playerMove = Function.prototype;
}
function prePlayerMove() {
  log.textContent += "Your turn. nimber = " + totalNimber + ".\n";
  for (var i=0; i<n; ++i) {
    var height = +towers.children[i].textContent;
    if (height != 1) return;
  }
  end("You lose");
}
function playerMove() {
  var oldHeight = +this.textContent, newHeight;
  while(!newHeight || newHeight <= 0 || oldHeight%newHeight || newHeight == oldHeight)
    newHeight = +prompt("Current tower height is " + oldHeight + ". Enter new height");
  change(this, newHeight, oldHeight, "You reduce");
  pcMove();
}
function pcMove() {
  log.textContent += "PC's turn (nimber = " + totalNimber + ").\n";
  if (totalNimber == 0) { // Oh shit.
    for (var i=0; i<n; ++i) {
      var oldHeight = +towers.children[i].textContent;
      if (oldHeight != 1)
        for (var j=2; j<=oldHeight; ++j)
          if (oldHeight % j == 0) {
            var newHeight = oldHeight / j;
            change(towers.children[i], newHeight, oldHeight, "PC reduces");
            prePlayerMove();
            return;
          }
    }
    end("PC loses");
  } else {
    for (var i=0; i<n; ++i) {
      var tower = towers.children[i];
      var objective = tower.dataset.nimber ^ totalNimber;
      if (objective < tower.dataset.nimber) {
        var oldHeight = +tower.textContent;
        var newHeight = oldHeight;
        var nim = 0;
        for (var j=2; j<=newHeight && nim<objective; ++j) {
          while(newHeight % j == 0 && nim<objective) {
            ++nim;
            newHeight /= j;
          }
        }
        newHeight = oldHeight / newHeight;
        if (nimber(newHeight) != objective) throw Error('Fatal error');
        change(tower, newHeight, oldHeight, "PC reduces");
        break;
      }
    }
    prePlayerMove();
  }
}
var n, m;
while(!Number.isInteger(n) || n < 0) n = +prompt("Number of towers");
while(!Number.isInteger(m) || m < 0) m = +prompt("Height of each tower");
var totalNimber = 0;
var towers = document.getElementById('towers');
var log = document.getElementById('log');
for (var i=0; i<n; ++i) {
  var nim = nimber(m);
  totalNimber ^= nim;
  var tower = document.createElement('div');
  tower.dataset.index = i+1;
  tower.dataset.nimber = nim;
  tower.textContent = m;
  tower.addEventListener('click', playerMove);
  towers.appendChild(tower);
}
pcMove();

#towers > div {
  display: inline-block;
  border: 1px solid;
  cursor: pointer;
  margin: 5px;
  padding: 5px;
}

<div id="towers"></div>
<pre id="log"></pre>