Doob 2 748 Опубликовано: 24 апреля, 2020 51 минуту назад, eu_tomat сказал: Теперь предлагаю подумать над тем, как решить конкретно эту задачу за одно сканирование. Хм.. Использовать артефакты дискретизации? Я пока не понял, как отсеять значения, без генерирования маски. Но кажется, должно сработать. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
NEO 541 Опубликовано: 24 апреля, 2020 http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/Random.java Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob 2 748 Опубликовано: 25 апреля, 2020 Что-то у меня не выходит вывести функцию, которая из полученного параметра будет вычислять принадлежность блока. Если сгенерировать значения шума и для каждого результата сканирования делать обратную операцию (result - 1.5) / d / 2 not in noise and (result - 3) / d / 2 in noise Тогда получается вот такое распределение: Вероятность угадать руду - 35.848%, вероятность перепутать с камнем - 0.024% Если вместо and использовать or, то получается 99.983% на руду и 48.682% на камень. Если попробовать разделить облака вероятностей линейно, то в лучшем случае будет 71.058% для руды и 28.166% для камня. Самый быстрый способ определять руду это хеш-таблица. Сгенерировать и хранить в памяти 287889 чисел (количество значений шума * все возможные дистанции). Точность будет 99.998% Более эффективного метода не придумал. Функция разделения облаков слишком высокочастотная, но должна быть другая, которая может из расстояния до блока и его результата сканирования, выдавать реальную плотность. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 25 апреля, 2020 3 часа назад, Doob сказал: Самый быстрый способ определять руду это хеш-таблица. Сгенерировать и хранить в памяти 287889 чисел (количество значений шума * все возможные дистанции). Точность будет 99.998% Более эффективного метода не придумал. Да, я тоже пока не придумал ничего лучшего как либо хранить хеш-таблицу, либо каждый раз заново пересчитывать её элементы для каждого вновь просканированного блока. Правда, я пока довольствовался умозрительными экспериментами, а на калькуляторе посчитал только озвученную задачу. Пока я потренируюсь на задаче пропроще. Для начала попробую оптимизировать вычисление константы шума с учётом новых сведений. Может, после этого появится хорошая идея. Upd: Ой, я соврал. Была же нормальная идея. Просто я уже увлёкся новой задачей. Но сейчас заглянул в калькулятор, а там решение моей же задачи. Даю ещё один намёк. Сделай обратное преобразование зашумлённого значения, исходя из предположения, что сканируется камень или руда. И теперь посмотри, чем эти значения друг от друга отличаются. Конкретно в моей задаче. А потом задайся вопросом, почему одно из них сильно вероятнее другого. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob 2 748 Опубликовано: 25 апреля, 2020 Ну это понятно, ошибка вычисления скатывается в фиксированный диапазон. Если я правильно насчитал, надо хранить 6885 значений, эффективность сканера будет 99.89%. Вполне неплохой результат. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 25 апреля, 2020 @Doob, я перестал понимать твои визуализации в двух последних постах. Я на них ничего не вижу. 1 час назад, Doob сказал: Если я правильно насчитал, надо хранить 6885 значений, эффективность сканера будет 99.89%. Вполне неплохой результат. Я не планирую хранить хеши шумов. Может быть, подумаю о хранении расстояний, чтобы не вызывать многократно функцию извлечения квадратного корня. Но оставшаяся часть реверсивных вычислений, мне кажется, слишком проста для того, чтобы занимать память этими хешами. Но да, надо будет проверить эти предположения в реальной работе. Тогда заодно и дам свою оценку шанса коллизий. Кстати, о коллизиях. Плотности блоков чаще всего кратны единице. Но бывает и 1.5 как у камня. Чем определяется плотность того или иного блока? Насколько дробной может быть плотность, как это регламентируется? Может ли, плотность блока быть 1.618, например? Какие они вообще бывают стандартные, типичные плотности? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Pengoid Автор темы 9 Опубликовано: 25 апреля, 2020 (изменено) 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 для бедрока. Изменено 25 апреля, 2020 пользователем Pengoid 1 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 25 апреля, 2020 28 минут назад, Pengoid сказал: А точно нужно вычислять само расстояние? А ты уже решил мою задачу, опираясь лишь на первый результат сканирования? Как её решить без извлечения корня, при этом не увеличив объём вычислений на порядок? 1 час назад, Pengoid сказал: есть исключения, например кварцевый блок, у него 0.80000001192093, но я во всех случаях пренебрегал подобными хвостами. Да, точно же! Получается, что теоретически какое угодно может быть значение плотности. Эти хвосты могут создать проблему для нового метода подавления шумов. 1 час назад, Pengoid сказал: думаю плотность зависит напрямую от времени ломания блока подходящим типом инструмента. А что у кварца за инструмент такой подходящий для ломания, что получилась такая странная плотность с хвостом? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Pengoid Автор темы 9 Опубликовано: 25 апреля, 2020 1 минуту назад, eu_tomat сказал: А ты уже решил мою задачу, опираясь лишь на первый результат сканирования? Как её решить без извлечения корня, при этом не увеличив объём вычислений на порядок? Да, точно же! Получается, что теоретически какое угодно может быть значение плотности. Эти хвосты могут создать проблему для нового метода подавления шумов. А что у кварца за инструмент такой подходящий для ломания, что получилась такая странная плотность с хвостом? 1. Насколько я пытался догадаться, вы хотите заранее вычислить рандом, который выдаст генератор, чтобы просто вычесть шум из значения сканированного блока для получения реальной плотности блока. В таком случае мои полномочия все. 2. Так как я неправильно понял метод подавления шумов, написал не в тему. 3. Мои предположения: в майнкрафте для каждого блока задается какое-то значение, это или и есть та самая твердость, или же значение, из которого при умножении на какую-то константу можно получить эту же твердость. По наблюдениям могу сказать, что для каждого инструмента должен быть некий коэффициент скорости добычи, который игнорируется, если инструмент не подходит и в качестве коэффициента используется скорость добычи руки (все это для выживания). Такая странная плотность у некоторых блоков для меня остается загадкой, но она не должна зависить от инструмента. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 25 апреля, 2020 3 минуты назад, Pengoid сказал: Насколько я пытался догадаться, вы хотите заранее вычислить рандом, который выдаст генератор, чтобы просто вычесть шум из значения сканированного блока для получения реальной плотности блока. Нет, это @NEO предлагал найти узявимость в ГПСЧ, а я пока воздержусь от этого способа. Я же считаю, что значение шума геосканера не совсем случайно, оно содержит своего рода цифровую подпись, по которой можно всегда или почти всегда (это ещё предстоит выяснить) восстановить точное значение именно шума в общем сигнале. Но для этого требуется выполнить обратное преобразование, одним из компонентов которого является расстояние. Ладно, посмотрим, как там @Doob решит задачу, да я и выложу ответ. Всё равно никто больше не пытается решать. Кстати, @Doob, у тебя в чём затык-то? Ты не уверен в решении моей задачи? Или в общем решении подобных задач? Решение задачи уже можно выкладывать? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Pengoid Автор темы 9 Опубликовано: 25 апреля, 2020 (изменено) Ой, кажись, я понял принцип. У нас при сканировании получается 256 вариантов шума, а на выходе мы имеем точное число с плавающей точкой. Считаем расстояние R. Тогда шум N = R*0.0606*[рандом от -128 до 127]/128 - P0 (полученное значение после сканирования), и тогда каким-то образом рандом подгоняется к преполагаемому значению твердости сканированного блока. Что-то я тугодумлю. Изменено 25 апреля, 2020 пользователем Pengoid Не от -127 до 128, а от -128 до 127 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
NEO 541 Опубликовано: 25 апреля, 2020 13 минуты назад, eu_tomat сказал: Я же считаю, что значение шума геосканера не совсем случайно, Сам написал гпсч и через секунду забыл. Семечкой вероятно всего выступает либо timestamp, либо тики, надо смотреть, но в данном случаеслучайных чисел не будет. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 25 апреля, 2020 15 минут назад, Pengoid сказал: Ой, кажись, я понял принцип. У нас при сканировании получается 256 вариантов шума, а на выходе мы имеем точное число с плавающей точкой. Считаем расстояние R. Тогда шум N = R*0.0606*[рандом от -128 до 127]/128 - P0 (полученное значение после сканирования), и тогда каким-то образом рандом подгоняется к преполагаемому значению твердости сканированного блока. Да, копать надо здесь. Раскручиваем наш сигнал назад к исходному рандому и проверяем характеристики на соответствие исходным. 1 минуту назад, NEO сказал: Сам написал гпсч и через секунду забыл. Нет, тут в другом фокус. Я не ищу уязвимость ГПСЧ, т.к. нашёл уязвимость в дальнейших за ГПСЧ преобразованиях. Эта уязвимость останется актуальной, даже если бы получаемый из ГПСЧ набор чисел вдруг оказался совершенно случайным. Так что, наши подходы сейчас различны. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Pengoid Автор темы 9 Опубликовано: 25 апреля, 2020 (изменено) Есть идея при условии, что мы пробуем отличать блоки, твердость которых кратна 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. Изменено 25 апреля, 2020 пользователем Pengoid 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob 2 748 Опубликовано: 26 апреля, 2020 11 час назад, eu_tomat сказал: я перестал понимать твои визуализации в двух последних постах. Я на них ничего не вижу. Это распределение получается, если провести обратную операцию и проверить совпадение в списке из 256 возможных вариантов шума для руды. При условии, что нет совпадения с шумом для камня. Серая область - распределение шумов камня, бирюзовая - руда, зеленая - распределение верно распознанной руды. Если добавить точно известную руду по максимуму камня (math.max(3 - R * 0.606, 1.5 + R * 0.06013)), тогда получаем вот такое: Вероятность попадания по руде вырастает до 70.695% На следующей гистограмме отображено решение задачи, для всех расстояний (на самом деле не для всех, но это более удобный масштаб) исходя из этой подсказки: 14 часа назад, eu_tomat сказал: И теперь посмотри, чем эти значения друг от друга отличаются. Конкретно в моей задаче. А потом задайся вопросом, почему одно из них сильно вероятнее другого. Красная область - распределение значений для камня, при условии, что мы пытаемся угадать руду. Зеленая - верно распознанная руда. Область пересечения занимает 7377 точек, при том, что реально пересекаются только 492. Итого, надо хранить 6845 точек. Точность получаем таким образом: имеем 444210 возможных значений для руды или камня, из них уникальных - 8224, следовательно 6845/8224 = 83.232%, если бы мы гадали по чему-то одному. Если же просто исключать камень по таблице, то точность будет 99.89% Пока поищу способ, разделить с такой же точностью, но без таблицы. 9 часов назад, Pengoid сказал: По наблюдениям могу сказать, что для каждого инструмента должен быть некий коэффициент скорости добычи, который игнорируется, если инструмент не подходит и в качестве коэффициента используется скорость добычи руки (все это для выживания). Есть такая штука, называется уровень инструмента, но могут быть еще дополнительные условия в коде игры/мода. Есть статья на вики, там написано, что такое твердость и зачем она нужна. Слово "плотность" подошла бы для взрывоустойчивости, но опенкомповский георадар работает на магии, поэтому мы обзываем твердость плотностью скорее по привычке. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob 2 748 Опубликовано: 26 апреля, 2020 Все оказалось очень просто, впрочем, как и все гениальное. Надо было пойти дальше и разобрать на атомы весь алгоритм наложения шума. Вот как легко и без лишней памяти классифицировать блок: Берем результат работы геосканера R, известную твердость блока H, расстояние до блока D, множитель шума из конфига N, подставляем это в следующую формулу: (R - H) / D / N * 128 * 33 % 1 Если результат не равен нулю, то это искомый блок. Стоит помнить, что точность значений 32 бита, поэтому при вычислении с большей точностью, надо результат округлять. Остается сократить половину формулы, чтобы делать меньше вычислений и получаем функцию, которая отсекает шум примерно на 99.31% Ура, товарищи! 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Pengoid Автор темы 9 Опубликовано: 26 апреля, 2020 17 минут назад, Doob сказал: (R - H) / D / N * 128 * 33 % 1 Можешь, пожалуйста, объяснить почему результат должен быть не равен нулю? А то я получил противоположный результат с такой же формулой, но без остатка от деления, то есть у меня число должно быть приблизительно целым, а значит по твой формуле у меня результат должен быть очень близким к нулю или нулем. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 26 апреля, 2020 5 минут назад, Pengoid сказал: Можешь, пожалуйста, объяснить почему результат должен быть не равен нулю? А то я получил противоположный результат с такой же формулой, но без остатка от деления, то есть у меня число должно быть приблизительно целым, а значит по твой формуле у меня результат должен быть очень близким к нулю или нулем. Полагаю, это описка. А ход рассуждений одинаков, вы оба нашли решение. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Doob 2 748 Опубликовано: 26 апреля, 2020 Да, все верно, я немного по-другому сформулировал, а исправить забыл. Тут штука в том, что при обратной операции восстанавливается дискретность 256 значений, а мы их по модулю 1 грохаем в ноль. Взять пример @eu_tomat, (1.295 - 3) / 30 / 2 * 128 * 33 = -120, как раз одно из возможных значений. Если подставим плотность 1.5, то получим -14.4, что совсем не годится. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Pengoid Автор темы 9 Опубликовано: 26 апреля, 2020 Только что, 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. Тогда получается, что формулы идентичны. Мало-ли, вдруг кто-то потом заметит. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах