Стратегия для соревнования IT_One_CUP. Базы данных.
Приказ на отпуск подписан, и вдруг приходит приятное сообщение: «IT ONE» объявляет о проведении соревнований на платформе https://cups.online по базам данных. Наступает открытие бета-тестирования задачи. Прочитав условия, задача показалась довольно простой. Во всяком случае условия не были вереницей непонятного текста.
Первая попытка отправить решение (к базовой стратегии, в которой корабль просто плавает между островами, дописано создание контрактов на покупку и продажу товара, если продавец и покупатель находятся на одном острове, дописывалось просто в текстовом редакторе) и в результате ошибка синтаксиса. Вторая и третья попытка аналогичны. Принято решение ждать local runner,а заодно поднять виртуальную машину с postgres и pgadmin.
Когда появился local runner, то стратегия была построена по следующему принципу: ищем наилучший заказ (количество товара / продавец / покупатель), назначаем его кораблю, записываем в свою таблицу и далее следуем плану по его выполнению. До финала идея стратегии не изменилась, но менялась её реализация.
Стратегия номер 1 (этап беты). Лучший заказ - это максимум разности цен покупки/продажи на минимальное количество среди можно купить/продать/перевезти. Ход 1 – для припаркованных кораблей, не назначенных на заказы, пытаемся создать контракт на продажу. Ход 2 – если не удалось, то отменяем «заказ», иначе создаем контракт на покупку. Ход 3 – если удалось, то отдаём кораблю приказы, иначе пытаемся снова покупать.
Стратегия номер 2 (этап беты). Добавил больше логирования. Особо ничего не менял. В какой-то момент делал таблицу короткого маршрута по обходу всех островов. Так и не пригодилась.
Стратегия номер 3. Добавил таблицу максимальных цен. Продажа только если цена близка к максимальной. Лучший заказ выбирается с учетом «максимальной» цены. К выбору заказа добавляется коэффициент 1.2 если корабль уже на острове продавца. Коэффициент родился как примерное соотношение затрачиваемого времени на всю сделку если надо плыть к острову продавца к времени сделки, если уже находишься там. В свет эта стратегия не вышла, т.к. локально играла очень плохо. Пришло время основного раунда. Позже, когда выяснился алгоритм изменения цены и посчитав, что при максимальной базовой цене прирост ее не такой уж и большой, я понял, что затраты времени на расчёт цены не окупят ее колебаний, поэтому выбирая лучший заказ я смотрел на цены в «моменте» и больше их не контролировал.
Стратегия 4. Инициализация таблицы расстояний между островами. Была с первых версий, но вызывалась если поле в служебной таблице было не инициализировано. Понял, что каждый раз трачу время на запрос к этой служебной таблице. В результате переписал на вызов инициализации, если время равно нулю. Изменен порядок контрактов. Контракты на продажу вынес в отдельный блок. Теперь «заказ» начинается с покупки товара. Это помогло отказаться от проверок на «успешность» контрактов. И для отвергнутых контрактов просто удаляются записи из таблицы «заказов», где идентификатор совпадает с идентификатором приказа на покупку. Лучший заказ – разница в цене покупки / продажи умноженная на минимум из предложения продавца / трюма корабля, умноженная на коэффициент 1.2. Заказы только среди покупателей, на островах которых нет моих товаров (если товары есть, значит я не успеваю их продавать и не стоит туда везти ещё товар). Продажа: товар продается только одному покупателю с наивысшей ценой (если уже есть контракт (но почему-то не реализованный), то другим не продаем. При времени более 99800 – продаём уже всем, кто есть на острове. С этой стратегией я вышел где-то на 7-9 место. В стратегии где-то была ошибка, т.к. иногда она не доигрывала игры.
Стратегия 5. Добавил логи окончания игры, чтобы посмотреть на сервере, что у меня на складах не продано и что перевозится.
Стратегия 6. Лучший заказ – как раньше, но теперь не участвую покупатели, для которых товар на острове и в пути меньше 500. Поправил ошибку, из-за которой иногда стратегия падала. В итоге ТОП-3.
Стратегия 7. Продажа товара всем покупателям на острове после 99700. Покупка до времени 87500 – 2 * вместимость корабля – как обычно, после расчёт количества с учетом того, чтоб хватило времени на приплыть, погрузить груз, переплыть, разгрузить, продать. Принудительное завершение стратегии в 90000, чтобы не светиться в ТОП-3. (несколько версий, что-то видимо подправлял).
Стратегия 8 (без логов, чтобы не тратилось время think на raise notice) и 9 (с логами). Понял, что пытаясь убрать покупателей, для которых товары везутся / на острове, никак не учитывается когда товары разгружаются. В итоге запрос на товары стал браться из моей таблицы «заказов». Теперь заказы ищутся, где на острове покупателя товара меньше 250 и удвоенное предложение покупателя больше, чем я собираюсь ему продавать. После 97500 – заказы ищутся среди покупателей, которым я вообще ничего не собираюсь продавать.
Стратегия 10. Какие-то попытки замеров времени отдельных блоков think и вывод их в лог.
Стратегия 11. Понял, что заполнение таблицы расстояний между островами съедает много времени и в первый 'think' большинство «заказов» не могут быть исполнены, т.к. противники их уже выкупили, поменял тактику. Во время «0» – просто выборка заказов без учета расстояний и выход . В итоге контроль, надо ли инициализировать таблицу, заключался проверкой, есть ли в ней записи. Дополнительно для времени больше 99700 сделал создания контрактов с покупателями (с которыми у меня не планируются отношения) на их максимум предложения. Это была надежда, что противникам это хоть чуть-чуть, но подпортит результат.
Стратегия 12. По итогу участвовала в рейтинге основного раунда. Для продажи товаров понял проблему: если товара мало (что скорее всего является следствием работы конкурента), возникает много отказов, т.к. за время моего хода конкурент выкупает количество, которое не успевает восстановится. Добавил для продажи правило: «если товара меньше 150, то контракт заключать только на половину». Для закупки товара (выбора заказа) изменил профит сделки на профит на единицу времени: разницу цен умножал на количество (минимум из вместимости трюма / предложения продавца), деленное на время погрузки, разгрузки, расстояния между островами и учёт на продолжительность самих 'think'ов. Продолжительность ‘think’ я принял за 70. Расстояние между островами я рассчитывал для каждого корабля, измерял во времени (дистанция / скорость) и время приводил к кратности 70.
Стратегия 13. Финал. За два дня до финала я для себя открыл грааль: приказы выполняются после того, как произошел выход из процедуры, а значит игровое время становится Tstart + 1000 * dTthink. К этому времени мир изменён и возможно выполнять действия, которые на момент самой процедуры я считал недоступными. То, что я использовал с самого начала: по логике работы сервера можно было отправить сразу приказ на покупку товара и загрузку этого товара. После выхода из процедуры сервер обрабатывал приказ на покупку. Если было успешно, то далее приказ на загрузку корабля тоже отрабатывал (погрузка начиналась), т.к. товар был на острове. В случае если покупка не удавалась, то сервер игнорировал приказ на загрузку, т.к. товара на складе не было. Конечно, могла быть проблема, если на одном острове я сразу делал два контракта на покупку и соответствующие приказы на погрузку: один из контрактов мог не сработать, а корабль мог начать грузиться товаром, т.к. на складе оказывалось количество от другого контракта. Для этого случая была пара блоков, где я контролировал такие случаи: если оказался корабль с грузом но без заказа, то я смотрел, где можно продать товар и делал заказ.
Что я добавил: для корабля, который движется с грузом, я добавлял приказы на разгрузку: по логике товар с грузом мог двигаться только на остров покупателя, поэтому его надо разгружать. В корабле мог быть только один товар, поэтому не надо было думать, что именно разгружать, информация о товаре хранилась в моей таблице. В итоге экономия одного вызова think.
Для корабля, который плывет без груза, я делал приказ на погрузку, т.к. корабль без груза мог плыть только к острову, на котором я купил товар для перепродажи. Еще экономия на одном вызове think.
Для корабля, который занимался погрузкой, я отдавал приказ на отплытие к острову покупателя. Это еще одна экономия.
В результате локально у меня результат увеличился примерно на 2-3%. Стратегия был готова в субботу, но залил я её за час до финала: другие игроки могли анализировать битвы и додуматься до такого же грааля, глядя на мой «спам» приказов.
Эта стратегия принесла мне второе место, проиграв стратегии, припасенный другим игроком, который был примерно на 7ой позиции рейтинга.