Bitfelder + funktionale Programmierung = Tic-Tac-Toe

Inhaltsverzeichnis

Tic-Tac-Toe ist ein höchst langweiliges Spiel. Sofern keiner der beiden Spieler einen Fehler macht, endet das Spiel stets unentschieden. Interessanter ist die Frage, wie sich auf einem Spielfeld ermitteln lässt, ob einer der beiden Spieler eine Reihe gebildet hat. Bitfelder und ein Blick auf die funktionale Programmierung helfen.

Der fiktive Computer WOPR erkennt in dem äußerst sehenswerten Spielfilm "WarGames – Kriegsspiele" die Sinnlosigkeit eines weltweiten nuklearen Kriegs, indem er Tic-Tac-Toe gegen sich selbst spielt. Sofern keiner der beiden Spieler einen Fehler macht, endet das Spiel stets unentschieden.

Daraufhin bricht der Computer die Vorbereitungen für den tatsächlichen Abschuss von Atomraketen ab und schließt mit den Worten:

"Ein seltsames Spiel. Der einzig gewinnbringende Zug ist, nicht zu spielen."

So langweilig das wiederholte Spielen von Tic-Tac-Toe also sein mag, so interessant kann dessen Implementierung sein. Besonders spannend ist dabei das effiziente Überprüfen, ob einer der beiden Spieler gewonnen hat, ob es also drei gleichartige Werte in einer Reihe gibt (horizontal, vertikal oder diagonal).

Gibt es einen Gewinner?

Als Voraussetzung sei gegeben, dass das Spielfeld als Array von neun Zeichen angelegt ist. Beispielhaft wird im Folgenden mit JavaScript gearbeitet, die Erkenntnisse gelten aber unabhängig von der gewählten Programmiersprache:

const state = [
  'X', ' ', ' ',
  ' ', 'O', ' ',
  ' ', 'O', 'X'
];

Wie lässt sich nun ermitteln, ob es eine Reihe gibt? Der naive Ansatz sieht vor, den Inhalt der einzelnen Felder abzufragen und zu vergleichen. Dazu kann man eine Funktion schreiben, der man das Zeichen des zu prüfenden Spielers übergibt, und die anschließend den Vergleich durchführt:

const isPlayerWinner = function (player) {
  return (
    (state[0] === player && state[0] === state[1] && state[1] === state[2]) ||
    (state[3] === player && state[3] === state[4] && state[4] === state[5]) ||
    (state[6] === player && state[6] === state[7] && state[7] === state[8]) ||
    (state[0] === player && state[0] === state[3] && state[3] === state[6]) ||
    (state[1] === player && state[1] === state[4] && state[4] === state[7]) ||
    (state[2] === player && state[2] === state[5] && state[5] === state[8]) ||
    (state[0] === player && state[0] === state[4] && state[4] === state[8]) ||
    (state[2] === player && state[2] === state[4] && state[4] === state[6])
  );
};

Die Lösung funktioniert, ist aber nicht elegant. Das merkt man beispielsweise dann, wenn man auf dem gleichen Weg ein größeres Spielfeld überprüfen will. Die Arbeit artet rasch in eintöniges Kopieren und Anpassen von Zeilen aus.

Map/Reduce

In einem Kommentar auf meinen Blogeintrag "Zeitlose Programmiersprachen" wurde vor einigen Tagen die Frage gestellt, was man als C++- oder Java-Entwickler durch einen Blick über den Tellerrand lernen könne, beispielsweise von Lisp.

Lisp weist im Gegensatz zu C++ und Java viele funktionale Aspekte auf und kennt daher unter anderem die Funktionen mapcar und reduce, die ihn ähnlicher Form unter anderem auch in JavaScript zur Verfügung stehen. Die map-Funktion bildet ein Array auf ein anderes ab, die reduce-Funktion hingegen reduziert ein Array auf einen einzigen Wert.

Auf diesem Weg lassen sich beispielsweise sehr einfach alle in einem Array gespeicherten Zahlen quadrieren oder summieren:

console.log([ 2, 3, 5, 7, 11 ].map(n => n ** 2));
// => 4, 9, 25, 49, 121

console.log([ 2, 3, 5, 7, 11 ].reduce((sum, n) => sum + n, 0));
// => 28

Wer funktional programmiert, für den gehören die beiden Funktionen zum Alltag. Reinen C++- oder Java-Entwicklern sind sie deutlich seltener ein Begriff. Was hat das nun mit Tic Tac Toe zu tun?

Spielstände nummerieren

Kennt man die beiden Funktionen, kommt man gegebenenfalls auf die Idee, jedem Feld des Spielfels eine Zahl zuzuordnen und den aktuellen Spielstand durch map auf die zugehörigen Zahlen abzubilden. Summiert man diese anschließend mithilfe von reduce, ergibt sich eine Zahl, die den aktuellen Spielstand beschreibt. Damit jede Stellung eindeutig beschrieben ist, ordnet man den Feldern die Zweierpotenzen zu:

   1 |   2 |   4
-----|-----|-----
   8 |  16 |  32
-----|-----|-----
  64 | 128 | 256

Gegeben sei nun nochmals folgender Spielstand:

 X |   |
---|---|---
   | O |
---|---|---
   | O | X

Dann belegt X die Felder mit den Werten 1 und 256, O die Felder mit den Werten 16 und 128. Addiert man die jeweiligen Werte, ergibt sich für X der Spielstand 257, für O der Spielstand 144. Das alles lässt sich unter Verwendung von map und reduce mit drei Zeilen Code erledigen:

const score = state.
  map((field, index) => field === player ? 2 ** index : 0).
  reduce((sum, value) => sum + value);

Der gleiche Code würde ohne jegliche Anpassung auch für größere Spielfelder funktionieren.

Bitweise vergleichen

Nun stellt man fest, dass man auch die Gewinnsituationen derart beziffern kann. Belegt beispielsweise ein Spieler die drei Felder der ersten Reihe, entspricht das dem Wert 7. Bei der zweiten Reihe ergibt sich der Wert 56, bei der dritten 448. Von diesen Zahlen gibt es insgesamt acht:

const winningScores = [ 7, 56, 73, 84, 146, 273, 292, 448 ];

Da die Werte aus Zweierpotenzen gebildet werden, lässt sich eine beliebige Stellung auch als Binärzahl mit neun Bit abbilden. Will man nun wissen, ob eine gegebene Stellung beispielsweise den Wert 7 enthält, genügt es, die beiden Werte mit dem bitweisen UND-Operator zu kombinieren und das Ergebnis zu überprüfen.

So ergibt sich beispielsweise für die beiden oben genannten Spielstände 257 und 144, dass diese die 7 jeweils nicht enthalten:

(7 & 257) === 7
// => false

(7 & 144) === 144
// => false

Um das nun für alle Gewinnstellungen auf einmal zu überprüfen und herauszufinden, ob mindestens für eine davon der zuvor genannte Test den Wert true zurückgibt, lässt sich die some-Funktion verwenden:

return winningScores.some(
  winningScore => (winningScore & score) === winningScore);

Damit kann die gesamte isPlayerWinner-Funktion mit gerade einmal sechs Zeilen Code geschrieben werden und ist dabei auf beliebige Spielfeldgrößen und Stellungen ohne Probleme anpassbar:

const isPlayerWinner = function (player) {
  const winningScores = [ 7, 56, 73, 84, 146, 273, 292, 448 ];

  const score = state.
    map((field, index) => field === player ? 2 ** index : 0).
    reduce((sum, value) => sum + value);

  return winningScores.some(
    winningScore => (winningScore & score) === winningScore);
};

Fazit

Um auf die Lösung zu kommen, braucht man Erfahrung mit Bitfeldern, bitweisen Operatoren und den Funktionen map und reduce. Zugegebenermaßen ist der Ansatz daher gedanklich deutlich anspruchsvoller als das naive Aufzählen und Verknüpfen aller Kombinationen, dafür aber auch weitaus eleganter und flexibler.

Wer aber bereits bei einfachen Aufgabenstellungen den Aufwand scheut, solche Wege zu suchen, wird das in komplexeren Situationen erst recht nicht machen. Es lohnt sich daher in jedem Fall, über solche Ansätze nachzudenken.

tl;dr: Für viele Probleme gibt es zwei Lösungen. Die eine ist naheliegend, eintönig und schlecht skalier- und wartbar. Die andere erfordert Nachdenken, ist aber weitaus eleganter und flexibler. Es lohnt sich häufig, auf die Suche nach einem solchen Lösungsweg zu gehen. ()