Представление 2D-карты двойников с как можно меньшим количеством «параметров».

Question

Я работаю над пошаговым игровым ИИ, используя метод нейронной сети, известный как АККУРАТНЫЙ.Я пытаюсь обучить сеть, которая может перемещаться по двумерному пространству (координаты X&Y), учитывая множество значений, которые хранятся в том, что фактически представляет собой двумерный массив.

Я вижу две стратегии использования нейронной сети:

1. Для каждой «ячейки» сетки предоставьте оценки различных эвристик в качестве входных данных для нейронов и создайте NN, которая фактически представляет собой очень сложную систему «оценки».Переместите неигрового персонажа (NPC) в место с наибольшим количеством очков.

2. Создайте сжатое значение для каждой эвристической меры (каким-то образом сжатое до минимально возможного количества битов) и предоставьте входной нейрон для каждой из этих мер.

Меня очень интересует второй вариант, потому что он требует наименьшего количества вычислений (время выполнения игры довольно велико), однако я не понимаю, какой подход я мог бы использовать для создания «маленькой» версии двух- размерные эвристические значения.Я знаю, что существуют такие методы, как преобразования Фурье, однако я не знаю, подойдут ли они для моей проблемы.По сути, я ищу способ преобразовать массив двойных чисел размером 50x50 в одно или, возможно, два двойных значения.Эти два двойных значения могут быть сжаты с потерями, мне не нужно иметь возможность вернуть исходные значения, мне просто нужен разумный механизм для изменения входных данных в небольшой размер.

Альтернативой этим двум возможностям является каким-то образом закодировать «регион» на основе некоторого расстояния от NPC (чтобы вы получили фактические значения для «близкой» ячейки и приближение для «далекой» ячейки).Я не знаю точно, как бы я это подключил, но это, по крайней мере, избавляет от необходимости оценивать каждую ячейку на каждом ходу игры (учитывая, что я рассматриваю около 5 миллионов раундов примерно по 1 секунде за раунд, любое упрощение Могу придумать, очень поможет).

Прошу прощения, если это не имеет особого смысла, это довольно сложная проблема, которая какое-то время поставила меня в тупик, и я не могу придумать простой способ ее описать.

Спасибо,

Эйдан

ОТРЕДАКТИРОВАНО ДЛЯ ДОБАВЛЕНИЯ (и изменения названия):

Благодаря Крису мы усовершенствовали то, что я ищу.Я ищу способ аппроксимировать линию (я могу преобразовать 2D-карту в линию) с минимальным количеством параметров.Раньше я использовал кубические сплайны для интерполяции, однако мне нужно что-то более осуществимое для набора данных, который довольно агрессивно варьируется от 0,0 до 1,0.Я полагаю, что на самом деле я ищу «хэш» карты.

Я знаю, что существуют такие методы, как кубические сплайны, на основе которых я могу определить некоторые «ключевые точки», и эти значения являются разумной аналогией того, что я ищу.Мне нужен способ взять 2500 значений и придумать небольшое представление этих значений, которое я могу использовать для нейронной сети.Я думаю, что НС можно научить делать вывод об истинном значении этих представлений или, по крайней мере, определять некоторую корреляцию между представлением и реальным миром, поэтому она не обязательно должна быть обратимой функцией, но я не думаю, что многие односторонние функции (такие как MD5, SHA) на самом деле тоже будут очень полезны...

Answer 1

По сути, любой алгоритм сжатия графики будет делать то, что вы хотите.Они сильно оптимизированы для сжатия двумерных массивов чисел до минимально возможного размера.

Отредактировано, чтобы добавить:

Еще одна вещь, которую следует учитывать, поскольку вы хотите использовать сжатие для сокращения времени обработки, заключается в том, что получение действительно высоких коэффициентов сжатия обычно требует большего количества вычислений для сжатия и распаковки массива.Вы можете достичь точки, когда будете тратить больше времени на сжатие и распаковку массива, чем на запуск нейронной сети.

Отредактировано еще раз, чтобы добавить:

Судя по вашим комментариям, похоже, что вам может понадобиться кривая заполнения пространства.Используйте кривую, чтобы превратить массив 50x50* в линию 1x2500, а затем придумайте формулу, которая аппроксимирует нужные значения для каждой ячейки массива.

*Обязателен ли массив 50x50?Гораздо проще заполнить кривую заполнения пространства, если это квадрат немного разных размеров.Кривая Гильберта хорошо работает, например, для измерений, которые являются степенями двойки.

Answer 2

Вы можете попробовать выполнить БПФ вашей 1D-линии, а затем удалить более поздние (высокочастотные) члены.Например, в MATLAB я сделал следующее:

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

Как правило, пики iFFT f были очень близки к пикам y.Это не обязательно были самые высокие точки y, но это были вершины.Например, в этом прогоне были пики при x=424, 475 и 725 в инвертированном БПФ f, а также были пики по y при x=423, 475 и 726.Однако глобальный максимум y находился на уровне x=503, что было пиком ifft(f), но не очень высоким.

Однако на самом деле это сокращает использование данных только вдвое, поскольку я преобразовал 1000 двойных значений в 250 комплексных значений.Дальнейшее увеличение можно получить, используя только действительную часть БПФ:

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) соответствовал пику y, который большую часть времени находился на расстоянии не более 2, и вы используете 1/4 пространства для непосредственного хранения двойного значения. .

Однако это все равно не дает вам результатов «одного или двух двойных значений».Теперь вы упаковываете 2500 двойников в 625.Вы можете поэкспериментировать, сократив больше терминов, но вам придется проверить больше значений «вблизи», сократив больше терминов.Возможно, вам удастся сохранить первые 10% терминов и найти максимум, а затем посмотреть на расстояние 3 или 4;это уменьшит ваши 2500 удвоений до «всего лишь» 250.Только тестирование позволит определить, что лучше всего подходит для вашего приложения.

Если вы Действительно В отчаянии вы можете опуститься до самых низких частот в 1% и поискать 5 или 6 в любом направлении истинного пика.Но в результате у вас все равно останется 25 дублей.

Я не думаю, что есть какой-либо способ превратить 2500 двойников только в 1 или 2 и превратить это во что-то значимое.Взгляните на тексты по теории информации, чтобы понять, почему.Я предлагаю вам приобрести MATLAB, GNU Octave или даже Excel, поиграть с чем-то вроде этого и найти результаты, которые лучше всего подходят для вас.