After identifying a lot of variables, offsets and subroutines in civ.exe, I as now able to decode the battle algorithm of Civilization. The results were really interesting, sometimes even surprising 
The algorithm strictly uses integer arithmetics, so when dividing, any fractions are lost. To keep this from influencing the battle calculations, both the attack and defense strength are effectively multiplied by 8. This allows for 3 different 50% bonuses to be applied consecutively without any loss of accuracy.
There are three modifiers which influence the chances of sucess and failure. To keep the step-by-step descriptions short and simple, I will explain these modifiers beforehand:
The Difficulty Modifier is only applied to Barbarian units. It is 1 on Chieftain, 2 on Warlord, 3 on Prince, 4 on King and 5 on Emperor difficulty.
The Terrain Modifier depends on the on the map square the defending unit is located at. It is 6 on mountains, 4 on hills, 3 on forest/jungle/swamp/river, and 2 on any other terrain types.
The Fortification Modifier of the defending unit is 8 if it is inside a fortress, 6 of it is fortified and NOT inside a fortress, and 4 if it is neither inside a fortress nor fortified.
Now before the units can actually fight, the game has to calculated their respective strengths, which brings us to...
Attack Strength Calculation Step-by-Step
Step 1: Determine the nominal attack value of the attacking unit and multiply it by 8.
Step 2: If the attacking unit is a Barbarian unit and the defending unit is player-controlled, multiply the attack strength by the Difficulty Modifier, then divide it by 4.
Step 3: If the attacking unit is a Barbarian unit and the defensing unit is AI-controlled, divide the attack strength by 2.
Step 4: If the attacking unit is a Barbarian unit and the defending unit is inside a city and the defending civilization does not control any other cities, set the attack strength to zero.
This actually makes the defending unit invincible in this special case. Might well save you from being obliterated by that unlucky hut at 3600BC.
Step 5: If the attacking unit is a Barbarian unit and the defending unit is inside a city with a Palace, divide the attack strength by 2.
Step 6: If the attacking unit is a veteran unit, increase the attack strength by 50%.
Step 7: If the attacking unit has only 0.2 movement points left, multiply the attack strength by 2, then divide it by 3. If the attacking unit has only 0.1 movement points left, then just divide by 3 instead.
Step 8: If the attacking unit is a Barbarian unit and the defending unit is player-controlled, check the difficulty level. On Chieftain and Warlord levels, divide the attack strength by 2.
Step 9: If the attacking unit is player-controlled, check the difficulty level. On Chieftain level, multiply the attack strength by 2.
So on Chieftain difficulty, it is often better to attack than be attacked, even with a defensive unit.
The combined Barbarian attack factors (against player-controlled units) from steps 2 and 8 are 12.5% on Chieftain, 25% on Warlord, 75% on Prince, 100% on King, and 125% on Emperor level.
Defense Strength Calculation Step-by-Step
Step 1: Determine the nominal defense value of defending unit.
Step 2: If the defending unit is a ground unit, multiply the defense strength by the Terrain Modifier.
This modifier effectively includes a factor of 2.
Step 3: If the defending unit is a ground unit, multiply the defense strength by the Fortification Modifier.
This modifier effectively includes a factor of 4, resulting in a combined factor of 8.
Step 4: If the defending unit is a sea or air unit, multiply the defense strength by 8.
This effectively treats the Terrain Modifier as 2, regardless of the actual terrain type. It also means that these units will never benefit from the Fortification Modifier.[/b]
Step 5: If the defending unit is inside a city with City Walls and the nominal attack value of the attacking unit is NOT equal to 12, check the domain of the defending unit. If the domain is NOT air, re-calculate steps 1 and 2 (ignore steps 3 and 4) and multiply the result by 12.
When determining if the attacking unit ignores City Walls, the game just checks for attack value, not unit type. So if you change any unit's attack rating to 12, the game will have it ignore City Walls as well.
Step 6: If the defending unit is a veteran unit, increase the defense strength by 50%.
Note that sea unit inside a city with City Walls will actually get the Terrain Modifier. This may be an omission from the programmers' side.
Also note that the bonuses from fortress, City Walls, and being fortified are mutually exclusive.
Determining the Main Defender of a Stack
If there are 2 or more units on the attacked square, then the game pre-calculates their defense strength, factoring in only the nominal defense value, the Terrain Modifier (not on ocean squares), the Veteran Bonus and a 50% bonus if the unit is fortified (not on ocean squares). The unit with the highest pre-calculated defense value is chosen as defender of the stack. If it's a tie, then unit with the lower unit ID takes precedence.
This may not be the optimal choice on fortress/city squares, because in these cases fortifying a unit does not make a difference in terms of defense strength.
In any case, the game will only consider the first 10 units of the stack (sorted by unit ID).
On ocean squares, the game will only consider sea units. If no sea unit is found among the first 10 units, the game will just choose the unit with the lowest ID, regardless of its domain.
Battle Outcome Determination
The game randomly generates a number between 0 (included) and the attack strength (excluded if greater than zero) of the attacking unit.
Likewise it also randomly generates a number between 0 (included) and the defense strength (excluded if greater than zero) of the defending unit.
The higher number wins. If it is a tie, the defender wins.
However, if the attacking unit is a Barbarian unit and the defending unit is inside a city, then, if the attacking unit won, the procedure will be repeated once. This time, the attacking unit wins on a tie. If the defending unit wins at least one out of the two rounds, it wins the battle.
Since an attacker rolling a zero will always lose, it's possible to lose any attacking unit even to a Diplomat. A non-veteran militia with 0.1 movement points only has a success chance of 50%, and even a veteran battleship will still fail in 1 out of 216 cases.
Determining the chance of victory is a bit complicated.
For the following formulae to work, if any of the attack/defense strengths are zero, you have to treat them as 1 instead.
If the attack strength (a) of the attacker is higher than the defense (d) strength of the defender, then the defender's victory chance is equal to
(d + 1) / (2 * a) ,
and the attacker's victory chance is then easily calculated by subtracting the above result from 1.
On the other hand, if the defense strength (d) of the defender is higher than (or equal to) the attack strength (a) of the attacker, then the attacker's victory chance is equal to
(a - 1) / (2 * d) ,
and again the defender's victory chance can be obtained by subtracting that result from 1.
This can lead to some unexpected probabilities. For example, one would "naturally" assume that (if no other modifiers are present) a militia with an attack rating of 1 roughly has a 33% chance of successfully attacking a phalanx with a defense rating of 2. But the actual chance is only 7/32, which is less than 22%.
For the re-roll (if a Barbarian unit attacks a city), replace the first formula by
(d - 1) / (2 * a)
and the second one by
(a + 1) / (2 * d)
to account for a tie now favoring the attacker instead of the defender.
Example
Veteran Bomber attacks veteran fortified Musketeers on a Forest square:
Attack Strength is...
... 8 * 12 = 96 after Step 1,
... 96 + 96/2 = 144 after Step 6.
(the other steps do not apply)
Defense Strength is...
... 3 after Step 1,
... 3 * 3 = 9 after Step 2,
... 9 * 6 = 54 after Step 3,
... 54 + 54/2 = 81 after Step 6.
(the other steps do not apply)
Minimum attacker's roll is 0, maximum is 143. Minimum defender's roll is 0, maximum is 80.
Determining the victory chance for the Musketeers:
(d + 1) / (2 * a) = 82/288 = 41/144 (approx. 28.5%)
Determining the victory chance for the Bomber:
1 - 41/144 = 144/144 - 41/144 = 103/144 (approx. 71.5%)
One More Example
Non-veteran Barbarian Legion attacks non-veteran fortified player-controlled Phalanx inside a city (no Palace and not the last city of the defending civ) on a River square, at Emperor level:
Attack Strength is...
... 3 * 8 = 24 after Step 1,
... 24 * 5/4 = 30 after Step 2.
(the other steps do not apply)
Defense Strength it...
... 2 after Step 1,
... 2 * 3 = 6 after Step 2,
... 6 * 6 = 36 after Step 3.
(the other steps do not apply)
Minimum attacker's roll is 0, maximum is 29. Minimum defender's roll is 0, maximum is 35.
Chance for the Legion to win the first round:
(a - 1) / (2 * d) = 29/72 (approx. 40.3%)
Chance for the Legion to win the second round (it needs to win both rounds in order to succeed):
(a + 1) / (2 * d) = 31/72 (approx. 43.1%)
To determine the victory chance for the Legion, multiply both chances:
29/72 * 31/72 = 899/5184 (approx. 17.3%)
Determining the victory chance for the Phalanx:
1 - 899/5184 = 5184/5184 - 899/5184 = 4285/5184 (approx. 82.7%)
Aftermath
After the battle, the victorious unit has a 50% chance to receive veteran status.
An attack by a bomber ends its turn. The game checks specifically for unit type 0x0F (Bomber).
If the attacking unit wins the battle and the defending unit was not inside a city or fortress, then game tries to delete all units at the defender's map square. If the unit type of the attacking unit is equal to 0x19 (Nuclear), then the game tries to delete all units at the defender's square and on all adjacent squares (except for units inside cities with SDI defenses, of course).
Now there's a built-in limitation: If there are more than 10 units at a square, the game will only delete 10 of them (more precisely, the 10 units with the lowest unit IDs). The remaining units will be unaffected.
Most of the time, this will be more than enough, but sometimes there will be survivors, especially when hitting a city with a nuke late-game.
Note that this also applies to a possible stack of attackers. Normally the Nuclear will, by nature, not be part of a unit stack. But technically it's possible. And since a Nuclear, unlike a Bomber, does not automatically end its turn after attacking, if would be possible to put 10 other units with lower IDs on the same square as the attacking Nuclear and have the Nuclear survive (so it could attack a second time ^^).
Any map square affected by a nuclear strike has a chance of 2/3 to become polluted, except for city squares, ocean squares, and squares which are already polluted.
The algorithm strictly uses integer arithmetics, so when dividing, any fractions are lost. To keep this from influencing the battle calculations, both the attack and defense strength are effectively multiplied by 8. This allows for 3 different 50% bonuses to be applied consecutively without any loss of accuracy.
There are three modifiers which influence the chances of sucess and failure. To keep the step-by-step descriptions short and simple, I will explain these modifiers beforehand:
The Difficulty Modifier is only applied to Barbarian units. It is 1 on Chieftain, 2 on Warlord, 3 on Prince, 4 on King and 5 on Emperor difficulty.
The Terrain Modifier depends on the on the map square the defending unit is located at. It is 6 on mountains, 4 on hills, 3 on forest/jungle/swamp/river, and 2 on any other terrain types.
The Fortification Modifier of the defending unit is 8 if it is inside a fortress, 6 of it is fortified and NOT inside a fortress, and 4 if it is neither inside a fortress nor fortified.
Now before the units can actually fight, the game has to calculated their respective strengths, which brings us to...
Attack Strength Calculation Step-by-Step
Step 1: Determine the nominal attack value of the attacking unit and multiply it by 8.
Step 2: If the attacking unit is a Barbarian unit and the defending unit is player-controlled, multiply the attack strength by the Difficulty Modifier, then divide it by 4.
Step 3: If the attacking unit is a Barbarian unit and the defensing unit is AI-controlled, divide the attack strength by 2.
Step 4: If the attacking unit is a Barbarian unit and the defending unit is inside a city and the defending civilization does not control any other cities, set the attack strength to zero.
This actually makes the defending unit invincible in this special case. Might well save you from being obliterated by that unlucky hut at 3600BC.
Step 5: If the attacking unit is a Barbarian unit and the defending unit is inside a city with a Palace, divide the attack strength by 2.
Step 6: If the attacking unit is a veteran unit, increase the attack strength by 50%.
Step 7: If the attacking unit has only 0.2 movement points left, multiply the attack strength by 2, then divide it by 3. If the attacking unit has only 0.1 movement points left, then just divide by 3 instead.
Step 8: If the attacking unit is a Barbarian unit and the defending unit is player-controlled, check the difficulty level. On Chieftain and Warlord levels, divide the attack strength by 2.
Step 9: If the attacking unit is player-controlled, check the difficulty level. On Chieftain level, multiply the attack strength by 2.
So on Chieftain difficulty, it is often better to attack than be attacked, even with a defensive unit.
The combined Barbarian attack factors (against player-controlled units) from steps 2 and 8 are 12.5% on Chieftain, 25% on Warlord, 75% on Prince, 100% on King, and 125% on Emperor level.
Defense Strength Calculation Step-by-Step
Step 1: Determine the nominal defense value of defending unit.
Step 2: If the defending unit is a ground unit, multiply the defense strength by the Terrain Modifier.
This modifier effectively includes a factor of 2.
Step 3: If the defending unit is a ground unit, multiply the defense strength by the Fortification Modifier.
This modifier effectively includes a factor of 4, resulting in a combined factor of 8.
Step 4: If the defending unit is a sea or air unit, multiply the defense strength by 8.
This effectively treats the Terrain Modifier as 2, regardless of the actual terrain type. It also means that these units will never benefit from the Fortification Modifier.[/b]
Step 5: If the defending unit is inside a city with City Walls and the nominal attack value of the attacking unit is NOT equal to 12, check the domain of the defending unit. If the domain is NOT air, re-calculate steps 1 and 2 (ignore steps 3 and 4) and multiply the result by 12.
When determining if the attacking unit ignores City Walls, the game just checks for attack value, not unit type. So if you change any unit's attack rating to 12, the game will have it ignore City Walls as well.
Step 6: If the defending unit is a veteran unit, increase the defense strength by 50%.
Note that sea unit inside a city with City Walls will actually get the Terrain Modifier. This may be an omission from the programmers' side.
Also note that the bonuses from fortress, City Walls, and being fortified are mutually exclusive.
Determining the Main Defender of a Stack
If there are 2 or more units on the attacked square, then the game pre-calculates their defense strength, factoring in only the nominal defense value, the Terrain Modifier (not on ocean squares), the Veteran Bonus and a 50% bonus if the unit is fortified (not on ocean squares). The unit with the highest pre-calculated defense value is chosen as defender of the stack. If it's a tie, then unit with the lower unit ID takes precedence.
This may not be the optimal choice on fortress/city squares, because in these cases fortifying a unit does not make a difference in terms of defense strength.
In any case, the game will only consider the first 10 units of the stack (sorted by unit ID).
On ocean squares, the game will only consider sea units. If no sea unit is found among the first 10 units, the game will just choose the unit with the lowest ID, regardless of its domain.
Battle Outcome Determination
The game randomly generates a number between 0 (included) and the attack strength (excluded if greater than zero) of the attacking unit.
Likewise it also randomly generates a number between 0 (included) and the defense strength (excluded if greater than zero) of the defending unit.
The higher number wins. If it is a tie, the defender wins.
However, if the attacking unit is a Barbarian unit and the defending unit is inside a city, then, if the attacking unit won, the procedure will be repeated once. This time, the attacking unit wins on a tie. If the defending unit wins at least one out of the two rounds, it wins the battle.
Since an attacker rolling a zero will always lose, it's possible to lose any attacking unit even to a Diplomat. A non-veteran militia with 0.1 movement points only has a success chance of 50%, and even a veteran battleship will still fail in 1 out of 216 cases.
Determining the chance of victory is a bit complicated.
For the following formulae to work, if any of the attack/defense strengths are zero, you have to treat them as 1 instead.
If the attack strength (a) of the attacker is higher than the defense (d) strength of the defender, then the defender's victory chance is equal to
(d + 1) / (2 * a) ,
and the attacker's victory chance is then easily calculated by subtracting the above result from 1.
On the other hand, if the defense strength (d) of the defender is higher than (or equal to) the attack strength (a) of the attacker, then the attacker's victory chance is equal to
(a - 1) / (2 * d) ,
and again the defender's victory chance can be obtained by subtracting that result from 1.
This can lead to some unexpected probabilities. For example, one would "naturally" assume that (if no other modifiers are present) a militia with an attack rating of 1 roughly has a 33% chance of successfully attacking a phalanx with a defense rating of 2. But the actual chance is only 7/32, which is less than 22%.
For the re-roll (if a Barbarian unit attacks a city), replace the first formula by
(d - 1) / (2 * a)
and the second one by
(a + 1) / (2 * d)
to account for a tie now favoring the attacker instead of the defender.
Example
Veteran Bomber attacks veteran fortified Musketeers on a Forest square:
Attack Strength is...
... 8 * 12 = 96 after Step 1,
... 96 + 96/2 = 144 after Step 6.
(the other steps do not apply)
Defense Strength is...
... 3 after Step 1,
... 3 * 3 = 9 after Step 2,
... 9 * 6 = 54 after Step 3,
... 54 + 54/2 = 81 after Step 6.
(the other steps do not apply)
Minimum attacker's roll is 0, maximum is 143. Minimum defender's roll is 0, maximum is 80.
Determining the victory chance for the Musketeers:
(d + 1) / (2 * a) = 82/288 = 41/144 (approx. 28.5%)
Determining the victory chance for the Bomber:
1 - 41/144 = 144/144 - 41/144 = 103/144 (approx. 71.5%)
One More Example
Non-veteran Barbarian Legion attacks non-veteran fortified player-controlled Phalanx inside a city (no Palace and not the last city of the defending civ) on a River square, at Emperor level:
Attack Strength is...
... 3 * 8 = 24 after Step 1,
... 24 * 5/4 = 30 after Step 2.
(the other steps do not apply)
Defense Strength it...
... 2 after Step 1,
... 2 * 3 = 6 after Step 2,
... 6 * 6 = 36 after Step 3.
(the other steps do not apply)
Minimum attacker's roll is 0, maximum is 29. Minimum defender's roll is 0, maximum is 35.
Chance for the Legion to win the first round:
(a - 1) / (2 * d) = 29/72 (approx. 40.3%)
Chance for the Legion to win the second round (it needs to win both rounds in order to succeed):
(a + 1) / (2 * d) = 31/72 (approx. 43.1%)
To determine the victory chance for the Legion, multiply both chances:
29/72 * 31/72 = 899/5184 (approx. 17.3%)
Determining the victory chance for the Phalanx:
1 - 899/5184 = 5184/5184 - 899/5184 = 4285/5184 (approx. 82.7%)
Aftermath
After the battle, the victorious unit has a 50% chance to receive veteran status.
An attack by a bomber ends its turn. The game checks specifically for unit type 0x0F (Bomber).
If the attacking unit wins the battle and the defending unit was not inside a city or fortress, then game tries to delete all units at the defender's map square. If the unit type of the attacking unit is equal to 0x19 (Nuclear), then the game tries to delete all units at the defender's square and on all adjacent squares (except for units inside cities with SDI defenses, of course).
Now there's a built-in limitation: If there are more than 10 units at a square, the game will only delete 10 of them (more precisely, the 10 units with the lowest unit IDs). The remaining units will be unaffected.
Most of the time, this will be more than enough, but sometimes there will be survivors, especially when hitting a city with a nuke late-game.
Note that this also applies to a possible stack of attackers. Normally the Nuclear will, by nature, not be part of a unit stack. But technically it's possible. And since a Nuclear, unlike a Bomber, does not automatically end its turn after attacking, if would be possible to put 10 other units with lower IDs on the same square as the attacking Nuclear and have the Nuclear survive (so it could attack a second time ^^).
Any map square affected by a nuclear strike has a chance of 2/3 to become polluted, except for city squares, ocean squares, and squares which are already polluted.
