가능한 한 적은 수의 "매개변수"로 복식의 2D 맵 표현

Question

저는 신경망 기술을 사용하여 턴제 게임 AI를 개발 중입니다. 정돈된.저는 사실상 2차원 배열에 저장된 다양한 값을 고려하여 2차원(X&Y 좌표) 공간에서 이동할 수 있는 네트워크를 훈련하려고 합니다.

신경망을 사용하는 두 가지 전략을 볼 수 있습니다.

1. 그리드의 각 "셀"에 대해 다양한 휴리스틱의 점수를 뉴런에 대한 입력으로 제공하고 사실상 매우 복잡한 "점수 계산" 시스템인 NN을 만듭니다.NPC(Non Playing Character)를 점수가 가장 높은 곳으로 이동하세요.

2. 각 경험적 측정값에 대해 압축된 값을 생성하고(어떻게든 가능한 한 적은 비트로 압축) 이러한 측정값 각각에 대한 입력 뉴런을 제공합니다.

옵션 2는 필요한 계산 양이 가장 적기 때문에(게임 실행 시간이 상당히 길기 때문에) 매우 관심이 있지만, 두 옵션의 "작은 표현" 버전을 만드는 데 어떤 접근 방식을 사용할 수 있는지 혼란스럽습니다. 차원적 경험적 가치.푸리에 변환과 같은 기술이 있다는 것을 알고 있지만 이것이 내 문제에 적합한지는 모르겠습니다.기본적으로 저는 50x50의 double 배열을 하나 또는 두 개의 double 값으로 변환하는 방법을 찾고 있습니다.이 두 개의 이중 값은 손실 압축될 수 있으므로 원래 값을 다시 가져올 필요는 없으며 입력 데이터를 작은 공간으로 변경하기 위한 합리적인 메커니즘만 필요합니다.

이 두 가지 가능성에 대한 대안은 NPC와의 거리를 기반으로 "영역"을 어떻게든 인코딩하는 것입니다. 따라서 "가까운" 셀에 대한 실제 값과 "먼" 셀에 대한 근사값을 얻을 수 있습니다.이것을 어떻게 연결해야 할지 정확히 모르겠지만 적어도 게임이 끝날 때마다 모든 셀을 평가할 필요가 없어집니다(라운드당 약 1초씩 약 500만 라운드를 보고 있으므로 단순화). 나는 큰 도움이 될 것이라고 생각해 낼 수 있습니다).

이것이 말이 되지 않는다면 사과드립니다. 그것은 한동안 저를 당황하게 만들었던 꽤 어려운 문제이고, 그것을 설명하는 쉬운 방법이 생각나지 않습니다.

감사합니다,

에이단

추가(및 제목 변경)를 위해 편집됨:

Chris 덕분에 우리는 내가 찾고 있는 것을 개선했습니다.내가 찾고 있는 것은 가능한 한 적은 매개변수로 선(2D 지도를 선으로 변환할 수 있음)을 근사화하는 방법입니다.이전에 보간을 위해 큐빅 스플라인을 사용한 적이 있지만 0.0에서 1.0 사이에서 매우 공격적으로 변하는 데이터 세트에 대해 훨씬 더 실현 가능한 것이 필요합니다.내가 실제로 찾고 있는 것은 지도의 "해시"라고 생각합니다.

나는 몇 가지 "핵심 사항"을 해결할 수 있는 큐빅 스플라인과 같은 기술이 있다는 것을 알고 있으며 이러한 값은 내가 찾고 있는 것에 대한 합리적인 비유입니다.2500개의 값을 가져와서 신경망에 사용할 수 있는 이러한 값을 작게 표현하는 방법이 필요합니다.나는 NN이 이러한 표현의 진정한 의미를 추론하거나 적어도 표현과 실제 세계 사이의 상관 관계를 결정하도록 훈련될 수 있다고 생각하므로 반드시 가역적 기능일 필요는 없지만 그렇게 생각하지 않습니다. 많은 단방향 기능(예: MD5, SHA)은 실제로 매우 도움이 될 것입니다...

Answer 1

기본적으로 모든 그래픽 압축 알고리즘이 원하는 작업을 수행 할 것입니다. 그들은 가능한 가장 작은 발자국으로 2D 숫자를 압축하기 위해 크게 최적화되었습니다.

추가하기 위해 편집 :

고려해야 할 또 다른 사항은 압축 시간을 줄이기 위해 압축을 사용하려고하기 때문에 실제로 높은 압축 비율을 얻는 데는 일반적으로 배열을 압축하고 압축 해제하기 위해 더 많은 계산이 포함된다는 것입니다. 신경망을 실행하는 것보다 배열을 압축하고 압축하는 데 더 많은 시간을 소비하는 지점에 도달 할 수 있습니다.

추가하기 위해 다시 편집 :

귀하의 의견을 바탕으로 원하는 것은 공간 충족 곡선. 곡선을 사용하여 50x50* 배열을 1x2500 라인으로 전환 한 다음 배열의 각 셀에 대해 원하는 값에 근접한 공식을 제시하십시오.

*배열은 50x50이어야합니까? 약간 다른 치수의 제곱 인 경우 공간 충전 곡선으로 채우는 것이 훨씬 쉬울 수 있습니다. 힐버트 곡선은 예를 들어 두 가지 힘의 치수에서 잘 작동합니다.

Answer 2

시도해 볼 수 있는 한 가지 방법은 1D 라인의 FFT를 취한 다음 이후의 (고빈도) 항을 제거하는 것입니다.예를 들어 MATLAB에서는 다음을 수행했습니다.

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

f의 iFFT 피크가 y의 피크에 매우 가까운 경향이 있었습니다.반드시 y의 최고점은 아니었지만 최고점이었습니다.예를 들어, 이 실행에서는 f의 역 FFT에서 x=424, 475 및 725에 피크가 있었고, x=423, 475 및 726에서 y에도 피크가 있었습니다.그러나 y의 전역 최대값은 x=503에 있었는데, 이는 ifft(f)에서 최고점이었지만 그다지 높지는 않았습니다.

그러나 이것은 1000 double을 250 복소수 값으로 변환했기 때문에 실제로 데이터 사용량을 절반으로 줄입니다.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)));

ifft(f)의 각 주요 피크는 대부분의 경우 최대 2 거리에 불과한 y의 피크에 해당하고 이중을 직접 저장하는 공간의 1/4을 사용하여 꽤 좋은 결과를 얻었습니다. .

그러나 이것은 여전히 ​​"하나 또는 두 개의 이중 값"의 결과를 얻지 못합니다.이제 2500개의 더블을 625개로 포장하고 있습니다.더 많은 항을 잘라서 실험할 수 있지만 더 많은 항을 잘라서 더 많은 값을 "가까이" 테스트해야 합니다.아마도 처음 10%의 용어를 유지하고 최대값을 찾은 다음 3~4개의 거리 내에서 볼 수 있습니다.이렇게 하면 2500배가 "단순한" 250배로 줄어듭니다.테스트를 통해서만 애플리케이션에 가장 적합한 것이 무엇인지 알아낼 수 있습니다.

만약 당신이 정말 절망적이라면 가장 낮은 1% 주파수까지 낮춰서 실제 피크를 찾기 위해 어느 방향에서든 5 또는 6을 검색할 수 있습니다.그러나 이것은 여전히 ​​25개의 복식을 남깁니다.

2500 double을 1 또는 2로 변환하고 의미 있는 것으로 되돌릴 수 있는 방법은 없다고 생각합니다.그 이유를 알아보려면 정보 이론 텍스트를 살펴보세요.MATLAB, GNU Octave 또는 Excel을 사용하여 이와 같은 것을 시험해보고 자신에게 가장 적합한 결과를 찾는 것이 좋습니다.