eu_tomat

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подробнее:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

Цитата

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

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

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

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

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

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

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

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

Цитата

Функция robot.durability() не показывает правильный износ для зачарованных инструментов.
Придется несколько раз ставить и разрушать блок, пока не обнаружится износ.

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

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

Цитата

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

Сейчас сканирования, конечно, экономятся, но при отсутствии блоков робот всё равно уходит в бесконечный цикл вращения.

Цитата

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

Интересно будет взглянуть. Придумать концепцию универсальной копалки мне так и не удалось, т.к. каждый мод вносит свою уникальную специфику. Даже уровень шума геосканера сильно влияет на оптимальный стиль копки. А ещё могут внезапно обнаружиться неожиданные препятствия, например, в виде ульев Forestry, непроходимых с помощью бура IC2, как это было с @artem211. Или, например, сейчас на EvilWorld есть шанс запутаться в лабиринте из магического стекла, установленного другими игроками. Работа с инструментами тоже сильно отличается: ванильные, IC2, Tinkers Construct, ThaumCraft – все они производятся, ремонтируются или заряжаются специфическим образом. Я тоже думал про модульную копалку, но так и не смог систематизировать возможности модов. Поэтому с интересом буду следить за твоими успехами.

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

Цитата

Робот сканирует под собой квадрат 16x16 блоков, опускаясь блок за блоком

Как борешься с шумами?

5 минут назад, Asior сказал:

Мост живой. Он на #ewilvorld так как фингер не играет, он остановил поддержку своего моста. Да и там пока что непонятки. После конфискации админского чатбокса, я порезал программу, так что теперь сообщения видно только из игры. В игру ничего писать нельзя.

Понятно. Моста Фингера нет. А в указанный тобой IRC-канал закралась ошибка. Оставлю ссылку, чтобы не приходилось долго искать

https://webchat.esper.net/?join=evilworld

А мост игрового чата и #cc.ru-server1 совсем умер?

02.01.2019 в 22:13, BrightYC сказал:

зачем в майне рыба нужна(Вернее, зачем её так много)?

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

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

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

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

В OpenComputers-MC1.7.10-1.7.2.1166-universal.jar setResponsePort влияет только на частоту ответа на команду, но сами команды продолжают приниматься с любых частот. Это баг или фича?

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

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

Починили да не все похоже. Народ, проверьте работает ли у вас правильно транспозер. Тоесть может он перемещать вещи из конкретного слота сундука в конкретный другой слот. Вчера с такой проблемой столкнулся на майне 1.7.10. А то если и правда не работает, пора Сангару писать.

Подтверждаю. При выполнении transposer.transferItem(1,5, 16, 2,2):

• 1.7.3 игнорирует номера слотов как источника, так и приемника, пересылая 16 предметов из первого слота в первый. Возвращает количество переданных предметов.
• 1.7.2 возвращает true, но зато перемещает предметы ровно в тот слот и из того слота, которые указаны.

Цитата

• Отрегулировали частоту выполнения хука, который шлёт этот ненавистный "too long without yielding", так что теперь и скорость исполнения кода должна гораздо возрасти, и с ошибкой этой код падать реже. Мы проверяли: некая гуи-либа с 1.6 fps до 2.5 fps только благодаря этому работать стала.

Скорость выполнения пока не тестировал, но частота прерываний по TLWY, непонятно, чем обусловленных, упала раз в 5 при переходе с версии 1.7.2 на 1.7.3. Проверялось на сборке OC+IC2exp в Майнкрафте версии 1.7.10.

Абсолютные значения, наверное, не имеют большого смысла, т.к. эта частота сильно зависит от модпака. Например, на сборке EvilWorld прерывания по TLWY возникали раз в 10 чаще, чем на лёгкой сборке OC+IC2exp. Но если кому интересно, то на лёгкой сборке с OC 1.7.3 я получил TLWY всего три раза за 200'000 тиков (2.7 часа). Плотность непрерывной вычислительной нагрузки составляла около 3/4 тика. Оставшаяся четверть тика в обязательном порядке тратилась на вызов pullSignal() с целью  избежать TLWY, что само по себе очень избыточно, но даже эта мера не обеспечила 100% гарантии успешного завершения кода.

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

Смена имени робота программным путём – одна из тех приятных возможностей, что была когда-то утеряна при переводе сервера с ComputerCraft на OpenComputers. Теперь причин для сожаления стало еще меньше.

getAllStacks и getInventoryName – тоже долгожданные возможности.

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

Как много всего вкусного! Сразу захотелось запустить Майнкрафт.

Методы getAllStacks и getInventoryName для контроллера инвентаря и транспозера. Наконец-то!

Методы getAllStacks и getInventoryName отсутсвуют как для контроллера инвентаря, так и для транспозера.