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

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


Log in to reply