Caster of Magic II Brainstorming Megathread

[Seravy]

Why? Because with the current game balance of RP and SP calcs, assuming that every player is of reasonable or similar competence, wasting resources in fighting an offensive war all the way to banishment is not worth it in 95% of cases as you lose relative progress in RP, SP, and unit build up against all non-participating wizards, and get very little in return because defenders have an overwhelming advantage in combat.

I disagree here. It's more than enough to conquer a significant portion of their cities and leave the fortress as is - something that can and will happen between AI players as well.
After that, the victim will not be able to develop their spells and casting skill - you need more than 2-3 cities to do that, and the wizard will be forced to spend most of the resources on military anyway because they will be under the "outnumbered by enemies on my home continent" situation. While eliminating this wizards at that time isn't worth it, they will disappear before Spell Blast becomes relevant, as higher tier spells from either the player or other AIs will overrun those last few cities as the garrison will be obsolete soon.
I don't expect an overly significant increase in endgame player count - if it did happen, then a lot of global spells would need to be redesigned but I'll worry about this after I see how it actually works in test games.

I should have explained what I meant a bit better.
First we should decide how we intend larger games to actually play out. On the existing 60x40 maps this isn't a question - conquering all of the territory is reasonably doable so while Spell of Mastery is a good alternate win condition, it's not overly important to the game as a whole. However, even on these maps, conquering the entire thing on high difficulty and landmass settings can take 20-25 hours.
Compared to this, a map of 200x200 has 16 times more territory. So using linear math, a conquest victory for these would take over 300 hours. Of course the actual time wouldn't be that high - ideally the AI turns will be faster and there will be prortionally more "I'm fighting a weaker enemy than myself so this war is quick" but it does show what I'm worried about. I think "Maximal" size maps with the highest number of opponents will be so large that Spell of Mastery will be the ONLY playable victory condition that can end the game in less than an eternity. If Spell of Mastery gets countered, you have to conquer at least the Sorcery players that have the spell. Not only does that take a lot of time but there is another issue.
Sorcery players can cast uncounterable Spell of Masteries. So what will happen is, even if I'm the first to reach Spell of Mastery, the Sorcery wizards will all counter it. While I'm busy fighting the first 1-2 of them, one of the others will reach Spell of Mastery as well, cast it and win and I can't counter it.
So it will result in larger maps becoming unwinnable without being a Sorcery player.

By "uncounterable Spell of Mastery" is mostly mean the strategy of casting it during a Time Stop. As there won't be a 30k mana cap, it will be possible to store enough mana to finish the entire Spell of Mastery while no one else gets a turn.
Additionally, Power Link counters Spell Blast. So whichever Sorcery player has it in play is the only one who can counter the others.
Edit :
...I'm wrong on this one because Spell Blast can counter Power Link and Time Stop. But only for the human player. In case of the AI, they are subject to game rules : they aren't allowed to use Spell Blast on these spells unless they both have Detect Magic up and are hostile to the other player. So as the human player all I need is dispelling the Detect Magic and cast my Time Stop. Which is actually worse because it means the human player always wins.

So...we probably need to first decide what we want to happen on these large maps. Are we ok with the game becoming endless, or do we want to provide a way to end it, which is Spell of Mastery? If the former, you are right and Spell Blast should be frequently available but then ways to force the Spell of Mastery through Spell Blast (Power Link and Time Stop) should be also somehow dealt with. If the latter, we need to make Spell Blast less frequent.
We might need to actually see how long these large map games take instead of trying to guesstimate to decide this.

On even bigger maps, there is no chance of getting to their Fortress before they can finish casting, as it only takes 2-3 turns.

We have variable SoM cost on the list of ideas for this reason, although 2-3 turns is inaccurate. It costs 15k currently which even for a crazy powerful AI with 1000 casting skill will still take 15 turns. (AI casting modifiers don't apply to Spell of Mastery)
Still, 15 turns times 4 movement is only a distance of 60 covered which is roughly one third of the largest map.

(as a side note, I'm worried about the AI's doomstack building capacity, as it pulls the best 9 units it has from the entire map. This is reasonable on a 60x40 map where the most possible distance is 30 which is less than 10 turns for most doomstack material units, but on 180x180 it will not work. However I have no good idea how to do it better. If I artificially split the map up to smaller areas like virtual continents, then units on different sides of a "border" will not be able to get into the same stack which will result it many weaker stacks instead of a few good ones.)

[massone]

I should have explained what I meant a bit better.
First we should decide how we intend larger games to actually play out. On the existing 60x40 maps this isn't a question - conquering all of the territory is reasonably doable so while Spell of Mastery is a good alternate win condition, it's not overly important to the game as a whole. However, even on these maps, conquering the entire thing on high difficulty and landmass settings can take 20-25 hours.
Compared to this, a map of 200x200 has 16 times more territory. So using linear math, a conquest victory for these would take over 300 hours. Of course the actual time wouldn't be that high - ideally the AI turns will be faster and there will be prortionally more "I'm fighting a weaker enemy than myself so this war is quick" but it does show what I'm worried about. I think "Maximal" size maps with the highest number of opponents will be so large that Spell of Mastery will be the ONLY playable victory condition that can end the game in less than an eternity. If Spell of Mastery gets countered, you have to conquer at least the Sorcery players that have the spell. Not only does that take a lot of time but there is another issue.
Sorcery players can cast uncounterable Spell of Masteries. So what will happen is, even if I'm the first to reach Spell of Mastery, the Sorcery wizards will all counter it. While I'm busy fighting the first 1-2 of them, one of the others will reach Spell of Mastery as well, cast it and win and I can't counter it.
So it will result in larger maps becoming unwinnable without being a Sorcery player.

By "uncounterable Spell of Mastery" is mostly mean the strategy of casting it during a Time Stop. As there won't be a 30k mana cap, it will be possible to store enough mana to finish the entire Spell of Mastery while no one else gets a turn.
Additionally, Power Link counters Spell Blast. So whichever Sorcery player has it in play is the only one who can counter the others.
Edit :
...I'm wrong on this one because Spell Blast can counter Power Link and Time Stop. But only for the human player. In case of the AI, they are subject to game rules : they aren't allowed to use Spell Blast on these spells unless they both have Detect Magic up and are hostile to the other player. So as the human player all I need is dispelling the Detect Magic and cast my Time Stop. Which is actually worse because it means the human player always wins.

That's exactly it. The main point of my post before was that Spell Blast is an important counter to a wide range of spells, some of which are just as game-winning as SoM, such as Power Link and Time Stop and a lot of other Very Rares, depending on when they're cast. And unfortunately, right now the AI's rules prevent them from effectively using it. In my example before, Spell Blast could have countered Call to Void too, and the AI did use it to counter CtV, but one of the Sorcery Wizards didn't have it, so they couldn't protect themselves. Getting half your towns nuked is pretty close to "game over" for that wizard.

I think that Spell Blast needs to be kept available widely, and for the AI to use it better than they do now. Always counter certain hostile spells that would be devastating, and always counter the big dangers like Power Link or Time Stop that can win the game if not stopped. And there's more--because of the efficient casting skill trade off, it's good to cast Spell Blast in a lot of cases when the opponent is using high cost spells.

So...we probably need to first decide what we want to happen on these large maps. Are we ok with the game becoming endless, or do we want to provide a way to end it, which is Spell of Mastery? If the former, you are right and Spell Blast should be frequently available but then ways to force the Spell of Mastery through Spell Blast (Power Link and Time Stop) should be also somehow dealt with. If the latter, we need to make Spell Blast less frequent.
We might need to actually see how long these large map games take instead of trying to guesstimate to decide this.

I think the real question shouldn't be how long games we want to be, but how to design a game that stays fun for as long as it plays. In many strategy games, the final "clean up" when you're the strongest and there's no question of victory is where a lot of players just stop playing. Nobody wants the game to feel like a chore. I don't think many people would complain if it takes extremely long to end the game, but it stays highly competitive and challenging the whole time all the way up to the end. After all, if they want to play a shorter game because they don't have that much time, they can just choose smaller maps and fewer players. If they want to play the big maps, it's almost certainly because they WANT to extend the game and have more opponents to play against for the late game.

We have variable SoM cost on the list of ideas for this reason, although 2-3 turns is inaccurate. It costs 15k currently which even for a crazy powerful AI with 1000 casting skill will still take 15 turns. (AI casting modifiers don't apply to Spell of Mastery)
Still, 15 turns times 4 movement is only a distance of 60 covered which is roughly one third of the largest map.

When I said 2-3 turns, I was referring to all of the other spells besides SoM which need to be stopped in a highly competitive game. Power Link and Time Stop only take 2-3 turns. I'm aware that the AI won't generally use it that way, and I agree it isn't good for the human player to be the only one who has access to this counter, but it's too important to the general balance that I really think any solution has to be to make the AI use it better instead.

EDIT: Or, we could make it Arcane.

(as a side note, I'm worried about the AI's doomstack building capacity, as it pulls the best 9 units it has from the entire map. This is reasonable on a 60x40 map where the most possible distance is 30 which is less than 10 turns for most doomstack material units, but on 180x180 it will not work. However I have no good idea how to do it better. If I artificially split the map up to smaller areas like virtual continents, then units on different sides of a "border" will not be able to get into the same stack which will result it many weaker stacks instead of a few good ones.)

I doubt there is any good solution without substantially altering source code. But if CoM 2 can have source code changes, maybe you can do something like this:

Categorize stacks into main roles: Assault, Garrison Reinforcement, and whatever else is relevant.

Assault should consist of the highest survivability units that can withstand the first-turn ranged onslaught when attacking into a fortified position. The high HP, high movement troops, most typically of summons and/or advanced normal troops.

Garrison Reinforcement should consist of the "ideal" garrison composition, which is used to quickly reinforce newly conquered territories or top up damaged garrisons. More than half ranged, and some tanks.

Assemble all forces into one of these roles based on proximity and minimum stack strength relative to available unit builds, according to templates. If the best available unit production is strength P, then we require all stacks to assemble to Strength S >= P * 5.

Each of the main roles refer to a number of templates the AI can draw from against particular matchups. These templates would take a lot of work to create for all the races and realms, but it would be programmatically easier than trying to implement a single universal AI algorithm for stack building that is actually good. Essentially, you can use real human intelligence from played games to give the AI a "cheat sheet" on metacompetitive compositions, then make the AI use it.

[Seravy]

I think that Spell Blast needs to be kept available widely, and for the AI to use it better than they do now. Always counter certain hostile spells that would be devastating, and always counter the big dangers like Power Link or Time Stop that can win the game if not stopped. And there's more--because of the efficient casting skill trade off, it's good to cast Spell Blast in a lot of cases when the opponent is using high cost spells.

That's not an option. If the AI is effective at countering all my late game spells, I might as well not play, and most players will feel the same. Which is why we spent over a week to discuss how and when the AI can use it, and that's not going to change or at most in the direction of the AI using it less in the "random curse" category which doesn't really serve any specific purpose.

but how to design a game that stays fun for as long as it plays.

That's exactly why Spell Blast should be less of a factor. It's not fun to play when your spells are countered consistently.

I don't think many people would complain if it takes extremely long to end the game, but it stays highly competitive and challenging the whole time all the way up to the end.

Depends. 20-30 hours is already extremely long. Assuming playing for 4 hours every day, that takes 5-7 days of playing. And that's for a single map in a single game.
I can't imagine playing the same map 10 times longer. But we'll have to see how long it actually takes, if it's "only" 30-40 hours, that's no problem.

I doubt there is any good solution without substantially altering source code. But if CoM 2 can have source code changes, maybe you can do something like this:

Ok, I think I need to explain this better.
The AI has two stackbuilding functions.

Function 1 gathers the best available units per continent (except those held back for garrisoning - I'm satisfied with how the AI decides on that). This is land based and typically works fine, once the AI has enough quality units around doing nothing. This is from the original game and is not doomstack building although it might build a doomstack if the units are that good, I don't refer to it as such.

By "doomstack building" I mean the CoM only function I added which takes then 9 best intercontinental movement capable (flying, waterwalking etc) idle units from the entire plane, and gathers them into one stack. The role of this is to provide the AI with a stack that builds up faster and contains top quality stuff that can also reach targets without transportation on ships. This generally is trying to mimic the "doomstack" strategy of human players, having one stack that can crush anything easily and is likely to survive the battle and do it again more than once.
This stack typically consists of 9 of the best AI flying summon available and/or some heroes mixed in. The AI only builds one of these at a time but already built stacks actively attacking targets won't prevent the AI to build another, only idle stacks with no targets do.

You can assume the AI already has a list of units it wants to use for the "doomstack" purpose and can rank which unit is best for it. The problem is not that, but this :
Currently the AI picks the top 9 units from this list each turn. So these units will move together and form the stack. It's consistently the same 9 units unless some of them dies or the AI produces something strictly better than these 9, so they cannot be replaced by another copy of the same type of unit - every turn the exact same 9 units will move closer to each other.
However if there is an unpredictable distance restriction, then how do I get this same result?

Let's say the AI has 5 Doom Bats on tile 1, 5 Doom Bats on tile 2, and 5 great drakes on tile 3.
The first algorytm will pick the 5 drakes and 4 oldest bats that existed from these and moves them closer. Next turn the same 9 bats will be the oldest so they get selected again and this keeps going until the bats are together, or even beyond that, as long as the stack isn't trying to attack something - the AI will keep picking it, see they are together and do nothing.

Let's assume now that tile 1 and tile 2 are 11 distance from each other but tile 3 is 52 distance from both.
Do I select 9 bats, or 4 drakes and 5 bats? Drakes are better but they are very far while bats are close. How do I guarantee the same units get selected next turn, considering anything that was not selected will more randomly, so it might get closer to the selected units than the last turn?

How do I even choose from a list of units sorted by their "value" if distance is a factor?

Would something as simple as "value= original value/(distance+X)" work? In that case X could affect how far the AI is willing to go for a better unit. But does this guarantee the AI will pick the same units?
Wait, what is "Distance" in this case? Distance from what? We haven't picked units yet so we don't know where we will send them. It's a circular definition. We have to pick units to know how far they are but we have to know how far they are to know which one we pick.
Of course we could look at every single combination possible and choose the one with the best sum but that takes n!/(n-x)!*(x!) time to compute which is basically infinite with any n reasonably expected in the game so we can't do that.

So apparently there two problems :
-How do I pick the 9 "best" units from the doomstack if both their position and value are factors to consider, is there an algorithm for this?
-Does that guarantee the selection will happen again next turn assuming any unit not selected can move anywhere randomly and units can have uneven movement speeds? If it selects a different group every turn, it won't work.

[prokolyo]

Little out of the box here, but would be possible to implement some type of political victory, like in MOO2 for example? Election type? With so many wizards, politics will be much more important I think.

Sent from my Pixel 3 using Tapatalk

[Seravy]

Possible in theory. I'm not sure if it would feel right for this game though.

[massone]

That's not an option. If the AI is effective at countering all my late game spells, I might as well not play, and most players will feel the same. Which is why we spent over a week to discuss how and when the AI can use it, and that's not going to change or at most in the direction of the AI using it less in the "random curse" category which doesn't really serve any specific purpose.

I understand why that is a problem, but I believe that should be a matter of difficulty levels.

I think we can both agree that AI is the most critical piece of any serious single-player strategy game. And the two most common complaints about AI in the genre are:
1. "The AI is cheating!"
2. "The AI is too dumb!"

Cheating is usually defined to be "taking an action/having a tool/knowing something which the human player cannot perform/does not have/can't know" based on the "rules" of the game.
Being "too dumb" is a result of the AI being unable to act with human-like intelligence and failing to effectively use mechanics the human player would.

Of course, sometimes players accuse the AI of cheating even when they're not, simply because they're losing. That happens too.

In practice, there's a range of player skills and enjoyment based on the perceived difficulty of the AI. But generally, what most players (and I encourage anyone else in this thread to pitch in to confirm this) will theoretically agree on is that in an "ideal world", the difficulty design should be based on 2 sets of changing factors:

1. Algorithmic changes to "intelligence" we can loosely label as ranging from "amateur" to "grandmaster", working solely within the normal rule set without consideration of cheating.
2. Bonuses to AI and other "cheating" behaviour, to make the AI perform beyond what is programmatically possible/practical to achieve in terms of "intelligence".

The effective use of Spell Blast fits within #1. A "grandmaster" level AI should absolutely be using it, because a "grandmaster" human player definitely would.

If the problem is that getting Spell Blasted too often makes the game unfun, then there are 2 good approaches. One is to use difficulty levels as above to manage it. The other is the same solution as when the AI isn't capable of handling the mechanic even at a decent level of skill -- removing it entirely so that the player doesn't have that advantage either.

The same applies to all other spells, but there is a nuance with curses in general. The question that must be asked is: is the AI simply being annoying, is the AI artificially targeting the human player in a form of cheating, or is the tactic actually one with an efficient payoff that moves towards Nash equilibrium? Many curses are inefficient plays because they don't increase advantage relative to the unaffected players.

This applies whether Spell Blast is Uncommon or Rare. The spell is a weakly dominant strategy in every payoff matrix for every Realm mix. It counters many other spells, some of which are strictly dominant. That there exist strictly dominant choices isn't good in the first place, but if their counter's availability was made more subject to luck, then the whole game becomes more lottery-like.

Is it really any fun to win or lose based on whether your opponents have Power Link or Time Stop in their spellbook, and how early they showed up, and you can't do anything to stop them because you don't have Spell Blast in your spellbook?

That's exactly why Spell Blast should be less of a factor. It's not fun to play when your spells are countered consistently.

It's also not fun to know that the AI can play much better by using it, and that they won't, because they were programmed not to, even on the highest difficulty.

Depends. 20-30 hours is already extremely long. Assuming playing for 4 hours every day, that takes 5-7 days of playing. And that's for a single map in a single game.
I can't imagine playing the same map 10 times longer. But we'll have to see how long it actually takes, if it's "only" 30-40 hours, that's no problem.

In EU4, 30 hours is a "typical" campaign for most people playing on average speed settings, and most players don't even play through the second half of the game. Newer players can spend 80+ hours playing through the first half. Given how popular the game is, and how many people complain about the game not lasting long enough into the late game because there's no challenge left after they grow too powerful relative to the remaining AI countries, I think 30-40 isn't extremely long at all, for a fun game.

considering anything that was not selected will more randomly

We've got the biggest problem right here. When the AI moving units RANDOMLY is part of the core algorithm, that's what I mean by there's no good solution without source code. The entire setup is very limiting. Frankly, I'm flabbergasted that you managed to add that COM-only algorithm using just hex code... But anyways, I'll try to come up with something that works with this.

So right now, as I understand it, we've got a function that builds 1 stack per continent at a time, then another function to build 1 stack per game at a time. Since you didn't specify the priority order, I'm assuming that it works like this:

1. Search 9 best units.
2. Assign the best unit list to "main doomstack n".
3. Identify the 9 best units per continent, excluding already assigned units.
4. Moving the continental best units into stacks.
5. Whenever a stack is fully built, loop with n+1 or the corresponding continental version, on steps 1-4 excluding already assigned units. If a new unit has an individual strength higher than the lowest strength unit in the main doomstack, move it to the doomstack and replace it.

To remove the distance circular definition and avoid ridiculous compute times, we can use the following "simple" solution:

Solution A:
1. Search for unassigned bestUnit. If there is a tie, choose the unit with distance shortest to Fortress, or some other point we believe to be best to amass troops.
2. Define bestUnit's current location or an empty spot next to it as the buildSpot.
3. Search next 8 best free units on strengthValue only. Calculate distanceToBuildSpot for each unit. Calculate modifiedValue = strengthValue - [distanceToBuildSpot] * [distanceWeightModifier]. Calculate lowestModifiedValue from among the 8 units.

4. Search next best free unit. Calculate modifiedValue. If lowestModifiedValue < modifiedValue, replace the old unit. If not, keep looping to next best free unit until lowestModifiedValue >= strengthValue. This loop will end when it is not possible for the next unit to replace any of the current chosen units, as modifiedValue is always <= strengthValue for any given unit.

For the overall value formula, I believe subtraction would be better than division in this case, and using a modifier to make larger distances give a bigger negative. I think your formula would be harder to intuit and adjust what impact distance has, but that's just personal preference.

5. Store sumOfStackValues from all the modifiedValues.

6. Next turn, search bestUnit again. If newUnit is built which is stronger than the bestUnit from last turn, run the algorithm again from #1 with newUnit's location as the buildSpot. Then compare the sumOfStackValues for the two calculations. If the newSum > oldSum, then build the stack at the new unit instead and discard the previous stack.

Without considering the complexity of the search algorithms being called, on its own this algorithm would be O(n).

[prokolyo]

Possible in theory. I'm not sure if it would feel right for this game though.

At any rate, having four and having fourteen opponents is a very different thing. MoM and MoO are my two favorite games, but I deep down always preferred the latter, mostly because of the more intricate politics with more opponents. YMMV ofc.

Sent from my Pixel 3 using Tapatalk

[Seravy]

1. Algorithmic changes to "intelligence" we can loosely label as ranging from "amateur" to "grandmaster", working solely within the normal rule set without consideration of cheating.

This is actually the thing. This isn't a PVP game. The rules for the AI and the human are different, intentionally. And those rules say the AI isn't allowed to do certain things that make the game not function well as a single player game. Some of these are specific, like "The AI can't recast Detect Magic too often"  but there are global ones too like "An AI isn't allowed to cast curse type spells when they are not hostile towards a player".

So no, the effective use of Spell Blast breaks the rules. Not the human rules - the AI rules.

There is such a thing as a too dumb opponent, yes. But there also is such a thing as a too good opponent. But you already covered that by mentioning the difficulty setting.

So yes, if you suggest the AI should always instantly recast Detect Magic on the highest difficulty setting, that's fine. We can do that but for the new highest level only, the one above Lunatic. It's too unfun for any other level.
However spell blasting people without being hostile is absolutely not possible because it actually violates a global diplomacy rule. Of course there is a workaround for that, the AI can simply declare war in reaction to seeing those spells, but honestly that's too harsh for any difficulty and it would actually help the player by making the AIs fight each other a lot more.

Is it really any fun to win or lose based on whether your opponents have Power Link or Time Stop in their spellbook, and how early they showed up, and you can't do anything to stop them because you don't have Spell Blast in your spellbook?

It's not but that's why they can't show up early. I mean, you can control when they show up through the difficulty settings. If they show up before you are ready to handle them, that either means you are playing a too high difficulty, or that those spells are too powerful.

We've got the biggest problem right here. When the AI moving units RANDOMLY is part of the core algorithm,

By randomly, I meant we can't predict how they will move because they will be handled by a different AI function in the future.
So they might end up moving closer to the doomstack or further away, but we can't count on either.

Since you didn't specify the priority order, I'm assuming that it works like this:

Ok, so this is how it works. (very simplified)

For each continent do 1-4 :
1. Do various stuff (send stacks to attack, etc)
2. find best 9 available unit still not having an order that's not a "mandatory garrison" unit. (mark all mandatory garrison units)
3. Send as many of these to the continent rally point as there is room left.
4. Do other stuff
5. Globally find the best 9 "doomstack" units that weren't mandatory garrison and weren't given an order to attack things and overwrite their order with moving to the average position between them.
6. So far nothing actually moved, these only assigned the orders to the unit. Now move all the units according to the selected order on them at once and next AI's turn starts after that.

Next turn, do the same, starting from 1.

2. Define bestUnit's current location or an empty spot next to it as the buildSpot.

So what if bestunit is the one very far away and the others are close?

Let's say I have 9 doom bats at place X, attempting to build a stack (they were chosen last turn). I summoned my first Great Drake at place Y, very far away. Place Y also has 8 of my leftover Sprites nearby that had absolutely nothing to do.
So "bestunit" is the Great Drake. So we have the drake and the doom bats. They are far so the Sprites will replace them, one at a time, until all 8 are replaced. So we have our fresh doomstack of 1 Great Drake and 8 Sprite, but our 9 Doom Bats which were only one turn away from reaching each other are ignored.
Or it could be worse : If we had 5 Sprites, then we'd have 1 Drake, 5 Sprites, and 3 Doom Bats but the Bats are very far so it'll take 20 turns for the stack to build up.
Ideally, the 9 Bats should be chosen because the Drake is too far, but since its location is the baseline, it doesn't work.

Why? Because "Buildspot Y" isn't a correct assumption. The correct buildspot is near X instead.


Ok, how about this one, would it work?

1. Select the best unit.
2. Find the 8 next best units that are all within range X of the best unit. If successful, send these 9 units to the same spot. If not, remove "bestunit" from the list.
3. Jump to 1 until the list is less than 9 units.

It guarantees the the best stack that's reasonable to gather within an acceptable amount of time but would it also guarantee the units won't get selected for different stacks and keep moving back and forth each turn?
hmmm...
assuming no higher tier new units :
1. Same best unit gets selected, good so far.
2. The old 9 have all moved closer to "bestunit" so they are still in range. However, if there was a unit that got skipped on the list, and that unit moved closer for any reason, it might get selected instead. But it's a better unit, and it's still within range so it works the same as it currently does (replacing bad units with better ones as soon as possible).
3. As long as the first stack didn't replace anything, the rest of the stacks stay deterministic as well. If it did, all stacks are pretty much starting over - but they will still reach each other in X/speed turns and replacing units will not happen often - it either needs a higher tier new unit, or needs a unit that's equal to but older than an existing unit to cross the distance limit on its own.

The remaining question is, can this cause a loop in the sense that a unit that replaces another through freely moving cross the distance limit end up with a different unit getting left out of the stack and crossing the limit causing a switch to happen again? I think the answer is "no". We replaced the lowest "value" unit in our 9 unit group so wherever it goes, it won't be valid for this stack again unless a unit actually dies. However it might become the "leader" of a second stack previously not possible that adds an unused unit that is higher on the priority list than the first stack. As these units keep moving closer, it might cause that higher unit to now be able to gather a stack of its own, changing the contents of the first stack. But that requires a higher value unused unit so it's finite. Eventually there won't be an unused "higher value" unit left and I think it would require astronomical bad luck for this trigger multiple times each after spending a relevant number of turns moving.
So maybe this is usable? Probably with an X around 20 (which covers a 40x40 area and should let stacks gather at most in 10-12 turns assuming move 2 or 5-6 turns with move 4).

Something else. We can also add a new, non-movement based doomstack building which works like this.
The AI already has a "frontier town" concept, selecting a city in a place it's most in need of troops and summons roughly at a 1/3 chance there. So how about we instead do this :

0. Any city with a full 9 intercontinental movement units that are high quality sends the units outside and is marked "immediate summoning is needed". (this will need to use a special movement code to not mark the units done so they can also attack later that turn using any leftover movement points)
1. If any towns are marked as "immediate summoning", summon things there instead of casting other spells, for that one turn only.
2. Any city with at least 6 intercontinental movement units which are a similar tier as the best available summoning spell, counts as a frontier city in addition to the existing one.
3. When summoning to the frontier city is chosen as the summon location and there are more than one, pick the one with the most such units.
4. Halve the priority of all summon spells that are not flying and waterwalking for summoning in that city and summon something.
5. (Target selection for waterwalking and Wraithform should prioritize units in a frontier city higher.)

There. What this achieves is two things : The AI can make new doomstacks where it matters and doesn't need to spend time gathering them in one spot AND any doomstack that conquers a city will be able to leave it and move on to attack more, without leaving the city entirely undefended. This is important as razing cannot be used to free the stack from its garrison duty if we remove instant razing. Basically, this allows the AI to also use doomstacks in a way more similar to the human player on top of simply pooling together whatever units it already had.

[massone]

So what if bestunit is the one very far away and the others are close?

Let's say I have 9 doom bats at place X, attempting to build a stack (they were chosen last turn). I summoned my first Great Drake at place Y, very far away. Place Y also has 8 of my leftover Sprites nearby that had absolutely nothing to do.
So "bestunit" is the Great Drake. So we have the drake and the doom bats. They are far so the Sprites will replace them, one at a time, until all 8 are replaced. So we have our fresh doomstack of 1 Great Drake and 8 Sprite, but our 9 Doom Bats which were only one turn away from reaching each other are ignored.
Or it could be worse : If we had 5 Sprites, then we'd have 1 Drake, 5 Sprites, and 3 Doom Bats but the Bats are very far so it'll take 20 turns for the stack to build up.
Ideally, the 9 Bats should be chosen because the Drake is too far, but since its location is the baseline, it doesn't work.

Why? Because "Buildspot Y" isn't a correct assumption. The correct buildspot is near X instead.

Not quite. In your scenario, the algorithm I provided would only result in this Drake + sprites stack if the sprite's strengthValues were higher than the modifiedValue of the Doom Bats. There's nothing wrong with that--because you set the distance modifier so that there's a distance beyond which you don't actually want to move the Doom Bats to the Great Drake, and that's the whole point of the distance mechanic we're contemplating.

Second, the doom bats will NOT move towards the Great Drake because of the sumOfStackValues check, when they are too far away. The doom bats will have a much lower modifiedValue in the calculation centering on the Great Drake, because there's more of them, the sum of the penalty is much larger than the penalty on just the Great Drake, so the algorithm will retain the old one.

If you applied a distance penalty of for example -1 in each modifiedValue calculation, this would be -8 in the sumOfStackValues when calculating the stack strength centering on the Great Drake because there are 8 Doom Bats far away, whereas for the stack centering on Doom Bats the penalty would only be -1 for the one Great Drake unit far away. Of course, you have to set the distance modifier in such a way that the calculations work out this way. There would be a threshold at which the algorithm would in fact choose the Great Drake instead, but in that case it should be at such a close distance that it doesn't actually matter.

I didn't mention this earlier, but in the case of retaining the old stack, the algorithm should proceed normally through step 2 - 5 again on the second turn. This would result in the Great Drake being chosen in step 4, and replacing one of the Doom Bats at the previously chosen location, not the other way around.

If you don't want the actual buildSpot to be at the location chosen in step 1, it's easy enough to have the units gather using the geometric median algorithm the game already uses, according to what you said about the "average position". The buildSpot is just a reference for the distance calculation.

Ok, how about this one, would it work?

1. Select the best unit.
2. Find the 8 next best units that are all within range X of the best unit. If successful, send these 9 units to the same spot. If not, remove "bestunit" from the list.
3. Jump to 1 until the list is less than 9 units.

It guarantees the the best stack that's reasonable to gather within an acceptable amount of time but would it also guarantee the units won't get selected for different stacks and keep moving back and forth each turn.

What is the "If successful" check? I didn't understand step 2 at all, so I'm afraid I can't comment on the the rest.

Something else. We can also add a new, non-movement based doomstack building which works like this.
The AI already has a "frontier town" concept, selecting a city in a place it's most in need of troops and summons roughly at a 1/3 chance there. So how about we instead do this :

0. Any city with a full 9 intercontinental movement units that are high quality sends the units outside and is marked "immediate summoning is needed". (this will need to use a special movement code to not mark the units done so they can also attack later that turn using any leftover movement points)
1. If any towns are marked as "immediate summoning", summon things there instead of casting other spells, for that one turn only.
2. Any city with at least 6 intercontinental movement units which are a similar tier as the best available summoning spell, counts as a frontier city in addition to the existing one.
3. When summoning to the frontier city is chosen as the summon location and there are more than one, pick the one with the most such units.
4. Halve the priority of all summon spells that are not flying and waterwalking for summoning in that city and summon something.
5. (Target selection for waterwalking and Wraithform should prioritize units in a frontier city higher.)

There. What this achives is two things : The AI can make new doomstacks where it matters and doesn't need to spend time gathering them in one spot AND any doomstack that conquers a city will be able to leave it and move on to attack more, without leaving the city entirely undefended. This is important as razing cannot be used to free the stack from its garrison duty if we remove instant razing. Basically, this allows the AI to also use doomstacks in a way more similar to the human player on top of simply pooling together whatever units it already had.

Wouldn't it be easier to just mark newly conquered cities as frontier cities that need reinforcement?

[Seravy]

What is the "If successful" check? I didn't understand step 2 at all, so I'm afraid I can't comment on the the rest.

It picks units that are at most distance X from the first. If there are at least 8 of those, that's success, if there aren't, that's fail.

Wouldn't it be easier to just mark newly conquered cities as frontier cities that need reinforcement?

No it wouldn't. That doesn't guarantee a city ever reaches the 9 units (as there are too many of them, or if there is a duraton limit, it might expire before the city is full) and those units will never leave the city as stack together - they can't normally bypass mandatory garrison requirements.

If you applied a distance penalty of for example -1 in each modifiedValue calculation, this would be -8 in the sumOfStackValues when calculating the stack strength centering on the Great Drake because there are 8 Doom Bats far away, whereas for the stack centering on Doom Bats the penalty would only be -1 for the one Great Drake unit far away.

Maybe I misunderstood but you didn't specify to do that.
You specified to pick he great drake then the 8 bats, then replace the bats one at a time with a better "modifiedvalue" in other worse a closer unit. If there are no closer units, the drake and 8 bats will be picked, even if the 9 bats could have been because we aren't iterating this for every unit, only the first one.

But you are right, if we loop this process picking each unit on the list as "best unit" and using their position as the "build spot" then it does work and it only takes n^2 time which is still okay, at least it looks ok at first sight.
I'm not very comfortable with it assuming buildpoints that aren't going to be the actual buildpoints.

For example if I have 7 bats at location X, one more 20 tiles to the east and one 20 tiles to the west then the total weight will be (9 bats value-40). If 7 are at X and 2 are 20 tiles to the east, none to the west then it's the same value.
But the first is going to take twice as much time to build the stack because the stackbuilding point is X, while in the other case it's 10 tiles east from X.
..in fact, the only thing that matters is the distance between the two units furthest from each other, the other 7 can be anywhere in between, the overall time spent is not different. But which two units are furthest actually changes when I replace a unit in a way that's not as simple as "lowest is best".
Example, I replace the unit 20 tiles to the east from the (7 at center, 2 at east) case with a unit that's 12 to the north which is the closest option (all units have the same value). That means I can no longer pick the 2 units 14 tiles to the south because that creates a 26 distance between the north and south units. However the correct solution would be the two south units - there was only one to the north so that doesn't let me remove the other east unit, keeping a total distance of 20.
Basically, choosing the unit to the north is a mistake even though it's the closest because there aren't enough other units in that direction. Maybe I do get the correct set if I start picking units from a different center, but maybe not, I don't know.

...anyway, this is way too complicated. Unless you can find a significant problem with mine, I will prefer that.
One more thing to consider. If the units are far away but there is no other option, then not building a stack might be better than going with the "best" option available.
(intercontinental) Units doing nothing are forced to go to the main action continent so eventually the units will be in range and can build a stack and I have a feeling doing that is actually faster than trying to move the long distance to get together first, then move another long distance to the main action continent anyway (or get used up in battles elsewhere because the stack is now powerful enough to attack things and those things won't be at the main battlefield.)
..okay this is pretty convincing, I think I should go with this one, but do tell if you can spot a mistake in my train of thought.
I do see one downside : if there is no main action continent. But that's not going to happen in CoM 2.