Rappresentando una mappa 2D dei doppi nel minor numero di “parametri” il più possibile

Question

Sto lavorando su un turn-based gioco AI utilizzando una tecnica neurale-rete conosciuta come NEAT . Sto tentando di addestrare una rete in grado di muoversi a due dimensioni (coordinate X e Y) Spazio proposta una varietà di valori che sono memorizzati in ciò che è effettivamente una matrice bidimensionale.

Posso vedere due strategie per l'utilizzo della rete neurale:

1. Per ogni "cella" nella griglia, fornire i punteggi delle diverse euristiche come input per neuroni e creare un NN che è effettivamente molto complicato "aver" sistema. Spostare il carattere non Playing (NPC) per la posizione con il punteggio più alto.

2. Creare un valore compresso per ogni misura heiuristic (in qualche modo compresso nel minor numero di bit come possibile) e fornire un neurone ingresso per ciascuna di queste misure.

Sono molto interessato a opzione due perché presenta la minor quantità di calcoli necessari (il tempo di esecuzione del gioco è abbastanza lunga), ma sono confuso come quello che approccio che ho potuto usare per creare la versione "piccola rappresentanza" di i valori heiuristic bidimensionali. So che ci sono tecniche come Fourier Trasformazioni là fuori, però non so se questi soddisferà il mio problema. Fondamentalmente sto cercando un modo per convertire una matrice 50x50 di doppie in una o forse due valori doppi. Questi due valori doppie possono essere con perdita-compressa, non ho bisogno di essere in grado di ottenere i valori originali di nuovo, ho solo bisogno di un meccanismo ragionevole per cambiare i dati di input in un piccolo ingombro.

Un'alternativa a queste due possibilità è quella di codificare in qualche modo una "regione" in base a una certa distanza dalla NPC (in modo da ottenere i valori effettivi per una "stretta" delle cellule, e un'approssimazione per una cella "lontano"). Non so esattamente come avrei legare questo in su, ma almeno elimina la necessità di valutare ogni cellula di ogni turno di gioco (dato che sto guardando circa 5 milioni di colpi a circa 1 secondo per ogni turno, qualsiasi semplificazione posso venire con sarebbe di grande aiuto).

Mi scuso se questo non sta facendo molto senso, è piuttosto un problema difficile che mi ha messo in difficoltà per un po ', e non riesco a pensare ad un modo semplice per descriverlo.

Grazie,

Aidan

A cura di aggiungere (e cambiare titolo):

Grazie a Chris Abbiamo migliorato quello che sto cercando. Quello che sto cercando è un modo per approssimare una linea (posso convertire la mappa 2D in una linea) nel minor numero di parametri possibili. Ho usato spline cubica per l'interpolazione prima, però ho bisogno di qualcosa di molto più fattibile per un set di dati che varia tra 0,0 e 1,0 abbastanza aggressivo. Quello che sto cercando realling per Suppongo che è un "hash" della mappa.

So che ci sono tecniche come spline cubiche che posso lavorare fuori alcuni "punti chiave" da, e questi valori sono un'analogia ragionevole per quello che sto cercando. Ho bisogno di un modo per prendere i valori 2500 e venire con una piccola rappresentazione di questi valori che posso usare per la rete neurale. Credo che il NN può essere addestrato per inferire il vero significato di queste rappresentazioni, o almeno per determinare qualche correlazione tra la rappresentazione e il mondo reale, in modo che non deve necessariamente essere una funzione reversibile, ma non credo molti funzione unidirezionale (come MD5 di, SHA di) sono in realtà sarà molto utile sia ...

Answer 1

In sostanza, qualsiasi algoritmo di compressione grafica sta per fare quello che vuoi. Sono pesantemente ottimizzati per la compressione di matrici 2D di numeri in un ingombro minimo.

A cura di aggiungere:

L'altra cosa da considerare, dal momento che stai cercando di utilizzare la compressione per ridurre i tempi di elaborazione, è che ottenere rapporti di compressione molto elevato comporta generalmente più di calcolo per comprimere e decomprimere l'array. Si può raggiungere un punto in cui si sta spendendo più tempo a comprimere e decomprimere la matrice che correre la rete neurale.

A cura di nuovo da aggiungere:

In base alle vostre osservazioni, suona come quello che si può desiderare è un . Usare la curva per trasformare il vostro 50x50 * array in una linea di 1x2500 e poi venire con una formula che approssima i valori desiderati per ogni cella della matrice.

* Fa la matrice deve essere 50x50? Essa può essere molto più facile da riempire con una curva di riempimento di spazio se è un quadrato di dimensioni leggermente diverse. La curva di Hilbert funziona bene per le dimensioni che sono potenze di due, per esempio.

Answer 2

Una cosa si può provare sta prendendo la FFT della vostra linea 1D e quindi rimuovendo successivamente i termini (ad alta frequenza). Per esempio, in MATLAB ho fatto la seguente:

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

Nei tendeva ad accadere è che i picchi della IFFT di f erano molto vicini ai picchi di y. Non erano necessariamente i punti più alti di y, ma erano picchi. Per esempio, questa corsa, c'erano picchi a x = 424, 475, e 725 nel FFT inverso di f, e c'erano picchi anche in y in x = 423, 475, e 726. Tuttavia, di y max globale era x = 503, che era un picco nel IFFT (f), ma non molto alta.

Tuttavia, questo taglia veramente solo l'utilizzo dei dati a metà, perché mi sono convertito 1000 raddoppia in 250 valori complessi. Un ulteriore aumento può essere ottenuto utilizzando solo la parte reale della FFT:

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

This ancora ceduti buoni risultati, con ogni picco maggiore di IFFT (f) corrispondente a un picco di y che era soltanto al massimo una distanza di 2 via la maggior parte del tempo, e si utilizza 1/4 lo spazio di memorizzazione il doppio direttamente.

Tuttavia, questo ancora non si ottiene il risultato di "uno o due valori doppi". Si è ora inscatolando 2500 raddoppia in 625. È possibile sperimentare di taglio più termini, ma si dovrà mettere alla prova più valori "da vicino" tagliando più termini. Forse si può tenere il primo 10% dei termini, e trovare il massimo, e poi guardare a una distanza di 3 o 4; questo ridurrebbe i tuoi 2500 raddoppia ad un "semplice" Solo 250. test sarà scoprire che cosa funziona meglio per la vostra applicazione.

Se sei davvero disperata, si può andare a partire da più basse frequenze di 1%, e cercare 5 o 6 in entrambe le direzioni per il vero picco. Ma questo lascia ancora con 25 doppie.

Non credo che ci sia alcun modo per convertire 2500 raddoppia in solo 1 o 2, e lo hanno reversibili in qualcosa di significativo. Date un'occhiata a informazioni testi di teoria capire perché. Vi suggerisco di ottenere MATLAB, GNU Octave, o anche Excel, e giocare con qualcosa di simile e trovare ciò che i risultati sono i migliori per voi.