Hi,

I have an issue in the game i am currently writing, I would like to integrate diplomatic relations between the different factions, in a manner similar to the Civilization / Galactic Civ. games. The data part I can do, and did:

The map is cut into sectors, each one has a value depending on various factors (resources, assets and so on) so knowing the point of interest is not a problem.

Each faction value others according to various factors (past aggressions, similar laws or not, nearby borders causing frictions and so on) so knowing who like/hate who without diplomacy isn't really either

They also have a value they can check to compare military strength, so they know if they are threatened by others or if they are dominant.

The different factions have the following tools to interact:

• Declaring war for a specific neighboring sector
• Giving gifts / send diplomatic ship to improve relations
• Insult to lower relations
• Trade agreements (allowing ships to buy/sell from other factions assets)
• Passage agreements (using jumpgates from other factions to get to their sectors)
• Military/Alliance agreements (both factions using military ships as one)
• Give/sell/ask for a sector to improve relation or get money or remove a threat

Each faction has values that can be used: diplomatic power (how persuasive is a faction), xenophobia (how resistant is a faction to offers from another (to balance diplomatic power), how warlike or "tradelike" is the faction and so on. Most of it heavily influenced by 4X games.

Going to war is easy, but for the rest, like making alliances, allowing ship passage / trading and so on in a believable way, I am kinda lost. I don't really see a sort of generic algorithm that would make AI controlled factions using diplomacy without relying on a nightmarish mess of nested If/else/if/else. While I am fairly used to FSM logics which i used (to an extend) for individual units I don't really see that working on a faction level.

I've looked left and right about diplomatic / strategic AI but the documentation is kinda sparse and usually war focused. And that is definitively not my problem, which is basically how to handle "peace" or maintain it (and why). Is there something obvious that I am missing ? Is it something so game dependent that there's no general ideas on how to handle such things without into going "crazy" genetic algorithms ?

At this point any pointer to related documents or advice is more than welcome

I will provide more data regarding the game' structure if you need it.

Anyway, thank you for you time.

Cheers,

SK.

edit: changed link toward my indieDB page instead of my site which is currently down.

Over the last few years, computer go playing has improved dramatically by using Monte Carlo Tree Search. Many of the techniques developed for computer go are applicable to a large class of games. The fact that you don't know what deals other players have made with each other might complicate things, but perhaps you can start by ignoring that, and think about it more once you have something working.

You need several ingredients:
* A class that represents the game situation. You'll need methods to know if the game is over (and how well each player did), what the available actions are for each player at any given time, and to perform an action.
* A so-called playout policy, which is a fast function that picks a random action from each available action to each player. This random selection need not be uniformly random: It's better if it selects moves that are obviously good more often than obviously bad moves. This doesn't need to be very smart at all.

The basic idea is that for each of the available actions at the current position, we play many random games (using the playout policy for every player) and we compute the average reward we get from them. Then simply pick the move with the highest average reward. In order to be able to simulate a significant number of random games, it is essential that the code be fast.

It is very possible that the AI resulting from doing what I just described will be good enough. If it's not, there are a few improvements you can try:
* Explore promising moves more often, treating the situation as a multi-armed bandit, and using an algorithm like UCB1. Actually, this is easy enough that you should do it even if the program is strong enough without it.
* Accumulate statistics for positions that have been visited multiple times by this procedure and apply the point above at those positions as well (this results in Monte Carlo Tree Search).
* Enrich the statistics using something called RAVE, or other techniques that exploit similarity between positions.

Hopefully that gives you enough ideas and search terms to get you started.

@Alvaro: First of all, thank you for this detailed answer, it's appreciated.

I should definitively try to learn to play go someday, that's not the first (or last) time I hear about this game in relation to AI for good reasons.

I should have specified that CPU cost / speed isn't a problem at all in my case, the game (plays in real time, not turn based) is fully multi-threaded, the faction AI runs in its own dedicated thread. Each faction AI is called every few minutes, and the time it takes to do its magic isn't really relevant, the individual units will still live their lives until their overlord tell them to do otherwise. So "brute-forcing" (sort of) thousands of scenarios has no real negative impact in my case.

It's getting really late for me so my apologies if I am mistaken, I will definitively check that again later tomorrow. But, basically, if I understand correctly I could make an additional class that abstract the diplomatic part of my game, then more or less brute force my way in what would be the most comfortable position for each faction by testing all the available options, removing the choices that are irrelevant, and putting a weight on the remaining ones according to the stats and data gathered by each faction ?

Yes, that's interesting. Weirdly enough i never thought about treating the diplomacy as a separate entity that i could work on with its own rules. Instead i was focusing on the whole game and trying to shoehorn the diplomacy into it (if it makes sense, English isn't my first language).

Anyway thank you a lot, that's a very interesting approach to this problem.

(note that i am still open to other suggestions as well ;))

edit: Even if it doesn't invalidate your suggestion at all, I think it's important to add for clarity sake, that my factions don't really want to "win" the game. The ideal state of the game is that weaker factions manage to survive, and that stronger ones collapse or at least stop expanding. It's not a wargame, but a game similar to Elite (or more accurately X3) where the player, after a long while, manage to have enough assets be a faction on it's own. AI factions are here to give context / story, not to annihilate any opposition. That's why managing / enforcing peace in a believable way is so important to me.

The different factions have the following tools to interact:

Declaring war for a specific neighboring sector
Giving gifts / send diplomatic ship to improve relations
Insult to lower relations
Trade agreements (allowing ships to buy/sell from other factions assets)
Passage agreements (using jumpgates from other factions to get to their sectors)
Military/Alliance agreements (both factions using military ships as one)
Give/sell/ask for a sector to improve relation or get money or remove a threat

Each faction has values that can be used: diplomatic power (how persuasive is a faction), xenophobia (how resistant is a faction to offers from another (to balance diplomatic power), how warlike or "tradelike" is the faction and so on. Most of it heavily influenced by 4X games.



Going to war is easy, but for the rest, like making alliances, allowing ship passage / trading and so on in a believable way, I am kinda lost. I don't really see a sort of generic algorithm that would make AI controlled factions using diplomacy without relying on a nightmarish mess of nested If/else/if/else. While I am fairly used to FSM logics which i used (to an extend) for individual units I don't really see that working on a faction level.

The major problem I see in this description of diplomacy is that most of it consists of arbitrary abstractions and ritual behaviour and it doesn't lend itself to translation into rules and game theory (which you need to have an AI that reasons in meaningful ways).

If factions are interested in their own prosperity (as opposed to hurting themselves to hurt others more, e.g. going to war) they can simply be friendly with everybody: reciprocal trade and passage agreements, occasional fair exchanges of territories for good reasons, massive military alliances (marking the few rogue factions outside the alliance as a potential threat), no wars, no gifts, no insults, no bad relationships, no persuasion, no xenophobia. Strategy would consist of being ready to go to war with neighbours that aren't in the alliance in case they do something funny.

This style of AI would have to evaluate the economical benefit from trade and passage agreements (maybe a Monte Carlo simulation of commerce and travel with and without the agreement) and the best selection and deployment of military forces (maybe more suitable for thorough searching over move trees containing fleet movements, battles etc.).

My preference would be to create a set of rules that give small factions some edge (guerrilla war, sympathy of the local population, difficulty of finding their hideouts, perhaps large factions get slowed down by bureaucracy and coordination problems...) and then let each faction really try hard to win. Otherwise you could end up with diplomatic actions that make little sense, where the dominant faction helps a weak faction without much justification, or where it becomes too transparent that they are collaborating to keep a healthy ecosystem of factions. Of course the guiding principle should be to make the illusion work for the player, by whatever means necessary.

My website just hit its quota limit (free hosting that i need to upgrade to a paid service), so here's two relevant screenshots i uploaded here:

-

@Alvaro :

Yes that's some really good ideas. I also thought about giving a strong negative diplomatic modifier (with 3rd parties) to strong factions for bullying much lesser ones, so there's at least a negative impact for an action that otherwise would have none when I run the decision making algorithm. Some "good" factions would also refuse altogether to completely raze the home sector cluster of another one, because, well, genocide is not considered acceptable. Now that i think of it, such rules also flesh out the lore of the game, that's good

Otherwise you could end up with diplomatic actions that make little sense, where the dominant faction helps a weak faction without much justification, or where it becomes too transparent that they are collaborating to keep a healthy ecosystem of factions.

Yes. The most important thing for me is to have a system where the player won't think "ohh this is gamey!" It has always been my design method to avoid artifices. Mostly because being both a coder and a gamer I tend to see right through them myself too quickly causing me to loose all interest in the said game.

When i was designing mods for space games (X3 from Egosoft), for player missions, i never relied on "click me to spawn 10 targets out of thin air" scenarios, instead I used targets that were existing in the game. If faction X ask the player to kill something from faction Y, the thing in question had really caused some damages. That's a philosophy I'd like to keep when dealing with diplomacy and war too.

-

@LorenzoGatti :

The major problem I see in this description of diplomacy is that most of it consists of arbitrary abstractions and ritual behaviour and it doesn't lend itself to translation into rules and game theory (which you need to have an AI that reasons in meaningful ways).

I do not necessarily agree, In the real world maybe (and even then) but in a game not so much. With a well structured enough system (and that's the system I am trying to determinate), each diplomatic action has pro and cons for the well being of the factions. Trade agreements mean more money for both so they can build more infrastructure. Selling sectors avoid greater material loss at the hand of an enemy. And so on. With the right rules and logic it can be quantified. It's no more arbitrary than all out warfare in my opinion.

If factions are interested in their own prosperity (as opposed to hurting themselves to hurt others more, e.g. going to war) they can simply be friendly with everybody: reciprocal trade and passage agreements, occasional fair exchanges of territories for good reasons, massive military alliances [...]

I may have badly worded my post by speaking too much of peace, sorry i was tired i should have known better. Enforcing global peace isn't an issue. going to war neither. Keeping factions somewhat alive is a bit tricky but manageable with a few additional rules. Achieving something that look coherent is my problem, modifiers by themselves help to keep peace or to choose between 2 possible targets, but not much else. Currently when two factions go into an all out war for 3 poor asteroids, they have no reason to stop. If you look at a Civilization game, most of the time they tend to act with a bit of reason, 2 allies don't go at war for petty things, the situation has to deteriorate before they declare war on each other (same goes in reverse), and wars tend to stop when an objective has been achieved.

This said, yes, using a Monte Carlo simulation to find what is an optimal/good agreement between 2 factions is an interesting idea, and I will look into it.

This style of AI would have to evaluate the economical benefit from trade and passage agreements (maybe a Monte Carlo simulation of commerce and travel with and without the agreement) and the best selection and deployment of military forces (maybe more suitable for thorough searching over move trees containing fleet movements, battles etc.).

As a side note, war deployment and AI is already written. The defensive part works with a basic but effective algorithm that sort owned sectors by strategic value, then for each of those sectors send enough ships to defend according to its "menace" value (how strong are hostile fleets at the borders) until all defensive military ships are assigned. The most important sectors are adequately defended, the lesser ones not so much, but given the usual map layout, there's not that many points of entry into a territory anyway. The offensive part check the current defenders of the sector + what can join + some margin if available. A faction AI won't switch into war mode if it hasn't roughly enough forces. But between the obvious disadvantage of entering a sector from a singular location not exactly simultaneously to fleet strength estimates being, well, estimates, the attacker doesn't always win.

-

Um, "rubber duck problem solving" theory in action. I completely overlooked the "war weariness" factor used in Civ and other 4X games.. The longer the war and the bigger the strength difference between 2 warring factions the higher it would be. This rule could reduce factories output and money generation mechanism of the aggressor. It's not a solution for everything, but it would at least give a reason to end a war that's going well military speaking without relying on purely artificial reasons.

Thank you both