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.

Re: Dominions III Artificial Intelligence
 

http://forum.shrapnelgames.com/images/smilies/rant.gif
A hasty jugement.
Look at space empire 4 ! Score of players fiddled with AI, improving score of them to the point where none of the ingame AI could handle the heat from the customs one.

There has even been AI contests where all customs AI battled each others just to decide who's the best.

Too bad we'll can't have that on Dom3.

http://forum.shrapnelgames.com/images/smilies/Sick.gif

Re: Dominions III Artificial Intelligence
 

Interestingly, the P=NP? problem will likely never be solved. The basic stucture of it is such that any proof will probably be unconstructive, i.e, it either is untrue, or it is impossible to proove whether it is right or not. The main problem in understanding this is that NP is NOT the same as non-P. a problem is NP if you can determine whether a proposed solution IS a solution in polynomial time. If someone could find an NP complete problem (that is one that if solved in polynomial time demonstrates that all NP can be)and solve it. the trouble is, if we find just 1 NP complete that is P, we have proved it, but no number of NP that do not =P will disprove it. The SAT gate of boolean computation is a very simple NP complete problem. If Illwinter can solve this, I, on behalf of all mathematicians from Euclid to the present, thank them.

But it won't happen. A minesweeper SAT gate would require all the computing power illwinter has at its disposal. Dominions3 would be impossible.

An'ya i Suotho,
Valandil

Re: Dominions III Artificial Intelligence
 

Flashbacks of my CS training...

Why are you doing this to me!!!

Re: Dominions III Artificial Intelligence
 

I think it's worse than NP-hard. It's either AI-hard (you can't program it because you can't specify the problem well enough, a common problem in Artificial Intelligence) or "NI-hard" -- you can't program it because even natural intelligences (people) can't think of algorithms to solve it. NI-hard problems make for good games, for some reason. http://forum.shrapnelgames.com/images/smilies/happy.gif

I agree, tho, that heuristics, approximations, and pre-computed answers (look-up tables) will help a lot. They're used heavily in industry, and they solve a lot of practical problems that are formally NP-hard. I work on stuff like that.

I think this is another case where I think it's worse than you think. http://forum.shrapnelgames.com/images/smilies/happy.gif http://forum.shrapnelgames.com/images/smilies/frown.gif I think there's a mismatch between the options the player wants for tactical combat and the tools the game provides for them.

There was a game called Deadlock that did much better. The details aren't that important, 'cept that that it was a strategy game where the tactical combat took place on the "province" maps, so in addition to attacking enemy units, troops could attack province buildings directly. Units were ordered around by simple pop-up menus, with choices like "(Attack|Protect) (Kind of unit|kind of building) until unit casualies = X%." That worked really well, because players really wanted to attack or defend buildings, but enemy units got in the way.

In Dom2, tho, what we really want to is give orders like "skirmishers harass enemy national heavy troops until lightly damaged, and then break off" or "high-path mages cast big buffs on friendly SCs, then blast enemy SCs until killed", but neither the UI nor the AI is geared toward this.

Ooo! Me! Me!me!me! I can't talk much about my paying work, but you can get an idea what I do and enjoy by looking up early MechMania contests (programming game AIs over a long weekend). You'll note that the first few contests were dominated by a small number of teams from the same schools. I was on one of them. http://forum.shrapnelgames.com/images/smilies/happy.gif We stopped dominating only 'cause the organizers politely asked us to stay away. http://forum.shrapnelgames.com/images/smilies/wink.gif


Oh, yeah! If nothing else, it would make it much easier to test strategy and tatics w/o having to hack the save files to get the "right" scenario set up.

Re: Dominions III Artificial Intelligence
 

In DomII there was no support for AI programming but I was still able to setup alot of variations and scenarios. Boosted starts for AIs, extra castles, alliances, hatreds, boosted gods, no gods, extra aggressive, less aggressive capable, extra equipment, and on and on and on. And then of course, randomized variants of all of it.

So even if AI programming isnt specifically supported, you can expect more capabilities along those lines. And you can expect me to jump right into it.

But just for the record I also vote that I would like for the game to have scripting hooks put in for 3rd party bot writing. And I also agree that Space Empires 3 (which I consider to be one of the very few peers to Dominions 2) is a great example of what benefits can happen by allowing player improvements in things like AI.

Gandalf Parker

Re: Dominions III Artificial Intelligence
 

Some remarks:

- Cherry first idea was about writing an external or scripting the internal Battle AI, to fix lots of its current shortcomings over a long time of evolvement. Sadly, this will never happen, because the DOM engine does not support that at all, and illwinter is not going to re-code everything from scratch.

- In SE4 (not 3, Gandalf!), there's no way to write own AI code or script "new" behaviour. There are lots of parameters one can set in a mod, though, to drastically alter the weighting in its decision making process.

- If I understand Johan correctly, this is the best we can hope for with DOM3 as well.

Re: Dominions III Artificial Intelligence
 

For turn-level AI, the only thing the Dom3 team need do is publish the client file descriptions. That is very little work. We can do the rest.

Security requires that the only thing coming from the clients back to the servers is orders and that the only thing coming from the servers to the clients is nation-specific info. This has to be done even if the client flie descriptions aren't published. Obfuscated files or not, Norfleet just demonstrates what every security professional will say, which is that concealment doesn't give usable security. Once that's done, you can't hack Dom3 from the client files, period.

Making the server recognize only orders from the client is trivial if it's not already done that way. You can sync order creation and check by having both run off a "doableBy(Commander commander)" method in the Order interface/abstract class. Item transfers and the gem/money spinners would need to be implemented as orders rather than as operations on the world model but that's easy if not already done.

Having the client (player's) view of the world operate from a representation of their knowledge of the world rather than the actual world model is not trivial but worth the effort even if not already done. Actually, even thinking about doing it the other way makes my head hurt - that would be WAY harder.

Re: Dominions III Artificial Intelligence
 

@curt : As I said above ...

@Johan K. : What do you think about releasing info 'bout the file formats to the public ?
And what about releasing the info to trustworthy members of the community only, who are willing to sign a NDA ?

Re: Dominions III Artificial Intelligence
 

I just wanted to point out that entire communities have evolved around games with AI scripting. I am a member of one such community:
http://aiscripters.com/

Please don't take this as meaning that I don't appreciate dominions in it's current state, I just look at AI scripting/modification being included as an opportunity to erase every other game from my hard drive. http://forum.shrapnelgames.com/images/smilies/happy.gif I think there are plenty of people who would take advantage of this feature if it were available.

Re: Dominions III Artificial Intelligence
 

Interesting. I joined a number of map-making communities back when I was working on turning the Dom2 maps into semi-AI variations. None of them proved helpful.

Lets hope that the Dom3 AI has some improvements.

Re: What Norfleet did
 

I did a search on Norfleet and I found that he was not the only one that found out how to cheat. Seems like the way to go is just to edit the 2h file with a hexeditor and by trial and error find out what can be done and what can not be done.

It would be possible to play a game where all players are human and then have a external program editing the 2h files for those that you do not plan to play. It would probably be a real painful exprience to do so. I remember whan I sat and decoded the map files in settlers 2 because a map was corrupt.