Цитата

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

На тестовом стенде свободный - 2 минуты 50 секунд, послойный - 3 минуты 9 секунд.

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

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

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

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

На стандартных генерациях ванилы, IC2, AE2 (тестировались отдельно) свободный обход существенно превосходит послойный (4 чанка, высота 64). Поэтому, статистика говорит в сторону этого подхода, а что админ накрутит генерацию - проблема индейцев.

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

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

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

Спасибо за пояснения, основные идеи понятны. Далее я сосредоточусь на менее однозначных моментах.

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

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

...

что админ накрутит генерацию - проблема индейцев.

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

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

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

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

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

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

Наиболее интересной мне показалась эта идея:

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

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

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

Да, хорошо, штраф сделать не просто разницей между верхним Y и текущим. А умножением, относительно всей доступной высоты. Так и сделаю.

Повороты можно даже не штрафовать, а делать анализ, на этапе поиска цели.

@Doob, я поспешил с плотностью алмаза. Сейчас посмотрел твою таблицу плотностей, и даже не поверил. Запустил Майн, проверил. Таблица верна.

То ли Алекс накрутил плотность в одной из старых сборок, то ли мне это приснилось. Я был уверен, что алмаз имел более высокую плотность, чем другие руды, а уран с большим отрывом имел плотность 9 или около того.

20.02.2019 в 06:12, Doob сказал:

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

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

Я тут попытался хоть как-то решить задачу поиска оптимального пути, но количество рудных блоков в чанке около 600 штук в сочетании с ограничениями на максимальный объём памяти не позволяют приблизиться к решению. Но я выполнил кластеризацию, и количество объектов уменьшилось до 75 с максимальным количеством до 35 блоков. А это уже реальная задача оптимизации.

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

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

Мне осталось протестировать 3 эвристики из 7. По готовности, опубликую результат с замерами.

Я предлагал рассчитывать путь до кластеров, а не одиночных блоков, еще когда сам играл с послойной добычей. Но зная как работает робот, считаю вычисление полного пути не эффективным - это сильно раздует код, а если рассчитывать еще с минимальным количеством действий, это ОЧЕНЬ сильно раздует код. Сложно представить, какая нагрузка на процессор будет даже при использовании метода Монте-Карло, может он будет падать с елдингами без остановки. Были бы в роботах квантовые процессоры, я бы конечно, запилил решение задачи коммивояжера.

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

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

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

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

Зря ты передёргиваешь. Копать весь чанк слоем через два я не предлагал.

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

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

Монте-Карло не самый лучший, зато самый компактный.

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

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

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

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

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

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

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

20 часов назад, Doob сказал:

программа на двух носителях это уже менее юзерфрендли

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

20 часов назад, Doob сказал:

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

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

Теперь о задаче коммивояжёра. Наш робот когда-то решал эту задачу послойной копкой, но неоптимально. Потом @artem211 оптимизировал перемещения, используя жадный алгоритм, который сейчас применяешь и ты. Логично предположить, что возможна и другая оптимизация. Идеал за разумное время, разумеется, недостижим, но достижимы лучшие эвристики. Вопрос лишь в том, насколько очередная эвристика хороша.

Подробнее:

Да, Монте-Карло очень компактен, это его единственное достоинство. Его логическим продолжением являются генетические алгоритмы, обладающие лучшей сходимостью. В ГА сложен не программный код, а поиск удачного способа кодирования генома. На данный момент я так и не нашёл идеального способа кодирования последовательностей: либо мутация в одном из генов вызывает цепную реакцию вторичных мутаций, либо один и тот же ген в разных последовательностях несёт разный смысл, что лишает ГА преимуществ в сравнении со случайным подбором. На данный момент лучшее, что я смог придумать на этой основе, оперирование одним мутирующим геномом. Мутация сводится к переворачиванию одного случайного участка цепи, изначально построенной жадным алгоритмом. Эффективность не проверялась, но это всяко эффективнее бездумного применения Монте-Карло.

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

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

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

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

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

Интересно было бы анализировать куб 5x5x5 вокруг роботом, это позволило бы при необходимости копать очень эффективно, но полный перебор в этом случае затруднён. Тут нужен новый трюк.

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

Обожаю Майнкрафт за такие задачи. А казалось бы, простая игра для детишек.
 

14 часов назад, John_Trucena сказал:

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

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

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

22.02.2019 в 07:35, Doob сказал:

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

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

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

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

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

26 минут назад, Doob сказал:

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

Да, хорошее решение. Я уже посмотрел последнюю запись блога.

38 минут назад, Doob сказал:

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

Да, медленная штука. Её обсуждение имело смысл только в противовес методам Монте-Карло.

29 минут назад, Doob сказал:

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

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

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

Но идея интересна, согласен.

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

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

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

23.02.2019 в 13:11, Doob сказал:

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

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

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

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

24.02.2019 в 19:05, John_Trucena сказал:

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

А за счёт чего он будет достигаться? Откуда робот узнает, что поступил не самым оптимальным образом? Сама по себе нейросеть в лучшем случае научится добывать хоть что-то и хоть как-то. 

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

Тут вопрос не в скорости, а в принципиальной возможности. Чтобы обучаться, нужно экспериментировать, сравнивать результаты со старыми. А как нейросеть поймёт, что текущий вариант действий лучше предыдушего, если ситуация каждый раз новая? Например, в прошлый раз было собрано 5 блоков руды за 5 секунд, а в этот 5 блоков за 7 секунд. На первый взгляд может показаться, что текущее решение хуже предыдущего, но на практике может оказаться, что прошлую задачу можно было выполнить за 4 секунды, а в этот раз 7 секунд являются наивысшим пределом. И как нам, не имея простого критерия правильности, обучить НС оптимальной копке?

С нейросетями, играющими в простые игры, понятно: прошёл уровень, собрал все бонусы, сохранил жизни -- молодец; не прошёл уровень -- учись дальше. Но с Майном не так: каждый участок для добычи уникален, а поиск оптимума реализуется прожорливыми алгоритмами, для замены которых, собственно, и потребовались "быстрые" нейросети.

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

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