# Tic-Tac-Toe mit Minimax in React

URL: https://www.mikebild.dev/de/blog/tic-tac-toe-minimax-react/

```js
function score(board, depth) {
  if (winnerOf(board) === COMPUTER) return 10 - depth;
  if (winnerOf(board) === HUMAN) return depth - 10;
  return 0;
}
```

Mehr Bewertung braucht ein unschlagbarer Tic-Tac-Toe-Gegner nicht. Ein Brett ist `10 - depth` wert, wenn der Rechner gewonnen hat, `depth - 10`, wenn der Mensch gewonnen hat, und null bei Remis. Die Suchtiefe im Wert sorgt nebenbei für Spielstil: Ein Sieg in zwei Zügen zählt mehr als einer in vier, eine Niederlage in vier Zügen ist weniger schlimm als eine in zwei. Der Gegner gewinnt also so früh wie möglich und verliert so spät wie möglich – falls er überhaupt verlieren kann, was bei fehlerfreiem Spiel nie eintritt.

Auffälliger als das, was in der Funktion steht, ist das, was fehlt: kein React, kein DOM, kein Event-Handler, kein `this`, kein `setState`. Ein Brett geht hinein, eine Zahl kommt heraus. Genau darum geht es in diesem Artikel. Das Spiel selbst ist trivial, jedes Kind lernt es in fünf Minuten. Interessant ist die Schnittlinie: Der komplette Gegner ist ein Satz reiner Funktionen über einem Array, und React rendert am Ende nur noch Zustand. Wer diese Linie nicht zieht, hat später weder testbare Logik noch eine austauschbare Oberfläche.

Das zugehörige Repository `react-tic-tac-toe` habe ich im Oktober 2016 gebaut, angestoßen durch Carsten Königs Othello in Elm – ein Projekt, das mich damals beeindruckt hat, weil dort dieselbe Trennung ganz selbstverständlich war. In Elm gibt es schlicht keine andere Möglichkeit: Spiellogik ist eine Funktion, die Ansicht eine andere. In JavaScript muss man sich dafür entscheiden.

## Das Brett ist ein Array, ein Zug ist ein neues Brett

Die Datenstruktur ist so klein, wie sie klingt: ein Array mit neun Feldern, jedes Feld `'X'`, `'O'` oder `null`. Die Indizes 0 bis 8 laufen zeilenweise von links oben nach rechts unten. Gewinnbedingungen sind acht Linien über diesen Indizes – drei Zeilen, drei Spalten, zwei Diagonalen.

```js
const HUMAN = 'X';
const COMPUTER = 'O';

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

function winnerOf(board) {
  const line = LINES.find(([a, b, c]) =>
    board[a] && board[a] === board[b] && board[a] === board[c]);
  return line ? board[line[0]] : null;
}

function movesFor(board) {
  return board.reduce((moves, field, index) =>
    field === null ? moves.concat(index) : moves, []);
}

function applyMove(board, index, player) {
  const next = board.slice();
  next[index] = player;
  return next;
}
```

Die wichtigste Entscheidung steckt in `applyMove`: Ein Zug verändert das Brett nicht, er erzeugt ein neues. `board.slice()` kopiert das Array, dann wird ein Feld gesetzt, das Original bleibt unangetastet. Für neun Elemente kostet das nichts, und es zahlt sich gleich doppelt aus.

Erstens für die Suche. Minimax probiert Züge hypothetisch aus: Was wäre, wenn der Rechner auf Feld 4 setzt und der Mensch dann auf Feld 0? Mit Mutation müsste jeder probierte Zug nach der Bewertung wieder zurückgenommen werden – klassisches Do/Undo mit allen Gelegenheiten, den Undo-Teil zu vergessen. Mit unveränderlichen Brettern gibt es nichts zurückzunehmen. Jeder Ast des Spielbaums hält sein eigenes Brett, und wenn die Rekursion zurückkehrt, ist das alte Brett noch exakt das alte Brett.

Zweitens für React. `setState` mit einem frischen Array bedeutet: Wer wissen will, ob sich etwas geändert hat, vergleicht Referenzen statt Inhalte. Dass das offizielle React-Tutorial – ausgerechnet ebenfalls ein Tic-Tac-Toe – an derselben Stelle `slice()` empfiehlt, ist kein Zufall. Unveränderliche Daten sind die Währung, in der React denkt. Dass dieselbe Entscheidung gleichzeitig den Suchalgorithmus vereinfacht und das UI-Modell bedient, war für mich der eigentliche Aha-Moment an diesem kleinen Projekt.

## Minimax, rekursiv erzählt

Der Algorithmus ist älter als jedes Web-Framework und lässt sich in einem Satz fassen: Ich wähle den Zug, der mein Ergebnis maximiert, unter der Annahme, dass der Gegner danach den Zug wählt, der mein Ergebnis minimiert – und so weiter, bis das Spiel entschieden ist. Zwei Spieler, abwechselnd Maximum und Minimum, daher der Name.

```js
function minimax(board, player, depth) {
  if (winnerOf(board) || movesFor(board).length === 0) {
    return score(board, depth);
  }

  const values = movesFor(board).map(index =>
    minimax(
      applyMove(board, index, player),
      player === COMPUTER ? HUMAN : COMPUTER,
      depth + 1
    ));

  return player === COMPUTER ? Math.max(...values) : Math.min(...values);
}

function bestMove(board) {
  const moves = movesFor(board);
  const values = moves.map(index =>
    minimax(applyMove(board, index, COMPUTER), HUMAN, 1));
  return moves[values.indexOf(Math.max(...values))];
}
```

Die Rekursion hat drei Bausteine, und alle drei stehen sichtbar im Code:

- Der Abbruch: Hat jemand gewonnen oder ist kein Feld mehr frei, liefert `score` den Wert des Endzustands.
- Der Schritt: Für jedes freie Feld entsteht per `applyMove` ein Folge-Brett, das mit vertauschtem Spieler und um eins erhöhter Tiefe bewertet wird.
- Die Auswahl: Ist der Rechner am Zug, gewinnt das Maximum der Kindwerte, sonst das Minimum.

`bestMove` ist dann nur noch die oberste Ebene dieser Suche, ausgeschrieben: alle eigenen Züge bewerten, den Index des besten zurückgeben. Ein kleiner Spielbaum zeigt, warum die Tiefe in der Bewertung den Unterschied zwischen einem korrekten und einem klugen Gegner ausmacht:

```mermaid
graph TD
  R["Brett, O am Zug<br/>nimmt das Maximum"] --> A["Zug auf Feld 2 blockt<br/>X am Zug, nimmt das Minimum"]
  R --> B["Zug auf Feld 5<br/>O gewinnt sofort: Wert +9"]
  A --> A1["X erzwingt später den Sieg<br/>Wert -6"]
  A --> A2["Remis<br/>Wert 0"]
  A -.-> AV["Minimum: -6"]
  B -.-> BV["Blatt: +9"]
```

Der Rechner steht hier vor der Wahl, eine gegnerische Reihe zu blocken oder selbst zu gewinnen. Ohne Tiefenbonus wären beide Siege gleich viel wert und die Wahl hinge von der Reihenfolge der Auswertung ab. Mit `10 - depth` ist der sofortige Sieg strikt besser – der Gegner spielt nicht nur fehlerfrei, sondern zielstrebig.

Zur Größenordnung: Von einem leeren Brett aus gibt es rund 255.000 mögliche Spielverläufe, mit jedem gesetzten Stein schrumpft der Baum drastisch. Ein Laptop bewertet das in Millisekunden, Optimierung ist rechnerisch unnötig. Im Repository steckt trotzdem eine Variante mit Alpha-Beta-Pruning, nicht-rekursiv formuliert – das war Neugier entlang der Elm-Vorlage, denn für Othello mit seinem 8×8-Brett ist Pruning keine Spielerei mehr, sondern Voraussetzung. Für den Artikel hier bleibe ich bewusst bei der rekursiven Grundform: Sie ist die Version, die man am Whiteboard herleiten kann, und [einfach schlägt elegant](https://www.mikebild.dev/de/blog/einfach-schlagen-elegant-statt-prozess/), solange die einfache Form messbar reicht.

## React rendert nur noch Zustand

Erst jetzt kommt React ins Spiel, und zwar mit einer betont langweiligen Rolle. Der gesamte Spielzustand ist `state.board`, und die einzige Stelle, an der sich dieser Zustand ändert, ist der Klick-Handler. Der Handler orchestriert zwei Züge – den des Menschen, dann den Antwortzug des Rechners – und delegiert alles Inhaltliche an die reinen Funktionen von oben.

```jsx
class Game extends React.Component {
  constructor(props) {
    super(props);
    this.state = { board: Array(9).fill(null) };
    this.handleClick = this.handleClick.bind(this);
  }

  handleClick(index) {
    const afterHuman = applyMove(this.state.board, index, HUMAN);
    const finished =
      winnerOf(afterHuman) || movesFor(afterHuman).length === 0;
    const nextBoard = finished
      ? afterHuman
      : applyMove(afterHuman, bestMove(afterHuman), COMPUTER);
    this.setState({ board: nextBoard });
  }

  render() {
    return <Board board={this.state.board} onSquareClick={this.handleClick} />;
  }
}

const Board = ({ board, onSquareClick }) => (
  <div className="board">
    {board.map((field, index) => (
      <button
        key={index}
        disabled={field !== null || winnerOf(board) !== null}
        onClick={() => onSquareClick(index)}
      >
        {field}
      </button>
    ))}
  </div>
);
```

`Board` ist eine zustandslose Funktionskomponente: Brett rein, neun Buttons raus. `Game` ist eine React-15-Klasse mit genau einem Zustandsfeld und genau einem Handler. Das Setup drumherum ist ein gewöhnliches create-react-app-Projekt – `npm install`, `npm start`, läuft auf Port 3000. Mehr Werkzeug braucht es 2017 für so etwas nicht mehr, und das ist eine angenehme Entwicklung.

Der Kontrast zum offiziellen React-Tutorial ist lehrreich. Dort ist Tic-Tac-Toe das Vehikel, um React zu erklären: Komponenten zerlegen, Zustand nach oben ziehen, Props nach unten reichen, am Ende eine Zeithistorie. Der Gegner ist ein zweiter Mensch, die Spiellogik beschränkt sich auf die Gewinnprüfung. Hier ist es genau andersherum: React ist das Vehikel, der Algorithmus das Zentrum. Beide Blickrichtungen sind berechtigt – aber nur die zweite zwingt einen, die Grenze zwischen Logik und Darstellung sauber zu ziehen, weil die Logik sonst sofort unhandlich wird.

```mermaid
flowchart LR
  subgraph core["Reine Funktionen – kein React-Import"]
    score --> minimax
    winnerOf --> minimax
    movesFor --> minimax
    applyMove --> minimax
    minimax --> bestMove
  end
  subgraph ui["React 15"]
    state["state.board"] --> render["render()"]
    render --> click["onClick(index)"]
  end
  click -->|"applyMove + bestMove"| core
  core -->|"neues Brett"| setState["setState"]
  setState --> state
```

Die Pfeile zwischen den beiden Kästen sind die ganze Kopplung: Der Handler ruft Funktionen auf und schreibt das Ergebnis zurück in den Zustand. Kein Import läuft in die Gegenrichtung. Man könnte den rechten Kasten durch eine Konsolenanwendung ersetzen, durch jQuery oder eben durch Elm – der linke Kasten würde es nicht bemerken.

## Tests ohne Browser

Diese Trennung ist keine Geschmacksfrage, sie ist messbar – am direktesten in den Tests. Die Spiellogik läuft in Node, ohne DOM, ohne jsdom, ohne gemocktes Event-System. Jest, das bei create-react-app gleich dabei ist, führt so etwas in Millisekunden aus:

```js
test('computer blocks an open line', () => {
  const board = [
    HUMAN,    HUMAN, null,
    COMPUTER, null,  null,
    null,     null,  null,
  ];
  expect(bestMove(board)).toBe(2);
});

test('computer prefers the immediate win over the block', () => {
  const board = [
    HUMAN,    HUMAN,    null,
    COMPUTER, COMPUTER, null,
    null,     null,     null,
  ];
  expect(bestMove(board)).toBe(5);
});
```

Das sind keine Unit-Tests im kleinteiligen Sinn, sondern Spielverstand als Spezifikation: Der Gegner muss eine offene Reihe blocken, und er muss den eigenen Sieg dem Block vorziehen. Solche Fälle lassen sich direkt aus Partien gewinnen – jedes Mal, wenn sich der Gegner beim Ausprobieren merkwürdig verhält, wird die Stellung zum Testfall. Bei mir war es anfangs genau so ein Fall: Ohne den Tiefenanteil in `score` schob die Suche einen sicheren Sieg vor sich her, weil ein Sieg in vier Zügen denselben Wert hatte wie einer in zwei. Die Stellung aus dem zweiten Test oben ist das Fossil dieses Fehlers.

Nun die Gegenprobe, und die habe ich in Reviews oft genug in freier Wildbahn gesehen: Die Zuglogik steckt im Klick-Handler, die Gewinnprüfung in `render`, der Rechnerzug in einem Lifecycle-Hook wie `componentDidUpdate`. Funktional identisch, aber jetzt gilt:

- Jeder Logik-Test braucht eine gemountete Komponente und simulierte Klicks – aus einem Funktionsaufruf wird ein Browser-Ritual.
- Die Stellung aus dem Fehlerfall lässt sich nicht direkt hinschreiben, sie muss durch eine Klickfolge erspielt werden.
- Ein Wechsel der UI-Bibliothek oder auch nur ein größeres Umbauen des Komponentenbaums reißt die Spiellogik mit um.
- Der Algorithmus ist nicht mehr am Stück lesbar, weil er über Handler, Render-Zweige und Lifecycle-Methoden verteilt ist.

Nichts davon ist bei drei mal drei Feldern dramatisch. Aber Tic-Tac-Toe ist hier ja nur das Versuchstier. Ersetzt man „Spiellogik" durch „Preisberechnung", „Validierung" oder „Planungsregeln", ist es dieselbe Entscheidung mit denselben Folgen – nur dass die verwobene Version dann nicht mehr an einem Nachmittag zu entflechten ist.

## Was ich daraus mitnehme

Minimax selbst wird kaum jemand im Projektalltag brauchen. Was bleibt, ist das Muster darunter. Der ganze Gegner ist eine Bewertungsfunktion plus eine Suche über unveränderlichen Werten – und weil das so ist, lässt er sich testen wie eine Preisformel und rendern mit was auch immer gerade da ist. React hat in diesem Projekt die Rolle, die ihm meiner Ansicht nach am besten steht: Zustand entgegennehmen, Oberfläche daraus machen, Eingaben zurückmelden. Nicht mehr.

Bemerkenswert finde ich, wie sehr die Teile zusammenpassen, ohne füreinander gebaut zu sein. Minimax verlangt unveränderliche Bretter, weil die Rekursion sonst Buchhaltung bräuchte. React belohnt unveränderliche Zustände, weil Vergleiche sonst teuer würden. Ein Algorithmus aus den Anfängen der Spieltheorie und eine UI-Bibliothek von 2013 treffen sich in derselben Disziplin: keine Mutation, Werte statt Änderungen. Das ist kein Zufall, sondern ein Hinweis darauf, dass diese Disziplin grundsätzlicher ist als jedes einzelne Werkzeug.

Wer das nachbauen will: ein Array mit neun Feldern, fünf reine Funktionen, eine Klasse mit einem Handler. Ein Nachmittag – und danach ein präzises Gespür dafür, wo in den eigenen, deutlich größeren Anwendungen die Linie zwischen Logik und Darstellung verlaufen sollte. Und ein Spiel, gegen das man nie wieder gewinnt.

## Weiterführende Quellen

- Repository `react-tic-tac-toe` („Tic Tac Toe in React with Minimax-AI"): https://github.com/MikeBild/react-tic-tac-toe
- Carsten Königs Othello in Elm, die Inspirationsquelle: https://github.com/CarstenKoenig/ElmOthello
- Das offizielle React-Tutorial (Tic-Tac-Toe, heutiger Stand): https://react.dev/learn/tutorial-tic-tac-toe
- Minimax im Überblick: https://en.wikipedia.org/wiki/Minimax
- Alpha-Beta-Pruning: https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning