Optimal Ptrading has nothing to do with a list.
The very use of a list precludes any optimal variation.
A list of any sectors will result in only one optimal route in most cases.
Perhaps more if the subset is big enough but as the same end result as to amount of ore will be the same what would be the point of looking for it. A simple bfs which filters the port data inside it will not result in the most efficient route to sell product.






Sorry for the hijack Helix but the whole file thing was covered in the first couple posts...Read file...optimize the route...party over.


I was trying to discuss ptrading in general. As I suspected you had a reason to use a list which has nothing to do with general ptrading. OZ came out with a ptrader using a bfs. And I was happy with that for years but it is not the most efficient...the reason for this is it doesn't factor in the unkown. It will go to the same port over and over if started in same place unless information is provided thru some other means..such as sharing a data base or importing swath synch info or visiting the sectors via a gridding script. This is the nature of math. If you establish the potential unknown then it can be used.


For example.


Sector 1000 (SBB) ==> (Sector 1101) ==> (Sector 1200) ==> Sector 1301 (SBB)

Lets assume that this route is gridded.
Lets also assume that there is a port in sector 1000 that meets our criteria for ptrading
Lets also assume that there is a port in sector 1301 that meets our criteria for ptrading

Our bfs ptrader will go from 1000 to 1301 using 1200 gas and trade happily.
If we have 50% port density then it is likely that a port exists in the unknown gridded sectors in between and lets assume that if there is a port there that meets our criteria for trading.

Our BFS ptrader would go right over it. Therefore missing the port which increase the efficiency.
Why? because it didn't take into account the potential "unknown" port. This is a simple example and there are more complicated ways of doing the math but it shows my point perfectly.

The use of 1200 gas to sell off to 2 ports....BFS

The use of 1200 gas to sell off to 3 ports (or at least the possiblility)...Parrots way.

(3 > 2) and always will be. Thats just the way it is. Based on the % of gridded unknown sectors and port density the number is significant.

Yes it does. And the question at hand was that he as a list,
and wants to read that list and visit it as efficiently as possible.

That was the problem at hand.



No it doesn't. If you have 2 ports to trade, A and B, and
the route between A and B is the same both ways, then
the optimal variation will be to trade the closest first.

Now this is where we diverge from an algorithmic solution
and the most optimal. If the route between A and B is not
the same both ways, then the sum of the distances must
be calculated and compared. Do that for 50 ports and you
rapidly reach a point beyond our current CPUs.



Yes, there is one optimal route. But as proven earlier, cash
is not a factor in that optimality. To further complicate things,
determining optimality is an NP-hard problem.



Again, given a list of ports you must trade, a simple BFS is
going to be more efficient than factoring in cash/ore. Nothing
you do can make profit exceed the sum of the ports.

Now, if the matter is about selecting ports rather than running
all of them, as I've said several times, then things vary. At
that point the goal is to select the best MCICs, provided they're
not very far away. But that goes to list selection, not running
the list.

Now there does exist heuristics that can improve a simple BFS,
but the improvement is minor, and not worth the time unless
you just enjoy doing it.

I think we covered the whole list thing nicely.
And its been covered many times on this forum.
Read list ==> optimize route ==> DONE.


I was attempting to segue the conversation to ptrading which I find more interesting.

Question comes then whether you're ptrading a list of
known ports or not. Once you reach a point where you
have a fixed list of ports, distance becomes the only
factor.

So the edge to be gained is when trading across small
non-upgraded ports, gathering MCICs for later upgrade,
and working from a list of MCICs gathered earlier.

Depending on the edits, that only lasts a day, so I haven't
put much time into building scripts for it. But, it is an area
that can be improved upon.

A bidirectional search is not the much more complicated than a breadthfirst search and could be very beneficial in universes with a lot of one way sectors. On the other hand, it takes a more processing and time to accomplish the goal, and may not be much more effective especially in higher turn games.

Trading a list usually means a bubble...so either some "strange truce utw unlim thing" OR a builder game.
I don't play the former and have just started in the latter. Being that the large bbl's are populated immediately then everyone knows where u and ALL your assets are. Seems to defeat the purpose of a low turn builder game with no probes but its predictable behavior. As I don't build in large bbl's I havent ever needed a list trader much. The few times we have needed one we just use the one vid wrote many years ago which handles multiple lists optimizes as it goes and does red rider robbing etc.

I would think a Farm script that jumps to the sector (either t or pwarp) and nego's the planets in place and picking up the fighters and maybe fuel etc would be more useful for bbl work.

Pwarp....get figs...nego planets...get fuel for battle planet...upgrade planets...Move on




Where you want to eke out the last drop from a ptrader is in a low turn game...Once its written for that purpose it will work just fine in an unlim. I macro buy my fuel in low turns usually as the red can just rob back the cash but with an option to best trade it. I could use Ephaggle to Blue trade but EP refuses to make his Haggle easy to use so its relegated to ppt duty only sad to say.

As far as processing time? Compared to the time it takes to buy 131 loads of fuel..Not really relevant unless it gets out of hand but it doesnt take long to run routes for 10 ports at a time in subsets and compare them. Also the getnearestwarp routine simplifies some of the search's you can do code wise.
I just use bfs variants now but getnearwarps might be faster in certain places

No, any upgraded list of ports constitutes a list.



Uhm, a truely multidirectional search is more complex than
that.

Consider this. With 2 ports, there exists 1 pair. With 3 ports,
there exists 3 pairs (AB, AC, BC). With 4 ports, there exist
6 pairs (AB, AC, AD, BC, BD, CD), with 5 ports, there exists
10 pairs (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE).

From this we can derive a simple equation to determine the
number of pairs in a set. Y = [N*(N-1)]/2

So for 5 we have (5*4)/2=10. Simple enough, right?

For 10 ports, we have (10*9)/2 or 45 possible pairs.

For 30 ports you have 15*29 = 435 possible pairs.

Now that assumes you're only trading 2 ports out of the list.
If you plan to trade more, it gets worse. The number of
subsets for a set is 2^N, ie: each element can be present
or not present. 2^30 = 1,073,741,824 possible subsets
(order not withstanding).

That assumes we allow ourselves to trade or not trade
any given port. if we must trade all ports, then we look
for the number of permutations. That's 30! = 30*29*28
*27*26!, etc, etc. That's... 3.653x10^32 number of
possible permutations.

This gets very complicated. If you can figure out a way to
test and find the most optimal path out of 3.653x10^32
possible permutations, then I am all ears. But if even each
permutation takes just 1ms, 1 millisecond, that's 8.388x10^21
years to search. I don't have that long.

Good luck.

Multidirectional search is comparing every port in the list to every other port in the list before you begin, and yes, that would be very complicated. When I said bidirectional search I meant checking the distance to and from each port in the list to position you are currently at, therefor eliminating the visited ports from the list as you proceed. Yes, you would have to run the bidirectional search after each port, but that would reduce the amount of ports on the list as you proceeded. The method I explained above wouldn't be all that complicated to accomplish, but as I said, it would take a bit more time and processing than doing a simple bfs at the beginning of the script and may not be worth the effort in some type games.

Right, but doing a bi-directional search on where u are versus
where you're going has no point since you probably won't be
returning back there immediately. Doing it on just 2 ports is
also not very useful since you need to know the best route
out of multiple ports.

If all you want to do is eliminate visited ports, there are
plenty of ways to do that. In the code earlier, I did that
by clearing the value from the array. In my megarob script,
I also do a port report too. All of that is built into the BFS,
or a few related functions.

Yes true. I was thinking in terms of port pairs or twarp distance. You are correct, you could, and should, just check the distance to the port from your current location in this case.
However, I do think this is very simple, economic method, for the simple reason that you are going to the nearest point from your current location, therefor using less fuel ore to get there.

Bingo...Stop there...Winner Winner Chicken Dinner!

I do 10 pairs at a time in trade mode and 10 sellers at a time in sell mode and the processing time is not noticeable really as a progress bar moving quickly takes your mind off the few seconds wait.

At the second set the script is Either waiting for the botted guy to finish the nego or for your nego to end. The actual wait in the preceding 9 is almost zero so all anyone has commented on was on how fast it goes.

Testing beyond 10 pairs or 10 sectors of sell didn't result in any measurable improvement in a measurable way. Of course if I reset a local server with a server side script then perhaps my testing would have been better. But 10 is were I stopped as going 20 deep took to long and I am impatient with slow script starts.

I know what you do, I also know you aren't trading the
optimal route. Something I've proven twice, now.

Well you don't have a copy of the script so we will have to differ and close the conversation as unproductive. Empirical data proves my methods produce more profit with less ore and increased data bringing increased income per turn with each run.

Actually, I have a copy of a lot of stuff that's found its way
to me. Additionally, I am the one that came up with the
"cash/ore" metric, lol.

Linky:
viewtopic.php?f=15&t=25523

Your empirical data is flawed. You cannot exceed the
maximum profit. Impossible things are impossible.

Income per turn has 2 factors, income and turns.

If you have X ports, you cannot exceed the maximum
profit on those ports. Which means the only factor is
turns. Whether those are turns buying down ore, selling
prod, or buying eq.

Now, negos take what they take, 1, maybe 2 turns per.
To that end, you want to nego to upgraded ports obviously.
Buying eq takes what it takes, too. You can stop after
the mega, but that reduces your cash too, reducing your
cashing turns and not increasing cash/turn efficiency.
So that cuts the entire problem down to the amount of ore
you buy, which is necessitated by the ore you burn trading.

If you actually work thru the details, you will find that
when trading a closed set of ports the only thing that
matters is the ore you burn. Every gain you pick up early,
you lose later.

Its only a "closed" set if the planet holds more EQ than the universe can buy

20k secotr 40% PD 4000 EQ buyers ...60,00,000 eq @ 1500 per buyer

I don't trade that much at a time therefore I have my pick of subsets.
Each subset has a different requirement in fuel to sell off the planet full of EQ.
Each subset has a different return on cash for eq.

A simple BFS allows only one subset.

Assume 3 equidistance ports...all three are buyers all three meet the filtering criteria

Given a once a day trading cycle and 100% regen. A bfs will go to the same port everytime.

This is not necessarily the "best" port nor the closest to the next good port.