The best kittens, technology, and video games blog in the world.

Monday, October 20, 2008

Put your variables on diet

Svanspervot on a Chair by Steffe from flickr (CC-NC-SA)

There are all kinds of categorization schemes for programming languages, by paradigms or checklists of supported features. Categorizations criteria tend to be highly subjective (e.g. "builtin support for regular expressions"), useless (e.g. "significant indentation"), or both (e.g. "does it have a standard").

I want to propose a new categorization - objective, easy to evaluate, and at the same time exposing something very deep about programming languages.

I will divide languages into:

  • thin variable languages - where variables refer to data.
  • fat variable languages - where variables contain data. Variables can also contain references to data, but there's a distinction between direct and indirect access.


This division is very old. Assembly language is obviously a fat variable language, even though its variable system is very simple - registers and memory locations contain stuff directly, or contain references (memory addresses) to stuff. As languages need to be compiled to assembly plenty of high performance languages follow this road. Fortran and C variables are just assembly variables plus types. C++ didn't break up with it, it made container variables much fatter and much more complicated - RAII, copy constructors, assignment operators, and all the related mess. Java in spite of superficial similarity to C++ is definitely a thin variable language.

Thin variable languages are also very old. The original Lisp was the first language with thin variables, and all Lisp dialects, just like all ML and Haskell dialects, are thin variable languages. I don't think a single seriously functional language uses fat variables.

All object-oriented languages, most popular of them being Smalltalk, Ruby, Javascript, and (let's be charitable) Java - use thin variables too. There are some fat languages like C++ and Perl with objects bolted on top of them, but they are definitely not object-oriented, they just support some limited object functionality.

Scripting languages are interesting. Old languages like Unix shell have very fat variables, even though all variables are simple strings. Perl and PHP continue this tradition, but Python and Ruby are soundly in the thin variable camp.

Observations


Having categorized all popular languages let's do some observations.

  • All (pure and impure, strict and lazy) functional languages are thin variable.
  • All honestly object-oriented languages are thin variable.
  • Thin variable languages and garbage collected languages are very closely related categories. There are some reference counted languages in both camps (Perl, PHP on thick side, Python on thin side), but there seem to be no thin language with manual memory allocation or thick language with full GC.
  • All segfaulting languages (assembly, C, C++) use fat variables, but many fat variable languages are non-segfaulting (Fortran, bash, Perl, PHP).
  • Dynamic typing is on both sides (Perl/PHP vs Lisp/Ruby).
  • Explicit static typing is also on both sides (C/C++ vs Java).
  • Implicit static typing is only no the thin side (ML/Haskell) and is actually quite popular there.
  • Almost all thin languages have closures. A few languages like Python and Java have less than full closures, in form of named inner functions or anonymous inner classes. In both cases it's a syntactic not semantic limitation.
  • Almost no thick language has closures. A big exception is Perl, which has full closures.
  • Lexical and global scope exists on both sides, in almost every language.
  • Dynamic scope is unusual, but is supported on both thick (Perl), and thin (some Lisp dialects including the original Lisp, Emacs Lisp, and Common Lisp, but not Scheme) side.
  • Rich literal notation is supported (Perl vs Python/Ruby/Lisp/ML/etc.) and not supported (C/C++ vs Java) on both sides.
  • Macros exists only on the thin side (Lisps, Dylan, Nemerle). There doesn't seem to be any obvious reason for it.


I could go on. It actually surprises me how many semantic differences follow the thin vs fat divide, with Perl and Java being the biggest outliers (and also their derivatives like PHP and C#). These outliers are very interesting. Java's lack of power is definitely syntactic not semantic and there is plenty of JVM languages which are little more than fully compatible alternative syntaxes for Java with more expressive power. Nothing like that ever happened to popular fat variable languages like C/C++, which fail for semantic not syntactic reasons.

The biggest outlier on the fat side in Perl. While Perl was able to get almost 100% score on supported features checklist, it seems to be an evolutionary dead end. Every new thin variable language steals ideas from Perl, but Perl 6 effort was never able to transform the language, and Perl programmers have been leaving for Ruby and Python for years now.

If you're writing a new language today, and every programmer should do that, just forget about fat variables. They have one big advantage of allowing explicit memory management, what can still result in more memory efficient programs, but that's about it. Expressiveness of fat variable languages have been pushed to the limits by Perl, and it seems it cannot be pushed any further. Thin side is already far ahead, with Ruby, Scheme, Haskell and all the small research languages you've never heard of.

Monday, October 06, 2008

Rome Total War strategy guide

cat&stone by Ray Chang from flickr (CC-NC-SA)
I'm not sure why but all strategy guides I've seen on the Internet suggest gameplay very different from how I've been playing. It's quite likely that on higher difficulty the strategy I'm proposing doesn't work any more, so you should listen to them instead of me.

In a way of full disclosure I play with fog of war turned off (~ toggle_fow), Follow AI movement turned off (in menu when you start), and battle camera movement restriction turned off (~ toggle_restrictcam). I don't think it affects difficulty at all, it mostly makes interface nicer.

You already know map of Europe, and turning off FOW doesn't reveal enemy units or buildings, so you still need some spies to learn that. Battle camera restrictions make giving orders to your units in battle much harder, especially when the battle gets bigger or you get some reinforcements. It's just user interface pain in the ass, so I got rid of it. I also played with low unit size not to fry my GPU, but it seemed to handle it quite nicely, so maybe I'll up it to medium next time.

Economy

I think the most confusing part of Rome: Total War interface is city income. Real city income is revenue minus garrison cost. Income displayed by the game is revenue minus total cost of your army divided proportionally to city population. This leads to bullshit numbers, as revenue is not growing proportionally to population. So totally ignore city income figures.

You want as much revenue and as little spending as possible. Two most important revenue sources are sea trade, and land trade. Build best ports you can, and paved roads (or even highways) as early as possible, and get trade right with everyone. Trade-enhancing buildings like traders, market etc. are also very useful. Trade revenues grow only slowly with city size, so you basically want to have as many cities as you can, even if they're quite small, as long you they can build paved roads or port (that's level 2).

The second biggest source of income is farming and mining. Because it doesn't depend on city size at all, it's better to build basic farming and mining everywhere you can before you build advanced farming/mining. For 4000 you can build two mines in two cities, producing 400/turn. If you built mines+mines upgrade in one city instead it would cost you 5500 and produce only 350/turn. It's quite similar with farms - it's cheaper to have a little everywhere than to concentrate them all in one place.

Your next major source of income are wonders. Hanging Gardens give you +20% to farming income, unfortunately it's on the edge of the map. Colossus of Rhodes is even better as gives you +40% to naval trade income and is often barely defended by very weak Greek Cities faction.

Taxes aren't worth that much. There's some tricky equation to make them grow much slower than population, so big cities produce maybe ten times less in taxes than you'd expect. And in any case tax income is going to be much lower than trade income, and as higher tax rates reduce growth and public order I normally set all tax rates to Low by default. In smaller settlements it's important for the sake of growth, in larger settlements for the sake of public order. If you don't want to grow the settlement any more and it has high public order you could set tax rates higher, but it's usually not worth the bother.

Public order

It's important to keep your public order high, otherwise citizens can rebel damaging population, buildings, and your soldiers, brigands will spawn more often, and the whole city may even rebel throwing your garrison away. If a big city with a lot of military buildings rebels they will have a very respectable army and will be a major pain in the ass to retake.

Public order is determined by many factors. First is distance to capital, with very distant settlements getting even as much as -80%. So move your capital close to center of your empire every now and then and try to conquer in one nice block, not random settlements all over the map. Starting positions of Carthage, Greek Cities and Parthia are pretty bad for this reason. It will also make your empire easier to defend, another reason to try having solid empire. There's even a Javascript app to determine best location for your capital.

Another is culture penalty. I'm not exactly sure how it's calculated, but it's based on buildings from foreign cultures. There are six cultures - Barbarian (Britons, Dacia, Gauls, Germans, Scythia, Spain), Carthaginian (Carthage, Numidia), Eastern (Armenia, Parthia, Pontus), Egyptian (Egypt), Greek (Greek Cities, Macedon, Seleucid, Thrace), and Roman (Brutii, Julii, Scipii, Senate), and conquering within your culture should give you no penalty.

Government buildings and religious buildings having the biggest effect, so the first thing you want to do to reduce it is destroying any religious building they might have and building your own. Then upgrade all buildings you can, especially government building, as upgrading removes culture penalty for them. If you cannot upgrade, you can sometimes destroy and rebuild, what's going to cost you some money but it will work. Unfortunately you cannot destroy many buildings, especially the important government buildings, so you might need to live with some culture penalty forever.

The next important factor is unrest. Unrest starts high when you conquer a city, and then goes down by 5% until reaching the base level, but only if public order is at least 75%. So if you can get a conquered city to 75% by temporary measures like large garrison and good governor then just by staying in the city for a few turns the unrest will disappear. On the other hand if you cannot even reach 75% you will have pretty much permanent problems with the city. Well, not really permanent as rioting kills of citizens, what solves your problem slowly, but if you think the city is going to be a problem, just enslave it, and by the time it grows back it will have no unrest. Basic unrest rates are 0% for most cities but can be 15% for many and even 30% for a few like Jerusalem.

The next factor is squalor, based on city size. Big cities simply have high squalor, and it makes people unhappy. That's why when you're conquering a new city, with high distance to capital, high culture penalty, high unrest, and high squalor, it will be totally ungovernable. Better to enslave or even exterminate its population to reduce squalor, then quickly raze their temples and build your own to reduce culture penalty, keep large garrison in it for a few turns to reduce unrest, and keep capital close to center of your empire to make distance to capital penalties manageable.

To increase public order you can build buildings, especially religious buildings which usually give you +10% increase per level. Some give you only +5% and some other bonus, so you need to decide if the extra bonus is worth losing 5-25% of public order (depending on city size, unfortunately you cannot change your mind easily later, you'd need to raze the temple completely and start from shrine). Depending on culture there are some other buildings like execution square, odeon, tavern etc.

Wonders are also helpful here. Statue of Zeus at Olympia gives you permanent bonus to all your settlements, capturing any wonder gives you a high bonus for a few turns but it wears off too quickly to be worth relying on.

Influence rating of the governor improves public unrest, but you won't have enough governors with high influence for all of your empire. I never did it, but maybe you could try a shitty governor and building an academy for him to get better stats. Governors can also get useful retinue from religious building.

A very important way of improving public order is garrison. The most important fact is that the bonus is based on ratio of total number of troops to total population. So 30 peasants are worth as much as 30 cataphracts. But everything including Town Guard is significantly more expensive per person than peasants - so seriously use only peasants as a garrison. Using serious combat troops for garrison in all your cities is going to cost you a lot of money, and you cannot even use them for crushing rebellions, as then you'd need another way of keeping your public order up.

Also - only use garrisons in small to medium settlements. In a small settlement, one stack of peasants can give you +80% garrison bonus (you can never go higher than that) and will cost you 100 denari/turn. In a large settlement, one stack of peasants will give you less than +5% and sitll cost you 100 denari/turn. Every other method costs the same no matter the settlement size. So it simply makes no sense to use garrison as a way of keeping large settlements happy, unless you positively have to. Much more effective ways are low taxes, religious buildings, governor influence, games, wonders etc. Oh and having absolutely no troops in a settlement gives it extra -15%, not to mention making it super easy to lose, so keep at least some peasants in all of them.

Tactics

Most strategy guides talk a lot about advanced unit types, but unless you play very slowly you will only get them in the end game, when you're so strong that it doesn't really matter that much.

A very important unit type are peasants, which you should use exclusively for garrisoning, but never for battles. Peasant garrisons are half the upkeep costs of the weakest battle units, so use them. If you have some spare peasants you can take them with your army so they can serve as an occupying force for the captured settlements, while your real forces go forward. Or maybe if someone needs to hold battering rams and you have pure-cavalry army, but that's already getting somewhat dubious.

One of the nicest things about Rome: Total War is richness of unit types and tactics you can develop with different combinations of unit types against different combinations of enemy unit types.

Many tactics can be formed around phalanges. First you take a wall of any units capable of forming a phalanx, which most factions can get almost immediately. Then you make either your opponent run into the wall of spears, or attack your opponent with this wall. If you set guard mode on your units will try to keep the wall of spears, if you set it to off they will break it to attack the enemy. Either can be useful depending on circumstances.

Even a phalanx formed with very cheap units can kill most of enemies. Non-phalanx infantry, and light cavalry will simply get massacred. With heavy cavalry, elephant, and chariots it's not that simple. Depending on your and their strength they might be killed by your phalanx (instant win) or break it (instant lose), but often they will simply get entangled in it without getting killed. Now it's time to attack, either with adjacent phalanx unit, or even better with your cavalry attacking from a side or a back. You will have some loses in your cheap phalanx, but you'll kill a much more expensive heavy cavalry unit this way, for a major win.

To fight with other phalanx you simply form a pushing match. If you have stronger phalanx, especially one with longer spears, you can outstab the enemy. If not, just attack the enemy phalanx with some cavalry while they cannot move.

The main problem with phalanges is that they are very vulnerable from flanks and back, so you want to keep some cavalry, or at least some non-phalanx infantry on both wings. Not only will it protect your phalanx, they can attack and destroy any enemy captured by it.

If enemy has some cavalry, you might want to take all your cavalry, charge into his, and try to destroy it before the infantry battle begins. Cavalry has very high charge bonuses so by properly maneuvering you can do disproportionate damage even without very strong units. If they rout, don't follow but go back to wings of your formation - you won't catch horses with horses, and your cavalry is too important to waste just yet. Even if the enemy reforms they won't have much morale left and you can rerout them later with a simple charge.

It's important to have cavalry superiority, even though the cavalry won't win the battle for you. If you charge at a phalanx, or even straightforward melee infantry, you're going to suffer heavy loses. Cavalry is strong because of high charge bonus, if they're entangled they suddenly become very vulnerable. There are some units you can safely charge at - missile units like archers/bowmen, peltasts/velites/skirmishers etc.; very light infantry like rebel peasants; other cavalry units, including generals (who are weak without their bonus charge); and later artillery units. Charging at anything else means high loses even with relatively heavy cavalry, and is outright suicidal for light cavalry. Even if some unit is weak, you can still suffer if there's a strong unit in its proximity. So obviously bowmen shouldn't be left without protection.

Another important thing you can do with cavalry is killing off routing infantry units. The difference between defeated army suffering 30% loses refilled in the first visit to nearby city, and 90% loses that are impossible to refill comes from your cavalry. Normally infantry cannot catch routing infantry, and cavalry cannot catch routing cavalry, so the only kind of massacre you will be able to do is cavalry massacring routing infantry. Even the cheapest light cavalry is very important just for this purpose.

If you have cavalry superiority you can get some missile units, or later some artillery. They are very weak against cavalry, and it's not too easy to protect them using just infantry after the chaos of the battle starts. Your tactics depends on range of your missile units, so usually it makes no sense at all to have multiple kinds of missile units in the same army. Either take all bowmen, or all peltasts, or all onagers, or some other consistent army.

Missile units cause free damage to your opponents. They can try to stand it out until you run out of ammo and suffer heavy casualties, or else they'll be forced to attack you on your terms. If the enemy has no cavalry and no missile units (or you just killed them with your cavalry), you can even send your missile units in skirmish mode way in front of your main units to pepper them with arrows and javelins. Normally however you want to keep them close to your units, either behind your main infantry line, or just in front and then making them fall back when the attack finally happens.

Missile troops alone are not going to win the battle. But with enough damage the enemy will be losing morale and will rout more easily. After some of the enemy starts routing the battle is pretty much won, and just use your cavalry to kill off what's left. Missile units are also quite useful at finishing off routing units.

There are a few more tactics you can try. Romans have strong infantry units that throw javelins before attacking. It's like an ok missile troop and a good melee troop in one unit. If you stand against enemy phalanx with Roman infantry try splitting your troops and attacking from flanks. It might work just fine.

Chariots are like heavy cavalry except you can have them very early in the right faction like Egypt and Seleucids. They have even lower defense than normal cavalry, so try charging through enemy unit to the other site, not on enemy unit. Also, never let enemy missile units fire at your chariots, or anybody to attack a standing chariot. It takes some practice to learn how to use chariots properly, but it's fully worth the effort.

If you have mixed heavy and light cavalry and want to charge a strong unit, charge with your heavy cavalry first, immediately followed by the light cavalry. This reduces your loses a lot. On the initial charge will still be capable of defending itself, so a heavy charge is needed. Just afterwards it will be completely disorganized so even light cavalry will be able to make a kill.

Sieges

You're not fighting for the sake of fighting, you're fighting to conquer, so many battles will be sieges. The good news is that in early game most settlements will at most wooden wall. Just make one battering ram, and here we go. Easy way to win a siege is having missile units and cavalry. Take battering ram and missile units to the gates, and fire at anybody standing next to the gate. Because unlike in a field battle they're not going to charge at you, if you're patient you can empty all your ammo on them and inflict severe loses, no need to hurry with the ram.

Once it's done take your cavalry and charge at everybody. Hopefully there aren't any strong phalanges in the vicinity of the gate now that you peppered them with arrows. Everything else will just rout when charged. It's important to kill them off now, otherwise they'll run towards the town square and reform there. As you go toward the town square just charge on every unit you find on the streets. AI tends not to offer any organized resistance on the streets, so it's going to be an easy kill. You may find some serious resistance in the town square, hopefully by this time you inflicted sufficient damage that it's just a matter of finishing everyone off.

In my experience for settlements without at least stone walls, AI defending army is a hell lot weaker than the same army would be on a field.

It's much much worse if they have stone walls and some missile units to man the walls. Because they're higher and protected by walls they're easily ten times as deadly as your missile units shooting at them. Add to that fire coming from towers, and reinforced games slowing down ramming a lot, and you can lose a quarter of your army before even coming inside.

You can obviously starve them, forcing them to attack you, but that's going to be very slow. Fortunately there's a much better way. First you need at least one hole in the walls. In can be gate opened by your spy, or a sap point, or hole made by your onagers if you already have them (onagers come late in the game, but so do stone walls). Then charge with all your cavalry, the more and heavier the better, and go towards the city center as soon as possible. By not wasting time on the gates and moving all your units at an instant you won't get fired upon that much. If you take the city center the enemy has 3 minutes to take it back or they lose and all die, so they'll have to go off their comfy wall posts and fight on the street, and they really suck at it.

If you make more holes you can choose one that will take you away from the walls as soon as possible, and that's the least defended. If you have some artillery you can even try to shoot at units protecting the hole to make it easier for your cavalry to charge over them. Unfortunately bowmen won't do, as enemy bowmen have better range while on the walls.

If this siege tactic won't work, well starving them is always an option.

I wouldn't depend on city defenses too much. Walls delay the enemy, but you still need enough field army to defeat him. Otherwise he can just starve you off.

Strategy

In Rome: Total War there's a very smooth transition between high level strategy and battle tactics, with both level affecting each other. Your strategic choices will have major impact on your battles, and your battles will have major strategic implications.

Unfortunately diplomacy is pretty much broken, and all AIs will attack you sooner rather than later, so you cannot go to the very high level and try forging one alliance against another alliance. Sadly it's like that in almost every strategy game I can think of. At least everybody against the player is better than everybody pussying out from every fight and letting you do whatever you want like in Colonization. So don't think too much about diplomacy.

You should have some idea on how you're going to play. In my last game with Egyptians I took all my armies, bought all the mercenaries I could, and expanded in three directions at once, west to Siwa and Cyrene, east to Petra, and Bostra, and north-west to Kydonia, and Sparta. Initial battles were tough, but this way I had a decent empire before anybody could even react. This plan was very ambitious, and it's quite likely that it might not have worked on higher difficulty levels, but it's a good idea to have some plan before starting to play.

It's important to move early, as you get some decent army to start with, often with units that you won't be able to make for a long time, while everybody's armies are still quite small and many settlements are barely defended, especially the rebel ones.

It's plenty of fun to start a war, but before you do think how you're going to end it. Can you take all enemy settlements quickly? Or at least all that are nearby, if the enemy is all over the place like Greek Cities, Carthage, and Parthia.

If you don't think of it, you might get into a long trench warfare that someone else will use to backstab you. In my last game I wasn't thinking enough about this and at one point I had wars with Parthia, Armenia, Seleucids, Pontus, Greek Cities, Macedon, Thrace, and all four Roman factions.

Your armies are investment. Don't keep them in secure cities. Actually don't keep them in cities at all - peasants should patrol cities, all your armies should be in the field fighting. Upkeep is very high compared to initial cost. Typically cost is about three turns worth of upkeep. So if you have a unit that's going to spend four or more turns doing nothing it's cheaper to disband it and make a new one when it's needed. You cannot make them as fast as you'd like to and you'd lose all experience, so maybe the threshold is higher than four, but armies should fight.

If you need some troops fast, and are far from your lands you might want to get some mercenaries, but normally cheaper and stronger units are available in your cities. Exception are units that you cannot produce but would like to, like Sarmatian Cavalry, and Createan Archers, depending on your faction.

Bribing is even more dubious practice. It costs more to bribe than to recruit an army (even mercenary army), defeat whoever you were thinking of bribing, and disband just afterwards. Bribing should be thought of as a really special case situation. Maybe if you want to bribe generals, because you cannot normally recruit them. But you can recruit a unit, take it into a fight, and you have a chance of getting "man of the hour" free general. I got plenty of generals this way.

Navy is expensive. You can do two things with Navy. In early game you want to transport armies from one coast to the other in a single turn (or otherwise as quickly as possible), so they are never vulnerable. There's no point fighting at this point, unless someone is trying to blockade you and you really have no choice.

The other thing is total domination of a sea. If you have plenty of money you can buy enough ships to take total control of a large body of water, like "whole Mediterranean sea east of Sicily". Just buy loads of ships, attack everywhere it in, then you can blockade everything, and safely transport all your troops.

There's little reason to go between the two extremely. Semi-strong navy that won't protect your transports is just throwing money away. If your navy isn't useful any more, just disband it.

When you're waging a war on a strategic level it's important to achieve local superiority of force. It doesn't matter who's got more units on the entire map. What matters is who's got more and better units in the place of battle. So go completely out of proportion, committing all your armies you can to the small part of the front where you want to achieve your objectives, like conquering enemy city, or destroying his not very strong armies. If AI has weakly protected settlement, take your big army and take it. If it has medium sized army in the field, crush it with army twice the size. If it took all its strongest units and heads towards your capital, raid his territory and force it to go back home.

You will be much more mobile if you have paved roads, a bit of navy, and no sense of fear. It's even more important to have all your battle troops on the front, not back home patrolling streets.

The biggest factor however is economy strong enough that you can easily raise new armies and replace your loses while the opponent cannot, even if they manage to win a few big battles, because that's how Rome became great!