Startseite Spiele Ada Lovelace Lightblue Schule

Spielbäume: TicTacTree

Das Spielfeld ist eine Anordnung aus Feldern, die ein -, ein X oder ein O enthalten. Für die Repräsentation bietet sich ein Array an. Das leere Feld sieht dann so aus:

['-', '-', '-', '-', '-', '-', '-', '-', '-']

Nach dem Startzug von X (fängt immer an!):

['X', '-', '-', '-', '-', '-', '-', '-', '-']

Alle Spielstellungen sind in einem Baum darstellbar. Die Knoten enthalten eine Stellung und ein Array nachfolger mit den direkten Folgestellungen. Vorgegeben ist die dazu passende Klasse Stellung. Sie enthält außerdem

• fertige Methoden nextToMove(), isWinningPosition() und isDraw() sowie
• leere Methoden expand(), expandAll() und count().

Aufgaben

1. Implementieren Sie die Methode expand() in der Klasse Stellung. Sie ermittelt das Array direkter Nachfolger einer Stellung (→ iterativ). Gewinnstellungen und volle Felder haben natürlich keine Nachfolger.

   Bei korrekter Implementierung sollte man mit dem Button aktuelle Position expandieren neue Stellungen erzeugen und dann den Baum weiter nach "unten" laufen können.

2. Implementieren Sie die Methode expandAll() in der Klasse Stellung. Sie ermittelt alle Nachfolger einer Stellung (→ rekursiv).

   Bei korrekter Implementierung sollte der Button vollständig expandieren alle Stellungen erzeugen und die manuelle Expansion der Knoten unnötig sein. Das kann ein wenig dauern, und Konsolenausgaben verlängern die Sache noch. Andererseits weiß man ohne oft nicht, ob und was passiert...

3. Der Baum aller Stellungen hat 9!=362880 Knoten. Im Spielbaum sind aber einige mehrfach enthalten, weil verschiedene Zugfolgen zu ihnen führen. Andere fehlen, weil zuvor eine Gewinnstellung erreicht wurde. Implementieren Sie count() so, dass die Anzahl der Knoten im Baum ermittelt wird.

Bonus
Bisher ging es mit dem vorhandenen UI. Ergänzen Sie in Stellung ein Attribut vorgaenger, das dem Konstruktor übergeben wird. So kann man den Baum auch rückwärts ablaufen. Wenn man einen Button dafür hat...

Hinweise

• Das Expandieren erfordert, Kopien des Feldarrays zu erstellen. Ohne ins Detail zu gehen: Eine "shallow copy" reicht aus. Kontext zum Nachlesen: pass by value/pass by reference.
• Zum Debugging empfiehlt sich wie immer in JS die Entwicklerkonsole (F12, dann Console). Nachrichten kann man dort mit console.log() schreiben.