Galaxy : maximizing growth? From: amead@s.psych.uiuc.edu (Alan Mead) Date: Tue, 16 Feb 1993 03:59:31 +0000 I think someone posted here saying that he had written software to maximize expansion. I was wondering (1) if anyone wanted to share code with me and/or (2) how it was done. I can think of 2 ways. I'm sorry this is so long. I'm posting here in the hopes that someone with more time will someday implement something like this and share it. I don't have the time right now. I started thinking about this because I have an empire of 74 worlds. Some are very far from the center of my empire and the undeveloped ones are literally scattered all over. I'm having a little trouble integrating all the possible decisions and I think even a simple computerized algorithm could improve on my present rate of growth. Here's how I would program it. The first, more fanciful (but not even vaguely realistic), way would have each world acting as an agent in a free market. They would accrue $ by producing CAP and COL and shipping it to other worlds. Under- or non-developed worlds would pay in accordance to their need and ability (where ability would be proportional to the productive capacity of a world; a homeworld would be maximally able to pay). The freighters would be worked into the system somehow; perhaps they would sell their services to the world accrueing the most points. The advantages of such a system would be: (1) very general; (2) able to output colorful summaries like "Such-and-such world hires so-and-so's free trader to run COL to world X"; (3) could be flexible (make all important parameters variables); and (4) the system would be fairly robust to disruptions like specifying that certain worlds must produce a certain commodity (like CAP or Cruiser_IV). The disadvantages would be: (1) no garauntee of anything like an optimal solution; (2) I don't know how to weigh in the decision to actually build freighters; (3) doesn't look down the road more than a turn; (4) doesn't use routes. The second way might use genetic algorithms. I'm no expert, but if you could characterize each decision as a "state" then you form strings of decisions states. Each one is a turn (ie, it contains one decision for each world and each frieghter group). Call this a "gene". Start with a population of genes of some sort. Perhaps random? Or perhaps you supply a quick, rough, first appproximation to the solution and allow the computer to improve it. You then apply each "gene". For each gene, determine how "well developed" your empire is and store this with the gene. Cause the genes that have high "well-developness" scores to "reproduce". That is, the next generation of "gene"s will be similar to the best genes of the last generation. I say "similar to" because you form new genes from the "parents" by mating sucessful parents (using "cross-over" and "mutation"). Cross-over produces two offspring from two parents by giveing segments of the parential gene to one or the other offspring. Eg, perhaps the parential genes of length 20 are broken into sections of 4 and one offspring receives units 1-4 from parent 1 and 5-8 from parent 2. Mutation is simply the replacement of one unit by a random unit. The attractiveness of this seemingly bizzarre practice is that entirely new strategems are created in produceing the offspring. Most of these mis-fits die immediately, but some are better and these survive. The whole process would break down into chaos except that you (1) allow most of the genes to re-produce (but maybe you allow the really sucessful ones to reproduce several times) and (2) you ensure that tha offspring really are similar to the parents by using gentle cross-overs and slight mutation rates. The advantages would be that this technique is an efficient way to search large, multi-dimentional solution spaces and a relatively optimal solution is likely to be found (I cannot prove that last assertion, but I think its true). The disadvatages would be: (1) what do you use as a starting point?; (2) might be a real pain in the ass to program (although some code exists in the PD or as FreeWare); (3) could chew up a lot of computer time; and (4) I don't know how you represent the decisions as genomes, I imagine each genome could take on hundreds or thousands of values. Also, I imagine that it would be difficult to constrain the algorithm not to use certain worlds so that they can produce warships, etc. Just a thought. -alan Up