Zurück zum Blog

Tech

Infinity TicTacToe

8 Min. Lesezeit

Klassisches TicTacToe ist schnell auserzählt: Meistens endet es unentschieden, sobald beide aufpassen. Ich habe eine Variante gesehen, die sich Infinity TicTacToe nennt – und damit wird es gleich ein bisschen spannender: Man muss auf einmal richtig mitdenken.

Die Regeländerung: nur drei Steine

Die eine besondere Regel lautet:

Jeder Spieler hat maximal drei Steine auf dem Brett. Setzt man einen vierten, verschwindet danach der älteste Stein.

Dadurch gibt es kein klassisches Unentschieden mehr – das Brett ist nie „voll", weil ständig Steine kommen und gehen. Man muss immer mitdenken, welcher eigene Stein als Nächstes verschwindet. Genau das macht es taktisch. Ein bisschen einfacher wird es dadurch, dass ich den Stein, der als Nächstes verschwindet, optisch hervorhebe. So weiß man wenigstens, was einen gleich erwartet.

Gewonnen hat weiterhin, wer drei eigene Steine in einer Reihe hat (Zeile, Spalte oder Diagonale).

Schritt 1: Der Spielzustand

Zuerst brauchen wir eine Art, den aktuellen Stand festzuhalten. Das Wichtigste dabei: Wir merken uns die Steine je Spieler in der Reihenfolge, in der sie gesetzt wurden – nur so wissen wir später, welcher der „älteste" ist.

function createGame(starter = 'X') {
  return {
    moves: { X: [], O: [] }, // Feld-Indizes 0..8, ältester Stein zuerst
    turn: starter,           // wer als Nächstes zieht
    moveCount: 0,
    status: 'running',       // 'running' | 'won' | 'draw'
    winner: null,
    winLine: null,           // die drei Felder der Gewinnreihe
  };
}

Die neun Felder nummerieren wir von 0 (oben links) bis 8 (unten rechts):

 0 | 1 | 2
---+---+---
 3 | 4 | 5
---+---+---
 6 | 7 | 8

Schritt 2: Wo darf man setzen?

Belegt sind alle Felder, auf denen ein Stein liegt – egal von wem. Alles andere ist frei. (Der noch sichtbare älteste Stein zählt weiterhin als belegt, deshalb kann man nicht „aus Versehen" auf das Feld setzen, das gleich frei wird.)

function occupied(state) {
  return new Set([...state.moves.X, ...state.moves.O]);
}

function legalMoves(state) {
  if (state.status !== 'running') return [];
  const taken = occupied(state);
  const free = [];
  for (let c = 0; c < 9; c++) if (!taken.has(c)) free.push(c);
  return free;
}

Schritt 3: Gewinn prüfen

Es gibt genau acht Möglichkeiten zu gewinnen. Die schreiben wir einmal auf und prüfen dann, ob eine davon vollständig einem Spieler gehört. Man könnte sie zwar auch berechnen, aber da sie sich nie ändern, spare ich mir das und lege die möglichen Gewinnkombinationen einfach in einem Array ab.

const LINES = [
  [0, 1, 2], [3, 4, 5], [6, 7, 8], // Zeilen
  [0, 3, 6], [1, 4, 7], [2, 5, 8], // Spalten
  [0, 4, 8], [2, 4, 6],            // Diagonalen
];

function findWinLine(cells) {
  const set = new Set(cells);
  for (const line of LINES) {
    if (line.every((c) => set.has(c))) return line;
  }
  return null;
}

Schritt 4: Einen Zug ausführen

Jetzt kommt das Herzstück. Ein Zug läuft so ab:

  1. Den Stein an die eigene Liste anhängen.
  2. Gewinn prüfen – schon jetzt, bevor etwas verschwindet.
  3. Sind es mehr als drei Steine, den ältesten entfernen (das ist der erste in der Liste).
  4. Sonst ist der andere Spieler dran.
const MAX_STONES = 3;
const MOVE_LIMIT = 60; // Notbremse: nach 60 Halbzügen Remis, damit es nie ewig läuft

function other(p) {
  return p === 'X' ? 'O' : 'X';
}

function applyMove(state, cell) {
  if (state.status !== 'running') return state;
  if (occupied(state).has(cell)) return state; // belegt -> ignorieren

  const p = state.turn;
  let list = [...state.moves[p], cell]; // 1) anhängen

  // 2) Gewinn direkt nach dem Setzen?
  let win = findWinLine(list);
  if (win) {
    return { ...state, moves: { ...state.moves, [p]: list },
             status: 'won', winner: p, winLine: win };
  }

  // 3) Vierter Stein -> ältesten entfernen
  if (list.length > MAX_STONES) list = list.slice(1);

  // 4) weiter geht's
  const moves = { ...state.moves, [p]: list };
  const moveCount = state.moveCount + 1;
  if (moveCount >= MOVE_LIMIT) return { ...state, moves, moveCount, status: 'draw' };
  return { ...state, moves, moveCount, turn: other(p) };
}

Wichtig ist die Reihenfolge in Schritt 2 und 3: Wenn der vierte Stein eine Reihe vervollständigt, gewinnt man – auch wenn im selben Moment der älteste Stein verschwinden würde. Der Gewinn zählt zuerst.

Und welcher Stein verschwindet als Nächstes? Der älteste, sobald das Limit erreicht ist:

function oldestStone(state, p) {
  const list = state.moves[p];
  return list.length >= MAX_STONES ? list[0] : null;
}

Den zeigen wir gleich verblasst an, damit man sieht, was beim nächsten Zug passiert.

Zur Sicherheit habe ich außerdem ein MOVE_LIMIT eingebaut, damit eine Partie nicht ewig laufen kann. 60 Halbzüge (das heißt 30 Züge pro Spieler) sind meiner Meinung nach ein guter Wert – das ist ohnehin schon ziemlich lang.

Schritt 5: Das Brett anzeigen

Jetzt machen wir das Ganze sichtbar. Ein bisschen HTML und CSS reichen:

<div id="board" style="display:grid;grid-template-columns:repeat(3,80px);gap:4px"></div>
<p id="status"></p>

const boardEl = document.getElementById('board');
const statusEl = document.getElementById('status');
let game = createGame('X');

function render() {
  boardEl.innerHTML = '';
  const oldestX = oldestStone(game, 'X');
  const oldestO = oldestStone(game, 'O');

  for (let i = 0; i < 9; i++) {
    const btn = document.createElement('button');
    btn.style.cssText = 'height:80px;font-size:32px';
    const owner = game.moves.X.includes(i) ? 'X'
                : game.moves.O.includes(i) ? 'O' : '';
    btn.textContent = owner;
    // der älteste Stein wird halbtransparent -> verschwindet als Nächstes
    if (i === oldestX || i === oldestO) btn.style.opacity = 0.4;
    btn.disabled = owner !== '' || game.status !== 'running';
    btn.onclick = () => play(i);
    boardEl.appendChild(btn);
  }

  statusEl.textContent =
    game.status === 'won' ? `${game.winner} gewinnt!`
  : game.status === 'draw' ? 'Unentschieden'
  : `${game.turn} ist dran`;
}

Ein Klick des Spielers löst einen Zug aus – dazu gleich mehr im letzten Schritt.

Schritt 6: Der Computer-Gegner

Ein Spiel gegen sich selbst ist langweilig. Wir brauchen einen Gegner. Der einfachste zieht einfach zufällig:

function randomMove(state) {
  const moves = legalMoves(state);
  return moves[Math.floor(Math.random() * moves.length)];
}

Das ist als Anfang völlig okay – aber unser Gegner soll auch mal gewinnen wollen. Dafür nehmen wir Minimax, einen klassischen Algorithmus für solche Spiele. Die Idee in einem Satz:

Der Computer spielt in Gedanken alle möglichen Züge durch, dann die Antworten darauf, dann die Antworten auf die Antworten … und wählt den Zug, der für ihn am besten ausgeht – in der Annahme, dass der Gegner ebenfalls optimal spielt.

Eine genauere Beschreibung des Minimax-Algorithmus findet man auf Wikipedia.

Weil man nicht bis ans Ende rechnen kann (durch das Verschwinden könnte das Spiel ewig laufen), begrenzen wir die Suchtiefe. Und wenn wir an dieser Grenze ankommen, brauchen wir eine grobe Einschätzung, wie gut eine Stellung ist:

function evaluate(state, me) {
  const opp = other(me);
  const mine = new Set(state.moves[me]);
  const theirs = new Set(state.moves[opp]);
  let score = 0;
  for (const line of LINES) {
    let m = 0, t = 0;
    for (const c of line) {
      if (mine.has(c)) m++;
      else if (theirs.has(c)) t++;
    }
    if (t === 0) score += m === 2 ? 10 : m; // eigene offene Reihe ist gut
    if (m === 0) score -= t === 2 ? 10 : t; // gegnerische offene Reihe ist schlecht
  }
  if (mine.has(4)) score += 3;   // die Mitte ist wertvoll
  if (theirs.has(4)) score -= 3;
  return score;
}

Und hier die eigentliche Suche. Sie ruft sich selbst auf (Rekursion) und benutzt einen kleinen Trick namens Alpha-Beta-Pruning, der offensichtlich schlechte Äste früh abschneidet:

function minimax(state, depth, alpha, beta, me) {
  if (state.status === 'won') return state.winner === me ? 1000 + depth : -1000 - depth;
  if (state.status === 'draw') return 0;
  if (depth === 0) return evaluate(state, me);

  const maximizing = state.turn === me;
  let best = maximizing ? -Infinity : Infinity;
  for (const m of legalMoves(state)) {
    const score = minimax(applyMove(state, m), depth - 1, alpha, beta, me);
    if (maximizing) {
      best = Math.max(best, score);
      alpha = Math.max(alpha, best);
    } else {
      best = Math.min(best, score);
      beta = Math.min(beta, best);
    }
    if (beta <= alpha) break; // dieser Ast lohnt sich nicht mehr
  }
  return best;
}

Das + depth bzw. - depth beim Gewinn sorgt dafür, dass der Computer schnelle Siege bevorzugt und Niederlagen möglichst lange hinauszögert.

Zum Schluss wählen wir aus allen Zügen den mit der besten Bewertung:

function chooseMove(state, depth = 6) {
  const me = state.turn;
  let bestScore = -Infinity;
  let best = [];
  for (const m of legalMoves(state)) {
    const score = minimax(applyMove(state, m), depth - 1, -Infinity, Infinity, me);
    if (score > bestScore) { bestScore = score; best = [m]; }
    else if (score === bestScore) best.push(m);
  }
  return best[Math.floor(Math.random() * best.length)]; // bei Gleichstand zufällig
}

Schwierigkeitsstufen sind jetzt ein Einzeiler: Man dreht an der Suchtiefe (depth) und mischt mit einer gewissen Wahrscheinlichkeit einen Zufallszug bei, damit der Gegner auch mal patzt:

function aiMove(state, { depth, randomRate }) {
  if (Math.random() < randomRate) return randomMove(state);
  return chooseMove(state, depth);
}

// z. B.: entspannt {depth:1, randomRate:0.5}  …  unmöglich {depth:9, randomRate:0}

Schritt 7: Alles verdrahten

Fehlt nur noch, Mensch und Computer abwechselnd ziehen zu lassen. Der Mensch ist X, der Computer O. Nach jedem Menschenzug legt der Computer eine kurze Denkpause ein – das fühlt sich natürlicher an als eine sofortige Antwort:

const LEVEL = { depth: 6, randomRate: 0.05 }; // „schwer"

function play(cell) {
  if (game.turn !== 'X' || game.status !== 'running') return;
  game = applyMove(game, cell);
  render();
  scheduleAi();
}

function scheduleAi() {
  if (game.turn !== 'O' || game.status !== 'running') return;
  const delay = 400 + Math.random() * 1100; // 400–1500 ms
  setTimeout(() => {
    game = applyMove(game, aiMove(game, LEVEL));
    render();
  }, delay);
}

// Wer beginnt, entscheidet der Zufall:
game = createGame(Math.random() < 0.5 ? 'X' : 'O');
render();
scheduleAi(); // falls der Computer anfängt

Das war's! Mit diesen paar Funktionen ist das Spiel komplett spielbar. Schön daran: Die eigentliche Logik (createGame, applyMove, findWinLine, minimax) weiß nichts von HTML oder einem Framework. Man kann sie unverändert testen oder in eine beliebige Oberfläche einbauen – genau so läuft sie auch hier im Spiel, nur noch mit einem einigermaßen ansprechenden Design (in meinen Augen).