Ich habe lange überlegt, eine KI für ein Brettspiel zu machen, und seit kurzem sammle ich Ressourcen und Algorithmen. Das Spiel ist nicht zufällig und die meiste Zeit, da & lt; 3 Züge für einen Spieler, manchmal gibt es & gt; 20 Züge. Ich möchte kritische Züge oder mehrdeutige Züge speichern, damit die KI aus ihren Fehlern lernt und beim nächsten Mal nicht den gleichen Fehler macht. Bewegungen, die sicher gewinnen oder verlieren, müssen nicht gespeichert werden. Ich habe also einen spärlichen Entscheidungsbaum für den Anfang von Spielen. Ich würde gerne wissen, wie ich diesen Entscheidungsbaum in einer Datenbank speichern soll? Die Datenbank muss nicht SQL sein, und ich weiß nicht, welche Datenbank für dieses spezielle Problem geeignet ist.
EDIT: Bitte sag mir nicht, den Entscheidungsbaum in den Speicher zu packen, stell dir das Spiel so kompliziert vor wie Schach.
Da du den Baum durchqueren wirst, scheint mir neo4j eine gute Lösung zu sein. SQL ist aufgrund der vielen Joins, die Sie für Abfragen benötigen, keine gute Wahl. Wie ich die Frage verstehe, fragen Sie nach einer Möglichkeit, ein Diagramm in einer Datenbank zu speichern, und neo4j ist eine Datenbank explizit für Graphen. Für die Spärlichkeit können Sie Arrays von Primitiven oder Strings an die Kanten Ihres Graphen anhängen, um Bewegungssequenzen mit PropertyContainern zu kodieren (bin ich der Meinung, dass durch Spärlichkeit und das Überspringen von Knoten gemeint ist, dass Ihre Baumkanten Sequenzen von Bewegungen statt von einzelnen sind) bewegt sich?).
Zunächst klingt das, was Sie zu tun versuchen, wie ein CBR-Problem: Ссылка . CBR wird eine Datenbank mit Entscheidungen haben, Ihr System würde theoretisch die besten verfügbaren Ergebnisse auswählen.
Daher würde ich vorschlagen, neo4j zu verwenden, was eine Nosql-Graph-Datenbank ist. Ссылка
Um dein Spiel darzustellen, ist jede Position ein Knoten im Graphen und jeder Knoten sollte mögliche Bewegungen von dieser Position enthalten. Sie können Scoring-Metriken verfolgen, die im Verlauf der Spiele gelernt werden, so dass die KI besser informiert ist.
Ich würde eine Dokumentendatenbank (NOSQL) wie RavenDB verwenden, da Sie jede Datenstruktur in der Datenbank speichern können.
Dokumente sind nicht flach wie in einer normalen SQL-Datenbank und das erlaubt Ihnen, hierarchische Daten wie Bäume direkt zu speichern:
%Vor%Hier sehen Sie einen Beispiel-JSON-Baum, der in RavenDB gespeichert werden kann.
RavenDB hat auch eine eingebaute Funktion, um hierarchische Daten abzufragen: Ссылка
Sehen Sie in der Dokumentation nach, wie RavenDB funktioniert.
Ressourcen:
Sie können Speicherabbilddatei als Speicher verwenden. Erstellen Sie zuerst "Compiler". Dieser Compiler analysiert die Textdatei und wandelt sie in eine kompakte Binärdarstellung um. Die Hauptanwendung wird diese binäre optimierte Datei in den Speicher abbilden. Dies wird Ihr Problem mit der Speichergrößenbeschränkung lösen
Beginnen Sie mit einem einfachen Datenbanktabellen-Design.
Entscheidungen: CurrentState BINARY (57) | NewState BINARY (57) | Score INT
CurrentState und NewState sind eine serialisierte Version des Spielstatus. Score ist eine Gewichtung für den NewState (positive Scores sind gute Moves, negative Scores sind schlechte Moves). Ihre KI kann diese Scores entsprechend aktualisieren.
Renju, verwendet ein 15x15-Board, jeder Speicherort kann entweder schwarz, weiß oder leer sein, so dass Sie Ceiling ((2Bits * 15 * 15) / 8) Bytes benötigen, um das Board zu serialisieren. In SQL wäre das ein BINARY (57) in T-SQL
Deine KI würde die aktuellen Bewegungen auswählen, die sie gespeichert hat wie ...
%Vor%Sie erhalten eine Liste aller gespeicherten nächsten Züge aus dem aktuellen Spielstand in der Reihenfolge der besten Punktzahl, um die geringste Punktzahl zu erreichen.
Ihre Tabellenstruktur hat einen eindeutigen zusammengesetzten Index (Primärschlüssel) (CurrentState, NewState), um die Suche zu erleichtern und Duplikate zu vermeiden.
Dies ist nicht die beste / optimalste Lösung, aber aufgrund Ihres Mangels an Datenbankkenntnissen glaube ich, dass es am einfachsten zu implementieren wäre und Ihnen einen guten Start verschafft.
Wenn ich mich mit Schach-Engines vergleiche, spielen diese aus dem Gedächtnis, vielleicht abgesehen von der Eröffnung von Bibliotheken. Schach ist zu kompliziert, um einen Entscheidungsbaum zu speichern. Schach-Engines spielen, indem sie heuristische Auswertungen potenziellen und flüchtigen zukünftigen Positionen zuordnen (nicht bewegt). Zukünftige Positionen werden durch eine begrenzte Tiefensuche gefunden, können für einige Zeit im Speicher zwischengespeichert werden, werden aber oft in jeder Runde neu berechnet, da der Suchraum einfach zu groß ist, um schneller gespeichert zu werden, als es neu berechnet werden kann.
Ich kann weder die Datenstrukturen, die Sie in Ihrem Baum handhaben, noch deren Komplexität klar erkennen.
Aber hier sind einige Gedanken, die Sie interessieren könnten:
Ich würde dies mit der traditionellen Art und Weise, wie ein Eröffnungsbuch in Schachmaschinen behandelt wird, angehen:
Schach-Engines berechnen normalerweise eine Hash-Funktion des aktuellen Spielzustands über Zobrist-Hashing , das ist a einfache Möglichkeit, eine gute Hash-Funktion für Gamestates zu erstellen.
Der große Vorteil dieses Ansatzes besteht darin, dass er sich um Transpositionen kümmert, das heißt, wenn Der gleiche Zustand kann über alternative Pfade erreicht werden, man muss sich keine Gedanken über diese alternativen Pfade machen, nur über das Spiel selbst.
Die meisten Schach-Engines verwenden statische Eröffnungsbücher, die aus aufgezeichneten Spielen kompiliert werden, und verwenden daher eine einfache Binärdatei, die diese Hashes auf eine Punktzahl abbildet; z.B.
%Vor%Die Einträge werden dann nach Hash sortiert und dank dem Caching des Betriebssystems eine einfache binäre Suche Durch die Datei werden die benötigten Einträge sehr schnell gefunden.
Wenn Sie jedoch möchten, dass die Engine kontinuierlich lernt, benötigen Sie eine kompliziertere Datenstruktur. An diesem Punkt lohnt es sich normalerweise nicht, selbst zu arbeiten, und Sie sollten eine verfügbare Bibliothek verwenden. Ich würde wahrscheinlich LevelDB verwenden, aber alles, was Sie Schlüssel-Wert-Paare speichern können, ist in Ordnung (Redis, SQLite , GDBM usw.)
Wie genau Sie die Punktzahlen aktualisieren, hängt von Ihrem Spiel ab. In Spielen mit vielen verfügbaren Daten ist ein einfacher Ansatz möglich, z. B. das Speichern des prozentualen Anteils der Spiele, die nach dem Zug gewonnen wurden, der zu der Position geführt hat. Wenn Sie weniger Daten haben, können Sie das Ergebnis einer Spielbaumsuche von der fraglichen Position aus als Ergebnis speichern. Maschinelle Lerntechniken wie Q-Lernen sind ebenfalls eine Möglichkeit, obwohl ich kein Programm kenne, das tatsächlich funktioniert tut dies in der Praxis.
Ich nehme an, Ihre Frage fragt, wie man einen Entscheidungsbaum in ein serielles Format umwandelt, das an einen Ort geschrieben und später zur Rekonstruktion des Baumes verwendet werden kann.
Versuchen Sie, eine Vorbestellung des Baums zu verwenden, indem Sie eine toString () - Funktion (oder eine Entsprechung) verwenden, um die an jedem Knoten des Entscheidungsbaums gespeicherten Daten in einen Textdeskriptor zu konvertieren. Bei der Vorbestellungsdurchquerung bedeute ich die Implementierung eines Algorithmus, der zuerst die toString () - Operation auf dem Knoten ausführt und die Ausgabe in eine Datenbank oder Datei schreibt und dann rekursiv die gleiche Operation auf seinen untergeordneten Knoten in einer bestimmten Reihenfolge ausführt. Da es sich um einen dünn besetzten Baum handelt, sollte Ihre toString () -Operation auch Informationen über das Vorhandensein oder Nichtvorhandensein von Teilbäumen enthalten.
Das Rekonstruieren des Baums ist einfach - der erste gespeicherte Wert ist der Wurzelknoten, der zweite ist das Wurzelelement des linken Teilbaums und so weiter. Die für jeden Knoten gespeicherten seriellen Daten sollten Informationen darüber enthalten, zu welchem Teilbaum der nächste eingegebene Knoten gehören sollte.
Tags und Links database data-structures artificial-intelligence storage decision-tree