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