Оптимальная стратегия

[Albus]

Собственно, есть игра, в которой вы можете строить виспы, которые производят дерево, и золотые шахты, которые дают золото. Характеристики сих производящих единиц следующие
Висп: стоимость 1млн монет - производит 1256 дерева в сек
Золотая шахта 1 - стоимость 64тыс дерева - производит 2тыс монет в сек
Золотая шахта 2 - стоимость 512тыс дерева - производит 24тыс монет в сек
Вы стартуете с одного виспа и 10тыс дерева, а также у вас есть фоновый доход в 8тыс монет в сек. Вы строите шахты и виспов. Чем больше шахт, тем больше золота, и соответственно виспов вы можете построить. И наоборот, чем больше виспов, тем выше добыча дерева, и тем больше шахт вы можете построить.
Вопрос, сколько нужно построить шахт 1 перед тем, как строить только шахты 2 (ибо они выгоднее), чтобы быстрее построить три шахты 2? (можно также взять пять шахт 2) Т.е. задача на оптимизацию экономики.
У меня вышло, что чтобы быстрее добраться до первой шахты 2, нужно сначала построить две шахты 1. Но если мы будем в начале строить много шахт 1, то у нас будет больше добыча золота, и мы построим больше виспов. Если сравнить эти две ситуации, то в первой (при двух шахтах 1) мы быстрее добираемся до оптимума по золоту, но проседаем по добыче дерева, так что неочевидно, какая стратегия лучше.
Вот собственно, задача

[Ian]

Вопрос, сколько нужно построить шахт 1 перед тем, как строить только шахты 2 (ибо они выгоднее), чтобы быстрее построить три шахты 2? (можно также взять пять шахт 2) Т.е. задача на оптимизацию экономики.

Вы сами так сузили задачу.Тогда это задача динамического программирования, победой считается постройка трех шахт 2, целевая функция -время до победы, с какими еще ресурсами придем к моменту победы -считаем несущественным. Отсюда свойства оптимального поведения: виспы надо строить в момент, когда на них набрались ресурсы (а куда еще это золото девать), а для употребления дерева вводим функцию управления всего из двух вариантов: u=0 (строим шахту 1 как только наберем дерево для нее) иначе u=1 (набираем дерево для шахты 2). Причем все варианты изменения функции управления просчитывать не надо, если в некоторый момент u=1 оптимальна, то в следующие моменты u=0 оптимальной быть не может, чем выше скорости добычи всего, тем скорее при локальной оптимизации будет u=1. Можно аналитически (+программно) отследить какие будут моменты перехода между состояниями (i,j,k)-количества виспов, шахт1 и шахт2, из них i мы не управляем, оно само растет по возможности, а добиваемся достижения k=3, причем в переходные моменты знаем ресурсы дерева и золота(один из них равен естественно нулю, так как только что весь истрачен, но другой-то важен).И вот значит вопрос после достижения какого j ставить u=1 вместо u=0. Я предлагаю вместо программы гонять саму игру несколько раз и засекать время, вот и узнаете.

[zykov]

Написал небольшой скрипт считающий время в зависимости от количества "шахт 1" (начиная с нуля).
Вот время:

Код: Выбрать все

412.36 399.98 400.14 399.49 401.27 405.11 407.55 411.11 415.08 418.45 422.25

3 "шахты 1" оптимально, хотя разница с одной шахтой не велика - 399.49 чуть меньше 399.98.
(для двух шахт время чуть больше, чем для одной, но там золота больше остаётся - почти 1000000)

[zykov]

Вот trace для трёх шахт, если интересно:

Код: Выбрать все

    T    w  g1 g2 wood     gold
  0      1  0  0  10000    0
 42.994  1  1  0  0        343949
 93.949  1  2  0  0        853503
 106.157 2  2  0  15333.3  0
 125.531 2  3  0  0        232484
 180.353 3  3  0  137714   0
 251.782 4  3  0  406857   0
 272.71  4  3  1  0        292994
 291.315 5  3  1  93473.7  0
 317.631 6  3  1  258737   0
 343.947 7  3  1  457053   0
 350.197 7  3  2  0        237489
 362.495 8  3  2  108129   0
 378.624 9  3  2  270194   0
 394.753 10 3  2  452516   0
 399.489 10 3  3  0        293631

[zykov]

Для 5 шахт второго типа будет:

Код: Выбрать все

481.62 467.52 465.84 463.66 463.94 466.26 467.31 469.57 472.25 474.37 477.02

Т.е. тоже 3 наиболее оптимально.

[Albus]

У меня получились похожие результаты, только со смещением Вы учитывали, что у нас есть лимит в лям дерева и золота? (и начальные 10k дерева)

Написал небольшой скрипт считающий время в зависимости от количества "шахт 1" (начиная с нуля).
Вот время:

Код: Выбрать все

412.36 399.98 400.14 399.49 401.27 405.11 407.55 411.11 415.08 418.45 422.25

3 "шахты 1" оптимально, хотя разница с одной шахтой не велика - 399.49 чуть меньше 399.98.
(для двух шахт время чуть больше, чем для одной, но там золота больше остаётся - почти 1000000)

У меня вышло

Код: Выбрать все

415 403 404 404 405 409 411 415 419 423 427

Для 5 шахт второго типа будет:

Код: Выбрать все

481.62 467.52 465.84 463.66 463.94 466.26 467.31 469.57 472.25 474.37 477.02

Т.е. тоже 3 наиболее оптимально.

Мой вариант

Код: Выбрать все

485 473 471 469 469 472 472 475 477 480 483

хотя я все в целых секундах считал (округление всегда вниз)

[zykov]

Source of the post Вы учитывали, что у нас есть лимит в лям дерева и золота?

Миллион не превышало, т.к. при достижении уровня сразу расходовалось (1М монет на лесопилку, 64к или 512к на шахту).

Source of the post и начальные 10k дерева

Да, в trace видно, что начинаем с 10к дерева.

Про эти 10к в вашем питон-скрипте забыли.

Код: Выбрать все

wisp=1
gold1=0
gold2=0
g=0
w=0

здесь нужно

Код: Выбрать все

w=10000

[Albus]

Миллион не превышало, т.к. при достижении уровня сразу расходовалось (1М монет на лесопилку, 64к или 512к на шахту).

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

Про эти 10к в вашем питон-скрипте забыли.

Код: Выбрать все

wisp=1
gold1=0
gold2=0
g=0
w=0

здесь нужно

Код: Выбрать все

w=10000

Да, в результатах выше это уже учтено
Тут еще интересно рассмотреть время жизни шахт (для шахты1-1000 сек, для шахты2-160 сек)
Первая задача такая же (достижение первых 4-5 шахт2)
А вторая получить максимум виспов (суммарного золота) за отведенное время (600 сек, 900-1000 сек)
То что шахты1 в плане содержания суммарного золота в 4 раза выгодней, чем шахты2, должно же как то выстрелить

[Albus]

Все-таки самая конечная цель это наиболее быстро потратить 15(30, и т.д.) миллионов золота и дерева на защитные сооружения (каждое стоит по лямнику золота и дерева) И да, после траты двух миллионов золота и дерева на защитные сооружения фоновый доход вырастает с 8 тыс до 32 тыс

[zykov]

Source of the post А тогда это наверное из-за того, что у меня миллион списывался не сразу, а когда пройдет целая секунда

Нет, это из-за того что в начале 0 дерева, а не 10к.
Сделал у себя ноль, получил:

Код: Выбрать все

414.61 403.32 404.21 403.44 405.37 409.16 411.63 415.24 419.18 422.56 426.38

Вот, если интеерсно, код Matlab для подсчёта:

Код: Выбрать все

function r = wood_gold(n)
  w=10000;
  g=0;
  nw=1;
  ng1=0;
  ng2=0;
  t=0;
  while true
    ws=1256*nw;
    gs=8000+2000*ng1+24000*ng2;
    dtw=(1000000-g)/gs;
    f1=(ng1 < n);
    if f1; w0=64000; else w0=512000; endif
    dtg=(w0-w)/ws;
    if dtw < dtg
      t=t+dtw;
      w=w+dtw*ws;
      g=g+dtw*gs-1000000;
      nw=nw+1;
    else
      t=t+dtg;
      w=w+dtg*ws-w0;
      g=g+dtg*gs;
      if f1; ng1=ng1+1; else ng2=ng2+1; endif
    endif
%    printf(" %g", [t nw ng1 ng2 w g]);
%    printf("\n");
    if ng2==3; break; endif
  endwhile
  r=t;
endfunction


Лучше считать, как у меня.
Делать сразу большие шаги по времени до следующей постройки, не шаги по 1 секунде, как в питон-скрипте.

[Albus]

Нет, это из-за того что в начале 0 дерева, а не 10к.
Сделал у себя ноль, получил:

Код: Выбрать все

414.61 403.32 404.21 403.44 405.37 409.16 411.63 415.24 419.18 422.56 426.38

Вот, если интеерсно, код Matlab для подсчёта:

Делал для 10к дерева. Для нуля вышло

Код: Выбрать все

418 406 408 408 409 413 415 420 423 427 431

Интересно) Если че, вот код, можно проверить в любом онлайн компиляторе питона

Код: Выбрать все

 wisp=1
gold1=0
gold2=0
g=0
w=10000
t=0
while gold2<4:
    g+=gold1*2000+gold2*24000+8000
    w+=wisp*1250
    if gold1<4:
        if w>=64000:
           gold1+=1
           w-=64000
    if w>=512000:
       gold2+=1
       w-=512000
    if g>=1000000:
       g=0
       wisp+=1
    t+=1
       
print(t) 


Делать сразу большие шаги по времени до следующей постройки, не шаги по 1 секунде, как в питон-скрипте.

Эт да, но лень было заморачиваться

[zykov]

Source of the post w+=wisp*1250

Почему 1250? В условии было 1256...

[Albus]

Source of the post w+=wisp*1250

Почему 1250? В условии было 1256...

Ой, да, но это даст ускорение порядка секунды
(для трех шахт2)

Код: Выбрать все

414 402 403 402 404 408 410 414 418 422 426

[zykov]

Ну и ошибка округления до целых накапливается.
Можете у себя в скрипте заменить шаг "1 секунда" на шаг "0.1 секунда" и посмотреть.

[zykov]

Сам попробовал сделать шаг 0.001

Код: Выбрать все

wisp=1
gold1=0
gold2=0
g=0
w=10000
t=0
while gold2<3:
    g+=(gold1*2000+gold2*24000+8000)/1000
    w+=(wisp*1256)/1000
    if gold1<3:
        if w>=64000:
           gold1+=1
           w-=64000
    if w>=512000:
       gold2+=1
       w-=512000
    if g>=1000000:
       g=0
       wisp+=1
    t+=0.001
       
print(t)

Получилось 399.491 для gold1=3 и gold2=3.
Так что это просто ошибка округления из-за шага в 1 секунду.

[Albus]

Точно Это мое выше

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

[zykov]

Не только, там везде ошибка округления.
Скажем, шахту можно построить в 272.7с, а у вас она построится только в 273с.
А могла бы давать золото уже 0.3с.
7200 золота потеряно.

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