Binären Baum erzeugen für KI(unsortiert)
-
Hi,
ich will einen binären Baum für meine Mühle KI erzeugen.Es wird prinzipiell von einem Ausgangspielfeld, für eine gewisse Tiefe jeder mögliche Zug berechnet, diese neuen Felder sollen in dem Baum gespeichert werden.
Rekursiv wäre das ja nicht so schwer nur dürfte das relativ schnell einen Stack Overflow produzieren, da es schon ab 2-3 Züge massig Varianten gibt.
Daher suche ich eine Lineare Lösung.Das ist die Knotenstruktur:
struct node{ struct field field; //Das neue Spielfeld speichern int value; //Den Wert des Zuges speichern int depth; //Die Zugtiefe speichern struct tree *partner; // Anderer Zug vom gleichen "Vater" struct tree *down; //Nachfolgender Zug };
Die Baumstruktur habe ich mir so vorgestellt:
root 61-62-63
| |
1-2-3-4-5-6
| |
| 21-22-23
|
11-12-13Nur irgendwie fällt mir kein linearer Algorithmus ein der wirklich den ganzen Baum berechnet.
Wäre dankabr wenn mir da jemand einen Tipp geben könnte
Gruß HiFish
-
Nur irgendwie fällt mir kein linearer Algorithmus ein der wirklich den ganzen Baum berechnet.
Es gibt keinen linearen Algorithmus, da die Anzahl der Elemente eines Baumes sehr schnell (exponentiell) mit der Höhe des Baumes anwächst. Generell gilt: #Stellungen = 2^(#Züge)
Schaue doch mal im Netz nach Tiefensuche, Breitensuche, A* Suche, Best-First Suche, Suche mit einem k-stufiges Lookahead, ...
-
HiFish2 schrieb:
Hi,
ich will einen binären Baum für meine Mühle KI erzeugen.Warum binär? Es gibt doch normalerweise mehr als zwei mögliche Züge.
Rekursiv wäre das ja nicht so schwer nur dürfte das relativ schnell einen Stack Overflow produzieren, da es schon ab 2-3 Züge massig Varianten gibt.
Die Zahl der Züge eines Spiels dürfte doch irgendwo in der Größenordnung von 100 liegen, das hält jeder Stack aus. Mir scheint, der Baum wird eher breit als tief. Die Zahl der Knoten ist das Problem, nicht die Rekursionstiefe.
Das ist die Knotenstruktur:
struct node{ struct field field; //Das neue Spielfeld speichern int value; //Den Wert des Zuges speichern int depth; //Die Zugtiefe speichern struct tree *partner; // Anderer Zug vom gleichen "Vater" struct tree *down; //Nachfolgender Zug };
Ach du willst einen allgemeinen Baum als binären Baum darstellen. OK, das ändert aber prinzipiell nichts, die Tiefe ändert sich um einen konstanten Faktor.