Spielbaum

Def.:

Ein Spielbaum ist ein Baum mit zwei Typen von Knoten: Minimum-Knoten und Maximum-Knoten.
Die Knoten repräsentieren Spielstellungen.
Der Wert eines Blattes wird bestimmt durch eine statische Stellungsbewertung.
Der Wert eines Minimum-Knotens ist das Minimum der Werte seiner Söhne.
Der Wert eines Maximum-Knotens ist das Maximum der Werte seiner Söhne.

Obacht: Bei Höhe $h$ und Verzweigungsgrad $d$ gibt es $d^{h-1}$ Blätter.
Z.B. $8$ Halbzüge mit je 20 Alternativen $\Rightarrow 25.600.000.000$ Blätter.

Beispiel für einen Spielbaum

Implementation eines nicht-binären Baums

Jeder Knoten hat einen Verweis auf den ältesten Sohn und den nächstjüngeren Bruder.

Source: SpielBaum.java     JavaDoc: SpielBaum.html    

Bemerkung: Die in der Klasse Spielbaum erwähnte Klasse Stellung hat einen leeren Rumpf und muss für ein reales Beispiel noch ausgestaltet werden. Analog wurde die Methode statisch nur als Platzhalter formuliert; auch hier fehlt ein konkretes Verfahren für die statische Stellungsbewertung, welche natürlich nur im ausgeglichenen Fall den Wert 0 zurückgeben wird und ansonsten durch positive bzw. negative Werte den Stellungsvorteil für den MAX-Spieler bzw. den MIN-Spieler ausdrückt.