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.

[Minz]

Also nachwievor, wenn du ein einigermaßen gut spielendes Programm schreiben willst bist du mit dem Ziel den Baum vorher aufzubauen auf einem denkbar schlechten Weg, eben aus zuvor genannten Gründen!

Das heißt du solltest den Baum Stück für Stück durchlaufen ohne ihn vorher komplett zu haben. Dabei bewertest du die Stellungen und merkst dir nur die Bewertungen.

Schaue dazu mal unter MiniMax Algorithmus im Internet nach.

Es handelt sich dabei um einen relativ einfachen rekursiven Algorithmus, der für Schach und Reversi(was ich nicht kenne) verwendet wird.

[Erring-Light]

Ich kenne den MiniMax Algo.

Mir is auch klar das ich nicht den kompletten Baum von anfang an erstellen kann. Es geht ja dadrum dem Computer "Taktik" beizubringen...also vorrausschauendes Spielen und je nach eingestelltem Schwierigkeitsgrad varrirt dann die Suchtiefe...also die Menge der Züge die der Computer vorraus berechnet...

@Minz:Reversi/Othello:

Spielfeld 8x8

Am Anfang liegen 4 Steine in der Mitte, 2 von jedem Spieler. Ein Stein kann nur dann gelegt werden wenn man mindestens einen Gegnerischen Stein mit zwei seiner eigenen (einer der schon liegt und einer der gesetzt wird) einschließt:
OoooO
o= Schwarz
O= Weiss
Das ganze geht natürlich auch Diagonal. Die eingeschlossenen Steine werden dann zu eigenen Steinen.
Jeder Spieler hat 32 Steine zur Verfügung, wer am Ende am meisten Steine auf dem Feld hat, hat gewonnen.

[Minz]

also liegt dein Problem eher in der Bewertung und nicht in der dynamisch Anzahl von Baumeinträgen?!?! Die dynamische Anzahl von Baumeinträgen wird nämlich unter Verwendung des MiniMax-Algos nämlich Nebensächlich.

Du übergibst dem Algo eine Stellung und guckst, welche weiteren sich aus dieser ergeben können. Diese Stellung werden allesamt bewertet. Die Anzahl ist dafür unerheblich.

Kluges Spielen ist da eine ganz andere Frage!!