Mathematical Structure of the Tech Tree

[Spoonwood]

Somehow the thought popped into my head that the tech tree consisted of a
sup-semilattice. Well, that's pretty wrong. Future tech 1 precedes future tech 2 which precedes future tech 3 ad infinitum... oh wait... Supposing the epic game which only has 540 turns, then there exist only 135 future techs achievable even with a future era start. So, future tech 135 qualifies as the supremum of such a tech tree, and consequently, along with the fact that tech research can't go faster than 4 turns once you hit future techs, there exists some future tech as the supremum of a tech tree that starts in the ancient age. Of course, the tech tree has no infimum as the set {Bronze Working, Pottery} doesn't have an infimum. They also don't have a supremum either, even though both work out as required for the middle age techs, so we don't have a semilattice structure for the tech tree.

What about the tech tree as a partially ordered set? Pottery, for example, doesn't precede or succeed itself, so reflexivity fails. In fact, NO tech preceds itself, so the tech ends up antireflexive. Antisymmetry would seem to hold by default, since if tech A precedes tech B and tech B precedes tech A, then tech A equals tech B. Transitivity also holds, as if tech A precedes tech B and tech B precedes tech C, then tech A precedes tech C. Symmetry doesn't hold. Therefore, the tech tree has the structure of a strict order with a supremum (or sup-strict order) since it comes out antireflexive, antisymmetric, transitive, and has a supremum due to the finite number of turns in the game.

 

[woodandearth]

How do you define the comparabilities between advances of different eras?

 

[Spoonwood]

Nice question woodandearth. It seems clear to me that all required techs at the end of an era precede techs at the start of the era. For example, Currency precedes Feudalism as much as it does Monotheism and Engineering. Construction, Philosophy, Code of Laws, Map Making, Horseback Riding, and Polytheism also precede the first three medieval techs in the same way Currency does. But, you really need all those ancient age techs. So, the ancient age techs don't precede the medieval techs, but rather their conjunction does, which doesn't fit as a tech.

As a simpler example, the conjunction of Philosophy and Code of Laws immediately precedes The Republic. That conjunction doesn't qualify as a tech. Consequently, I guess we can't talk about the mathematical structure (in terms of set theory) of the set of all techs. However, we can still talk about the mathematical structure of the set of all techs and all techs under conjunction, with a conjunction of techs coming as a element of its own. For the conjunction of techs commutavity and associativity hold, e.g. in terms of order, Philosophy and Code of Laws=Code of Laws and Philosophy.

 

[Fiddlin Nero]

I spent a lot of time with my CAD program doing Tech Trees showing all of the possible pathes from Ancient to Modern. I'm curious to know if you hope to garner some game advantage or just curious to see if you can make some mathematical sense out of it? I've never regretted doing all those tech trees and enjoyed the exercise of visualizing this aspect of the game.

 

[Spoonwood]

Just make mathematical sense out of it, or something like that. I don't expect anything with respect to gameplay.

 

[ThinkTank]

As a simpler example, the conjunction of Philosophy and Code of Laws immediately precedes The Republic. That conjunction doesn't qualify as a tech.

Why not? This only follows if you have a peconceived definition of conjunction and how it relates to the precedence order. I think The Republic is a perfect exampe of a least upper bound.

(BTW, it is a bit confusing to talk about conjunction here, as what you mean is join (least upper bound or supremum), but he usual mathematical notation for conjunction is the same as for meet (greatest lower bound, infimum).)

It is normal in math to distinguish strict and non-strict versions of a relation, like < and <=. In this perspective, the tech tree defines a relation of "strict precedence".
The precedence relation can then be defined as "strictly precede or equal". This certainly does give a partially ordered set. We do not have a a lattice as meets don't generally exist (consider the ages starting techs). However, in the usual definition of least upper bound, The Republic is the least upper bound of Philosophy and Code of Laws.

Consequently, I guess we can't talk about the mathematical structure (in terms of set theory) of the set of all techs.

I suppose that, even if what I wrote above is al wrong, this is something you really did not want to say.

 

[Spoonwood]

Why not? This only follows if you have a peconceived definition of conjunction and how it relates to the precedence order. I think The Republic is a perfect exampe of a least upper bound.

That does work for Philosophy and Code of Laws with Republic, contrary to what I said before. But, we don't have a supremum for the join of Metallurgy, Theory of Gravity, and Magnetism. I guess the word conjunction does come out a bit confusing in a way.

I don't know why I talked about "precede or equal", instead of just "precede", and in such a case, of course, we do have a POSET. We do have a greatest element in the last future tech, with no least element in the tree.

 

[1940LaSalle]

I thought I was fairly sophisticated with respect to math, having aced differential equations 30+ years ago, and being reasonably conversant with such topics as elliptic functions and partial differential equations, but I have to say straight out that this discussion leaves me completely baffled. Exactly what branch of math are we dealing with here: some variant of set theory? And if so, can you recommend some sort of guide to gain some reasonable understanding of the discussion, please?

 

[Spoonwood]

Order theory.

 

[Lanzelot]

I would view the tech tree as an "ordered graph", not as a "set". That way many aspects fall into place much more easily. The techs are the "vertices" and the "precedes-relationships" are the "edges".

Lanzelot

Edit: I think the correct English term here is "directed graph", not "ordered graph"?! It's been so long ago...

 

[Lanzelot]

Graph Theory

By assigning the tech cost of the following tech to the link (edge) between two techs, you can even turn it into a "directed weighted graph".

 

[ThinkTank]

I would view the tech tree as an "ordered graph", not as a "set".

This is really a non-issue as (almost) all of mathematics can expressed in set theory, even in the strong sense that (almost) everything is a set. As a relevant example, the first definition of graph given in the Wikipedia article Graph is a definition of graph in terms of concepts of set theory.

If you meant to say that the ordering aspect is more important than the membership aspect (so we have an ordered set rather than only just a set), then I completely agree, and graphs are prime examples of structured sets.

 

[Spoonwood]

ThinkTank beat me to that one. Additionally, the membership aspect even among sets has a relationship to an ordering aspect of sets, in that a set with no members precedes a set which does have members which precedes any reference set we may use for discussion. Or in numbers 0000000...<0010000...<1111111...

 

[Lanzelot]

This is really a non-issue as (almost) all of mathematics can expressed in set theory, even in the strong sense that (almost) everything is a set. As a relevant example, the first definition of graph given in the Wikipedia article Graph is a definition of graph in terms of concepts of set theory.

If you meant to say that the ordering aspect is more important than the membership aspect (so we have an ordered set rather than only just a set), then I completely agree, and graphs are prime examples of structured sets.

Yes, perhaps I expressed myself a bit unclear. Of course a graph is also a set (or rather "two sets", the set of the vertices and the set of the edges). What I want to say: the tech tree is much more than just a plain set. The most important/interesting aspect of the tech tree is the relations between it's members.

And I think it's more than just an "ordered set", if you also want to model the aspect that different techs have different prices. So a directed weighted graph may be the best point to start.

However, I realize just now, the sets of vertices and edges would be a bit more complicated than I first thought: for example there is no link between Philosophy and Republic. There woud be a link between {Philosophy, Code o Laws} and Republic. So we would need to throw in a few "tuples" of techs in order to model those techs that have more than one prerequisite?!

Or what if we "reverse" the order of the links? Instead of drawing a link from Philo to Rep and from CoL to Rep, we draw two links from Rep to Philo and CoL. This would then mean: if you own Rep, you must also own Philo and CoL. This kind of structure could then be used as follows: given a set of techs (the ones that you currently own) and any arbitrary tech X, the algorithm would follow all paths from X downwards, until they "end" in the given set of starting techs. The output would then be: all techs that you need to research on the way to X, and (by summing up all numbers on the edges encountered on the way) the total number of beakers necessary for that.
(Perhaps CivAssistII is using an algorithm like that?)

 

[Spoonwood]

And I think it's more than just an "ordered set", if you also want to model the aspect that different techs have different prices. So a directed weighted graph may be the best point to start.

I think I agree with you on the condition that you want to talk about tech cost. I didn't have that in mind. But, interestingly enough though, if we want to talk about the prices of techs for the human player in terms of beakers, then I don't think we can use a number to represent the "weight" here. Ignoring the Great Library, and stealing techs in terms of gold, etc., we'll need a multi-variable function which has as its inputs the map size m, the difficulty level d, and the number of non-human tribes known who have that tech k (anything else?), and as its output the tech's cost in beakers b, or f(m, d, k)=b. Edit: technically speaking the function should get notated f : (m, d, k)->b, with f((m, d, k))=b indicating that the function for the triple (m, d, k) has value of b, but I don't see such a technicality mattering all that much here. f ends up as a non-increasing function, given an ordering of map sizes from tiny to huge, difficulty level from chieftain to sid, number of tribes known from 0 to 31, and appropriate numbers for map sizes and difficulty level.

For anyone new the concept of multi-variable function, and more use to the concept of single variable functions, the concept of a multi-variable function really doesn't come as all that strange. Addition, multiplication, subtraction, division, maximum, and minimum with two inputs all come as examples of two-variable functions which you surely already have familiarity with.

The output would then be: all techs that you need to research on the way to X, and (by summing up all numbers on the edges encountered on the way) the total number of beakers necessary for that.

Careful, the cost of Alphabet computed by an accurate algorithm here will probably differ when you know Writing as to when you know Literature.

 

[Lanzelot]

But, interestingly enough though, if we want to talk about the prices of techs for the human player in terms of beakers, then I don't think we can use a number to represent the "weight" here. Ignoring the Great Library, and stealing techs in terms of gold, etc., we'll need a multi-variable function which has as its inputs the map size m, the difficulty level d, and the number of non-human tribes known who have that tech k (anything else?), and as its output the tech's cost in beakers b, or f(m, d, k)=b.

Yes, this complicates matters a bit. However, I suggest the following to keep it simple: each tech has a "base value" assigned to it, which is constant. (Unless you modify it in the game editor. Some of the mods & scenarios have done that. But let's consider only the unmodified standard C3C game, and then the base value for each tech is indeed constant.) We could use these base values as the weights for the edges. Then any algorithm doing some computations on the graph, would work with the base values, and only in the end, when a concrete result has to be printed out, convert the accumulated base values to "real beaker values" by applying the known modifiers for map size, difficulty level and number of known AIs having the techs. (Perhaps we should store that last number in the graph as well, as an attribute for each vertex?! I guess this is, where we cross the line between mathematics and computer science... The graph is still a "mathematical structure". However, once we start to store additional information in it, it becomes a "data structure".)

Calculation of tech costs is only one possible application of such a graph. Basically it should be able to answer all questions that the "ordered set" approach can answer. (Like: "what techs can I research next?") And a few additional ones.
I think this is due to the fact that a graph is a "richer" structure than a set, so naturally it carries more information.

 

[Lanzelot]

Careful, the cost of Alphabet computed by an accurate algorithm here will probably differ when you know Writing as to when you know Literature.

Perhaps it's not a good idea to put the weight on the edges. (Because then we have no place for storing the values of the 7 starting techs: these don't have any edges pointing further down...) We would rather need to put the weights on the vertices. Then in the beginning of a game, 5 of the starting techs would have their natural base values, and two of them would get the value "0" assigned. (But is this structure still a weighted graph then?!)

 

[ThinkTank]

Putting the weights on the edges somehow seems more natural to me and also would more easily allow for applying shortest-path algorithms. To overcome the starting techs issue you can then add an "imaginary" start node signifying complete ignorance, and then set the weigts of the 2 starting techs to 0.

 

[ThinkTank]

(Double post)

 

[Lanzelot]

To overcome the starting techs issue you can then add an "imaginary" start node signifying complete ignorance, and then set the weigts of the 2 starting techs to 0.

Good idea! I think now we arrived at a quite useful model.

Lanzelot