Area Tradewar, Msg#396, May-30-93 14:27:18 From: Woody Weaver To: Albin Gersich Subject: mapping the universe from sector 1 The new twassist feature has piqued my mathematical curiousity. For those who just want TW tips, space bar now. For developers or those who might be interested in the algorithms of mapping the universe, keep going. The problem, of course, is to generate the directed graph that is a trade wars universe. Currently, the number of nodes in the graph is 1000, the graph is sparse, with at most six outgoing edges and average between two and three outgoing edges, and is mostly strongly connected (i.e. a path between any two nodes in either direction). What we have going for us is an oracle that will display the shortest path between two nodes. The time it takes to get a response from the oracle is a function of the actual distance, but appears to be more than a tenth but less than a second if the path actually exists. Let's talk undirected graphs, then modify things later. (In particular, for practical results, assuming all edges are two-way is probably useful; it doesn't solve the problem of finding the star dock, as Joel's findsga does, but for general trading/combat issues its a good first approximation.) The level diagram of a graph rooted at r is an ordering of the nodes of the graph by distance from r; i.e. r, then all its neighbors, then all nodes at distance 2 from r, then all nodes at distance three, etc. An edge (u,v) is an external i-edge if u is at distance i from r, and v is at distance i+1; the edge is an internal i-edge if u and v are both at distance i. (Note that EVERY edge is either an external i-edge or internal i-edge for some i.) Okay, here is an algorithm. The first pass is to pick up all the external edges rooted at 1. Set a bit for each node as an extreme vertex. Set a bit for each node as unattached, set the bit for sector 1 as attached, then run s from 2 to 1000 with if s is not attached, plot the course from 1 to s parse the course to get v0=1, - v1 - v2 - ... - vn = s store the edge (vi, vi+1), i=0..n-1 set vi as attached, i=1..n turn off the bit for vi as extreme, i=1..n-1. How many course plots do we have to make? A priori, I don't have an answer; if the graph were pathological and we were unlucky, it could be as much as the size of the graph. Note that we have to at least attach each dead end, this is a lower bound. Let's estimate that we have to make 500 course plots at a 0.75 sec each, or around 7 minutes. At this point, we have ALL the external edges. Moreover, we also know that any edge we are missing MUST be between a pair of nodes at the same distance from 1. Here is some data: the format is "number at distance(internal/external edges)" St.Marys bbs, stellar dispersion from sector 1: 1( 0/ 6) 6( 12/ 21) 14( 2/ 43) 27( 2/ 77) 51( 2/146) 97( 19/290) 177( 47/450) 233( 91/487) 198( 51/345) 112( 15/179) 50( 2/ 75) 20( 0/ 30) 9( 0/ 12) 3( 0/ 4) 1( 0/ 2) 1( 0/ 1) 0( 0/ 0) 0( 0/ 0) 0( 0/ 0) 0( 0/ 0) There are 0 unreachable sectors, 1000 reachable sectors. Average number of warps in reachable sectors: 2.411 Average distance to (known) sectors: 6.99 diogenes.club bbs, stellar dispersion from sector 1: 1( 0/ 6) 6( 12/ 22) 16( 2/ 49) 33( 2/102) 75( 6/221) 140( 36/393) 225( 91/512) 224( 65/436) 152( 19/245) 73( 13/110) 36( 2/ 46) 9( 0/ 17) 7( 0/ 9) 3( 0/ 3) 0( 0/ 0) There are 0 unreachable sectors, 1000 reachable sectors. Average number of warps in reachable sectors: 2.419 Average distance to (known) sectors: 6.51 grateful.med bbs, stellar dispersion from sector 1: 1( 0/ 6) 6( 12/ 20) 13( 2/ 35) 22( 0/ 71) 51( 10/142) 92( 10/250) 150( 43/375) 191( 66/424) 183( 63/362) 142( 22/247) 83( 10/127) 35( 2/ 57) 16( 0/ 25) 7( 0/ 9) 2( 0/ 4) 2( 0/ 2) 0( 0/ 0) 0( 0/ 0) 0( 0/ 0) 0( 0/ 0) There are 0 unreachable sectors, 996 reachable sectors. Average number of warps in reachable sectors: 2.406 Average distance to (known) sectors: 7.33 The numbers are pretty consistent. The point is that this is fairly effective. For SMC, there are 243 internal edges that would be missed, 2168 external edges, so 90% of the internal edges. Now consider the one-way character. Just reverse the procedure! I.e. here, we first clear all the attached bits, then plot courses back from s to 1. We won't have to do as many course plots this time: start with all the "extreme" sectors (since you have to do that anyway) and that will cover everything except sectors with back doors. Just pick up the remaining, and you will have developed the entire level diagram. Now what is missing? The internal edges, since they won't have been seen in any shortest course plot. Its likely that this is a sufficient place to stop: we've used up ten or twelve minutes of bbs time, and we've got 90% of the edges, and we certainly have a good picture of the stellar dispersion from sector 1. (Actually, because you want to buy etherprobes at the stardock and fire them off from there, it might be nice to do all this from the stardock rather than 1.) This seems to meet all the tactical issues, and then if you fire etherprobes at all the extreme nodes and parse the reports back, you will have a valid map (because you've passed through every sector). What if you don't want to spend the money on the four hundred etherprobes? Because of one-way warps, the level diagram of the opposite directed edges rooted at 1 will have a slightly different structure in terms of nodes at a fixed distance, you can actually gain more negative information about where the internal edges are *not* located. At this point, one could do two things: as you are developing the original sector scans, build the sets of nodes at the same distance, and then do course plots between pairs to see if the edges exist. (These course plots would run very fast, as most of the time the paths would be of length 1 or 2.) Alternatively, one could just repeat the above process of generating the level diagram rooted at another node. Now, the edge would have to be internal to both level diagrams to be hidden; if r and s are your two nodes, and (u,v) is the hidden edge, then u, v have to be the same distance from r *and* the same distance from s, in *both* directions, which should be rather unlikely in these random graphs. Probably best is a hybrid: for each level diagram rooted at r, you get a partition of the nodes (by distance). Combining level diagrams, you simply refine the partitions. Repeat until the size of each partition is one or two, then directly course plot between the nodes to determine if the internal edge exists. Interesting. I first thought about using the silly oracle several years ago -- it is absurd that you don't have direct information about warps, but you can plot all of the warps leaving a node -- but didn't think very hard about it. It easy to see that you can get a complete set of information by plotting 1000*999 course pairs, but a million course plots is clearly a waste of time. Albin, it was very insightful to recognize that this can be quickly done. The other reason that I didn't write the routine is that it would (I thought) take all the fun out of exploration. Now, I find that exploration is rather boring, and that knowledge of the warps is not as important as knowing the location of the ports and whether or not the port has been visited/blocked -- i.e. the etherprobe information. What would perhaps make the most sense is to have readily available the "map" of the universe, i.e. the warps, but that we can't have set up contacts at a port (i.e. visited it) unless we pay a fee to contact the port administrator, or have an etherprobe pass by (and deposit a permanent transmitter, aka "visiting"). It seems to me that this feature of TWASSIST is very useful and very sensible. ... "42? 7 and a half million years and all you can come up with is 42?!" --- Blue Wave/TG v2.12 [NR] * Origin: Grateful Med BBS;Concord, CA.(510)-689-0347 (1:161/63.0) ------------------------------------------------------------------------------ Area Tradewar, Msg#399, Jun-04-93 12:57:10 From: David Myers To: Joel Downer Subject: Mapping The Universe JD> Give me 100% explored on day 1, and I can optimize my ether-probing and JD> find planets very early. I'm not certain 100% is possible. Please see a followup to Woody's post on level diagrams that explains why. JD> And I'm just talking about my conventional JD> way of optimizing ether probing, never mind the *optimal* approaches JD> that should be available with 100% explored. I'm not sure whether JD> you've added a feature like this to TWAssist yet, but it should be JD> possible to do scary things with 100% explored, 50-75 ether probes, and JD> the avoids feature in the game. An analysis program that can duplicate JD> Gary's course-plotting results could figure out a list of avoids to JD> set, base locations, regions to density-scan, and targets to use to JD> ether probe and/or density-scan all 1,000 sectors at extremely low cost. What Gary is probably using is a breadth first search on an adjacency list; an adjacency list is how he stores his warp data on disk. If so, the particulars of which courses he plots are dependent on the order of warps in the game's list, and that order probably cannot be matched in 15 minutes of course plotting online. David. --- Maximus 2.01wb * Origin: Isolated Pawn * TW UTILS in NC * 919-471-1440 * 14.4K (1:3641/281) ------------------------------------------------------------------------------ Area Tradewar, Msg#324, Jun-04-93 13:03:14 From: David Myers To: Woody Weaver Subject: Level Diags <--> Ext Edges !?? Ok, this has been driving me batty at work: In your recent post to Albin, you assert that a level diagram (and by this I mean the adjacency list that results from plotting courses from a root r to all other nodes, and then from all extreme nodes back to r) contains all external edges of the graph. This simply isn't true. I can demonstrate a graph, with a reasonable course plotter, whose level diagram misses an external edge. Consider the graph defined by the following adjacency list (in a pseudo .SCT format): 1 2 5 2 1 3 3 2 4 4 3 6 5 1 6 6 4 5 Assume that the course plotter is a breadth-first search(BFS), and that the BFS visits nodes on this list from left to right. Then the level diagram rooted at 1 obtained from this graph will miss the external edge (4,6). It is important to note that topologically this graph is a cycle, and that imbedded cycles in a larger graph G could generate the same problem. The existence of the problem *does* depend on the ordering of the edges in the adjacency list, in this case if the nodes in sector 4 are reversed, the problem goes away. Now if the above graph G is a subgraph of a larger graph H (say a TW game), and G is singly connected to H through the node 1, then the whole graph will suffer the same problem that a level diagram rooted at 1 does, and the only way to eliminate the problem would be to trace courses internally in the loop. Even Albin's protocol will suffer from this problem if it does not take explicit measures to check for potential cycles on the periphery of the TW universe. I don't think the assumption that Gary uses a breadth first search is a problem, since the data structure saved to disk is an adjacency list, and a breadth-first search is a good way to determine either the distance to a node, or the shortest possible path to a node using an adjacency list, and it is simple to code. David (workin' on TWFT 099, whose alpha version does level diagrams BTW). --- Maximus 2.01wb * Origin: Isolated Pawn * TW UTILS in NC * 919-471-1440 * 14.4K (1:3641/281) ------------------------------------------------------------------------------ Area Tradewar, Msg#305, Jun-05-93 16:36:46 From: David Myers To: Woody Weaver Subject: Level Diagrams in Reality.. Ok, I recently collected 3 level diagrams in files called mytest2.ast, mytest3.ast, and mytest4.ast respectively. I then merged these 3 files into a single file called mymerge.ast. I then collected a CIM file and compared the CIM data to these actual level diagrams: ------------------------------------------------------- When mytest2.ast is compared to the CIM File mycim.ast There are 1497 Total Warps in the CIM File And 354 Total missing and/or extra warps. With 491 sectors out of 1000 compared, then the Efficiency of mytest2.ast is: 76.35 ------------------------------------------------------- When mytest3.ast is compared to the CIM File mycim.ast There are 1497 Total Warps in the CIM File And 347 Total missing and/or extra warps. With 491 sectors out of 1000 compared, then the Efficiency of mytest3.ast is: 76.82 ------------------------------------------------------- When mytest4.ast is compared to the CIM File mycim.ast There are 1497 Total Warps in the CIM File And 345 Total missing and/or extra warps. With 491 sectors out of 1000 compared, then the Efficiency of mytest4.ast is: 76.95 ------------------------------------------------------- When mymerge.ast is compared to the CIM File mycim.ast There are 1497 Total Warps in the CIM File And 64 Total missing and/or extra warps. With 491 sectors out of 1000 compared, then the Efficiency of mymerge.ast is: 95.72 Now I'll leave it to the pundits here to ponder what would happen to these efficiencies if all of the sectors had been collected in my CIM (Would efficiencies go up? down?). My belief is that these are a *good* estimate of coverage but probably an underestimate of coverage since many of the missing sectors are undoubtedly dead-ends and known in detail by any of the LDs. Nonetheless, the final efficiency of the merged diagrams is approaching the 99% efficiency I had predicted based on Woody's theoretical calculations. That *single* LDs fail as often as they do is probably due to cycle effects, since with ordinary single cycles, you lose an external edge 50% of the time, a bicycle can lose either 1 or 2 edges, a tricycle will lose 2 or 3 edges, and so on. Since cycle-based edge losses are highly root dependent, then multiple LDs tend to pick up these hanging external edges. David Myers. --- Maximus 2.01wb * Origin: Isolated Pawn * TW UTILS in NC * 919-471-1440 * 14.4K (1:3641/281) ------------------------------------------------------------------------------