Monster Media 1993 #2/Image.iso/comm/twft099b.zip/MAPPING.TXT

Text File | 1993-06-07 | 15KB | 308 lines

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)
------------------------------------------------------------------------------