Civ1 exploit: design flaw in randomness

• CIV uses a very classic "seed"-based random algorithm:
  • The algorithm is initialized with a pair of seed values S1 and S2, which are computed from the system date and time at CIV startup
  • The random routine takes a single integer N as argument, and returns a value from 0 to N-1 included, computed using complicated mathematical formulas involving the input value N, and the seed values S1 and S2
  • At the same time, every call to the random routine also re-updates the seed values S1 and S2

• first, it is quite hard to control the date and time when CIV starts
• second it is even harder to make sure that the date and time when CIV initializes the seeds is always the same, as your CPU make take more or less time between the launch of CIV.EXE and the instruction that compute the seed.

darkpanda said:

in addition, there are calls that, indeed, re-seed the randomness generator; typically, when displaying a City View, the random seed is re-initialized to the total sum of the city name's ASCII character codes (can you believe it! I just found this out 5 minutes ago...) while the 2nd variable is reset to 0; this ensures that a given city has always the same "random" - yet identical - streets and buildings layout

Click to expand...

• you could control when the seed is initialized by displaying a City view
• moreover, you could control the value of the initial seed - and thus the sequence of random values! - by choosing a carefully crafted City (name, size, buildings)

• The aim is to verify that randomness can be manipulated by displaying City View
• The initial condition: a newly started game, with just a 1-citizen capital city and a militia next to an unvisited tribal hut:
  
• I performed 3 series of tests: in each series, the test is run 10 times, and the outcome of the tribal hut visit by the militia is recorded:
  • Series 1: the saved initial condition is re-loaded using the F10-hack, then the militia visits the tribal hut
  • Series 2: the saved initial condition is re-loaded manually, by exiting then restarting CIV, then the militia visits the tribal hut
  • Series 3: the saved initial condition is re-loaded using the F10-hack, then the City View is displayed, and finally the militia visits the tribal hut
• Hereunder are the outcomes of the 3 series of tests:
  

  test #	series 1	series 2	series 3
  1	friendly tribe of skilled mercenaries (Cavalry)	friendly tribe of skilled mercenaries (Cavalry)	metal deposits of value 50
  2	scrolls of ancient wisdom (Masonry)	metal deposits of value 50	metal deposits of value 50
  3	scrolls of ancient wisdom (Alphabet)	friendly tribe of skilled mercenaries (Cavalry)	metal deposits of value 50
  4	scrolls of ancient wisdom (Horseback Riding)	scrolls of ancient wisdom (Alphabet)	metal deposits of value 50
  5	metal deposits of value 50	metal deposits of value 50	metal deposits of value 50
  6	metal deposits of value 50	friendly tribe of skilled mercenaries (Legion)	metal deposits of value 50
  7	metal deposits of value 50	scrolls of ancient wisdom (Masonry)	metal deposits of value 50
  8	metal deposits of value 50	scrolls of ancient wisdom (Alphabet)	metal deposits of value 50
  9	friendly tribe of skilled mercenaries (Legion)	metal deposits of value 50	metal deposits of value 50
  10	friendly tribe of skilled mercenaries (Cavalry)	scrolls of ancient wisdom (Alphabet)	metal deposits of value 50

• Initially, the city name is Ulundi (I skipped Zimbabwe by mistake on pressing ESC on the first turn...). According to the seed formula, its value is computed as the sum of the name's ASCII character codes:
  
  Code:

     U - 85
     l - 108
     u - 117
     n - 110
     d - 100
     i - 105
  ----------
  [B]seed = [COLOR="Blue"]625[/COLOR][/B]

• I incremented the seed to 626 by changing the name to Uluodi
• Then I re-ran the series 3 and obtained the following results:
  

  test #	series 3
  1	friendly tribe of skilled mercenaries (Cavalry)
  2	friendly tribe of skilled mercenaries (Cavalry)
  3	friendly tribe of skilled mercenaries (Cavalry)
  4	friendly tribe of skilled mercenaries (Cavalry)
  5	friendly tribe of skilled mercenaries (Cavalry)
  6	friendly tribe of skilled mercenaries (Cavalry)
  7	friendly tribe of skilled mercenaries (Cavalry)
  8	friendly tribe of skilled mercenaries (Cavalry)
  9	friendly tribe of skilled mercenaries (Cavalry)
  10	friendly tribe of skilled mercenaries (Cavalry)

• Series 4: the city size is 2
  
• Series 5: the city size is 2 and a Granary is built
  
• Series 6: the city size is 3
  
• Series 7: the city size is 3 and Barracks are built
  

• Will it work for a series of huts ? i.e. if I have several huts that can be visisted, and I display the city before each hut, will I get the same outcomes every time ?
• Can I force battles to be victorious, even if a militia attacks a fortified Mech. Inf. ?

Urtica dioica said:

I'd have to know more about exactly how the rand() function here works, but it should be possible to make a two-column table that shows what name to use for every kind of city, such that the next attacker is guaranteed to win, no matter what the units. I just reread Civ1 Combat Mechanics Explained, and it should work as long as the attack rand() call always returns positive, and the defense rand() always zero.

Click to expand...

Urtica dioica said:

I love this discovery. You just took a couple useless, purely cosmetic features (change city name, city view) and made them into a game-changing strategy. Beautiful.

Click to expand...

Urtica dioica said:

I probably should have checked for veteran status on my winning militia, but the thought didn't cross my mind. Oops.

Click to expand...

public class TestRandom2 {

	public static void main(String[] args) {
		TestRandom2 r0 = new TestRandom2(0x26A);
//		TestRandom2 r1 = new TestRandom2(10);
//		TestRandom2 r2 = new TestRandom2(10);
//		TestRandom2 r3 = new TestRandom2(10);
//		TestRandom2 r4 = new TestRandom2(10);

		int t = 50;
		
		int[][] tt = new int[5][t];
		
		for(int i=0;i<t;i++) {
			tt[0][i] = r0.next(2);   
//			tt[1][i] = r1.next(10);  
//			tt[2][i] = r2.next(20);  
//			tt[3][i] = r3.next(100); 
//			tt[4][i] = r4.next(250); 

			for(int j=0;j<1;j++) {
				System.out.print(""+tt[j][i]+(tt[j][i]<10?"   ":tt[j][i]<100?"  ":" ")+" seed1: "+r0.ds5BDA+" - seed2: "+r0.ds5BDC);
			}
			System.out.println();
		}
	}
	
	private short initialSeed;
	
	private long counter;

	private short _ax; // 16-bit AX register
	private short _bx; // 16-bit BX register
	private short _cx; // 16-bit CX register
	private short _dx; // 16-bit DX register

	boolean _zf = false; // ZERO flag
	boolean _cf = false; // CARRY flag
	boolean _of = false; // OVERFLOW flag

	java.util.Stack<Short> stack; 

	short ds5BDA; // seed 1, initially same as TerrainMasterWord
	short ds5BDC; // seed 2, initially 0

	public TestRandom2() {
		this((int)(System.currentTimeMillis()&0xFFFF));
	}
	
	public TestRandom2(int seed) {
		ds5BDA = (short) seed;
		initialSeed = (short) seed;
		ds5BDC = 0x0;
		stack = new java.util.Stack<Short>();
		counter = 0;
	}
	
	//Copy constructor
	public TestRandom2(TestRandom2 tr2) {
		ds5BDA = tr2.ds5BDA;
		initialSeed = tr2.initialSeed;
		ds5BDC = tr2.ds5BDC;
		stack = new java.util.Stack<Short>(); stack.addAll(tr2.stack);
		counter = tr2.counter;
	}

	public int next(int max) {
		_random((short) max);
		counter++;
		return _ax;
	}

	private void _asm_mul(short value) {
		int _eax = ((int)_ax)&0xFFFF;
		_eax *= value;
		_dx = (short) (_eax>>16);
		_ax = (short) (_eax);
		_cf = (_dx!=0x0);
		_of = _cf;
	}
	private void _asm_add_ax(short value) {
		int _eax = (((int)_ax)&0xFFFF) + (((int)value)&0xFFFF);
		_cf = ((_eax&0xFFFF0000) != 0);
		_ax = (short)(_eax);
	}
	private void _asm_add_dx(short value) {
		int _edx = (((int)_dx)&0xFFFF) + (((int)value)&0xFFFF);
		_cf = ((_edx&0xFFFF0000) != 0);
		_dx = (short)(_edx);
	}
	private void _asm_adc_dx(short value) {
		int _edx = (short) (_dx + value +(_cf?1:0));
		_cf = ((_edx&0xFFFF0000) != 0);
		_dx = (short)(_edx);
	}
	private void _asm_cwd() {
		_dx = (short) (_ax<0?-1:0);
	}
	void _asm_rcr_ax(int i) {
		boolean _tmpcf = _cf;
		_cf = ((_ax&0x1)==1);
		_ax >>= 1;
		if(_tmpcf) _ax |= 0x8000;
		else _ax &= 0x7FFF;
	}
	void _asm_sar_dx() {
		_cf = (_dx&0x1) == 0x1;
		_dx>>=1;
	}
	
	private void RandomPartFormula(short arg_0, short arg_2, short arg_4, short arg_6) {
		_ax = arg_2;
		_bx = arg_6;
		_bx |= _ax; _zf = (_bx==0);
		_bx = arg_4;
		if(_zf) {
			_ax = arg_0;
			_asm_mul(_bx);
		} else {
			_asm_mul(_bx);
			_cx = _ax;
			_ax = arg_0;
			_asm_mul(arg_6);
			_cx += _ax;
			_ax = arg_0;
			_asm_mul(_bx);
			//_dx += _cx; // TODO: actuall 'add' sets flags too
			_asm_add_dx(_cx);
		}
	}
	private void RandomSub1() {
		_ax = 0x43FD;
		_dx = 3;
		RandomPartFormula(ds5BDA,ds5BDC,_ax,_dx);
		_asm_add_ax((short) 0x9EC3);
		_asm_adc_dx((short) 0x26);
		ds5BDA = _ax;
		ds5BDC = _dx;
		_ax = _dx;
		_ax &= 0x7FFF;
	}
	
	private void RandomSub2() {
		_cx &= 0xFF; // xor ch,ch
		while(_cx!=0) {
			_asm_sar_dx();
			_asm_rcr_ax(1);
			_cx--;
		}
	}
	
	private void _random(short arg_0) {
		_ax = arg_0;
		_asm_cwd();
		stack.push(_dx);
		stack.push(_ax);
		
		RandomSub1();
		
		_asm_cwd();
		stack.push(_dx);
		stack.push(_ax);
		
		RandomPartFormula(stack.pop(),stack.pop(),stack.pop(),stack.pop());
		
		_cx = (short) ((_cx&0xFF00)|0x0F);
		
		RandomSub2();
	}

	public short getInitialSeed() {
		return initialSeed;
	}
	public long getCounter() {
		return counter;
	}

	public boolean equals(TestRandom2 tr2) {
		boolean eq = true;
		eq &= (initialSeed == tr2.initialSeed);
		eq &= (counter == tr2.counter);
		eq &= (ds5BDA == tr2.ds5BDA);
		eq &= (ds5BDC == tr2.ds5BDC);
		eq &= (stack.equals(tr2.stack));
		return eq;
	}
}

urbancaver said:

or always discover a scroll... How many civ advancements could you acquire simply from huts?

Click to expand...

kirkham7 said:

So, would it be possible to always discover a new city? It would be quite interesting to play a game and always get a new city when you find a hut.

Click to expand...

• It should be possible to get new cities or advances whenever you want, theoretically
• Correcting myself (1): return value '0' by the random routine does actually depend on input value N, but not in a problematic way, only partially
• Correcting myself (2): after a few DosBox-Debug runs, I discovered that my ported Java routine has bugs; it updates the seed 1 properly, but not the seed 2, so the sequences of random values is not the same as CIV for the same seeds... Working on solving this at the moment -> Java code fixed directly in post above (edited 9/24/2013)

• the first trick is that the number of calls to the random routine is very variable, and highly self-dependent: whether or not an additional random call is performed depends a lot on the result of the previous random calls; this is because CIV randomly selects buildings locations on the map, and does trial and error re-selecting random positions if the previous one is occupied
• the second trick is that not only this number of calls depends on the city name, city size and existing buildings (and wonders), but it also depends on the number of techs the city owner possesses; this makes randomness control even more difficult, as even with stable non-changing cities, discovering new techs interfers with the random seed prediction -> experiments show that random results are actually independent from random results (edited 9/24/2013)
• the third trick is that, upon exiting the city screen, coming back to the map screen may trigger an additional random call - or not !; this is less of burden and usually it can be detected by looking at the screen changing animation: fade out to black then fade in to map means there was no random call; re-displaying the map screen with "random" square re-tiling means there was a single random call -> exiting the city screen after city view always cross-fades, without map refresh; anyhow this trick becomes irrelevant as long as we now ho many random calls ahead is the "non-0 / 0" sequence (edited 9/24/2013)

For the moment, I see 3 ways to progress on this:

1. Establish a list of city names, for cities with 1 citizen and no building, for all possible tech counts, that will make you win combat for sure; the tech count is actually divided by 2, so a list of 36 names should be enough - except for those chasing Future Tech records; then all you need is to build a city, that you maintain at population 1 at all times, and without buildings, and rename it as necessary (CIV EN 474.05 only has the built-in "rename" feature)
2. Write a small program (embedded in JCivED, for example) that will find out winning city names for any given city in any given savegame, as necessary
3. Start an exhaustive, brute force research for unique names that may (possibly) make the odds independent from one or several factors (such as number of techs, buildings or population, etc.); including all impacting factors, this quickly goes into the 10 billion combinations to try out, very likely to take a long while...

In any case, you can see that it is really not that obvious to exploit this design flaw... So in the end, it may not be a critical flaw at all

• If you let the Militia attack directly, you're basically guaranteed to lose by a crushing defeat
• Now re-load the savegame, click on the city e6 (previously London), display the city view, leave the city screen, DO NOT click anywhere on the map or minimap, and let the Militia attack Paris immediatly... I'll leave it to you to see what happens... It's always a weirdly great feeling to see a Mech. Inf. crushed by a Militia

1. Althought the CIV code uses the City Owner's "tech count", experiments show that in effect, tech count does not influence the total number of random calls... So we can basically ignore it for our purpose
2. When trying out all possible combinations of city improvements and wonders, they produced highly redundant number of random calls, and analyzing it further, it seems the total number of random calls only depends on the number of buildings and/or wonders, but not on their actual type (some buildings and wonders should be ignored though: palace, city walls, aqueduct, mass transit, power plant, hydro plant, Pyramids, Great Wall, Colossus and Hoover Dam); this is quite logical if you consider that all improvements have the same land area usage in the city view, and same for wonders

CIV RANDOM HACK - Attack table

1. In your CIV game, select the city you wish to rename in order to force the odds; note: the city must NOT contain any Wonder (except for Pyramids, Colossus, Great Wall and Hoover Dam: those will not impact the process)
2. Count the buildings in your city; note: do NOT include Palace, City walls, Aqueduct, Mass Transit, Power plant or Hydro plant in your count
3. In the table below, locate the cells whose row number matches your city size, and whose column number matches the city's building count:
   • The first cell contains the city name to re-assign to your city
   • The second cell contains the number of additional random calls necessary before launching the attack
4. Rename your city accordingly; note1: be very careful to follow the case, spacings, etc.; note2: in Civ EN v474.05, this can be done with the "Rename" button in the City Screen; in other versions, the only way is to hack your SVE file with JCivED, TerraForm, or a plain hex editor
5. If the number of additional random calls is not '+0', press 'C' or click on the map as many times as required: each time it will redraw the map, increasing the random calls by 1 call; note: if the value is '+0', skip this step
6. ATTACK!

1. First, CIV City Names (EN versions)
2. Second, real world city names (based on publicly available world cities databases), using the shortest one that matches a seed (max length <12)
3. Third, generated artifical city names, as short as possible, that match the seeds

darkpanda said:

I tried the savegame above in CIV EN 474.01 and EN 474.05, and it works perfectly in both, so my guess is that it will work in all EN versions of CIV.

Click to expand...

jarvisc said:

See what I said about opening "pand...ora's box"? That table from darkpanda is the contents

Click to expand...

jarvisc said:

However, I had some inconsistent results. Hearing that a map-click/redraw causes a rand() call to be made would explain it though.

I think it's hilarious and fantastic that something like this went unnoticed for 20+ years...

Click to expand...

• if rand(500) returns 0, then rand(N) will also return 0 for any N<500
• if rand(2) returns 1, then rand(N) will return values >= 1 for any N>2

gps said:

It doesn't seem work in WinCiv 1.2.0. Popping the hut after city-screen in the attached file gives different results:

View attachment 361503

Click to expand...