Dynamische Bäume???

[Erring-Light]

Hey@all!

Ich bin gerade daran mit einem Freund ein Spiel zu proggen (Reversi/Othello).

Für die KI hab ich eine Wertetabelle für die einzelnen Felder (8x8) angelegt. Die KI soll jetzt die nächsten 2-5 (je nach Aufwand und Schwierigkeitsgerad) Züge vorraus berechnen. Alle notwendigen Dtaen werden in einem Datentyp Spielstand gespeichert.

Mein Problem ist jetzt:
Nach jedem Zug kann ein Spieler unterschiedlich viele neue Züge machen...wie kann ich das in einem Baum berücksichtigen? In einem Binärbaum gibt es ja immer nur einen Verweis nach rechts und einen nach links...wie siehts jetzt aber mit einer dynamischen Anzahl aus die je nach Ebene variiert...wie kann ich z.B. ein Funktion AddVerweis realisieren die immer wenn ich noch einen zusätzlichen Verweis brauche diesen auch einfügt.

Oder fällt jemdand eine bessere Lösung ein wie ich die Vorrausberechnungen speichern und auswerten könnte?

Wer noch mehr Informationen braucht => einfach Fragen.

Schon mal vielen Dank fürs lesen!

[Minz]

das ist gar nicht so einfach zu beantworten ohne zu wissen, wie du überhaupt vorgehst!

Wieviele Züge sind ungefähr im Schnitt möglich? Wenn nicht beantwortbar wieviele Züge sind maximal möglich? In Folge der Beantwortung: Willst du wirklich den kompletten Baum vorher aufbauen, bevor du ihn durchsuchst (Speicher!)? Bedenke wenn pro Zug angenommen 10 Züge möglich sind und du willst in die Tiefe 5 gehen, würde das bei zwei Spielern bedeuten, dass du gerade mal 2,5 Züge beider Spieler in voraus berechnest! und selbst das kostet dich 10*10*10*10*10=100.000 Verzweigungen !!

[Jens Schumann]

Hallo,
Du kannst einen Baum mit TList-Nachfahren aufbauen.
So mach ich es immer. Jeder Konten ist dann ein TList-Nachfahre.
Dann kann jeder Konten mehrere Unterknoten haben.

[Minz]

erm Jens, hast du meinen Beitrag gelesen? :D

[Jens Schumann]

Zitat:

Zitat von Minz

erm Jens, hast du meinen Beitrag gelesen? :D

Nein

[Minz]

Dann wäre dir aber klar geworden, weshalb ein solcher Lösungsweg unbrauchbar ist!

[Skiron]

wenne dynamische bäume willst, brauchste nur die Items einer TreeView Nehmen

[Minz]

s.o.

[atreju2oo0]

Warum wollt Ihr Komponenten dafür benutzen???
Ich würde einfach mit Zeigern arbeiten und daraus den Baum aufbauen...

Im übrigen hat Minz natürlich recht, dass dein Backtracking-Verfahren ziemlich Speicherintensiv
ist!
Ohne Bewertung der Spielzüge kommt man da nicht weit!

[Erring-Light]

Schomma danke für die Antworten!

Ich kann leider kein Max für die MoeglichenZuege angeben...weil ich es selbst nicht kenne, das ist ja mein Problem.

Bei dem Spiel Reversi passiert am Anfang kaum was. Um so mehr Steine gesetzt werden (32 je Spieler) um so mehr möglichkieten hat man neue Steine zu setzten...das geht dann so bis ins letzte Drittel...da sind nicht mehr so viele freie Felder, dementsprechend auch nicht mehr so viele Möglichkeiten zu setzten.

Die Berwertung der einzelnen Züge erfolgt dann per Wertetabelle. Um den Speicher/Baum zu reduzieren hab ich auch schon verschiedene Methoden gefunden (alpha-beta-prunning...etc), also daran solls nich liegen...und selbst wenn...das Proggy soll erst ma laufen, da is der Speicher egal *hehe*

Mein Hauptproblem war einfach nur wie ich den Baum realisieren kann. Mit Zeigern wär ja das naheliegenste, aber dafür muss man sich ja noch einen extra Typ definieren => da lieght das Problem. Bei einem Binärbaum is klar das jeder Knoten nur 2 Nachfolger hat, also kann man das ja so direkt im Typ definieren...was wäre aber wenn der Binärbaum kein Binärbaum is und auch ma 3 oder mehr Nachfolger hat?
Gibt es ne z.B. ne Möglichkeit die Funktion AddNachfolger (Beispiel) zu schreiben, die den Zeigertyp so ändert das ich für den jeweiligen Knoten die exakte Anzahl an Nachfolgeknoten habe...
=>
Rechter Nachfolger
/
Knoten ...
\ /
Linker Nachfolger- ...
\
...

Hoffe jetzt ist alles ein bisschen klarer geworden...evt ist mein Thematitel nicht so passend.