Darstellung einer 2D-Karte von Doubles mit möglichst wenigen „Parametern“.

Question

Ich arbeite an einer rundenbasierten Spiel-KI unter Verwendung einer neuronalen Netzwerktechnik namens SAUBER.Ich versuche, ein Netzwerk zu trainieren, das sich in einem zweidimensionalen Raum (X- und Y-Koordinaten) bewegen kann, wenn verschiedene Werte in einem praktisch zweidimensionalen Array gespeichert sind.

Ich kann zwei Strategien für die Nutzung des neuronalen Netzwerks erkennen:

1. Stellen Sie für jede „Zelle“ im Raster die Bewertungen der verschiedenen Heuristiken als Eingaben für Neuronen bereit und erstellen Sie ein NN, das im Grunde ein sehr kompliziertes „Bewertungssystem“ ist.Bewegen Sie den nicht spielenden Charakter (NPC) an den Ort mit der höchsten Punktzahl.

2. Erstellen Sie einen komprimierten Wert für jedes heiuristische Maß (irgendwie komprimiert auf so wenige Bits wie möglich) und stellen Sie für jedes dieser Maße ein Eingabeneuron bereit.

Ich interessiere mich sehr für Option zwei, da sie den geringsten Rechenaufwand erfordert (die Laufzeit des Spiels ist ziemlich lang), allerdings bin ich verwirrt, welchen Ansatz ich verwenden könnte, um die „kleine Darstellung“-Version der beiden zu erstellen. dimensionale heiuristische Werte.Ich weiß, dass es Techniken wie Fourier-Transformationen gibt, aber ich weiß nicht, ob diese für mein Problem geeignet sind.Grundsätzlich suche ich nach einer Möglichkeit, ein 50x50-Array von Doubles in einen oder vielleicht zwei Double-Werte umzuwandeln.Diese beiden Doppelwerte können verlustbehaftet komprimiert werden. Ich muss nicht in der Lage sein, die ursprünglichen Werte wiederherzustellen, ich benötige lediglich einen vernünftigen Mechanismus, um die Eingabedaten in einen kleinen Footprint umzuwandeln.

Eine Alternative zu diesen beiden Möglichkeiten besteht darin, eine „Region“ irgendwie basierend auf einer gewissen Entfernung vom NPC zu kodieren (so dass Sie die tatsächlichen Werte für eine „nahe“ Zelle und eine Näherung für eine „ferne“ Zelle erhalten).Ich weiß nicht genau, wie ich das verkabeln würde, aber es macht zumindest die Notwendigkeit überflüssig, jede Zelle in jeder Runde des Spiels zu bewerten (vorausgesetzt, ich sehe etwa 5 Millionen Runden bei etwa 1 Sekunde pro Runde, was auch immer die Vereinfachung ist). Ich kann mir etwas einfallen lassen, das würde sehr helfen).

Es tut mir leid, wenn das nicht viel Sinn ergibt, es ist ein ziemlich schwieriges Problem, das mich schon seit einiger Zeit ratlos macht, und mir fällt keine einfache Möglichkeit ein, es zu beschreiben.

Danke schön,

Aidan

BEARBEITET ZUM HINZUFÜGEN (und zum Ändern des Titels):

Dank Chris haben wir das, was ich suche, verfeinert.Was ich suche, ist eine Möglichkeit, eine Linie (ich kann die 2D-Karte in eine Linie umwandeln) mit möglichst wenigen Parametern anzunähern.Ich habe schon früher kubische Splines für die Interpolation verwendet, aber ich brauche etwas viel praktikableres für einen Datensatz, der ziemlich aggressiv zwischen 0,0 und 1,0 variiert.Was ich wirklich suche, ist vermutlich ein „Hash“ der Karte.

Ich weiß, dass es Techniken wie kubische Splines gibt, aus denen ich einige „Schlüsselpunkte“ ermitteln kann, und diese Werte sind eine vernünftige Analogie für das, was ich suche.Ich brauche eine Möglichkeit, aus den 2500 Werten eine kleine Darstellung dieser Werte zu erstellen, die ich für das neuronale Netzwerk verwenden kann.Ich denke, das NN kann trainiert werden, um auf die wahre Bedeutung dieser Darstellungen zu schließen oder zumindest eine gewisse Korrelation zwischen der Darstellung und der realen Welt festzustellen, es muss also nicht unbedingt eine reversible Funktion sein, aber ich glaube nicht Viele Einwegfunktionen (wie MD5s, SHAs) werden tatsächlich auch sehr hilfreich sein ...

Answer 1

Grundsätzlich wird jeder Grafikkomprimierungsalgorithmus tun, was Sie wollen.Sie sind stark für die Komprimierung von 2D-Zahlenfeldern auf die kleinstmögliche Fläche optimiert.

Bearbeitet, um Folgendes hinzuzufügen:

Da Sie die Verarbeitungszeit mithilfe der Komprimierung verkürzen möchten, sollten Sie außerdem berücksichtigen, dass das Erreichen wirklich hoher Komprimierungsraten im Allgemeinen mehr Berechnungen zum Komprimieren und Dekomprimieren des Arrays erfordert.Möglicherweise erreichen Sie einen Punkt, an dem Sie mehr Zeit mit der Komprimierung und Dekomprimierung des Arrays verbringen als mit der Ausführung des neuronalen Netzwerks.

Nochmals bearbeitet, um Folgendes hinzuzufügen:

Basierend auf Ihren Kommentaren hört es sich so an, als ob Sie sich vielleicht eins wünschen raumfüllende Kurve.Verwenden Sie die Kurve, um Ihr 50x50*-Array in eine 1x2500-Linie umzuwandeln, und erstellen Sie dann eine Formel, die die gewünschten Werte für jede Zelle des Arrays annähert.

*Muss das Array 50x50 groß sein?Es kann viel einfacher sein, mit einer raumfüllenden Kurve zu füllen, wenn es sich um ein Quadrat mit leicht unterschiedlichen Abmessungen handelt.Die Hilbert-Kurve funktioniert beispielsweise gut für Dimensionen, die Zweierpotenzen sind.

Answer 2

Sie können versuchen, die FFT Ihrer 1D-Linie zu nehmen und dann spätere (Hochfrequenz-)Terme zu entfernen.In MATLAB habe ich zum Beispiel Folgendes gemacht:

x = [1:1000];
y = rand(1,1000);
f = fft(y, 250); % truncate to 250 terms
plot(x,y, x,abs(ifft(f), 1000));

Die Tendenz bestand darin, dass die Spitzen der iFFT von f sehr nahe an den Spitzen von y lagen.Es waren nicht unbedingt die höchsten Punkte des Jahres, aber es waren Gipfel.In diesem Lauf gab es beispielsweise Spitzen bei x=424, 475 und 725 in der invertierten FFT von f, und es gab auch Spitzen in y bei x=423, 475 und 726.Allerdings lag das globale Maximum von y bei x=503, was ein Spitzenwert in ifft(f) war, aber kein sehr hoher.

Dies halbiert Ihren Datenverbrauch jedoch nur wirklich, da ich 1000 Doubles in 250 komplexe Werte umgewandelt habe.Eine weitere Steigerung kann erreicht werden, indem nur der Realteil der FFT verwendet wird:

x = [1:1000];
y = rand(1,1000);
f = real(fft(y, 250)); % only uses 1/4 the space now
plot(x,y, x,abs(ifft(f, 1000)));

Dies lieferte immer noch ziemlich gute Ergebnisse, da jeder Hauptpeak von ifft(f) einem Peak in y entspricht, der die meiste Zeit nur höchstens 2 entfernt war, und Sie 1/4 des Platzes für die direkte Speicherung des Doubles benötigen .

Allerdings erhalten Sie dadurch immer noch nicht die Ergebnisse von „ein oder zwei doppelten Werten“.Sie packen jetzt 2500 Doubles in 625.Sie können experimentieren, indem Sie mehr Begriffe ausschneiden, aber Sie müssen mehr Werte „aus der Nähe“ testen, indem Sie mehr Begriffe ausschneiden.Vielleicht können Sie die ersten 10 % der Begriffe beibehalten, das Maximum ermitteln und dann innerhalb eines Abstands von 3 oder 4 suchen;Dies würde Ihre 2500 Verdoppelungen auf „nur“ 250 reduzieren.Nur durch Testen können Sie herausfinden, was für Ihre Anwendung am besten funktioniert.

Wenn du bist Wirklich Wenn Sie verzweifelt sind, können Sie bis zu den niedrigsten Frequenzen von 1 % gehen und 5 oder 6 in beide Richtungen nach dem wahren Höhepunkt suchen.Damit bleiben Ihnen aber immer noch 25 Doubles.

Ich glaube nicht, dass es eine Möglichkeit gibt, 2500 Doubles in nur 1 oder 2 umzuwandeln und sie in etwas Sinnvolles umzuwandeln.Werfen Sie einen Blick auf Texte zur Informationstheorie, um herauszufinden, warum.Ich schlage vor, dass Sie sich MATLAB, GNU Octave oder sogar Excel besorgen und mit so etwas herumspielen und herausfinden, welche Ergebnisse für Sie am besten sind.