Welche Datenstruktur für Spielbäume?

Status
Nicht offen für weitere Antworten.

elturco

Mitglied
Hallo,

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

Grüße
 

elturco

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

Zunera

Aktives Mitglied
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

Bekanntes Mitglied
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

Aktives Mitglied
@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

Mitglied
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 ?
 

Zunera

Aktives Mitglied
@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

Mitglied
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

Bekanntes Mitglied
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.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Welche Datenstruktur für welche Problemstellung? Java Basics - Anfänger-Themen 10
S Welche Datenstruktur für Tabelle/DB? Java Basics - Anfänger-Themen 5
F Welche Datenstruktur für Matrix mit Vektoren? Java Basics - Anfänger-Themen 2
K Welche Datenstruktur für eine Bibliotheksanwendung? Java Basics - Anfänger-Themen 5
FelixN Teilsummenproblem / welche Datenstruktur Java Basics - Anfänger-Themen 2
M Implementieren einer Datenstruktur, welche nur 5 Objekte speichert Java Basics - Anfänger-Themen 3
S Welche Datenstruktur ist die optimalste um Funktionen fuer bestimmte Wertebereiche abzurufen..? Java Basics - Anfänger-Themen 5
StupidAttack Gson, welche Datenstruktur? Java Basics - Anfänger-Themen 4
B Finden gemeinsamer Kanten: welche Datenstruktur ? Java Basics - Anfänger-Themen 9
G Welche Datenstruktur ( Sets / Maps)? Java Basics - Anfänger-Themen 10
U Welche Datenstruktur soll ich nehmen? Java Basics - Anfänger-Themen 11
G Welche Datenstruktur ist hier die sinnvolste Java Basics - Anfänger-Themen 6
E welche Datenstruktur (Collection) Java Basics - Anfänger-Themen 4
6 Welche Datenstruktur? Java Basics - Anfänger-Themen 3
P Welche Datenstruktur um schnell zu suchen? Java Basics - Anfänger-Themen 25
C Java Array Struktur, welche ist wann besser? Java Basics - Anfänger-Themen 12
N Welche Objekte kann man zu einem Set hinzufügen Java Basics - Anfänger-Themen 4
berserkerdq2 Habe eine Klasse, welche public ist, diese hat eine public Methode, die nicht static ist. Wenn ich nun versuche aufzurufen Probleme? Java Basics - Anfänger-Themen 8
berserkerdq2 Habe zwei exceptions, welche ist ein Kommunikationsfehler und welche ein Ausgabefehler? Java Basics - Anfänger-Themen 4
G Welche Attribute kommen in den Konstruktor? Java Basics - Anfänger-Themen 5
Jambolo Methode, welche die 3 letzten Parameter Werte speichert Java Basics - Anfänger-Themen 20
Q SMS basierte Applikationen, welche Programmiersprache? Java Basics - Anfänger-Themen 8
Igig1 Welche Werte sind als default Werte in einem Array, der als Datentyp eine Klasse hat? Java Basics - Anfänger-Themen 1
D Welche GUI Library für eine Client Server Chat App Java Basics - Anfänger-Themen 14
H Welche Werte bei Objekterzeugung eingeben? Java Basics - Anfänger-Themen 2
Arita welche Fehler gibt es noch? wie kann ich es noch vervollständigen Java Basics - Anfänger-Themen 15
tony241188 Implementieren Sie die Klasse Hersteller, welche die folgenden Elektrogeräte produziert Java Basics - Anfänger-Themen 3
P Welche Zeile in Tadople gibt einen compiler error? Java Basics - Anfänger-Themen 5
W Welche Komponente ist geeignet? Java Basics - Anfänger-Themen 1
A Welche Operation ist das? Java Basics - Anfänger-Themen 2
J Welche Java-Version installieren Java Basics - Anfänger-Themen 9
M Ausgabe einer Liste welche mehrere Stacks enthält Java Basics - Anfänger-Themen 3
K GUI Entwicklung - Welche Richtung passt für euch zum mobilen Zeitalter? Java Basics - Anfänger-Themen 4
T Datenbank | Welche am Sinnvollsten? Java Basics - Anfänger-Themen 5
S Welche Verteilung? Java Basics - Anfänger-Themen 1
L Welche Methode? Java Basics - Anfänger-Themen 7
O Methoden welche ich implementier Java Basics - Anfänger-Themen 11
A Wie erkennt die JVM welche class verwendet werden muss? Java Basics - Anfänger-Themen 3
M JDK installieren Welche Software bei XP? Java Basics - Anfänger-Themen 5
H Welche IDE zum Buch "Programmieren mit Java" von Reinhard Schiedermeier des Verlags Pearson Studium Java Basics - Anfänger-Themen 19
U Best Practice Fehleranalyse, welche Fehler macht Ihr beim Lernen bzw. auch später Java Basics - Anfänger-Themen 12
E jProgressbar, 6 Versuche, welche value angeben ? Java Basics - Anfänger-Themen 3
M Welche Entwicklungsumgebung? Java Basics - Anfänger-Themen 32
I Welche Schleife/Bedingung nehme ich her Java Basics - Anfänger-Themen 5
C Methoden Welche JSoup Methoden Und Parameter für diese HTML Tags Java Basics - Anfänger-Themen 4
K Erste Schritte Java lernen - Welche Bücher? Java Basics - Anfänger-Themen 1
P welche Komponente ist im Layout? Java Basics - Anfänger-Themen 2
TheMenox Methoden Bestimmung an welche Methode eine andere Methode ihren Wert weitergeben soll Java Basics - Anfänger-Themen 35
K Methoden mit den Namen accept. Welche Funktion haben diese? Java Basics - Anfänger-Themen 2
G Lambda Ausdruck: Welche Methode ist die Richtige? Java Basics - Anfänger-Themen 1
J Welche Methoden laufen im neuen thread ?? Java Basics - Anfänger-Themen 9
G Welche Java-Version auf meinem Rechner? Java Basics - Anfänger-Themen 2
Z Methoden Zugriff mit Klasse 3 auf Methode von Klasse 2 welche in Klasse 1 erzeugt wird Java Basics - Anfänger-Themen 6
A Klassen welche Klassen importiert Eclipse automatisch Java Basics - Anfänger-Themen 2
V welche Methode am besten sich für JPG einfügung in Java anzugewöhnen ? Java Basics - Anfänger-Themen 4
M Welche externen Bibliotheken sind in Java sehr zu empfehlen? Java Basics - Anfänger-Themen 4
I Grafische Benutzeroberflächen - welche Komponente nehme ich am besten? Java Basics - Anfänger-Themen 13
G Welche JAVA IDE? Java Basics - Anfänger-Themen 3
S Klassen Zugriff auf Attribute einer zweiten Klasse, welche durch dritte gesettet wurden? Java Basics - Anfänger-Themen 2
E wann welche Konstanten verwenden? Java Basics - Anfänger-Themen 7
K Welche Java Version ist die richtige Java Basics - Anfänger-Themen 3
V Welche Exceptions müssen importiert werden? Java Basics - Anfänger-Themen 3
A Design Pattern - Welche? Java Basics - Anfänger-Themen 33
C Datenbank - Welche Java Basics - Anfänger-Themen 5
S Welche Art von Liste? Java Basics - Anfänger-Themen 3
S Eigene Exception Schreiben und Welche Auslösen wie ? Java Basics - Anfänger-Themen 7
A Wenn genau welche Liste verwenden? Java Basics - Anfänger-Themen 6
T Welche Schleife? Java Basics - Anfänger-Themen 6
P Java Stream, wann welche Stream verwenden? Java Basics - Anfänger-Themen 3
S Collections Welche Collection ist am geeignetsten? Java Basics - Anfänger-Themen 3
S Input/Output Welche Möglichkeiten Eingabe von User abfragen Java Basics - Anfänger-Themen 5
P Swing - Welche Klasse für ausgeben von Ergebnissen? Java Basics - Anfänger-Themen 3
R Welche Datenstruktor für diese Liste? Java Basics - Anfänger-Themen 6
B Erste Schritte Welche Kenntnisse brauche ich für diese Programmidee? Java Basics - Anfänger-Themen 4
P Vererbung herausfinden welche Klasse was erbt Java Basics - Anfänger-Themen 3
K welche art von Liste für TableModell Java Basics - Anfänger-Themen 2
D Welche API für komplexe XML-Struktur? Java Basics - Anfänger-Themen 25
S welche Programmstruktur? Java Basics - Anfänger-Themen 8
M Welche Datenbank? Java Basics - Anfänger-Themen 5
B Welche Themengebiete benötige ich? Java Basics - Anfänger-Themen 7
S Welche Collection kann sich selber sortieren? Java Basics - Anfänger-Themen 8
H Welche Art der Ein/Ausgabe Java Basics - Anfänger-Themen 2
U Welche(s) Framework(s) wären geeignet? Java Basics - Anfänger-Themen 8
StrikeTom Welche Dateitypen unterstützt JMF (Java Media Framework)? Java Basics - Anfänger-Themen 6
S Welche Collection? Java Basics - Anfänger-Themen 5
A Welche UML Software benutzt ihr / ist empfehlenswert? Java Basics - Anfänger-Themen 2
N Welche Datenstukturen und Methoden Java Basics - Anfänger-Themen 3
L Auswahl auf welche Art gespeichert werden soll Java Basics - Anfänger-Themen 6
B Welche Java-Installation ist aktiv? Java Basics - Anfänger-Themen 2
S Welche möglichkeiten gibt es eine Zahl zu spiegeln? Java Basics - Anfänger-Themen 17
U Welche Seite für Anfänger Java Basics - Anfänger-Themen 11
K Welche Entwicklungsumgebung für Einsteiger? Java Basics - Anfänger-Themen 16
S Webapplikation welche alternative zu gwt? Java Basics - Anfänger-Themen 2
cowabunga1984 Unit-Testing - Welche Testfälle sind relevant? Java Basics - Anfänger-Themen 4
S Welche Methode in JFrame überschreiben? Java Basics - Anfänger-Themen 12
H Designfrage: Welche Liste? Java Basics - Anfänger-Themen 3
Z Welche IO-Klasse verwenden? Java Basics - Anfänger-Themen 2
M Der Java Schlüsselwort null; ?Welche Anweisung und Sinn? Java Basics - Anfänger-Themen 12
G Herausfinden, welche Componente als LETZTES focus hatte Java Basics - Anfänger-Themen 2
H Welche PDF Biblothek? Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben