Nim: Bouton's XOR Strategy

// Nim — normal play, last-stone-wins, vs an XOR-perfect bot.
// You go first. Tap a stone to remove it AND every stone to its right in
// that same row. The bot replies after a short delay using the optimal
// Bouton (1901) strategy: drive the XOR of pile sizes to zero whenever
// possible. The live Nim-sum is shown so you can watch the math.

const INITIAL = [1, 3, 5, 7];
let rows;            // current pile sizes
let turn;            // "player" | "bot" | "over"
let winner;          // "player" | "bot" | null
let botTimer;        // countdown in seconds until bot moves
let lastClicks = [];
let hoverRow = -1;
let hoverCol = -1;   // hover column = first stone that would be removed
let lastMessage = "";
let W = 0, H = 0;
let pilesStr = "";       // cached "a XOR b XOR ..." display string
let pilesStrKey = "";    // marker so we only rebuild on change

function reset() {
  rows = INITIAL.slice();
  turn = "player";
  winner = null;
  botTimer = 0;
  lastMessage = "your move";
  pilesStrKey = "";
}

function init({ width, height }) {
  W = width; H = height;
  reset();
}

function xorSum(arr) {
  let x = 0;
  for (let i = 0; i < arr.length; i++) x ^= arr[i];
  return x;
}

function totalStones(arr) {
  let t = 0;
  for (let i = 0; i < arr.length; i++) t += arr[i];
  return t;
}

// Optimal Bouton move: find a pile whose XOR with current sum reduces it.
// If nim-sum is zero (losing for mover), play a "least damaging" move:
// take one stone from the largest pile.
function botMove() {
  const x = xorSum(rows);
  if (x === 0) {
    // Losing position — take 1 from the largest pile
    let bi = 0;
    for (let i = 1; i < rows.length; i++) if (rows[i] > rows[bi]) bi = i;
    if (rows[bi] === 0) return; // nothing to do
    rows[bi] -= 1;
    return;
  }
  // Find a pile p where p XOR x < p; reduce it to p XOR x.
  for (let i = 0; i < rows.length; i++) {
    const target = rows[i] ^ x;
    if (target < rows[i]) {
      rows[i] = target;
      return;
    }
  }
}

function gameOver() {
  return totalStones(rows) === 0;
}

// Geometry: each row gets a horizontal band; stones are circles laid left-to-right.
function layout() {
  const maxStones = Math.max.apply(null, INITIAL);
  const rowsN = INITIAL.length;
  const topPad = 70;
  const botPad = 90;
  const sidePad = 24;
  const usableH = Math.max(40, H - topPad - botPad);
  const bandH = usableH / rowsN;
  const stoneR = Math.min(bandH * 0.36, (W - sidePad * 2) / (maxStones * 2.2));
  const gap = stoneR * 2.15;
  return { topPad, sidePad, bandH, stoneR, gap, rowsN, maxStones };
}

// Returns {row, col} of the stone under (px, py), or null. col is 0-indexed
// within the current rows[r] count.
function pickStone(px, py, geom) {
  const { topPad, sidePad, bandH, stoneR, gap } = geom;
  for (let r = 0; r < rows.length; r++) {
    const cy = topPad + bandH * (r + 0.5);
    if (py < cy - stoneR - 4 || py > cy + stoneR + 4) continue;
    const count = rows[r];
    if (count === 0) continue;
    const rowW = (count - 1) * gap;
    const x0 = (W - rowW) / 2;
    for (let c = 0; c < count; c++) {
      const cx = x0 + c * gap;
      const dx = px - cx, dy = py - cy;
      if (dx * dx + dy * dy <= (stoneR + 4) * (stoneR + 4)) {
        return { row: r, col: c };
      }
    }
    // Also accept clicks anywhere on the row band as "the nearest stone"
    if (py >= cy - bandH * 0.45 && py <= cy + bandH * 0.45) {
      // map x to nearest column
      let bestC = 0, bestD = Infinity;
      for (let c = 0; c < count; c++) {
        const cx = x0 + c * gap;
        const d = Math.abs(px - cx);
        if (d < bestD) { bestD = d; bestC = c; }
      }
      return { row: r, col: bestC };
    }
  }
  return null;
}

// Restart button rect when game is over
function restartRect() {
  const w = 180, h = 40;
  return { x: (W - w) / 2, y: H - 60, w, h };
}

function tick({ ctx, dt, width, height, input }) {
  W = width; H = height;
  const geom = layout();

  // Hover update
  const hit = pickStone(input.mouseX, input.mouseY, geom);
  hoverRow = hit ? hit.row : -1;
  hoverCol = hit ? hit.col : -1;

  // Consume clicks. On game over, any tap restarts (the play-again button is
  // just a visual affordance for the same behavior). On the player's turn we
  // ignore stray clicks during bot thinking.
  const clicks = input.consumeClicks ? input.consumeClicks() : [];
  if (clicks && clicks.length) {
    for (let i = 0; i < clicks.length; i++) {
      const c = clicks[i];
      if (turn === "over") {
        reset();
        break;
      }
      if (turn !== "player") continue;
      const pick = pickStone(c.x, c.y, geom);
      if (!pick) continue;
      // Remove that stone and all to its right in that row.
      // rows[r] becomes pick.col (kept stones are indices 0..col-1)
      if (pick.col < rows[pick.row]) {
        rows[pick.row] = pick.col;
        if (gameOver()) {
          // Player took the last stone — player wins (normal play).
          winner = "player";
          turn = "over";
          lastMessage = "you took the last stone — you win";
        } else {
          turn = "bot";
          botTimer = 0.55;
          lastMessage = "thinking...";
        }
        break;
      }
    }
  }

  // Reset on R
  if (input.justPressed && (input.justPressed("r") || input.justPressed("R"))) {
    reset();
  }

  // Bot turn
  if (turn === "bot") {
    botTimer -= dt;
    if (botTimer <= 0) {
      botMove();
      if (gameOver()) {
        winner = "bot";
        turn = "over";
        lastMessage = "bot took the last stone — bot wins";
      } else {
        turn = "player";
        lastMessage = "your move";
      }
    }
  }

  // ---- Draw ----
  ctx.fillStyle = "#0e1116";
  ctx.fillRect(0, 0, W, H);

  // Title bar
  ctx.fillStyle = "#e6edf3";
  ctx.textBaseline = "top";
  ctx.textAlign = "left";
  ctx.font = "bold 16px sans-serif";
  ctx.fillText("Nim", 14, 12);

  // Live Nim-sum (XOR) display in top-right
  const x = xorSum(rows);
  ctx.textAlign = "right";
  ctx.font = "bold 14px ui-monospace, monospace";
  ctx.fillStyle = x === 0 ? "#5dd39e" : "#f6c177";
  // Rebuild the piles display string only when the rows actually change —
  // saves a per-frame map+join allocation that ran for the entire game.
  const key = rows.join(",");
  if (key !== pilesStrKey) {
    let s = String(rows[0]);
    for (let i = 1; i < rows.length; i++) s += " XOR " + rows[i];
    pilesStr = s;
    pilesStrKey = key;
  }
  ctx.fillText(pilesStr + " = " + x, W - 14, 12);
  ctx.font = "11px sans-serif";
  ctx.fillStyle = "rgba(230,237,243,0.55)";
  ctx.fillText(x === 0 ? "nim-sum 0  (mover loses w/ best play)" : "nim-sum nonzero  (mover wins w/ best play)", W - 14, 32);

  // Draw rows of stones
  const { topPad, bandH, stoneR, gap } = geom;
  for (let r = 0; r < rows.length; r++) {
    const cy = topPad + bandH * (r + 0.5);
    const count = rows[r];
    // Row label
    ctx.fillStyle = "rgba(230,237,243,0.45)";
    ctx.font = "12px ui-monospace, monospace";
    ctx.textAlign = "left";
    ctx.fillText("row " + (r + 1) + " [" + count + "]", 14, cy - 8);

    // Original row outline (ghost stones for removed ones)
    const orig = INITIAL[r];
    const rowW = (orig - 1) * gap;
    const x0 = (W - rowW) / 2;
    for (let c = 0; c < orig; c++) {
      const cx = x0 + c * gap;
      if (c >= count) {
        // removed
        ctx.beginPath();
        ctx.arc(cx, cy, stoneR * 0.6, 0, Math.PI * 2);
        ctx.strokeStyle = "rgba(120,120,140,0.18)";
        ctx.lineWidth = 1;
        ctx.stroke();
        continue;
      }
      // live stone
      const isHovered = (turn === "player" && hoverRow === r && c >= hoverCol);
      ctx.beginPath();
      ctx.arc(cx, cy, stoneR, 0, Math.PI * 2);
      const grad = ctx.createRadialGradient(cx - stoneR * 0.35, cy - stoneR * 0.35, stoneR * 0.15, cx, cy, stoneR);
      if (isHovered) {
        grad.addColorStop(0, "#ffb38a");
        grad.addColorStop(1, "#b94a2c");
      } else {
        grad.addColorStop(0, "#cfd8e3");
        grad.addColorStop(1, "#5a6577");
      }
      ctx.fillStyle = grad;
      ctx.fill();
      ctx.lineWidth = 1;
      ctx.strokeStyle = isHovered ? "rgba(255,180,140,0.9)" : "rgba(0,0,0,0.35)";
      ctx.stroke();
    }
  }

  // Bottom status bar
  ctx.textAlign = "center";
  ctx.textBaseline = "alphabetic";
  ctx.font = "13px sans-serif";
  let statusColor = "rgba(230,237,243,0.85)";
  if (turn === "bot") statusColor = "#f6c177";
  if (turn === "over") statusColor = (winner === "player") ? "#5dd39e" : "#eb6f92";
  ctx.fillStyle = statusColor;
  ctx.fillText(lastMessage, W / 2, H - 70);

  // Hint
  if (turn === "player") {
    ctx.font = "11px sans-serif";
    ctx.fillStyle = "rgba(230,237,243,0.45)";
    ctx.fillText("tap a stone to remove it and every stone to its right in that row", W / 2, H - 50);
  }

  // Restart button when over
  if (turn === "over") {
    const r = restartRect();
    ctx.fillStyle = "#1f2430";
    ctx.strokeStyle = "rgba(230,237,243,0.4)";
    ctx.lineWidth = 1;
    ctx.beginPath();
    const rad = 8;
    ctx.moveTo(r.x + rad, r.y);
    ctx.lineTo(r.x + r.w - rad, r.y);
    ctx.quadraticCurveTo(r.x + r.w, r.y, r.x + r.w, r.y + rad);
    ctx.lineTo(r.x + r.w, r.y + r.h - rad);
    ctx.quadraticCurveTo(r.x + r.w, r.y + r.h, r.x + r.w - rad, r.y + r.h);
    ctx.lineTo(r.x + rad, r.y + r.h);
    ctx.quadraticCurveTo(r.x, r.y + r.h, r.x, r.y + r.h - rad);
    ctx.lineTo(r.x, r.y + rad);
    ctx.quadraticCurveTo(r.x, r.y, r.x + rad, r.y);
    ctx.closePath();
    ctx.fill();
    ctx.stroke();
    ctx.fillStyle = "#e6edf3";
    ctx.font = "bold 14px sans-serif";
    ctx.textBaseline = "middle";
    ctx.fillText("play again", r.x + r.w / 2, r.y + r.h / 2);
  }
}