Dominions III Artificial Intelligence
 

Dominions II is fun, diverse, interesting, and complex. Dominions III will be bigger and better. What more could a person possibly want in a strategy game, other than scantily-clad blood slaves of all races and genders? In my opinion... Artificial Intelligence, Balance, and Ease of Use.

The Johans and Ostermans of the world are already doing their part in improving Dominions’ graphics, interface, balance, variety, mechanics, and who knows what else. However, they are primarily a 3-ish person, part-time team – trying to make the best strategy game ever. A lot of the coding problems are (probably) NP-hard, like ideal unit-mix recruitment, battle spell selection and order, site-searching order, and battle target-selection. This means that no amount of effort (barring a monumental mathematical breakthrough) will produce a perfect algorithm, but that the algorithms can be improved indefinitely; and when choosing between addressing a problem that can be solved in a week versus toying with a provably unsolvable NP-hard problem, any programmer who wants to finish a project will choose the solvable one. So without disrespect to JO, almost no single aspect of the Dominions III AI could be perfected even if he had a team of 100 Turings and Babbages working under him for a decade. However, they would continually improve, and the extra labor would free up time for Johan to work on whatever he finds most interesting.

In my opinion: many of the issues with exploits, balance, and micromanagement are really symptoms of AI and related algorithms, and will not improve significantly with any amount of effort into UI design, data balancing, or even game-mechanic changes.

There is a hard limit to the change one can affect through the current and expected data modding capabilities, and it is insufficient to compensate for (e.g.) the ineffective tactics of skirmish troops. As such – and bearing in mind that I do not speak for Illwinter, or with any authority, for that matter – would anyone in the forums be willing and able to engage in code-modding, if Illwinter was so benevolent as to make it a possibility? I’m thinking of algorithmic things, ranging from the function “int whatProvinceShouldISiteSearchNext(SiteGraph explored, Unit bobTheMage)” to a complete tactical combat AI.

I would love to work on the tactical AI, because it is vital in single and multiplayer games, because it can be so frustrating, because a huge amount of micromanagement (scripting, etc) is dedicated to compensating for the tactical AI’s nuances, and because a better tactical AI would negate lot of the balancing issues I was unable to address via data modding. If I wrote a tactical AI, it would be extremely slow (slower than you would want in a commercial game, but fine for 1-turn-per-day PBEM games) but thorough, because I don’t care if Dominions III takes 5 seconds or 5 minutes to process turns (as long as there was some user-configurable, finite limit); though it would be nice to be able to examine my empire in the meantime. This does not mean I can write something better than the current tactical AI, but it would certainly be slower http://forum.shrapnelgames.com/images/smilies/happy.gif

Would anyone else utilize deep code-modding capabilities if they were available? Bear in mind that answering “Yes” when you mean “Maybe” or "Yes I want other people to do this, but I won't" might possibly divert Illwinter’s attention away from more important matters.

Illwinter - if you have any comments about code-modding, changes in AI since Dominions II, proving P==NP, or the weather up there in the North Pole, I'm sure we'd all be glad to hear them http://forum.shrapnelgames.com/images/smilies/happy.gif

Re: Dominions III Artificial Intelligence
 

I'd be unwilling, and utterly unable. However, I am curious what NP stands for in your post http://forum.shrapnelgames.com/images/smilies/wink.gif

Re: Dominions III Artificial Intelligence
 

Hi Cherry!

At the risk of being unpopular, there won't being any support for programming your own AI in Dominions III. It would be much work to do and believe almost no one would take advantage of that possibility anyway. If there will be a way to influence the AI it will be mod settings that are easy to fiddle around with.

Re: Dominions III Artificial Intelligence
 

I would be interested, but short of time and maybe somewhat unable, too.

Actually, I didn't expect DOM3 to have scriptable AI. Would mean they have to throw away the engine and re-code everything from ground up. Would take at least 10 years IMHO.

As for players doing AIs own their own: There are games where players code the AI. FreeCiv, obviously, but did you check out Civ Evolution (http://www.c-evo.org/)? It's done by one lonely guy, and there are several external AIs, made by players obviously, available. And they do quite a good job (both)

What about an external AI? We would just need the file formats for that, to be able to read them in ... .

That would be not quite 100% of what Cherry envisions, though? If I understood right, you wanted to fiddle with the "MM AI", so battle setup, sitesearching etc could be handed over to the AI in most cases.

Have no idea how that could be done - unless one writes a "turn pre-/postprocessor", which loads the turn file, writes the first 'standing' orders into the orders file, starts DOM3 to have the player have a look at the turn, and then maybe does some processing afterwards, too.

Could even be scripted in Tcl I think, but would be a monumental task. And would need a 5 Ghz CPU to run. .. or wouldn't it? Hmmm .. if done multi-threaded, it could run on 2 CPUs at once (or DOM3 on one and the app on the other), and everyone will have 2 cores when DOM3 finally arrives I'm sure http://forum.shrapnelgames.com/images/smilies/wink.gif
Maybe even make it a "parallel processor", which peeks into the files folder now and then and reacts to changes to player makes. O.c. DOM3 would need some possibility to re-load the turn and the order file...

Oh, dreaming again...

A.

Re: Dominions III Artificial Intelligence
 

Nondeterministic polynomial. This is a class of problems that have no known solution in polynomial time - for example, if the problem involved 20 provinces, there is no known algorithm that could solve it in 20^X steps, where X is some constant. However, the problems can be solved in exponential time, like X^20, but this is much slower.

"Nondeterministic" means that they could be solved in polynomial time on a nondeterministic computer (a quantum computer) or with an infinite number of parallel computers.


Hi Johan!

That's OK, I figured as much =) It doesn't seem like there's much interest in it anyway.



That's kind of what I've been mulling. If one could decode the turn files, any sort of strategic AI algorithm could probably be implemented... with a lot of work. Combat AI would still be off-limits, though.

Highly Parameterized AI
 

Ok, so code-modding is out, but as for "a way to influence the AI through mod settings that are easy to fiddle around with"... how about parameterizing the AI, and making all the parameters moddable?

For example, a mod file might look like this:

<font class="small">Code:</font><hr /><pre>
Abysia_Recruit_Mage_Priority==80
Abysia_Recruit_Heavy_Infantry_Priority==150
Abysia_Recruit_Assassin_Priority==40
Abysia_Build_Temple_Priority==160
Abysia_Build_Fort_Priority==220

Mictlan_Recruit_Mage_Priority==130
Mictlan_Recruit_Heavy_Infantry_Priority==20
Mictlan_Recruit_Light_Infantry_Priority==100
Mictlan_Recruit_Sacred_Priority==250
Mictlan_Blood_Hunt_Priority==1000
Mictlan_Blood_Sacrifice_Priority==400
Mictlan_Build_Temple_Priority==40
Mictlan_Build_Fort_Priority==50
</pre><hr />


The values could range from 0 (never) to 1000, with the default of 100 meaning "the usual amount". They would modify AI behaviors, such that setting "Mictlan_Recruit_Sacred_Priority==250" would make the AI try to recruit 2.5 times as many sacred units as normal. Or, at least, it would increase the number of sacreds in the unit mix. "Mictlan_Recruit_Heavy_Cavalry_Priority==0" would make them never recruit heavy cavs, even if they conquered an indy province that had them.


Things I feel might benefit from parameters. Note that each of these should be moddable per-nation! And note that the numbers generally modify behavioral probabilities, rather than setting a fixed order in which the activities occur; if research_priority is greater than blood_hunt_priority, both activities would still occur at the same time, but more mages would (generally) be devoted to research.


1) Mage Orders (only for stationary mages)
Search
Research
Blood Hunt
Summon
Craft Artifact
Cast Spells


2) Army Orders (only for stationary armies)
Defend
Patrol
Siege
Break Siege


3) Priest Orders (only for stationary priests)
Search
Preach
Sacrifice
Reanimate


4) Strategic: Research
(one per magic school)


5) Strategic: Buildings
Fort
Temple
Lab


6) Nation Design
Combat Chassis (probability a combat chassis is selected...)
Bless Chassis
Rainbow Chassis
Dominion Strength (priority of spending points here)
Order, Growth, etc. (one per scale)
(one per magic path)


7) Recruitment Priority

This is a little different. First, all Dominions II units need a "role" or "type" (that is displayed in the unit description). This could be auto-generated based on simple rules regarding their stats and equipment. They should be changable through modding, though. Then the recruitment priorities can be set for each type (for each nation).

Types:

Scout
Spy
Assassin
Commander
Priest
Mage

Militia
Skirmisher (light infantry w/ javelin)
Medium Infantry
Heavy Infantry

Horse Archer
Light Cavalry
Heavy Cavalry

Slinger
Archer
Crossbow

Melee Monster (anything with lots of HP, like Jotuns, Hydras, elephants)
Ranged Monster (Illithids, Jotun Hurlers)


Properties: these are parameterized independantly of unit types.

National
Indy
Flyer
Amphibian
Aquatic
Magical
Trampler
Sacred


8) Tactical Spellcasting
Summon
Mass Damage
Single Damage
Mass Support
Single Support
Self Support
Gemcosting Spells
Additional Gem Usage



That's a bit confusing, so here is an example of a complete null-mod for Abysia's strategic AI, that does nothing:

<font class="small">Code:</font><hr /><pre>

** Mage Orders **

Abysia_Mage_Search_Priority=100
Abysia_Mage_Research_Priority=100
Abysia_Mage_Blood_Hunt_Priority=100
Abysia_Mage_Summon_Priority=100
Abysia_Mage_Craft_Artifact_Priority=100
Abysia_Mage_Cast_Spells_Priority=100



** Army Orders **

Abysia_Army_Defend_Priority=100
Abysia_Army_Patrol_Priority=100
Abysia_Army_Siege_Priority=100
Abysia_Army_Break_Siege_Priority=100



** Priest Orders **

Abysia_Priest_Search_Priority=100
Abysia_Priest_Preach_Priority=100
Abysia_Priest_Reanimate_Priority=100
Abysia_Priest_Sacrifice_Priority=100



** Research **

Abysia_Research_Construction_Priority=100
.....
Abysia_Research_Thaumaturgy_Priority=100



** Buildings **

Abysia_Build_Fort_Priority=100
Abysia_Build_Temple_Priority=100
Abysia_Build_Lab_Priority=100



** Nation Design **

Abysia_God_Chassis_Quality_Priority=100
Abysia_God_Combat_Chassis_Priority=100
Abysia_God_Bless_Chassis_Priority=100
Abysia_God_Rainbow_Chassis_Priority=100

Abysia_God_Dominion_Strength_Priority=100
Abysia_God_Fortress_Quality_Priority=100
Abysia_God_Increasing_Magic_Paths_Priority=100

Abysia_God_Nature_Magic_Priority=100
.....
Abysia_God_Fire_Magic_Priority=100

Abysia_God_Growth_Scale_Priority=100
.....
Abysia_God_Luck_Scale_Priority=100



** Recruitment **

** Properties **
Abysia_Recruit_National_Priority=100
Abysia_Recruit_Indy_Priority=100
Abysia_Recruit_Flyer_Priority=100
Abysia_Recruit_Amphibian_Priority=100
Abysia_Recruit_Aquatic_Priority=100
Abysia_Recruit_Magical_Priority=100
Abysia_Recruit_Trampler_Priority=100
Abysia_Recruit_Sacred_Priority=100
Abysia_Recruit_Undead_Priority=100

** Types (Commander) ***
Abysia_Recruit_Scout_Priority=100
Abysia_Recruit_Spy_Priority=100
Abysia_Recruit_Assassin_Priority=100
Abysia_Recruit_Commander_Priority=100
Abysia_Recruit_Priest_Priority=100
Abysia_Recruit_Mage_Priority=100

** Types (Infantry) ***
Abysia_Recruit_Militia_Priority=100
Abysia_Recruit_Skirmisher_Priority=100
Abysia_Recruit_Medium_Infantry_Priority=100
Abysia_Recruit_Heavy_Infantry_Priority=100

** Types (Mounted) ***
Abysia_Recruit_Horse_Archer_Priority=100
Abysia_Recruit_Light_Cavalry_Priority=100
Abysia_Recruit_Heavy_Cavalry_Priority=100

** Types (Ranged) ***
Abysia_Recruit_Slinger_Priority=100
Abysia_Recruit_Archer_Priority=100
Abysia_Recruit_Crossbow_Priority=100

** Types (Large) ***
Abysia_Recruit_Melee_Monster_Priority=100
Abysia_Recruit_Ranged_Monster_Priority=100



** Tactical Spellcasting **

Abysia_Tactical_Summon_Spell_Priority=100
Abysia_Tactical_Mass_Damage_Spell_Priority=100
Abysia_Tactical_Single_Damage_Spell_Priority=100
Abysia_Tactical_Mass_Support_Spell_Priority=100
Abysia_Tactical_Single_Support_Spell_Priority=100
Abysia_Tactical_Self_Support_Spell_Priority=100
Abysia_Tactical_Gemcosting_Spell_Priority=100
Abysia_Tactical_Use_Additional_Gems_Priority=100
</pre><hr />

Re: Highly Parameterized AI
 

I'd be willing and able to help with a program to read the turn files and give units orders to reduce micro management. I imagine the devs would have to show us how to read the files. If it becomes a possibility, I'll gladly help out with coding (C/C++ only) and writing algorithms.

Re: Highly Parameterized AI
 

IIRC, it has been said earlier that giving out the turn files' syntax would make it very easy to cheat and make cheating scripts, but it stil would give only limited modding capabilities for those few people who would even want to try such a thing.

Re: Highly Parameterized AI
 

Hmmm... I don't buy that argument.
( Btw., we're not talking about modding the game, but some way to automatically generate orders for all those tedious MM-task, and maybe a player-made external AI which whould use the same alghorithms. That's something different)

1) If there's a 100% check of orders on the server side, you would need to exploit bugs to cheat. And as every DOM can be run as client as well as as server, all the code to do the checks is available in the .exe =&gt; no need for and problems with dublicated code in client and server.

2) If I knew the file formats, I would be able to write an application (external AI), that can do everything a player can. Even more so: DOM in either server or client mode doesn't have any kind of memory. That's one of the causes why the AI has some troubles.
An external app could write all the info a player gets every turn to a file, so you e.g. always know which sites are in provinces you once owned, or which armies you have seen 2 or 4 turns before.
Furthermore, you could use that app to write orders to the turn file, e.g. have a commander move,patrol,move,patrol in your provinces automatically.
With everything in place, one could build an AI on top of those functions, which is -potentially- much more capable than the current one. And it wouldn't do anything else than read in a normally generated turn file, process it and write an order file, as the player does using DOM itself.

3)Security by obscurity is temporary at best
It's only a matter of time, before some figures out how things work. Sometimes you're lucky, but mostly those interested in such actvities are indeed more interested in self-profiling (even by cheating) than sharing their knowledge with the community. Search the forum for "Norfleet" ...

If, however, 1) does not apply, because the checks are made in client mode, I would suggest they throw away their code and start re-coding the game... .

Re: Highly Parameterized AI
 

I remember Norfleet, but I only know what he did, not how.

I haven't thought about the matter myself, though. I only remembered reading a similar comment from a dev once. You might well be right in both that the client shouldn't do anything without the server verifying it, AND that then releasing information about the turn files wouldn't give any more possibilities to cheat.