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 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