Algorithmus für Spielbaum

[sigma547]

Hi,

ich haber folgendes Anfängerproblem:

Gegeben ist ein Beispiel-Spielbaum

Die Werte an den Endknoten sind gegeben.
Berechnet werden soll die expected value (EV) der Knoten für die jeweilige Route, die gewählt wird.
Der erste Knoten hat bspw. für die Route oben eine EV von -0,61 und unten eine EV von +1,65.
Diese habe ich im Beispiel mit eingetragen.

Momentan bin ich soweit, dass ich jeweils eine Klasse "Knoten" und "Endknoten" erstellt habe.
Endknoten hat die Variable "payoff".
Knoten hat die Variable "routeOben" und "routeUnten", sowie "evOben" und "evUnten", was ja berechnet werden soll.

Wie kann ich das effizient programmieren?
Das ist nur ein Beispiel. Das Programm soll später Spielbäume mit zig Ästen berechnen können.

Any Ideas? 🙂

 

[Marco13]

Bei Bäumen bietet sich oft was rekursives an. Wenn die Bäume sehr tief werden, oder das sehr zeitkritisch ist, kann man sich ggf. was iteratives überlegen, und prüfen, OB das effizienter oder besser ist. Aber sonst, GANZ grob...

private float ev = 0;

float computeEV()
{
    if (isLeaf) { return knownEV; } /* EV schon bekannt */
    else {
        float ev0 = child0.computeEv();        
        float ev1 = child1.computeEv();
        ev = combine(ev0, ev1);
    }
    return ev;
}

 

[sigma547]

Danke! Versuche das mal zu implementieren 😉

 

[sigma547]

Danke nochmals an Marco. Das war sehr hilfreich.

Ich habe noch eine zweite Frage:

Für jeden Knoten muss eine "contribution" berechnet werden. Diese ist das Produkt aller Aktionswahrscheinlichkeiten des Gegners, die zu diesem Knoten geführt haben.

Im Beispiel habe ich ein Knoten markiert. Es handelt sich um einen roten Knoten.
Von der Wurzel bis zu diesem Knoten hat der Gegner (blauer Knoten) einmal mit einer Wahrscheinlichkeit von 0.7 und einmal mit 0.1 dazu beigetragen, dass dieser Knoten quasi erreicht wurde.

Erschwerend kommt vielleicht noch hinzu, dass sich rote und blaue Knoten immer abwechseln. Es kann auch vorkommen, dass zwei Knoten gleichen Geschlechts aufeinander folgen (ist im Beispiel nicht gegeben).

Wie kann ich das für einen gegebenen Knoten berechnen?
Danke!!

 

[Marco13]

Ggf. solltest du genauer den Zusammenhang beschreiben.

Auf basis des bisherigen KÖNNTE man grundsätzlich sowas machen wie

void computeThisValue(Color c)
{
    float value = 1.0;
    Node current = this;
    while (current.parent != null) {
        if (current.parent.color == c) value *= factor(current, current.parent);
        current = current.parent;
    }
    return value;
}

was davon ausgeht, dass jeder Knoten sein "parent" kennt, und diese Methode "factor" den Wert zurückgibt, der an der Kante steht, die von 'current.parent' zu 'current' führt.

AAAABER: Das setzt voraus, dass man das 'parent' kennt, und diese 'factor'-Methode ist krampfig. Außerdem könnte es sein, dass man das deutlich geschickter und effizienter programmieren könnte, wenn man das von der Wurzel ausgehend für alle Knoten berechnen würde. Du solltest ggf. genauer beschreiben, wie deine bisherigen Klassen aussehen, und insbesondere, welche Anforderungen es schon gibt und noch geben wird. Das schleißt auch die Frage ein, welche Methode wann wie oft von wem aufgerufen wird. Vielleicht wäre es praktisch, eine Klasse "Edge" zu machen, die jeweils zwei Knoten verbindet, und die z.B. auch den EV speichert. Vielleicht wäre es auch gut, die EVs (und diesen neuen zu berechnenden Aktionswahrscheinlichkeitswert) direkt zu berechnen, wenn man den Baum aufbaut (und direkt in den Knoten zu speichern). Die neuen Werte sind ja nur eine Aufmultiplizierung von einigen, die man schon hat.

 

[sigma547]

DAANKE!