Welche Datenstruktur für Spielbäume?

[elturco]

Hallo,

ich möchte ein Spielbaum programmieren, wie kann ich denn am besten ein Spielbaum im Computer darstellen ?

Grüße

 

[Wildcard]

Was ist denn ein Spielbaum? :bae:

 

[elturco]

Das ist ein "gewönlicher" Baum, wird bei der Programmierung von Spielen verwendet. Ist jedock kein Binärere Baum, die Verzweigungen können extrem groß sein.

 

[Wildcard]

Dann würde ich ein TreeModel nehmen.
Sind zwar eigentlich für JTrees gedacht, aber who cares...

 

[elturco]

Danke für den Tipp ich gucke mir das mal an ..

 

[elturco]

Vielleicht jetzt ne Dumme Frage aber, kann man den einen TreeBaum mit einem DFS Algorithmus durchlaufen ?

 

[Zunera]

Also erstmal zur Begriffsklärung von Spielbaum:

Def.:
Ein Spielbaum ist ein Baum mit zwei Typen von Knoten: Minimum-Knoten und Maximum-Knoten.
Die Knoten repräsentieren Spielstellungen.
Der Wert eines Blattes wird bestimmt durch eine statische Stellungsbewertung.
Der Wert eines Minimum-Knotens ist das Minimum der Werte seiner Söhne.
Der Wert eines Maximum-Knotens ist das Maximum der Werte seiner Söhne.

(hier gefunden)

Dieser "Spielbaum" ist theoretisch, d.h. man implementiert ihn nicht direkt sondern erstellt/durchläuft ihn am Besten mittels alpha/beta-Pruning - ein rekursives Verfahren (funktioniert per DFS) um die bestmögliche Lösung für ein Problem zu finden, wie zB den besten Spielzug ermitteln.

Hier näher ins Detail zu gehen würde den Rahmen und meine Zeit sprengen, aber es gibt ja Google! Einen sehr guten Einstieg findest du in diesem PDF-Dokument...

Als gutes Beispiel hier noch ein Link zu einem Spielbaum für TicTacToe (unvollständig).

Hinweis: Spielbäume haben nix mit TreeModel oder sonstigen "Tree"-Klassen zu tun - verschwende keine Zeit dich für dieses Problem da reinzulesen.

 

[padde479]

Das klingt doch sehr nach Spieletheorie, John Nash läßt grüßen. Da würde ich mir erst einmal die Grundlagen aneignen. Irgendwann kann man sich dann an die Implementierung machen. Hier würde mir das Stichwort LinkedList einfallen.

 

[Zunera]

@Padde:
Stimmt, Spielbäume sind natürlich ein Teil von Spieltheorie, aber John Nash muss man dabei nicht zu Rate ziehen. Und auch auf keinen Fall LinkedList!!
Nochmal ganz kurz: Ein Spielbaum ist eine Darstellung, wie bei einem Spiel (bevorzugt 1vs1) sich der Spielverlauf entwickeln kann. Genutzt bei Computerspielern. Bei der Programmierung erstellt man ihn nicht selbst - sondern durch eine rekursive Funktion, welche alle möglichen Spielzüge bis zu einer gewissen Tiefe durchgeht und die beste Lösung zurückliefert (so dass zB in 5 Spielzügen - was auch immer der Gegenspieler macht - der "Computerspieler" den besseren Stand hat).

 

[elturco]

Zunera danke Dir erstmal...

Also mir würd in erster Linie die Implementation mit Adjazenlisten einfallen, und darauf den DFS Algo anwenden um ihn zu duirchlaufen ?

Was meinst Du ?

 

[AlArenal]

Buch macht kluch: http://www.amazon.de/Algorithms-Java-Part-Graph-Algorithms/dp/0201361213

Tolles Ding zum Lesen, so für die Badewanne und so

 

[Zunera]

@elturco
AlArenal hat recht, du solltest dich erstmal etwas reinlesen... ich habe das Gefühl, du hast selbst das PDF-Dokument, welches ich verlinkt habe, noch nicht näher angeschaut, denn sonst würde die Frage nach Adjazenlisten gar nicht auftauchen. Ich weiß gar nicht, ob ich es noch deutlicher sagen kann:
Man braucht KEINEN speziellen Datentyp! Der "Spielbaum" ist die theoretische Darstellung von dem was passiert/passieren soll, wenn ein "Computerspieler" rekursiv per DFS bis zu einer bestimmten Tiefe alle möglichen Spielzüge im vorraus berechnet, um daraus den besten aktuellen Spielzug für sich zu finden.
Google doch selber mal nach Spielbäumen und vor allem nach Computerspielern (zB für TicTacToe), da findest du sicherlich Beispielprogramme, die dir weiterhelfen können.

 

[elturco]

ja das Buch werde ich mir anschaffen müssen, das Dokument was Du hier gepostet hast habe ich mir schon angeguckt, ich weiß halt nicht, wie ich einen Spielbaum im Computer repräsentieren kann ?
Mir ist Klar, es ist ein Baum, mit einem hohen Branching Faktor( TICTACTOE).

Lass mich noch eine kurze Frage stellen, kann ich das denn mit einem gewöhnlichen Baum im Computer repräsentieren,
(kein binärer) um danach es mit DFS zu durchlaufen ?

Grüße

 

[LoN_Nemesis]

Bei TicTacToe kannst du vielleicht wirklich den kompletten Baum erstellen und im Speicher halten, bei anderen Spielen wie Schach dürfte das eher schwierig werden. Aber wie schon mehrfach gesagt ist Spielbaum nicht wirklich ein komplett existierender Baum, sondern eher eine Art systematische Vorschrift alle möglichen Züge zu erzeugen.