Introducing ROMULUS: the Total CIV4 Tile Optimizer. Know what to build, and where!

Hello everybody,

This is my first post, and it is to announce urbi et orbi ROMULUS, a Java utility for CIV4 I've been working on these past months.

ROMULUS is an improvement optimizer: it calculates the best improvements that can be built on the terrain under your city's direct control (the "fat cross") in order to maximize either food, production or commerce. ROMULUS takes into account everything that may affect a tile's yield: base terrain characteristics, resources, technologies, selected buildings, possible improvements, even leader traits.

ROMULUS analyses every single possible combination of improvements in the fat cross, calculating irrigation extent and fcp values according to all modifiers, for each possible configuration It lets you edit terrain, edit which improvements you want to be considered in the final solution, and also save the solution to a simple text-based map that you can later print and use in your game. The ultimate 6000-year plan! All controlled by an easy-to-use, no-frills basic GUI. (with a Help page incorporated, don't worry!). Not the prettiest thing, perhaps, you won't see a bunch of fancy graphics, but it is a powerful and accurate gray beast

It is really quite complete. Here is the list of features it has:



* From the terrain info entered by the user, it correctly calculates the fcp (food, commerce, production) values of unimproved terrain.

* From the base terrain Romulus determines all applicable improvements in that tile and how they change the tile fcp’s. Romulus takes into account all relevant factors, such as base terrain characteristics, technologies, resources, access to fresh water, and more.

* Romulus let you select which technologies are going to be used in your map. In this way you can have realistic maps with techs that influence the improvements availability and/or bonuses, among other effects.

* You can include the extra effects of having a financial leader, lighthouse or Colossus wonder in your map.

* City square logic is implemented, allowing for the correct calculation of fcp’s in the city square according to resources, elevation and other factors.

* Romulus exhaustively explores every possible improvements configuration in the great cross, returning the best improvement configuration that maximizes food, commerce or production as specified by the user.

* Romulus correctly calculates the spreading of irrigation in every possible configuration, to accurately determine food values while optimizing.

* Romulus allows the user to “fix” an improvement, that is, to select an improvement in a tile so that all other improvement possibilities in that tile are ignored. This allows the user to customize the optimization process by preserving improvements considered essential or already built, and also to reduce the “combinatorial explosion” that a full-blown optimization of many tiles produces (see details later).

* The optimal improvement map can be saved to a simple text file, so you can print it and use it in your game.

* Base terrain maps can be loaded and save for further exploration.

* Romulus offers a simple user interface with a base terrain view, improvement view and optimal configuration view, plus standard controls to interact with the application and an information area with status and optimization information.


*******************

This is version 0.9. I'll release version 1.0 after you, my dear co-civ4 fanatics, test Romulus to the breaking point. Please download it, play with it, criticize it (constructively, of course!) and demolish it or praise it to your pleasure. I think it is a great tool for the beginning player, and also for the more advanced one (especially after version 1.0, when certain more refined optimization options I have in mind will get implemented). Try it!

ROMULUS is a Java app distributed as a JAR file, copyrighted under the GNU General Public License.

To use it, download it, decompress it and double-click on the Romulus.jar file. If instead of executing it just opens in your Winzip or similar compression utility, it is because in your system the .jar extension is associated with a compression utility (because .jar in fact is a compressed format). Change the association to your Java runtime in the control panel, or alternatively right-click on Romulus and select opening it with Java (in Vista).

Have fun!

Samsara

Comments?

Seems cool.

Maybe their optimizer hasn't finished yet?
I put in a town with 20 grasslands, and I got this:



I don't think it will finish this year. You need a better algorithm.

Hi barbertje,

Thank you for downloading Romulus, and good question. It is inevitable that you get an astronomical number of possibilities if you are going to explore all configurations of a full map without any restraints. It is mathematically impossible to avoid it, so it is up to the user to limit the available options.

(And is no error: in that map, you have 4 possible improvements per tile. There are 20 tiles, so 4 x 4 x .... = 4^20 = that BIG number)

I implemented a way to do it, and described it in the Help page, towards the end of the Optimization section, if I remember correctly. Normally, you can reasonably limit the number of improvements of certain tiles based of things like obvious improvements (frex., usually a flood plain with wheat is a great place to have a farm, or you really need to have a mine over that cooper resource, etc.), or even limit the desirable improvements to only a few (For example, in a tile with 6 possible improvements, you may find you are really looking only for 3 of them). Also, many times you can eliminate the "No Improv" option because usually an improvement is better than nothing. It also depends on what you are trying to maximize. If food, you can safely eliminate some workshops options. Etc.

To do this, go to the All Improvements view and click on the desired tile. A dialog will appear where you can pick which improvements you want to be considered in your optimization. Play around eliminating/selecting improvements until you have a reasonable number of configurations to compute.

In my system (a rather standard laptop), reasonable is in the low hundred millions, taking something like two minutes or less. YMMV. I've done run in the 700 millions range, and they take about 30 min here.

I hope this helps. Romulus is tackling a difficult, numerically heavy problem. It need some user guidance in some cases, like the extreme one you tested here.

Thanks again, and have fun!

Samsara

Samsara said:

Also, many times you can eliminate the "No Improv" option because usually an improvement is better than nothing. To do this, go to the All Improvements view and click on the desired tile. A dialog will appear where you can pick which improvements you want to be considered in your optimization.

Click to expand...

I submit that there is no tile type such that "no improvement" is better than all possible improvements. Ergo, the program should at least default to turning off "no improv" on all tiles.

Another obvious optimisation would be to have a straightforward way (default?) to build the associated improvement on any tile with a resource.

An issue is that one must know how much extra food, if any, is available from outside (Sid's/Cereal); and keep an idea of the city's food supply. A city with lots of food from Sid's can build workshops everywhere; one that must support itself cannot.

A less obvious optimisation is to recognise that tile improvements are mostly independent of each other. The only non-independent improvement is farms. Hence it is not necessary to enumerate all the something^20 cases - especially because without knowing from where outside the BFC fresh water might come, one cannot in principle assess the effect of chaining farms anyway.

Particularly, the hint ought to come from the test case here. It is obviously very easy to predict the best F/P/C outcome for a city surrounded by 20 grasslands. It is just about the easiest case possible. If it looks like the hardest, the algorithm one is using must be demented.

Hi Damerell, thank you for submitting your ideas here. Let me see...

I submit that there is no tile type such that "no improvement" is better than all possible improvements. Ergo, the program should at least default to turning off "no improv" on all tiles.

Click to expand...

You know, I thought about it and I think that it is mostly true. Mostly. It depends on the optimization goal. For example, in a grassland with forest, you get No Improv fcp:2/0/1. With a farm it could be (depending on irrigation and biology) 3-4/0/0. You earn at least +1f, but lose 1p. If your optimizing for production, no improv may be actually better! (depending, of course, on whatever is happening in the rest of the cross).

You can right now eliminate "no improv" manually from each tile, but is a bit of a chore. Anyway, I think your idea of having "no improv" as an globally optional thing is valid, to be used only as a just-in-case scenario. It will be included in the next version. Congrats for contributing

Another obvious optimisation would be to have a straightforward way (default?) to build the associated improvement on any tile with a resource.

Click to expand...

Yes, it is obvious. But, as with the former case, there may be a situation where you actually want something else there. It would be quite rare, so it will have to be implemented as an "uncouple resorce/improvement" option in a global configuration, together with the "No Improv" option above.

An issue is that one must know how much extra food, if any, is available from outside (Sid's/Cereal); and keep an idea of the city's food supply. A city with lots of food from Sid's can build workshops everywhere; one that must support itself cannot.

Click to expand...

Oops, forgot to mention that Romulus currently is designed for vanilla only (version 0.9, remember!)

A less obvious optimisation is to recognise that tile improvements are mostly independent of each other. The only non-independent improvement is farms. Hence it is not necessary to enumerate all the something^20 cases - especially because without knowing from where outside the BFC fresh water might come, one cannot in principle assess the effect of chaining farms anyway.

Particularly, the hint ought to come from the test case here. It is obviously very easy to predict the best F/P/C outcome for a city surrounded by 20 grasslands. It is just about the easiest case possible. If it looks like the hardest, the algorithm one is using must be demented.

Click to expand...

Ok, you got me thinking here.

First, let's begin with the algorithm. Right now I'm just using a brute-force approach, no heuristics whatsoever (again, this is version 0.9!). With brute force, the raw number of improvements per tile is decisive, not the, let's say, quality of each tile. Definitely will need some heuristics.

The problem is, I think, that I need to "simplify" the cross, pre-proccessing it to eliminate tiles with identical improvement lists, substituting them for an (abstract) single tile and a multiplication factor. Damn good observation, Damerell. Will work on it.

Irrigation (and farms) are a different matter: it depends on the topology of the farms, and in each possible configuration that topology will change, so I see no way of simplifying it Outside influences? Well, I guess they are essentially unpredictable, unless one tries to work with a whole continent (!). Will have to accept that limitation. A partial workaround could be to define a border tile likely to be so influenced by the outside as a water source itself. Anyway I think that irrigation from outside the cross is not that common, either, in a real game. (crosses fingers)

Excellent! I knew that putting Romulus "under fire" would get me good ideas from you guys. I'll improve it. Thank again, Damerell, for your criticism.


EDIT: For all you guys reading this, remember you can still use Romulus profitably if you manually select a few improvements in certain key tiles until the number of combinations goes down (to about the low hundreds millions, 100 millions or less, depending on your computer and patience). What we are arguing here is how to make Romulus much more efficient with less user intervention.


Second Edit: Damerell, after some needed sleep and reconsideration, I think the problem is actually bigger and not easily solvable. One can try to simplify the bfc when dealing with tiles with identical improvements, but "identical" means not only have the same kind of improv, but the same output. And farms are the big exception! Depending on irrigation and techs a possible farm can have diverse output, or even not exist! (frex, with civil service and no biology, a farm may or not exist in any flatland, depending on a farm chain reaching it). Therefore, in tiles with a possible farm improvement, calculating irrigation is sine qua non to determining tile equality, and irrigation depends on configuration...so you have to go through every config regardless.

So the key may be in optimizing irrigation calculus, or simplifying it some way, or even make it unnecessary in some instances (Romulus already skips irr calculus with no civil service discovered, of course).

For tiles with identical possible improvements, and no farms in them, a direct simplification is possible (like tiles with the same hill/plain/grassland, for example).

That's why the simple case of "all grassland" is not that simple. A human can recognize it at once. A computer can't, due to farm + irrigation = complexity. A computer would have to solve the topology of the map to then "realize" that in fact all the tiles can be irrigated, so all farm are equivalent, so all grassland tiles are equivalent. It is a variation of the classical computing problem of shape (or topology) recognition, notoriously hard for our electronic friends.

I'll try a combination of some heuristics (rules-of-the-thumb in AI-speak) and genetic algorithms to explore this enourmous search space. Meanwhile, brute force still works, with a bit of human help ;-)


Regards,
Samsara

I have not looked at it yet but it sounds like an interesting project. I like seeing people take on these challenges and contributing to the community in this way, so thanks for your efforts.

Mec AntiKythera said:

I have not looked at it yet but it sounds like an interesting project. I like seeing people take on these challenges and contributing to the community in this way, so thanks for your efforts.

Click to expand...

Thanks, AntiKythera!

Nice work, look forward to playing with this.

deep64blue said:

Nice work, look forward to playing with this.

Click to expand...

Thank you, deep64blue! I hope it is helpful!

...And now let me inform you all on the further developments towards version 1.0!


I've been playing with some methods that considerably simplify the optimization problems by pre-processing the great cross so that the possible configurations are either greatly reduced and/or the search space is much easier to actually search (by ordering it according to distance to the absolute max, more on that later). And the good thing of having a brute force approach already implemented is that brute force, though slow and sometimes in need of human help, is never wrong. So by comparing results I know if I screwed up with the new methods


If this works out well, version 1.0 should be much, much faster and require much less user help, if any. I'm already looking forward to implementing a more general case, one where you aren't just maximizing for one quantity, but for the three quantities at the same time in different proportions, using a weighted mean to determine the overall fitness of a given configuration. For example, you could tell Romulus to optimize your city for 65% food, 15% commerce and 20% production, meaning that you want a final configuration were food has a relative "importance" of 65%, and so on.

I'll have something ready in a week or two. Stay tuned!

Regards,
Samsara

I am not convinced this is quite the right approach. In particular, food has no value in and of itself. You need to ask how the player values specialists, not food. I would start as follows:

Ask the player's happy cap. If less than 20, only work that many squares. If more, regard food that would support unhappy people as worthless. Allow the player to input a value indicating that happiness should not be limited (for late-game use).

Ask the amount of bonus food from corporations or other causes. Yes, you said vanilla-only; but knowing this one number and a few fiddles for improvements immediately supports BTS. And what does everyone play these days?

Ask for the health cap, and take account of how this changes the population attainable for a given food output. Once again, support an "unlimited" input for very late game use. Account for the way chopping forests will change this.

Ask for the maximum number of specialists the player regards as useful (or feasible) in this city. Allow a "unlimited" input for... well, y'know.

Now ask the player... the relative values they assign to specialists, hammers, and commerce. This is not the same as relative weight. In the all-grassland case, for example, relative weights will cause a mix of improvements to be recommended; but relative values will cause it to recommend just one improvement. Now this seems odd, but of course most cities are not all one terrain type; assigning relative values lets me say I value hammers (for example) 1.2 times as much as commerce, but the program will still recommend a 3C improvement over a 2H one, all else being equal.

Now score improvement layouts by the total value generated using those figures, not forgetting that it may be worth working fewer than 20 tiles to generate more specialists. (Remember we have assigned all specialists the same value; not totally correct, but close enough given the "maximum useful number" question. We don't try and score the hammers that might be generated if an engineer was chosen, etc; we just ask how much the player values "a specialist").

Those are some good points. I do think you should be able to choose what population you are evaluating and how many specialists you want to be able to run. That way you can weigh short and long term goals against each other.

Hi damerell, good to see you again.

Let examine your (quite interesting!) propositions one by one.

damerell said:

I am not convinced this is quite the right approach. In particular, food has no value in and of itself. You need to ask how the player values specialists, not food. I would start as follows:

Click to expand...

I could go for a semantic nitpick and say that on the contrary, food and people are the basis of everything, but I see in what sense you mean it. So, to examine the food-as-resource-for-other-things angle...

Mmmm...I think food in fact has value in and of itself in the early and middle game, because it is not only used to support specialists or for support work on tiles with little food, but for further growth. So you would really need (if planning for an early or medium era) not just a balance between specialists, hammers and commerce, but between food for specialists, food for growth, hammers, and commerce. Doable I think, but harder.

I have decided to leave specialists out of the next version because I have as a priority right now to make the basic optimizations more efficient. Once fcp optimizations are faster/better, I'll go to the "secondary effects", such as the number and kind of specialists in the city.

And, due to the same development strategy of going from easy/less detail to harder/more detail, I'll continue to develop for vanilla only until I have that well-wrapped up. I guess there are still plenty of vanillistas around to make it worthwhile. (I wonder how good does this work for BTS right now anyway? Is Romulus very off the mark?)

About the proposed health and happiness caps. Doable, definitively, but better to be implemented in a later version, as explained above. Meanwhile, remember that you are not forced to fill the whole map. To (partially!) simulate the caps, just don't use all the tiles. (Ok, this really simulates a user that doesn't go beyond the caps, not the penalizations, but hey, something's something!).

Now ask the player... the relative values they assign to specialists, hammers, and commerce. This is not the same as relative weight. In the all-grassland case, for example, relative weights will cause a mix of improvements to be recommended; but relative values will cause it to recommend just one improvement. Now this seems odd, but of course most cities are not all one terrain type; assigning relative values lets me say I value hammers (for example) 1.2 times as much as commerce, but the program will still recommend a 3C improvement over a 2H one, all else being equal.

Click to expand...

I'm not sure you explained the difference between your concept of value and my concept of weight with enough detail. I think we're talking about the same thing. Can you please try again? Thanks, and sorry for asking.

I'll tell you what Romulus does right now, and what I intend to implement:

Right now Romulus doesn't uses a weighted evaluation. It just selects the global configuration with the maximum numerical value for the selected magnitude (f, c or p). Or, if you wish, it uses a virtual weighted evaluation with one coefficient set at 1 and the rest at 0, but that is really nitpicking on my part

What I want to implement later is to select an optimal configuration based on a score computed from a proper weighted formula, like score = wf * F + wp*P + wc*C.

(the FPC's are gfc totals)

In the all-grassland case, it won't necessarily produce a variety of improvs all the time, or the same improv all the time. It will depend on the exact weight values you use.

If you want to produce the same improvs everywhere, you'll just use the simple maximizations we already use. Frex., for commerce you get town everywhere, etc.


Ok, that's enough for one post . As always, thank you damerell for your input. Good to see people interested in Romulus!


See you around,
Samsara

Samsara said:

Mmmm...I think food in fact has value in and of itself in the early and middle game, because it is not only used to support specialists or for support work on tiles with little food, but for further growth.

Click to expand...

That is true to a degree, but of course it is pretty straightforward to alter the improvement strategy temporarily because a city is still growing to the steady-state size. I don't need a program to tell me that, if I want to grow faster, I should replace those workshops in the final plan with farms for now.

I have decided to leave specialists out of the next version because I have as a priority right now to make the basic optimizations more efficient. Once fcp optimizations are faster/better, I'll go to the "secondary effects", such as the number and kind of specialists in the city.

Click to expand...

I disagree strongly. First of all, I don't think you need to worry about the kind of specialists. The player knows what sort they want - all they need to know is how many they can have.

Secondly, you will make a rod for your own back by trying to value specialists' output. All of a sudden, the program has to know what culture is worth, what beakers are worth, what a GPP is worth (and that's a vexed question)...

And, due to the same development strategy of going from easy/less detail to harder/more detail, I'll continue to develop for vanilla only until I have that well-wrapped up.

Click to expand...

I think this is a mistake. As mentioned, the only real changes are some tile improvement / civic combinations might be different - a few minutes' data entry - and the idea of bonus food from corporations. But... even in vanilla, one might have had bonus food from tile events, so supporting bonus food also helps vanilla players. And also, while I appreciate the desire to keep any programming project simple in the early stages, we're talking about inputting one number.

About the proposed health and happiness caps. Doable, definitively, but better to be implemented in a later version, as explained above. Meanwhile, remember that you are not forced to fill the whole map. To (partially!) simulate the caps, just don't use all the tiles. (Ok, this really simulates a user that doesn't go beyond the caps, not the penalizations, but hey, something's something!).

Click to expand...

This may work for happy caps - although it leaves the user trying to work out which tiles are best, which is surely defeating the point of the exercise - but the health cap is more complicated, since obviously one can expand beyond it, it's just more expensive. Answering the question of when growth beyond the health cap has become uneconomic is exactly what a program like this should do well.

I'm not sure you explained the difference between your concept of value and my concept of weight with enough detail. I think we're talking about the same thing. Can you please try again?

Click to expand...

Weight, as I use the term: if I say hammers are weight 2 and commerce is weight 1, the program recommends a city that produces 66% hammers and 33% commerce.

Value... actually, value is the score computation you suggest later. So I think we agree and this is purely terminology.

In the all-grassland case, it won't necessarily produce a variety of improvs all the time, or the same improv all the time. It will depend on the exact weight values you use.

Click to expand...

Sure, it will, if the health cap is not an issue (and we're at SP so even a workshop can feed itself). Because every tile can feed itself, changing the score value produces a sudden flip; if the commerce from a town is valued more than the hammers from a workshop, suddenly 20 workshops become 20 towns.

But what I'm saying is this case is very unlikely in reality - both because of the layout and because in practice health caps intervene.

I also realised what to do about the "farm graph". Have the player mark tiles as "possible to irrigate". Now, just like every other kind of tile, you can reduce the vast number of possibilities by treating all "irrigateable grassland" tiles the same, and all "non-irrigateable grassland" tiles the same, ditto for plains. Before Civil Service this just works. Even after Civil Service, it's easy for the player; if the final layout's unfeasible, they remove the "possible to irrigate" flag on the tiles that are unfeasible and run the program again.

Hi damerell,

Sorry for being late, I was busy with things from that pesky "real life", as some call it...

I like some of your proposals, but, to summarize, I'd rather work on this at my own pace, from simple to complex, and by making absolutely sure that the "simple" actually works. I've seen too many software projects going to hell because of putting too much functionality too early (overextension without courthouses, obviously ) and then having to heavily backtrack because something basic was discovered wrong. Since this is just a hobby I think I can go as easy as I want, for once!

But don't worry, health and happy caps will be eventually implemented in some way. My only worry is to avoid "feature creep" in Romulus, and ending up having to virtually simulate a whole city, and Fireaxis not even paying me a single cent! . Ditto for specialists. About them, as you say, one only needs the desired number (or the final number, if the users doesn't specify), not the type. Good.

Finally, don't worry about irrigation. It is already implemented in the current version, and I tested it extensively to make sure it is correct. A single irrigation calculus for a single possible configuration is not heavy, so the problem is not there. The problem resides in the number of possible configurations one has to feed the optimization machine in the first place. That's what I'm working on right now.

And now, back to programming! See you around!

Samsara


PS:The simplification your propose for irrigation, alas, won't work. You can't simplify like that because you lose the key thing: topological info, who is next to who. And not only that, you need to know which tile is a water source and which isn't. And also remember that irrigation needs farms to propagate, not any improvement. The user can make a guess, as you said, but Romulus already calculates all that without human intervention so there's no need of it (and, as you said, even that human guess can be wrong!). And also, by fixing so many tiles to be farms (which you will need to do for it to plausibly work) most probably you'll lose optimization opportunities.

Regards!
S.

Samsara said:

PS:The simplification your propose for irrigation, alas, won't work. You can't simplify like that because you lose the key thing: topological info, who is next to who. And not only that, you need to know which tile is a water source and which isn't.

Click to expand...

No, you don't. If the user marks potentially irrigateable tiles correctly - tiles to which there is a possible farm chain - it'll work just fine. The program comes back and recommends a number of tiles to irrigate, and the user picks that many, working from the water source outwards. On non-resource flatlands, farms and cottages and workshops can be arranged however you please for the same total benefit. It might break down if the program recommends a watermill that blocks a farm chain, or if the program doesn't recommend enough farms to get the water chain to a food resource; but the former case can be fixed by changing which tiles were marked potentially irrigateable.

Will the user to able to set goals? What I mean is, say you want to build a commerce city. It could well be that you would want to start out with some farms to grow the city and then later convert these to cottages when you hit the happy cap. Perhaps Romulus could tell me the best way to get to a size six city while maximizing commerce. How many farms to I need and when do I convert them to cottages?

Improvements are dynamic and can change in time. Pasture the pigs first, mine them later? Mine them, build a forge or library or granary, then pasture them? That would get quite complicated very quickly though.

Mec AntiKythera said:

Will the user to able to set goals? What I mean is, say you want to build a commerce city. It could well be that you would want to start out with some farms to grow the city and then later convert these to cottages when you hit the happy cap. Perhaps Romulus could tell me the best way to get to a size six city while maximizing commerce. How many farms to I need and when do I convert them to cottages?

Click to expand...

Of course it's up to Samsara, but that seems well beyond the scope. It is, after all, entirely obvious how to grow as quickly as possible to size six; build farms on the six best farm spots. To go beyond that would be to say "maximise output of commerce by turn n", perhaps recognising the rate at which one values early production over late production, to work out if the city should grow rapidly and then switch to cottages or cottage immediately and grow slowly, and what penalty should we assess for the extra worker turns in the second case... we're looking at a much harder problem.