Darstellen einer 2D-Karte von Doppel in so wenigen "Parametern" wie möglich

Question

Ich arbeite an einem rundenbasierten Spiel AI mit einer neuronalen Netzwerk-Technik bekannt als NEAT. Ich versuche, ein Netzwerk zu trainieren, das sich um einen zweidimensionalen (X & Y coords) Raum bewegen kann, der eine Vielzahl von Werten enthält, die in einem zweidimensionalen Array gespeichert sind.

I zwei Strategien für die Verwendung des neuronalen Netzes unter:

1. Für jede „Zelle“ in dem Gitter, die Scores aus den verschiedenen Heuristiken als Eingaben an Neuronen sorgen und einen NN schaffen, die effektiv ist ein sehr kompliziertes "Scoring" -System. Verschiebe den nicht spielenden Charakter (NPC) zum Ort mit der höchsten Punktzahl.

2. Erstellen Sie einen komprimierten Wert für jedes heuristische Maß (irgendwie komprimiert in so wenig Bits wie möglich) und stellen Sie ein Eingabe-Neuron für jedes dieser Maße bereit.

Ich bin sehr daran interessiert, Option zwei, weil es die geringste Menge an Berechnungen erforderlich (die Laufzeit des Spiels ist ziemlich lang) präsentiert, aber wie ich bin verwirrt, was Ansatz, den ich die „kleinen schaffen nutzen könnte Repräsentation "Version der zweidimensionalen heuristischen Werte. Ich weiß, dass es Techniken wie Fourier-Transformationen gibt, aber ich weiß nicht, ob diese meinem Problem entsprechen. Im Grunde bin ich auf der Suche nach einer Möglichkeit, ein 50x50 Array von Double in einen oder sogar zwei Double-Werte zu konvertieren. Diese zwei doppelten Werte können verlustbehaftet komprimiert sein, ich muss nicht in der Lage sein, die ursprünglichen Werte zurück zu bekommen, ich brauche nur einen vernünftigen Mechanismus, um die Eingabedaten in einen kleinen Footprint zu ändern.

Eine Alternative zu diesen beiden Möglichkeiten besteht darin, irgendwie eine "Region" basierend auf einer gewissen Entfernung vom NPC zu kodieren (so erhalten Sie die tatsächlichen Werte für eine "nahe" Zelle und eine Annäherung für eine "ferne" Zelle). Ich weiß nicht genau, wie ich das einrichten würde, aber es wird zumindest die Notwendigkeit beseitigt, jede Zelle in jeder Runde des Spiels zu bewerten (vorausgesetzt, ich betrachte ungefähr 5 Millionen Runden bei ungefähr 1 Sekunde pro Runde, jede Vereinfachung) Ich kann mir vorstellen, würde sehr helfen).

Ich entschuldige mich, wenn das nicht viel Sinn macht, es ist ein ziemlich schwieriges Problem, das mich für eine Weile ratlos hat, und ich kann mir nicht eine einfache Möglichkeit vorstellen, es zu beschreiben.

Thankyou,

Aidan

HINZUFÜGEN EDITED (und ändern Titel):

Dank Chris haben wir verfeinert, was ich suche. Was ich suche, ist eine Möglichkeit, eine Linie (ich kann die 2D-Karte in eine Linie umwandeln) in so wenigen Parametern wie möglich anzunähern. Ich habe zuvor kubische Splines für die Interpolation verwendet, aber ich brauche etwas viel Machbareres für einen Datensatz, der ziemlich aggressiv zwischen 0,0 und 1,0 variiert. Was ich suche, nehme ich an, ist ein "Hash" der Karte.

Ich weiß, es gibt Techniken wie kubische Splines, aus denen ich einige "Schlüsselpunkte" ausarbeiten kann, und diese Werte sind eine sinnvolle Analogie für das, wonach ich suche. Ich brauche einen Weg, um die 2500 Werte zu nehmen und eine kleine Repräsentation dieser Werte zu finden, die ich für das neurale Netzwerk verwenden kann. Ich denke, der NN kann trainiert werden, um die wahre Bedeutung dieser Repräsentationen abzuleiten, oder zumindest um eine Korrelation zwischen der Repräsentation und der realen Welt zu bestimmen, also muss es nicht notwendigerweise eine reversible Funktion sein, aber ich denke nicht Viele One-Way-Funktionen (wie MD5, SHA) sind tatsächlich sehr hilfreich, entweder ...

Answer 1

Im Grunde wird jeder Grafikkomprimierungsalgorithmus tun, was Sie wollen. Sie sind stark optimiert, um 2D-Zahlenfelder auf kleinstem Raum zu komprimieren.

Edited hinzufügen:

Die andere Sache zu prüfen, da Sie die Komprimierung verwenden gesuchte Verarbeitungszeit zu reduzieren, besteht darin, dass die Anordnung zum Komprimieren und Dekomprimieren wirklich hoch im Allgemeinen mehr Rechen Verhältnisse Kompression bekommen beinhaltet . Sie können einen Punkt erreichen, an dem Sie mehr Zeit mit der Komprimierung und Dekomprimierung des Arrays verbringen als mit dem Ausführen des neuronalen Netzwerks.

wieder Edited hinzufügen:

Basierend auf Ihre Kommentare, es klingt wie das, was Sie wollen, kann ein space-filling curve ist. Verwenden Sie die Kurve, um Ihr 50x50 * -Array in eine 1x2500-Linie zu verwandeln, und erstellen Sie dann eine Formel, die den gewünschten Werten für jede Zelle des Arrays entspricht.

* Muss das Array 50x50 sein? Es kann viel einfacher sein, mit einer Raumfüllkurve zu füllen, wenn es sich um ein Quadrat mit etwas anderen Abmessungen handelt. Die Hilbert-Kurve eignet sich gut für Dimensionen, die beispielsweise Zweierpotenzen sind.

Answer 2

Eine Sache, die Sie versuchen können, ist die FFT Ihrer 1D-Leitung zu nehmen und später (hochfrequente) Bedingungen zu entfernen. Zum Beispiel in MATLAB habe ich folgendes:

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

Was war geschehen eher, dass die Spitzen der IFFT von f Spitzen von y sehr nahe waren. Sie waren nicht unbedingt die höchsten Punkte von y, aber sie waren Spitzen. Zum Beispiel gab es bei diesem Durchlauf in der invertierten FFT von f Peaks bei x = 424, 475 und 725, und es gab auch Peaks in y bei x = 423, 475 und 726. Jedoch war das globale Maximum von y bei x = 503, was eine Spitze in ift (f) war, aber nicht sehr hoch.

Das halbiert jedoch nur Ihre Datennutzung wirklich, weil ich 1000 doppelte in 250 komplexe Werte umwandelte. Eine weitere Erhöhung kann nur erhalten werden, indem der Realteil der FFT unter Verwendung von:

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))); 

Dieses immer noch recht gute Ergebnisse erzielt, wobei jeder Hauptpeak von IFFT (f) auf einen Spitzenwert in y entspricht, der höchstens war eine Entfernung von 2 weg die meiste Zeit, und Sie verwenden 1/4 der Speicherplatz der Doppel direkt speichern.

Dies führt jedoch immer noch nicht zu den Ergebnissen von "ein oder zwei Doppelwerte". Sie packen jetzt 2500 Doppel in 625. Sie können experimentieren, indem Sie mehr Begriffe schneiden, aber Sie müssen mehr Werte "aus der Nähe" testen, indem Sie mehr Begriffe schneiden. Vielleicht kannst du die ersten 10% der Begriffe behalten und das Maximum finden und dann innerhalb einer Entfernung von 3 oder 4 schauen; Das würde Ihre 2500 Doubles zu einem "bloßen" 250 reduzieren. Nur das Testen wird herausfinden, was am besten für Ihre Anwendung funktioniert.

Wenn Sie wirklich verzweifelt sind, können Sie so niedrig wie die niedrigsten 1% Frequenzen gehen und suchen 5 oder 6 in beide Richtungen für die wahre Spitze. Aber das lässt immer noch 25 Doppelgänger übrig.

Ich glaube nicht, dass es eine Möglichkeit gibt, 2500 Doppel in nur 1 oder 2 zu konvertieren, und es in alles Sinnvolle reversibel zu haben. Werfen Sie einen Blick auf Texte der Informationstheorie, um zu sehen, warum. Ich schlage vor, Sie erhalten MATLAB, GNU Octave oder sogar Excel und spielen mit so etwas herum und finden, welche Ergebnisse für Sie am besten sind.