Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » Container für Baumstruktur
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
06.05.2016, 11:02 Uhr
Noby



 Ich versuche gerade eine Baumstruktur für ein Schachprogramm zu entwerfen, die Anzahl der Zweige pro Knoten sollen sich aus der jeweils möglichen Anzahl der zulässigen Züge ergeben, Breite und Länge der Struktur somit sehr variabel. Dabei will ich den Baum von oben nach unten als auch von unten nach oben durchforsten können (die Endpunkte des Baums will ich dafür in einer Liste abspeichern, also sobald das definierte Ende erreicht ist, z.B. Zugzahl oder Zeit, wird der Endknoten in die Liste gespeichert, damit ich rasch von unten noch oben durchrechnen kann).

Bislang habe ich mit rohen Zeigern gebastelt, aber es wurde empfohlen, Container zu verwenden.

Welches Container-Template wäre hierfür zu empfehlen? multimap oder set?

Oder soll ich doch lieber rohe Zeiger verwenden, weil die vorhandenen Templates/Container nicht wirklich den Support für Baumstrukturen leisten?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
06.05.2016, 17:20 Uhr
Hans
Library Walker
(Operator)


Hi,

soweit wie ich Deinen Beitrag verstehe, würde ich Dir erst einmal empfehlen, Dich mit Baumstrukturen zu beschäftigen, das wäre also erst einmal mit rohen Zeigern, um ein Gefühl für die Arbeit damit zu bekommen.

Hans
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
07.05.2016, 13:30 Uhr
ao

(Operator)


Nach meiner Erfahrung sind Container rohen Zeigerverwaltungen praktisch immer überlegen

Welches Container-Template sinnvoll ist, das richtet sich nach den Operationen, die auf dem Container überwiegend ausgeführt werden.

std::vector zum Beispiel ist gut, wenn freier indizierter Zugriff auf die Elemente wichtig ist, und weniger gut beim Anfügen, Einfügen und Herauslöschen von Elementen (dabei wird der Feldinhalt umkopiert)

std::list hat seine Stärken genau dabei (Anfügen, Einfügen, Löschen) und beim Traversieren vom Anfang zum Ende (oder zurück), aber weniger beim indizierten Zugriff (der wird nachgebildet über Traversieren und Mitzählen).

Man muss also abschätzen, welche Operationen häufig gemacht werden, und einen Container wählen, der diese Operationen gut kann, d.h. schnell und mit wenig Overhead.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
17.05.2016, 17:17 Uhr
derfuchs



 Meinst du nicht, dass das schon entworfen wurde und du das einfach für dich nutzen kannst?

Also ich versteh nicht direkt was du vor hast, aber du willst doch ein Baumdiagramm nach dem Minimax-Algorithmus erstellen, wenn ich das richtig verstehe? Also eine Baumstruktur erstellen, wie es hier bei Wikipedia beschrieben ist?

Grüße vom Fuchs
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
17.05.2016, 18:55 Uhr
~Noby
Gast


@derfuchs: Korrekt, ein Baum nach Minimax-Logik.

Allerdings für ein Schachprogramm, demnach mit sehr vielen Verzweigungen und ggf. sehr tief. Die Rekursion mit Baumstruktur habe ich bereits (stürzt nur gerade noch ab).

Das ganze sollte jedoch schnell und sicher sein, deswegen die Frage nach Containern.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
18.05.2016, 09:45 Uhr
derfuchs



 Uiui, da hast du dir ja was vorgenommen. Da bin ich dann wohl leider raus, ich drück dir aber die Daumen, dass am Ende alles so klappt, wie du dir das vorstellst!
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
18.05.2016, 13:14 Uhr
ao

(Operator)



Zitat von ~Noby:
mit sehr vielen Verzweigungen und ggf. sehr tief. Die Rekursion mit Baumstruktur habe ich bereits (stürzt nur gerade noch ab).

Bei Rekursion mit sehr großer Tiefe kann es passieren, dass dir der Speicher ausgeht (Stack overflow), besonders dann, wenn jeder rekursive Aufruf noch eine nennenswerte Menge lokaler Daten anlegt. Das kann die Ursache für den Absturz sein.

Es kann aber auch sein, dass du einem Pointer folgst, der ins Klo zeigt, zum Beispiel weil er nicht initialisiert wurde, oder weil er auf ein Objekt gebogen wurde, das nicht seinem Typ entspricht (falscher reinterpret_cast), oder weil das Objekt, auf das er mal gezeigt hat, inzwischen schon wieder weg ist. Beliebte Ursachen hierzu sind early deletions (ein mit new geholtes Objekt wurde mit delete zerlegt, aber es gibt noch weitere Zeiger, die darauf verweisen) und lokale Objekte innerhalb einer Funktion, deren Adresse nach draußen gereicht und irgendwo gespeichert wurde.

Sowas zu debuggen kann sehr mühsam sein. Es kann helfen, das Allozieren und das Verwenden der Speicherbereiche zu loggen und die entstandenen Logfiles zu vergleichen. Erschwerend kommt bei dieser Klasse von Fehlern hinzu, dass Code-Modifikationen dafür sorgen können, dass sich das Fehlerbild verändert (sogenannte "Heisenbugs"). Du bist nicht zu beneiden. Nimm es als Lektion in Phantasie und Ausdauer.


Zitat:
Das ganze sollte jedoch schnell und sicher sein, deswegen die Frage nach Containern.

Dass rohe Zeiger tendenziell unsicher sind und ein Container bevorzugt werden sollte, steht meiner Meinung nach außer Zweifel. Zu der Frage, welcher Container: Siehe oben.
Dieser Post wurde am 18.05.2016 um 13:27 Uhr von ao editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
18.05.2016, 15:13 Uhr
Noby



 @derfuchs: Danke, ich bemühe mich!

@ao: Meine Pointer ins Nichts debugge ich schon die ganze Zeit. Lerneffekt vorhanden, durch Zusatzcode suche ich die Stelle, wo sich der Code ins Nirvana verabschiedet oder der Code undefiniert wird. Klappt zwar als Fehlersuche (man kommt voran), aber mühsam, deswegen Frage als Container.

Die undefinierte Anzahl von möglichen Zügen in einer Stellte habe ich als verkette Liste abgebildet. Zum Beispiel sind beim Schach in der Ausgangsstellung für Weiß 20 Züge möglich, dann für Schwarz wieder 20, und dann wird es aber variabel. Mit Arrays[z.B. 100]/vector will ich hier deswegen nicht arbeiten. Für diese Liste könnte ich aber std::list nehmen. Aus jedem möglichen Zug ergibt sich wieder eine Stellung mit undefinierter Anzahl möglicher Züge, so dass sich ein Baum ergibt. Demnach müssten die Liste mit Elementen so sein, dass sie als Knoten weitere std::list haben können, also z.B. ein object mit einer std::list für die möglichen Züge in der Stelle, einem Iterator für den Knoten darüber (= Zug, der zur Stellung geführt hat), einem spezifischen object für den Zug, z.B. Sg1-f3. Scheint mir im Moment konzeptionell gut (zumindest bis es wieder abstürzt). Irgendetwas wird mir einfallen.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
18.05.2016, 16:26 Uhr
ao

(Operator)


Du könntest mal so einen Ansatz hier versuchen - keine Ahnung, wie weit du damit kommst:

C++:

#include <list>
#include <string>

class Move
{
    std::string move;                //    z.B. "Sg1-f3"
    std::list<Move> nextMoves;        //    alle möglichen folgenden Züge
    int rating;                        //    Bewertung des Zugs
    
public:

    Move (const std::string & move_) : move (move_), rating (0) {}
    
    int Rate ();                    //    Diesen Zug bewerten. Braucht evtl. die Ratings der Folgezüge.
};

int Move::Rate ()
{
    rating = 0;
    for (std::list<Move>::iterator it = nextMoves.begin (); it != nextMoves.end (); it++)
    {
        rating += it->Rate ();    //  Dies iteriert quasi-rekursiv über alle Listen im Baum.
                        // quasi-rekursiv deshalb, weil Rate zwar sich selber aufruft,
                        // aber nicht auf demselben Objekt, sondern im Kontext eines anderen Objekts.
                        // Trotzdem muss man hier den Stackverbrauch im Blick halten.
    }
        
    return rating;
}

int main ()
{
    Move move ("Sg1-f3");
    return 0;
}


Array[100] ist Mist, da hast du Recht. Aber ein std::vector hat genau wie std::list eine variable Größe, wäre also grundsätzlich geeignet. Und die Iterator-Syntax (siehe Methode Rate) ist bei vector und list genau gleich, die Container sind hier also leicht austauschbar. Du würdest nur in der Laufzeit merken, dass beim vector das Verlängern zunehmend teurer wird, während es bei der list immer dasselbe kostet.
Dieser Post wurde am 18.05.2016 um 16:34 Uhr von ao editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
18.05.2016, 19:37 Uhr
Noby



 @ao: Super, danke. Genau so soll es aussehen, außer dass der Zug ausgeweitet werden muss, da in gewissen Fällen es einen Unterschied macht, was der Vorzug war, z.B. bei enpassant oder wenn eine Figur geschlagen worden ist (denn ich will nicht alle Stellungen speichern, dann muss aber die geschlagene Figur irgendwo gespeichert werden), dann Rochade-Verlust, oder ich mache alles in den String hinein, auch eine Lösung.

Der Zug kann nur über die untersten Züge bewertet werden (MiniMax-Algorithmus), da Schwarz und Weiß ihre Stellungen konträr bewerten, demnach muss ich den Baum vollständig rückwärts gehen können.

Der Baum geht bis ganz nach unten (entsprechend der gesetzten Grenzen), bewertet die Stellung, speichert sie im Knoten, geht zur nächsten möglichen Endstellung etc. Und dann wird über den Minimax-Algo der jeweils höhere Knoten bewertet bis zu den jetzt anstehenden Zugoptionen. Der Aufbau des Baumes läuft über Rekursion, den Minimax-Algo will ich in vorläufig möglichst davon trennen, damit es für mich übersichtlich bleibt und ich meine Bugs finde.

Eigentlich brauche ich noch eine Zeigerstruktur in der class Move, dass ich im Baum von unten nach oben komme.

Ich kann morgen meinen Versuch mit rohen Pointern hier einstellen, der dann in eine Container-Version überführt werden kann.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: