--- a/src/ai/ai.hpp
+++ b/src/ai/ai.hpp
@@ -24,6 +24,9 @@
 		START_NEXT_EASY   = 48,
 		START_NEXT_MEDIUM = 24,
 		START_NEXT_HARD   = 12,
+		START_NEXT_MIN    = 0,
+		START_NEXT_MAX    = 120,
+		START_NEXT_DEVIATION = 2,
 	};
 
 	/**

--- a/src/ai/ai_config.cpp
+++ b/src/ai/ai_config.cpp
@@ -17,11 +17,17 @@
 	this->info = (name == NULL) ? NULL : AI::FindInfo(this->name, version);
 	this->version = (info == NULL) ? -1 : info->GetVersion();
 
+	/* The special casing for start_date is here to ensure that the
+	 *  start_date setting won't change even if you chose another AI. */
+	int start_date = this->GetSetting("start_date");
+
 	for (SettingValueList::iterator it = this->settings.begin(); it != this->settings.end(); it++) {
 		free((void*)(*it).first);
 	}
 	this->settings.clear();
 
+	this->SetSetting("start_date", start_date);
+
 	if (_game_mode == GM_NORMAL && this->info != NULL) {
 		/* If we're in an existing game and the AI is changed, set all settings
 		 *  for the AI that have the random flag to a random value. */
@@ -30,6 +36,7 @@
 				this->SetSetting((*it).name, InteractiveRandomRange((*it).max_value - (*it).min_value) + (*it).min_value);
 			}
 		}
+		this->AddRandomDeviation();
 	}
 
 }
@@ -43,6 +50,7 @@
 	for (SettingValueList::const_iterator it = config->settings.begin(); it != config->settings.end(); it++) {
 		this->settings[strdup((*it).first)] = (*it).second;
 	}
+	this->AddRandomDeviation();
 }
 
 AIConfig::~AIConfig()
@@ -75,11 +83,19 @@
 
 int AIConfig::GetSetting(const char *name)
 {
-	assert(this->info != NULL);
-
 	SettingValueList::iterator it = this->settings.find(name);
 	/* Return the default value if the setting is not set, or if we are in a not-custom difficult level */
 	if (it == this->settings.end() || ((_game_mode == GM_MENU) ? _settings_newgame.difficulty.diff_level : _settings_game.difficulty.diff_level) != 3) {
+		if (this->info == NULL) {
+			assert(strcmp("start_date", name) == 0);
+			switch ((_game_mode == GM_MENU) ? _settings_newgame.difficulty.diff_level : _settings_game.difficulty.diff_level) {
+				case 0: return AI::START_NEXT_EASY;
+				case 1: return AI::START_NEXT_MEDIUM;
+				case 2: return AI::START_NEXT_HARD;
+				case 3: return AI::START_NEXT_MEDIUM;
+				default: NOT_REACHED();
+			}
+		}
 		return this->info->GetSettingDefaultValue(name);
 	}
 	return (*it).second;
@@ -88,12 +104,16 @@
 void AIConfig::SetSetting(const char *name, int value)
 {
 	/* You can only set ai specific settings if an AI is selected. */
-	assert(this->info != NULL);
+	if (this->info == NULL && strcmp("start_date", name) != 0) return;
 
-	const AIConfigItem *config_item = this->info->GetConfigItem(name);
-	if (config_item == NULL) return;
+	if (this->info == NULL && strcmp("start_date", name) == 0) {
+		value = Clamp(value, AI::START_NEXT_MIN, AI::START_NEXT_MAX);
+	} else {
+		const AIConfigItem *config_item = this->info->GetConfigItem(name);
+		if (config_item == NULL) return;
 
-	value = Clamp(value, config_item->min_value, config_item->max_value);
+		value = Clamp(value, config_item->min_value, config_item->max_value);
+	}
 
 	SettingValueList::iterator it = this->settings.find(name);
 	if (it != this->settings.end()) {
@@ -103,6 +123,29 @@
 	}
 }
 
+void AIConfig::AddRandomDeviation()
+{
+	/* No AI configured, so fall back to some defaults */
+	if (this->info == NULL) {
+		int base_start_date;
+		switch (_settings_game.difficulty.diff_level) {
+			case 0: base_start_date = AI::START_NEXT_EASY; break;
+			case 1: base_start_date = AI::START_NEXT_MEDIUM; break;
+			case 2: base_start_date = AI::START_NEXT_HARD; break;
+			case 3: base_start_date = AI::START_NEXT_MEDIUM; break;
+			default: NOT_REACHED();
+		}
+		this->SetSetting("start_date", InteractiveRandomRange(AI::START_NEXT_DEVIATION * 2) - AI::START_NEXT_DEVIATION + base_start_date);
+		return;
+	}
+
+	for (AIConfigItemList::const_iterator it = this->info->GetConfigList()->begin(); it != this->info->GetConfigList()->end(); it++) {
+		if ((*it).random_deviation != 0) {
+			this->SetSetting((*it).name, InteractiveRandomRange((*it).random_deviation * 2) - (*it).random_deviation + this->GetSetting((*it).name));
+		}
+	}
+}
+
 bool AIConfig::HasAI()
 {
 	return this->info != NULL;

--- a/src/ai/ai_config.hpp
+++ b/src/ai/ai_config.hpp
@@ -64,6 +64,11 @@
 	void SetSetting(const char *name, int value);
 
 	/**
+	 * Randomize all settings the AI requested to be randomized.
+	 */
+	void AddRandomDeviation();
+
+	/**
 	 * Is this config attached to an AI?
 	 */
 	bool HasAI();

--- a/src/ai/ai_core.cpp
+++ b/src/ai/ai_core.cpp
@@ -229,20 +229,9 @@
 
 /* static */ int AI::GetStartNextTime()
 {
+	/* Find the first company which doesn't exist yet */
 	for (CompanyID c = COMPANY_FIRST; c < MAX_COMPANIES; c++) {
-		if (IsValidCompanyID(c)) continue;
-
-		AIConfig *config = AIConfig::GetConfig(c);
-		if (config->HasAI()) return config->GetSetting("start_date");
-
-		/* No AI configured, so fall back to some defaults */
-		switch (_settings_game.difficulty.diff_level) {
-			case 0: return AI::START_NEXT_EASY;
-			case 1: return AI::START_NEXT_MEDIUM;
-			case 2: return AI::START_NEXT_HARD;
-			case 3: return AI::START_NEXT_MEDIUM;
-			default: NOT_REACHED();
-		}
+		if (!IsValidCompanyID(c)) return AIConfig::GetConfig(c)->GetSetting("start_date");
 	}
 
 	/* Currently no AI can be started, check again in a year. */

--- a/src/ai/ai_info.cpp
+++ b/src/ai/ai_info.cpp
@@ -154,12 +154,13 @@
 	AIConfigItem config;
 	config.name = strdup("start_date");
 	config.description = strdup("The amount of months after the start of the last AI, this AI will start (give or take).");
-	config.min_value = 0;
-	config.max_value = 120;
+	config.min_value = AI::START_NEXT_MIN;
+	config.max_value = AI::START_NEXT_MAX;
 	config.easy_value   = AI::START_NEXT_EASY;
 	config.medium_value = AI::START_NEXT_MEDIUM;
 	config.hard_value   = AI::START_NEXT_HARD;
 	config.custom_value = AI::START_NEXT_MEDIUM;
+	config.random_deviation = AI::START_NEXT_DEVIATION;
 	config.flags = AICONFIG_NONE;
 	info->config_list.push_back(config);
 
@@ -256,6 +257,11 @@
 			sq_getinteger(vm, -1, &res);
 			config.hard_value = res;
 			items |= 0x040;
+		}  else if (strcmp(key, "random_deviation") == 0) {
+			SQInteger res;
+			sq_getinteger(vm, -1, &res);
+			config.random_deviation = res;
+			items |= 0x200;
 		} else if (strcmp(key, "custom_value") == 0) {
 			SQInteger res;
 			sq_getinteger(vm, -1, &res);
@@ -277,6 +283,17 @@
 	}
 	sq_pop(vm, 1);
 
+	/* Don't allow both random_deviation and AICONFIG_RANDOM to
+	 * be set for the same config item. */
+	if ((items & 0x200) != 0 && (config.flags & AICONFIG_RANDOM) != 0) {
+		char error[1024];
+		snprintf(error, sizeof(error), "Setting both random_deviation and AICONFIG_RANDOM is not allowed");
+		this->engine->ThrowError(error);
+		return SQ_ERROR;
+	}
+	/* Reset the bit for random_deviation as it's optional. */
+	items &= ~0x200;
+
 	/* Make sure all properties are defined */
 	uint mask = (config.flags & AICONFIG_BOOLEAN) ? 0x1F3 : 0x1FF;
 	if (items != mask) {

--- a/src/ai/ai_info.hpp
+++ b/src/ai/ai_info.hpp
@@ -23,6 +23,7 @@
 	int easy_value;          //!< The default value on easy difficulty setting.
 	int medium_value;        //!< The default value on medium difficulty setting.
 	int hard_value;          //!< The default value on hard difficulty setting.
+	int random_deviation;    //!< The maximum random deviation from the default value.
 	AIConfigFlags flags;     //!< Flags for the configuration setting.
 };
 

--- a/src/company_cmd.cpp
+++ b/src/company_cmd.cpp
@@ -468,8 +468,7 @@
 
 void StartupCompanies()
 {
-	/* The AI starts like in the setting with +2 month max */
-	_next_competitor_start = _settings_game.difficulty.competitor_start_time * 90 * DAY_TICKS + RandomRange(60 * DAY_TICKS) + 1;
+	_next_competitor_start = 0;
 }
 
 static void MaybeStartNewCompany()
@@ -483,12 +482,7 @@
 		if (c->is_ai) n++;
 	}
 
-	/* when there's a lot of computers in game, the probability that a new one starts is lower */
-	if (n < (uint)_settings_game.difficulty.max_no_competitors &&
-			n < (_network_server ?
-				InteractiveRandomRange(_settings_game.difficulty.max_no_competitors + 2) :
-				RandomRange(_settings_game.difficulty.max_no_competitors + 2)
-			)) {
+	if (n < (uint)_settings_game.difficulty.max_no_competitors) {
 		/* Send a command to all clients to start up a new AI.
 		 * Works fine for Multiplayer and Singleplayer */
 		DoCommandP(0, 1, 0, CMD_COMPANY_CTRL);
@@ -511,10 +505,14 @@
 	if (IsValidCompanyID((CompanyID)_cur_company_tick_index)) {
 		Company *c = GetCompany((CompanyID)_cur_company_tick_index);
 		if (c->name_1 != 0) GenerateCompanyName(c);
+	}
 
-		if (AI::CanStartNew() && _game_mode != GM_MENU && !--_next_competitor_start) {
-			MaybeStartNewCompany();
-		}
+	if (_next_competitor_start == 0) {
+		_next_competitor_start = AI::GetStartNextTime() * 30 * DAY_TICKS;
+	}
+
+	if (AI::CanStartNew() && _game_mode != GM_MENU && --_next_competitor_start == 0) {
+		MaybeStartNewCompany();
 	}
 
 	_cur_company_tick_index = (_cur_company_tick_index + 1) % MAX_COMPANIES;