In-Development TradeDangerous: power-user trade optimizer

Avi0013 · Jun 21, 2018

For Mark's case, I get the same results with simple as I do limited recursion, but the simple takes ~57 seconds and the limited took about 88 seconds.

SIMPLE IS FIRST:

F:\Elite\TD>trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress
* Hop 1: .........1 origins
* Hop 2: .....1,538 origins .. 5,040-2,981,520cr gain, 7-4,141cr/ton
Orang/Bessel Gateway -> Orang/Bessel Gateway (score: 1708820.401607)

Load from Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
720 x Slavery/Imperial Slaves 14,339cr vs 17,539cr, 12 hrs vs 26 days
Expect to gain 2,304,000cr (3,200cr/ton)

Load from Ju Shosi/De Lay Point (2.07Kls, BMk:N, Pad:L, Plt:Y, Shp:N, Out:Y, Ref:Y):
628 x Weapons/Reactive Armour 833cr vs 2,441cr, 26 days vs 12 hrs
92 x Weapons/Non-lethal Weapons 632cr vs 1,766cr, 26 days vs 12 hrs
Expect to gain 1,114,152cr (1,547.43cr/ton)
----------------------------------------------------------------------------
Finish at Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 3,418,152cr (2,373cr/ton) => est 11,003,418,152cr total

F:\Elite\TD>trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress
* Hop 1: .........1 origins
* Hop 2: .....1,538 origins .. 5,040-2,981,520cr gain, 7-4,141cr/ton
Orang/Bessel Gateway -> Orang/Bessel Gateway (score: 1708820.401607)

Load from Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
720 x Slavery/Imperial Slaves 14,339cr vs 17,539cr, 12 hrs vs 26 days
Expect to gain 2,304,000cr (3,200cr/ton)

Load from Ju Shosi/De Lay Point (2.07Kls, BMk:N, Pad:L, Plt:Y, Shp:N, Out:Y, Ref:Y):
628 x Weapons/Reactive Armour 833cr vs 2,441cr, 26 days vs 12 hrs
92 x Weapons/Non-lethal Weapons 632cr vs 1,766cr, 26 days vs 12 hrs
Expect to gain 1,114,152cr (1,547.43cr/ton)
----------------------------------------------------------------------------
Finish at Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 3,418,152cr (2,373cr/ton) => est 11,003,418,152cr total

Now for Tromodor's case. Here, both routines took abouy 28 seconds.

SIMPLE IS FIRST:

F:\Elite\TD>trade.py run --from fujin --to fujin --hops 4 --age 2 -vvv --summary --pla=YN? --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress --pad-size=L
* Hop 1: .........1 origins
* Hop 2: .......261 origins .. 648-180,600cr gain, 9-1,204cr/ton
* Hop 3: .....1,341 origins .. 7,060-741,930cr gain, 23-2,473cr/ton
NOTE: Pruned 2192 origins too far from any end stations
* Hop 4: .......339 origins .. 536,700-1,165,918cr gain, 1,192-2,590cr/ton
Fujin/Futen Spaceport -> Fujin/Futen Spaceport (score: 1315679.347652)
Start CR: 35,000,000
Hops : 4
Jumps : 8
Gain CR : 1,312,668
Gain/Hop: 328,167
Final CR: 36,312,668

Load from Fujin/Futen Spaceport (560ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
72 x Textiles/Natural Fabrics 352cr vs 815cr, 4 hrs vs 3 hrs, total: 25,344cr
78 x Textiles/Leather 204cr vs 615cr, 4 hrs vs 3 hrs, total: 15,912cr
Expect to gain 65,394cr (435.96cr/ton)

Load from GCRV 1568/Cernan Dock (1.36Kls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 246cr vs 4,723cr, 3 hrs vs 4 hrs, total: 36,900cr
Expect to gain 671,550cr (4,477cr/ton)

Load from Daruwutja/Acropolis (740ls, BMk:N, Pad:L, Plt:N, Shp:N, Out:Y, Ref:Y):
142 x Weapons/Reactive Armour 227cr vs 2,664cr, 5 hrs, total: 32,234cr
8 x Weapons/Personal Weapons 416cr vs 3,531cr, 5 hrs, total: 3,328cr
Expect to gain 370,974cr (2,473.16cr/ton)

Load from Snoquot/Wrangell City (71ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Machinery/Marine Equipment 3,621cr vs 4,986cr, 5 hrs vs 4 hrs, total: 543,150cr
Expect to gain 204,750cr (1,365cr/ton)
----------------------------------------------------------------------------
Finish at Fujin/Futen Spaceport (560ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,312,668cr (2,187cr/ton) => est 51,312,668cr total

F:\Elite\TD>trade.py run --from fujin --to fujin --hops 4 --age 2 -vvv --summary --pla=YN? --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress --pad-size=L
* Hop 1: .........1 origins
* Hop 2: .......261 origins .. 648-180,600cr gain, 9-1,204cr/ton
* Hop 3: .....1,341 origins .. 7,060-741,930cr gain, 23-2,473cr/ton
NOTE: Pruned 2192 origins too far from any end stations
* Hop 4: .......339 origins .. 536,700-1,165,918cr gain, 1,192-2,590cr/ton
Fujin/Futen Spaceport -> Fujin/Futen Spaceport (score: 1315679.347652)
Start CR: 35,000,000
Hops : 4
Jumps : 8
Gain CR : 1,312,668
Gain/Hop: 328,167
Final CR: 36,312,668

Load from Fujin/Futen Spaceport (560ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
72 x Textiles/Natural Fabrics 352cr vs 815cr, 4 hrs vs 3 hrs, total: 25,344cr
78 x Textiles/Leather 204cr vs 615cr, 4 hrs vs 3 hrs, total: 15,912cr
Expect to gain 65,394cr (435.96cr/ton)

Load from GCRV 1568/Cernan Dock (1.36Kls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 246cr vs 4,723cr, 3 hrs vs 4 hrs, total: 36,900cr
Expect to gain 671,550cr (4,477cr/ton)

Load from Daruwutja/Acropolis (740ls, BMk:N, Pad:L, Plt:N, Shp:N, Out:Y, Ref:Y):
142 x Weapons/Reactive Armour 227cr vs 2,664cr, 5 hrs, total: 32,234cr
8 x Weapons/Personal Weapons 416cr vs 3,531cr, 5 hrs, total: 3,328cr
Expect to gain 370,974cr (2,473.16cr/ton)

Load from Snoquot/Wrangell City (71ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Machinery/Marine Equipment 3,621cr vs 4,986cr, 5 hrs vs 4 hrs, total: 543,150cr
Expect to gain 204,750cr (1,365cr/ton)
----------------------------------------------------------------------------
Finish at Fujin/Futen Spaceport (560ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,312,668cr (2,187cr/ton) => est 51,312,668cr total

Now the next case is interesting. The first entry is the limited recursion, it took 120 seconds, and ended returning a worse result than the simple fit, which took around 40 seconds.

F:\Elite\TD>trade.py run --from "HYL/Sch" --to "SIGRU/Hern" --hops 3 -vvv --summary --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress
* Hop 1: .........1 origins
* Hop 2: .....1,083 origins .. 4,050-483,000cr gain, 27-3,220cr/ton
NOTE: Pruned 5288 origins too far from any end stations
* Hop 3: .....1,717 origins .. 435,900-1,060,800cr gain, 1,453-3,536cr/ton
Hyldeptu/Schroeder Gateway -> Sigru/Hernandez Gateway (score: 1200793.100512)
Start CR: 35,000,000
Hops : 3
Jumps : 5
Gain CR : 1,204,266
Gain/Hop: 401,422
Final CR: 36,204,266

Load from Hyldeptu/Schroeder Gateway (922ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Technology/Robotics 1,957cr vs 3,911cr, 13 hrs vs 25 days, total: 293,550cr
Expect to gain 293,100cr (1,954cr/ton)

Load from Snotricopa/Hobaugh Settlement (872ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 51cr vs 5,116cr, 25 days vs 32 days, total: 7,650cr
Expect to gain 759,750cr (5,065cr/ton)

Load from Wolf 265/Felice Prospect (7.38Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:N, Ref:Y):
71 x Metals/Titanium 563cr vs 1,423cr, 32 days vs 28 days, total: 39,973cr
33 x Metals/Uranium 2,113cr vs 3,239cr, 32 days vs 28 days, total: 69,729cr
20 x Metals/Gallium 4,419cr vs 5,845cr, 32 days vs 28 days, total: 88,380cr
18 x Metals/Indium 5,163cr vs 6,534cr, 32 days vs 28 days, total: 92,934cr
Expect to gain 151,416cr (1,066.31cr/ton)
----------------------------------------------------------------------------
Finish at Sigru/Hernandez Gateway (10ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,204,266cr (2,724cr/ton) => est 51,204,266cr total

F:\Elite\TD>trade.py run --from "HYL/Sch" --to "SIGRU/Hern" --hops 3 -vvv --summary --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress
* Hop 1: .........1 origins
* Hop 2: .....1,083 origins .. 4,050-483,000cr gain, 27-3,220cr/ton
NOTE: Pruned 5288 origins too far from any end stations
* Hop 3: .....1,717 origins .. 435,900-1,060,800cr gain, 1,453-3,536cr/ton
Hyldeptu/Schroeder Gateway -> Sigru/Hernandez Gateway (score: 1226335.845144)
Start CR: 35,000,000
Hops : 3
Jumps : 5
Gain CR : 1,229,734
Gain/Hop: 409,911
Final CR: 36,229,734

Load from Hyldeptu/Schroeder Gateway (922ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Technology/Robotics 1,957cr vs 3,911cr, 13 hrs vs 25 days, total: 293,550cr
Expect to gain 293,100cr (1,954cr/ton)

Load from Snotricopa/Hobaugh Settlement (872ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 51cr vs 5,116cr, 25 days vs 32 days, total: 7,650cr
Expect to gain 759,750cr (5,065cr/ton)

Load from Wolf 265/Felice Prospect (7.38Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:N, Ref:Y):
33 x Metals/Uranium 2,113cr vs 3,239cr, 32 days vs 28 days, total: 69,729cr
20 x Metals/Gallium 4,419cr vs 5,845cr, 32 days vs 28 days, total: 88,380cr
18 x Metals/Indium 5,163cr vs 6,534cr, 32 days vs 28 days, total: 92,934cr
27 x Metals/Titanium 563cr vs 1,423cr, 32 days vs 28 days, total: 15,201cr
16 x Industrial Materials/Superconductors 5,904cr vs 7,222cr, 32 days vs 28 days, total: 94,464cr
10 x Metals/Cobalt 233cr vs 1,106cr, 32 days vs 28 days, total: 2,330cr
5 x Metals/Beryllium 7,299cr vs 9,024cr, 32 days vs 28 days, total: 36,495cr
8 x Industrial Materials/Semiconductors 443cr vs 1,335cr, 32 days vs 28 days, total: 3,544cr
5 x Metals/Lithium 1,102cr vs 2,146cr, 32 days vs 28 days, total: 5,510cr
3 x Metals/Silver 4,032cr vs 5,508cr, 32 days vs 28 days, total: 12,096cr
3 x Metals/Tantalum 3,258cr vs 4,626cr, 32 days vs 28 days, total: 9,774cr
1 x Industrial Materials/Insulating Membrane 9,323cr vs 11,580cr, 32 days vs 28 days, total: 9,323cr
1 x Metals/Gold 9,155cr vs 10,875cr, 32 days vs 28 days, total: 9,155cr
Expect to gain 176,884cr (1,179.23cr/ton)
----------------------------------------------------------------------------
Finish at Sigru/Hernandez Gateway (10ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,229,734cr (2,732cr/ton) => est 51,229,734cr total

Clearly the greedy algorithm when applied to the capacity constraint ordered by profit (since weights are 1 as they are all tons) is finding a more lucrative use of the capacity going from Wolf 265/Felice Prospect to Sigru/Hernandez. The profit table of this one hop is:

Code:

F:\Elite\TD>trade trade "Wolf 265/Felice Prospec" "SIGR/Hern" -vvv
Item                                         Profit       Cost    AvgCost     Buying     AvgBuy     Supply     Demand   SrcAge   DstAge
---------------------------------------------------------------------------------------------------------------------------------------
Industrial Materials/Insulating Membrane      2,257      9,323       9926      11580      10913          1      7,153    32.96    28.59
Metals/Beryllium                              1,725      7,299       7594       9024       8216          5     21,530    32.96    28.59
Metals/Gold                                   1,720      9,155       9206      10875       9837          1     12,116    32.96    28.59
Metals/Silver                                 1,476      4,032       4360       5508       4813          3    132,005    32.96    28.59
Metals/Gallium                                1,426      4,419       4666       5845       5152         20     30,152    32.96    28.59
Metals/Indium                                 1,371      5,163       5375       6534       5805         18     13,213    32.96    28.59
Metals/Tantalum                               1,368      3,258       3543       4626       3994          3    225,091    32.96    28.59
Industrial Materials/Superconductors          1,318      5,904       6137       7222       6663         16     34,550    32.96    28.59
Metals/Uranium                                1,126      2,113       2388       3239       2782         33    206,888    32.96    28.59
Metals/Lithium                                1,044      1,102       1402       2146       1715          5     59,826    32.96    28.59
Industrial Materials/Semiconductors             892        443        813       1335       1082          8     70,587    32.96    28.59
Metals/Cobalt                                   873        233        629       1106        740         10     63,879    32.96    28.59
Metals/Titanium                                 860        563        914       1423       1137         71     81,523    32.96    28.59
Metals/Copper                                   482        425        441        907        607         42    153,165    32.96    28.59
Textiles/Conductive Fabrics                     447        521        561        968        869         14    172,669    32.96    28.59
Industrial Materials/Polymers                   444        132        115        576        323         58    335,369    32.96    28.59
Metals/Aluminium                                419        243        300        662        463         59    202,272    32.96    28.59
Textiles/Synthetic Fabrics                      263        120        154        383        332         41    492,570    32.96    28.59
Chemicals/Explosives                            172        193        281        365        436         15     14,067    32.96    28.59

I have no idea what the limited recursion is doing, but the greedy algorithm is clearly sweeping up all those lucrative limited supply items (like Insulating Membranes and Beryllium) first before spending credits on other items like Titanium. The greedy algorithm happens to also be the exact (optimal) BKP solution in this case and up to a capacity of 420. Beyond that, the C-code for BKP crashes out

eyeonus said:
I said should.... So it's only 99.7% of the time. I'm okay with that.

I'm an actuary; we're supposed to be frustratingly pedantic like that

eyeonus said:
Well, thank Oliver for that. The list gets passed in sorted on profit, with lower cost winning when profits are tied.

Oh yeah, that video that shows the thing never actually freezes, and hints as to why it's being so slow:
https://youtu.be/fkCjyXC1n2A

Yes, sorting, even worst case, is O(n^2) and most decent implementations are O(n log n). Actual recursion is going to be exponential O(2^n) as this is NP-hard so you have to assume enumeration of all possibilities. YOUCH!

Tromador · Jun 21, 2018

Avi0013 said:
I'm an actuary; we're supposed to be pedantic like that.

Normally I am all for pedantry, grammar facism, spelling mockery and the like, but I think in this thread, where all of us are likely of that mindset, there is a large risk of getting sidetracked into unnecessary detail rather than dealing with the substance, so probably best avoided if possible.

eyeonus · Jun 21, 2018

Avi0013 said:
Now the next case is interesting. The first entry is the limited recursion, it took 120 seconds, and ended returning a worse result than the simple fit, which took around 40 seconds.

F:\Elite\TD>trade.py run --from "HYL/Sch" --to "SIGRU/Hern" --hops 3 -vvv --summary --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress
* Hop 1: .........1 origins
* Hop 2: .....1,083 origins .. 4,050-483,000cr gain, 27-3,220cr/ton
NOTE: Pruned 5288 origins too far from any end stations
* Hop 3: .....1,717 origins .. 435,900-1,060,800cr gain, 1,453-3,536cr/ton
Hyldeptu/Schroeder Gateway -> Sigru/Hernandez Gateway (score: 1200793.100512)
Start CR: 35,000,000
Hops : 3
Jumps : 5
Gain CR : 1,204,266
Gain/Hop: 401,422
Final CR: 36,204,266

Load from Hyldeptu/Schroeder Gateway (922ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Technology/Robotics 1,957cr vs 3,911cr, 13 hrs vs 25 days, total: 293,550cr
Expect to gain 293,100cr (1,954cr/ton)

Load from Snotricopa/Hobaugh Settlement (872ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 51cr vs 5,116cr, 25 days vs 32 days, total: 7,650cr
Expect to gain 759,750cr (5,065cr/ton)

Load from Wolf 265/Felice Prospect (7.38Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:N, Ref:Y):
71 x Metals/Titanium 563cr vs 1,423cr, 32 days vs 28 days, total: 39,973cr
33 x Metals/Uranium 2,113cr vs 3,239cr, 32 days vs 28 days, total: 69,729cr
20 x Metals/Gallium 4,419cr vs 5,845cr, 32 days vs 28 days, total: 88,380cr
18 x Metals/Indium 5,163cr vs 6,534cr, 32 days vs 28 days, total: 92,934cr
Expect to gain 151,416cr (1,066.31cr/ton)
----------------------------------------------------------------------------
Finish at Sigru/Hernandez Gateway (10ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,204,266cr (2,724cr/ton) => est 51,204,266cr total

F:\Elite\TD>trade.py run --from "HYL/Sch" --to "SIGRU/Hern" --hops 3 -vvv --summary --credits=50000000 --capacity=150 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress
* Hop 1: .........1 origins
* Hop 2: .....1,083 origins .. 4,050-483,000cr gain, 27-3,220cr/ton
NOTE: Pruned 5288 origins too far from any end stations
* Hop 3: .....1,717 origins .. 435,900-1,060,800cr gain, 1,453-3,536cr/ton
Hyldeptu/Schroeder Gateway -> Sigru/Hernandez Gateway (score: 1226335.845144)
Start CR: 35,000,000
Hops : 3
Jumps : 5
Gain CR : 1,229,734
Gain/Hop: 409,911
Final CR: 36,229,734

Load from Hyldeptu/Schroeder Gateway (922ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Technology/Robotics 1,957cr vs 3,911cr, 13 hrs vs 25 days, total: 293,550cr
Expect to gain 293,100cr (1,954cr/ton)

Load from Snotricopa/Hobaugh Settlement (872ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
150 x Medicines/Basic Medicines 51cr vs 5,116cr, 25 days vs 32 days, total: 7,650cr
Expect to gain 759,750cr (5,065cr/ton)

Load from Wolf 265/Felice Prospect (7.38Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:N, Ref:Y):
33 x Metals/Uranium 2,113cr vs 3,239cr, 32 days vs 28 days, total: 69,729cr
20 x Metals/Gallium 4,419cr vs 5,845cr, 32 days vs 28 days, total: 88,380cr
18 x Metals/Indium 5,163cr vs 6,534cr, 32 days vs 28 days, total: 92,934cr
27 x Metals/Titanium 563cr vs 1,423cr, 32 days vs 28 days, total: 15,201cr
16 x Industrial Materials/Superconductors 5,904cr vs 7,222cr, 32 days vs 28 days, total: 94,464cr
10 x Metals/Cobalt 233cr vs 1,106cr, 32 days vs 28 days, total: 2,330cr
5 x Metals/Beryllium 7,299cr vs 9,024cr, 32 days vs 28 days, total: 36,495cr
8 x Industrial Materials/Semiconductors 443cr vs 1,335cr, 32 days vs 28 days, total: 3,544cr
5 x Metals/Lithium 1,102cr vs 2,146cr, 32 days vs 28 days, total: 5,510cr
3 x Metals/Silver 4,032cr vs 5,508cr, 32 days vs 28 days, total: 12,096cr
3 x Metals/Tantalum 3,258cr vs 4,626cr, 32 days vs 28 days, total: 9,774cr
1 x Industrial Materials/Insulating Membrane 9,323cr vs 11,580cr, 32 days vs 28 days, total: 9,323cr
1 x Metals/Gold 9,155cr vs 10,875cr, 32 days vs 28 days, total: 9,155cr
Expect to gain 176,884cr (1,179.23cr/ton)
----------------------------------------------------------------------------
Finish at Sigru/Hernandez Gateway (10ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 1,229,734cr (2,732cr/ton) => est 51,229,734cr total

Clearly the greedy algorithm when applied to the capacity constraint ordered by profit (since weights are 1 as they are all tons) is finding a more lucrative use of the capacity going from Wolf 265/Felice Prospect to Sigru/Hernandez.

The reason for this is quite simple and rather obvious if you think about it. Limiting the recursion means limiting the max amount of different items per station. With a recursion limit of four, the algorithm will never find a solution at a station that involves more than 4 different items. That's why the limited recursion's item list is so much shorter than the simple's item list. I mean, it looks to me like we bought the everything at that station in the simple list.

I don't think limiting recursion is a good solution.

Possibly limiting the max offset that's allowed to recurse to, say 10? In other words, find the best solution, including recursion, up to item10, but from that point on don't allow any recursion and just assume we've found the best one? Or maybe go hybrid and finish off everything past item10 with the simpleFit algorithm?

Avi0013 · Jun 21, 2018

I'm happy killing the recursion completely. The LBKP algorithm is in the worst case, very good, and in the best case, the exact optimal solution. It's only off by a handful of switches around the break item, and it's polynomial time instead of exponential time. I agree that limiting recursion is suboptimal, I didn't realize just HOW suboptimal it was. Time to go all Red Queen on that subroutine

eyeonus · Jun 21, 2018

Pushed. I think, with the new penalty formula and the new load algorithm, we've just solved the two biggest problems in TD. Hip hip?

Avi0013 · Jun 21, 2018

eyeonus said:
Pushed. I think, with the new penalty formula and the new load algorithm, we've just solved the two biggest problems in TD. Hip hip?

HOORAY!![up][up][up]

Avi0013 · Jun 21, 2018

Can you imagine doing this under recursion? Yes, this took 13 minutes on my machine, and it's not eligible for parallel processing since it's dependant, but TD checked over 26K stations in 13 minutes. That's pretty sweet!

F:\Elite\TD>trade.py run --from "HYL/Sch" --hops 4 --jumps 2 -vvv --summary --credits=50000000 --capacity=250 --ly-per=29.09 --empty-ly=33.31 --insurance=15000000 --progress
* Hop 1: .........1 origins
* Hop 2: .....1,083 origins .. 6,750-805,000cr gain, 27-3,220cr/ton
* Hop 3: .....7,005 origins .. 193,750-1,768,000cr gain, 387-3,536cr/ton
* Hop 4: ....18,584 origins .. 336,750-2,622,000cr gain, 449-3,530cr/ton
Hyldeptu/Schroeder Gateway -> HIP 17118/Vries Landing (score: 3664003.862396)
Start CR: 35,000,000
Hops : 4
Jumps : 8
Gain CR : 3,678,826
Gain/Hop: 919,706
Final CR: 38,678,826

Load from Hyldeptu/Schroeder Gateway (922ls, BMk:Y, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
250 x Textiles/Military Grade Fabrics 966cr vs 4,110cr, 15 hrs vs 10 days, total: 241,500cr
Expect to gain 786,000cr (3,144cr/ton)

Load from Hyades Sector OO-P b6-4/Coblentz Silo (32ls, BMk:N, Pad:L, Plt:Y, Shp:N, Out:Y, Ref:Y):
248 x Weapons/Reactive Armour 1,800cr vs 4,043cr, 10 days vs 23 days, total: 446,400cr
2 x Weapons/Non-lethal Weapons 1,416cr vs 3,197cr, 10 days vs 23 days, total: 2,832cr
Expect to gain 559,826cr (2,239.3cr/ton)

Load from Kim 2-17/Rutherford Landing (25Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:Y, Ref:Y):
250 x Metals/Tantalum 2,245cr vs 5,261cr, 23 days vs 24 days, total: 561,250cr
Expect to gain 754,000cr (3,016cr/ton)

Load from 36 Persei/Busch Port (4.88Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:N, Ref:Y):
250 x Medicines/Basic Medicines 102cr vs 6,418cr, 24 days vs 24 days, total: 25,500cr
Expect to gain 1,579,000cr (6,316cr/ton)
----------------------------------------------------------------------------
Finish at HIP 17118/Vries Landing (16Kls, BMk:Y, Pad:M, Plt:N, Shp:N, Out:N, Ref:Y) gaining 3,678,826cr (3,678cr/ton) => est 53,678,826cr total

MarkAusten · Jun 21, 2018

eyeonus said:
Pushed. I think, with the new penalty formula and the new load algorithm, we've just solved the two biggest problems in TD. Hip hip?

HUZZAH!

MarkAusten · Jun 21, 2018

Avi0013 said:
Mark, this is great, but what are your starting credits, or can I assume that you the 928,245 cr you would need to buy out the entire stock?

11 billion, effectively making the problem purely a bounded knapsack problem.

MarkAusten · Jun 21, 2018

Avi0013 said:
I'm an actuary; we're supposed to be frustratingly pedantic like that

And I'm an engineer and you probably know the joke about engineers and mathematicians.

eyeonus · Jun 21, 2018

MarkAusten said:
And I'm an engineer and you probably know the joke about engineers and mathematicians.

Which one? There's thousands.

For example:

A mathematician, a physicist, and an engineer are riding a train through Scotland.

The engineer looks out the window, sees a black sheep, and exclaims, "Hey! They've got black sheep in Scotland!"

The physicist looks out the window and corrects the engineer, "Strictly speaking, all we know is that there's at least one black sheep in Scotland."

The mathematician looks out the window and corrects the physicist, " Strictly speaking, all we know is that is that at least one side of one sheep is black in Scotland."

Or how about this one:

An engineer and a mathematician have to build a fence around a flock of sheep, using as little material as possible.

The engineer forms the flock into a circular shape and constructs a fence around it.

The mathematician thinks for a while, then builds a fence around himself and defines himself as being outside.

Hey, let's throw a physicist into the mix as well:

A Statistician, Engineer and Physicist go to the horse track. Each have their system for betting on the winner and they're sure of it.

After the race is over, the Statistician wanders into the nearby bar, defeated. He notices the Engineer, sits down next to him, and begins lamenting: "I don't understand it. I tabulated the recent performance of all these horses, cross-referenced them with trends for others of their breed, considered seasonal variability, everything. I couldn't have lost."

"Yeah," says the Engineer, "well, forget that. I ran simulations based on their weight, mechanical ratios, performance models, everything, and I'm no better off."

Suddenly, they notice a commotion in the corner. The Physicist is sitting there, buying rounds and counting his winnings. The Engineer and Statistician decide they've got to know, so they shuffle over and ask him, "what's your secret, how'd you do it?"

The Physicist leans back, takes a deep breath, and begins, "Well, first I assumed all the horses were spherical and identical..."

MarkAusten · Jun 21, 2018

eyeonus said:
Which one? There's thousands:

An engineer and a mathematician are put into a room 20 feet square and told to stand with their backs to opposite walls. In the centre of the room stands a naked object of their desire. They are then told that they can half the distance between them and centre of the room every 10 seconds. The Mathematician walks out of the room stating that the was an impossible task since he would never reach his objective. The engineer, however, says that he will happily do this since in a minute or so he would be close enough for all practical purposes.

MarkAusten · Jun 21, 2018

As a quick test I ran the following command on the data as at 2018.06.21 07:00:00:

trade.py run --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --max-days-old=3 --ls-max=500 --supply=10000 --loop --summary -vv --progress

Note that this has no starting station but does have a limit on price age, supply and ls-to-station. It ran in 1m 29s finding a route that had a profit of 4,022,640 Cr.

I'd say that Eyeonus is correct, this is now useful again.

Then removing the ls-to-station limit ran the routine in 3m 31s for a profit of 4,558, 320 Cr.
Then removing the supply limit ran the routine in 4m 34ss for a profit of 4,777,200 Cr.
Then removing the price age ran the routine in 44m 11s for a profit of Cr 5,287,680 Cr.

I wouldn't normally bother removing the price age limit, I generally run with a max of 3 days here. Personally I think that the price age should be a mandatory parameter in the range 1-7 defaulting to 3. Allowing an unbounded price age make no sense to me. It also really increases the run time as you can see from the above.

eyeonus · Jun 21, 2018

Just remember that there are 10 kinds of people in the world:

Those that don't understand binary representation, and those that do.

eyeonus · Jun 21, 2018

I disagree for one very simple reason- if everyone only ever goes to the stations with recent data, the stations with older data will never get visited, which means the data will never get updated, and it's entirely possible that if that data did get updated, you might get a better run than if it wasn't updated and you ignored it.

In my experience, there are only two kinds of commanders that visit a variety of systems- traders and explorers, and explorers spend most of their time in uninhabited systems. Bounty hunters, etc., tend to stick to the same system, re-docking at the same port over and over again, so the only people we can depend on to get the old data updated is traders willing to gamble on visiting stations with old data.

Personally, I'm willing to take a short-term loss in profit to go update a station with older data since it means everyone, including me, will have more up-to-date data from that station once I have visited it, which means more accurate results from the next trade run I do. With that in mind, I never put an age limit on my runs.

Also, the time increase you see is because you were looking for the highest possible trade in the known universe. I'm willing to bet that if you had removed the age limit first, you'd now be blaming the supply limit for drastic time increase.

I doubt there's nearly so much of an increase in realistic runs, of the "give me 4 hops starting from here" variety.

Runs those again with a starting station and let's see the run-time measurements. Even better, run those commands with every combination of those limits and let's see how they stack up.

MarkAusten · Jun 21, 2018

eyeonus said:
I disagree for one very simple reason- if everyone only ever goes to the stations with recent data, the stations with older data will never get visited, which means the data will never get updated, and it's entirely possible that if that data did get updated, you might get a better run than if it wasn't updated and you ignored it.

Also, the time increase you see if because you were looking for the highest possible trade in the known universe. I doubt there's nearly so much of an increase in realistic runs, of the "give me 4 hops starting from here" variety.

Runs those again with a starting station and let's see the run-time measurements.

Personally, I'm willing to take a short-term loss in profit to go update a station with older data since it means everyone, including me, will have more up-to-date data from that station once I have visited it, which means more accurate results from the next trade run I do. With that in mind, I never put an age limit on my runs.

Fair point.

I have to say that so far I've never found a route with a price age over 7 days that turned out to be that profitable, but I do take your point about visiting little visited stations. To use your argument further, you probably should occasionally run the known universe option to find those stations that are even less visited that are not in your locality.

eyeonus · Jun 21, 2018

MarkAusten said:
Fair point.

I have to say that so far I've never found a route with a price age over 7 days that turned out to be that profitable, but I do take your point about visiting little visited stations. To use your argument further, you probably should occasionally run the known universe option to find those stations that are even less visited that are not in your locality.

TD has the "olddata" command for just that- finding the station with the oldest data in the database.

eyeonus · Jun 21, 2018

Okay, so this is more for me because I want to get this down before I forget and I'm about to go to work so I don't have time to work on this right now, but I thought I'd put it here because I think you guys should know this is a thing, and maybe one of you will take a crack at it and give me a PR, thus saving me a bit of effort:

Solution to problem of commodities that have been removed as a saleable item from a station not being updated as such and remaining in DB with the old data, because both EDDN and EDDB updates do not include removed items:
(To be implemented in the listener's message processor method):
Create a Dict of the commodities list containing each of the commodities, already processed and ready for insertion. (Basically what's being done now, except that as it is now it inserts directly after processing.)
--side note: Make sure the key for each entry in the Dict is the name of the commodity, so e.g. processed_item['Hydrogen Fuel'] = (demand_price = commodity['sellPrice'], ...)
Loop through the item_ids keys and

Code:

for each key:
    if key in processed_item:
        to_insert = processed_item[key]
    else:
        to_insert = 0'd entry
perform insert

By 0'd entry, TD has a set of values for listings that will cause TD to auto-remove them the next time it reloads the DB, and ignore them until then. Refer to the TD documentation on CORRECTIONS to find out what it is. (Pretty sure it's just every value set to 0, including the timestamp.)
--sidenote - from_live must be set to 1 when inseting a 0'd entry so that the listings exporter will include it in the live file, ensuring it gets propagated to all the clients. TD ignores from_live, so this is not a problem.

CMDR Ibizan · Jun 21, 2018

eyeonus said:
TD has the "olddata" command for just that- finding the station with the oldest data in the database.

Ah, something I can comment on. Thanks and rep to those of you involved in the discussion over the past few days but as most of it went so far over my head there wasn’t anything I could say on the matter. I did think at one point that you’d forgotten that “It’s only a game!” (can I say that?) but it all came together in the end. Well done and thanks again.

Oh yes, my comment - almost forgot. I normally play Elite with my brother in a wing and very often use the olddata to find stations nearby that need an update and visit them while I am waiting for said wingmate to report for duty. We both use TD Helper GUI and it cheered us both up when Mark started looking at updating it. A TD request please. When running the olddata command it always gives stations with both large and medium landing pads in the results even though we use —pad=L. Not a huge problem but it would be good to be able to filter out the medium ones that neither of us can use.

Now I just need to go through the previous few pages to find where I can download this new updated version of TD!

Thanks again guys.....

eyeonus · Jun 21, 2018

CMDR Ibizan said:
Ah, something I can comment on. Thanks and rep to those of you involved in the discussion over the past few days but as most of it went so far over my head there wasn’t anything I could say on the matter. I did think at one point that you’d forgotten that “It’s only a game!” (can I say that?) but it all came together in the end. Well done and thanks again.

Oh yes, my comment - almost forgot. I normally play Elite with my brother in a wing and very often use the olddata to find stations nearby that need an update and visit them while I am waiting for said wingmate to report for duty. We both use TD Helper GUI and it cheered us both up when Mark started looking at updating it. A TD request please. When running the olddata command it always gives stations with both large and medium landing pads in the results even though we use —pad=L. Not a huge problem but it would be good to be able to filter out the medium ones that neither of us can use.

Now I just need to go through the previous few pages to find where I can download this new updated version of TD!

Thanks again guys.....

https://github.com/eyeonus/Trade-Dangerous

Keep in mind this is a beta and not considered ready for release yet. Use at your own risk. (I don't think you'll have any problems, but fair warning.)

Also, submit that request as an issue on the github or I'll forget about it.