Перейти к содержимому
Pengoid

Вычисление погрешности геосканера

Рекомендуемые сообщения

51 минуту назад, eu_tomat сказал:

Теперь предлагаю подумать над тем, как решить конкретно эту задачу за одно сканирование.

 

Хм.. Использовать артефакты дискретизации? Я пока не понял, как отсеять значения, без генерирования маски. Но кажется, должно сработать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Если сгенерировать значения шума и для каждого результата сканирования делать обратную операцию

(result - 1.5) / d / 2 not in noise and (result - 3) / d / 2 in noise

Тогда получается вот такое распределение:

QRV6G1A.png

 

Вероятность угадать руду - 35.848%, вероятность перепутать с камнем - 0.024%

Если вместо and использовать or, то получается 99.983% на руду и 48.682% на камень.

 

Если попробовать разделить облака вероятностей линейно, то в лучшем случае будет 71.058% для руды и 28.166% для камня.

 

Самый быстрый способ определять руду это хеш-таблица. Сгенерировать и хранить в памяти 287889 чисел (количество значений шума * все возможные дистанции). Точность будет 99.998%

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
3 часа назад, Doob сказал:

Самый быстрый способ определять руду это хеш-таблица. Сгенерировать и хранить в памяти 287889 чисел (количество значений шума * все возможные дистанции). Точность будет 99.998%

 

Более эффективного метода не придумал.

Да, я тоже пока не придумал ничего лучшего как либо хранить хеш-таблицу, либо каждый раз заново пересчитывать её элементы для каждого вновь просканированного блока. Правда, я пока довольствовался умозрительными экспериментами, а на калькуляторе посчитал только озвученную задачу.

 

Пока я потренируюсь на задаче пропроще. Для начала попробую оптимизировать вычисление константы шума с учётом новых сведений. Может, после этого появится хорошая идея.

 

Upd:

Ой, я соврал. Была же нормальная идея. Просто я уже увлёкся новой задачей. Но сейчас заглянул в калькулятор, а там решение моей же задачи.

 

Даю ещё один намёк. Сделай обратное преобразование зашумлённого значения, исходя из предположения, что сканируется камень или руда. И теперь посмотри, чем эти значения друг от друга отличаются. Конкретно в моей задаче. А потом задайся вопросом, почему одно из них сильно вероятнее другого.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Ну это понятно, ошибка вычисления скатывается в фиксированный диапазон.

 

71EAKbU.png

 

Если я правильно насчитал, надо хранить 6885 значений, эффективность сканера будет 99.89%. Вполне неплохой результат.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Doob, я перестал понимать твои визуализации в двух последних постах. Я на них ничего не вижу.

 

1 час назад, Doob сказал:

Если я правильно насчитал, надо хранить 6885 значений, эффективность сканера будет 99.89%. Вполне неплохой результат.

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

 

Кстати, о коллизиях. Плотности блоков чаще всего кратны единице. Но бывает и 1.5 как у камня. Чем определяется плотность того или иного блока? Насколько дробной может быть плотность, как это регламентируется? Может ли, плотность блока быть 1.618, например? Какие они вообще бывают стандартные, типичные плотности?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, eu_tomat сказал:

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

А точно нужно вычислять само расстояние? Если требуется сравнить расстояние с другим значением, можно просто само значение возвести в квадрат, вместо того, чтобы извлекать корень, это менее ресурсоемко.

 

1 час назад, eu_tomat сказал:

Кстати, о коллизиях. Плотности блоков чаще всего кратны единице. Но бывает и 1.5 как у камня. Чем определяется плотность того или иного блока? Насколько дробной может быть плотность, как это регламентируется? Может ли, плотность блока быть 1.618, например? Какие они вообще бывают стандартные, типичные плотности?

Я просканировал кучу блоков, и думаю плотность зависит напрямую от времени ломания блока подходящим типом инструмента.

Точнее, соотношение времени ломания для одного и того же подходящего для выбранных блоков инструмента будет равняться соотношению плотностей. В основном они кратны 0.1, есть исключения, например кварцевый блок, у него 0.80000001192093, но я во всех случаях пренебрегал подобными хвостами. У листвы плотность 0.2, песка, земли, плотного льда - 0.5, блока алмаза, железа - 5. У факелов, некоторых редстоун-компонентов плотность 0 (они мгновенно ломаются рукой в выживании). Исключение - обсидиан, имеет плотность 50, точно такая же у небесного камня из AE2 (можно легко находить метеориты). Есть два блока из IC2, которые имеют относительно уникальные плотности: 20 у базальта и 80 у укрепленного камня, я их хотел использовать для того, чтобы роботы могли точно определять свои координаты без улучшения навигации. У бедрока плотность -1, скорее всего так будет для всех неломающихся блоков.

Для всех вышеперечисленных блоков соблюдалась закономерность с временем ломания. И да, "hardness" - это скорее твердость, чем плотность, что лучше объясняет прямую зависимость значения от времени разрушения блока и значение -1 для бедрока.

Изменено пользователем Pengoid

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
28 минут назад, Pengoid сказал:

А точно нужно вычислять само расстояние?

А ты уже решил мою задачу, опираясь лишь на первый результат сканирования? Как её решить без извлечения корня, при этом не увеличив объём вычислений на порядок?

 

1 час назад, Pengoid сказал:

есть исключения, например кварцевый блок, у него 0.80000001192093, но я во всех случаях пренебрегал подобными хвостами.

Да, точно же! Получается, что теоретически какое угодно может быть значение плотности. Эти хвосты могут создать проблему для нового метода подавления шумов.

 

1 час назад, Pengoid сказал:

думаю плотность зависит напрямую от времени ломания блока подходящим типом инструмента.

А что у кварца за инструмент такой подходящий для ломания, что получилась такая странная плотность с хвостом?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 минуту назад, eu_tomat сказал:

А ты уже решил мою задачу, опираясь лишь на первый результат сканирования? Как её решить без извлечения корня, при этом не увеличив объём вычислений на порядок?

 

Да, точно же! Получается, что теоретически какое угодно может быть значение плотности. Эти хвосты могут создать проблему для нового метода подавления шумов.

 

А что у кварца за инструмент такой подходящий для ломания, что получилась такая странная плотность с хвостом?

1. Насколько я пытался догадаться, вы хотите заранее вычислить рандом, который выдаст генератор, чтобы просто вычесть шум из значения сканированного блока для получения реальной плотности блока. В таком случае мои полномочия все.

 

2. Так как я неправильно понял метод подавления шумов, написал не в тему.

 

3. Мои предположения: в майнкрафте для каждого блока задается какое-то значение, это или и есть та самая твердость, или же значение, из которого при умножении на какую-то константу можно получить эту же твердость. По наблюдениям могу сказать, что для каждого инструмента должен быть некий коэффициент скорости добычи, который игнорируется, если инструмент не подходит и в качестве коэффициента используется скорость добычи руки (все это для выживания).

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
3 минуты назад, Pengoid сказал:

Насколько я пытался догадаться, вы хотите заранее вычислить рандом, который выдаст генератор, чтобы просто вычесть шум из значения сканированного блока для получения реальной плотности блока.

Нет, это @NEO предлагал найти узявимость в ГПСЧ, а я пока воздержусь от этого способа.

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

 

Ладно, посмотрим, как там @Doob решит задачу, да я и выложу ответ. Всё равно никто больше не пытается решать.

Кстати, @Doob, у тебя в чём затык-то? Ты не уверен в решении моей задачи? Или в общем решении подобных задач? Решение задачи уже можно выкладывать?

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Ой, кажись, я понял принцип. У нас при сканировании получается 256 вариантов шума, а на выходе мы имеем точное число с плавающей точкой.

Считаем расстояние R. Тогда шум N = R*0.0606*[рандом от -128 до 127]/128 - P0 (полученное значение после сканирования), и тогда каким-то образом рандом подгоняется к преполагаемому значению твердости сканированного блока. Что-то я тугодумлю.

Изменено пользователем Pengoid
Не от -127 до 128, а от -128 до 127

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
13 минуты назад, eu_tomat сказал:

Я же считаю, что значение шума геосканера не совсем случайно,

Сам написал гпсч и через секунду забыл.:D Семечкой вероятно всего выступает либо timestamp, либо тики, надо смотреть, но в данном случаеслучайных чисел не будет.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
15 минут назад, Pengoid сказал:

Ой, кажись, я понял принцип. У нас при сканировании получается 256 вариантов шума, а на выходе мы имеем точное число с плавающей точкой.

Считаем расстояние R. Тогда шум N = R*0.0606*[рандом от -128 до 127]/128 - P0 (полученное значение после сканирования), и тогда каким-то образом рандом подгоняется к преполагаемому значению твердости сканированного блока.

Да, копать надо здесь. Раскручиваем наш сигнал назад к исходному рандому и проверяем характеристики на соответствие исходным.

 

1 минуту назад, NEO сказал:

Сам написал гпсч и через секунду забыл.

Нет, тут в другом фокус. Я не ищу уязвимость ГПСЧ, т.к. нашёл уязвимость в дальнейших за ГПСЧ преобразованиях. Эта уязвимость останется актуальной, даже если бы получаемый из ГПСЧ набор чисел вдруг оказался совершенно случайным. Так что, наши подходы сейчас различны.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Есть идея при условии, что мы пробуем отличать блоки, твердость которых кратна 0.1 (для кварцевых и других блоков со странной плотностью не работает).

Из неправильно выведенной мною формулы:

1 час назад, Pengoid сказал:

N = R*0.0606*[рандом от -128 до 127]/128 - P0

Которая на самом деле N = P0 - R*0.0606*[rand(-128; 127)]/128

Будем перебирать возможные плотности блоков в диапазоне максимальной погрешности.

На максимальном расстоянии будет больше 70 вариантов, но надо учесть, что плотность не может быть отрицательной (если это не бедрок), этот диапазон скорее всего можно будет сузить.

Тогда из формулы рассчитываем число, выдаваемое генератором:

K = (P0 - N)*128/(0.0606*R).

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

 

Upd:

Можно создать массив плотностей возможных блоков, а не подбирать с шагом в 0.1.

Изменено пользователем Pengoid

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
11 час назад, eu_tomat сказал:

я перестал понимать твои визуализации в двух последних постах. Я на них ничего не вижу.

 

Это распределение получается, если провести обратную операцию и проверить совпадение в списке из 256 возможных вариантов шума для руды. При условии, что нет совпадения с шумом для камня.

QRV6G1A.png

 

Серая область - распределение шумов камня, бирюзовая - руда, зеленая - распределение верно распознанной руды.

 

Если добавить точно известную руду по максимуму камня (math.max(3 - R * 0.606, 1.5 + R * 0.06013)), тогда получаем вот такое:

Вероятность попадания по руде вырастает до 70.695%

YzLZj1S.png

 

 

На следующей гистограмме отображено решение задачи, для всех расстояний (на самом деле не для всех, но это более удобный масштаб) исходя из этой подсказки:

14 часа назад, eu_tomat сказал:

И теперь посмотри, чем эти значения друг от друга отличаются. Конкретно в моей задаче. А потом задайся вопросом, почему одно из них сильно вероятнее другого.

71EAKbU.png

 

Красная область - распределение значений для камня, при условии, что мы пытаемся угадать руду. Зеленая - верно распознанная руда.

Область пересечения занимает 7377 точек, при том, что реально пересекаются только 492. Итого, надо хранить 6845 точек.

 

Точность получаем таким образом: имеем 444210 возможных значений для руды или камня, из них уникальных - 8224, следовательно 6845/8224 = 83.232%, если бы мы гадали по чему-то одному. Если же просто исключать камень по таблице, то точность будет 99.89%

Пока поищу способ, разделить с такой же точностью, но без таблицы.

 

 

 

 

9 часов назад, Pengoid сказал:

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

Есть такая штука, называется уровень инструмента, но могут быть еще дополнительные условия в коде игры/мода.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Все оказалось очень просто, впрочем, как и все гениальное.

Надо было пойти дальше и разобрать на атомы весь алгоритм наложения шума.

 

Вот как легко и без лишней памяти классифицировать блок:

Берем результат работы геосканера R, известную твердость блока H, расстояние до блока D, множитель шума из конфига N, подставляем это в следующую формулу:

(R - H) / D / N * 128 * 33 % 1

 

Если результат не равен нулю, то это искомый блок.

Стоит помнить, что точность значений 32 бита, поэтому при вычислении с большей точностью, надо результат округлять.

Остается сократить половину формулы, чтобы делать меньше вычислений и получаем функцию, которая отсекает шум примерно на 99.31%

 

Ура, товарищи!

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
17 минут назад, Doob сказал:

(R - H) / D / N * 128 * 33 % 1

Можешь, пожалуйста, объяснить почему результат должен быть не равен нулю? А то я получил противоположный результат с такой же формулой, но без остатка от деления, то есть у меня число должно быть приблизительно целым, а значит по твой формуле у меня результат должен быть очень близким к нулю или нулем.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
5 минут назад, Pengoid сказал:

Можешь, пожалуйста, объяснить почему результат должен быть не равен нулю? А то я получил противоположный результат с такой же формулой, но без остатка от деления, то есть у меня число должно быть приблизительно целым, а значит по твой формуле у меня результат должен быть очень близким к нулю или нулем.

Полагаю, это описка. А ход рассуждений одинаков, вы оба нашли решение.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Да, все верно, я немного по-другому сформулировал, а исправить забыл.

 

Тут штука в том, что при обратной операции восстанавливается дискретность 256 значений, а мы их по модулю 1 грохаем в ноль.

Взять пример @eu_tomat,  (1.295 - 3) / 30 / 2 * 128 * 33 = -120, как раз одно из возможных значений.

Если подставим плотность 1.5, то получим -14.4, что совсем не годится.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Только что, eu_tomat сказал:

Полагаю, это описка. А ход рассуждений одинаков, вы оба нашли решение.

Все не так гладко, только сейчас заметил, я ошибся два раза, но прийти к результату это не помешало.

N - это шум, P0 - это данные сканирования, H - реальная твердость, которую я даже не указал, хотя в способе решения предлагал ее подставлять.

13 часа назад, Pengoid сказал:

K = (P0 - N)*128/(0.0606*R).

По логике P0 = N + H.

Но из своей формулы я получаю:

13 часа назад, Pengoid сказал:

N = P0 - R*0.0606*[rand(-128; 127)]/128

N = P0 - N, хотя на самом деле H = P0 - N, чем процитированная формула и равняется, разница полученного значения и шума.

Короче, я перепутал N с H.

Тогда получается, что формулы идентичны.

 

Мало-ли, вдруг кто-то потом заметит.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...