AI Diplomacy model

[Per]

There was a question in another thread about what AI diplomacy model might be appropriate for freeciv. Since I am trying to program such a model, I will briefly spell out what I've been trying to do and hope that people can contribute some ideas or links to discussions about this topic.

First of all, you need to realize how diplomacy in freeciv works. When two players "meet", each has a window in which various proposals are put forth, and then each player might "ok" or not the entire deal.

So what is needed is some kind of model to estimate whether such a deal is beneficial to the AI or not (and also if doing the deal will make the game fun). What I did was to try to convert every proposal into a gold value. The worth of treaties between players are estimated by looking at our desire for war or peace with that player, and his relative military strength.

The AI will pick one player as his main target, and attempt to achieve peace, cease fire or alliances with every other player while pounding on this target. The target selection depends on three factors: economic strength (gang up on and bring down the strongest), relative military strength (try not to be suicidal) and spacerace (always attack someone who is about to win by space race unless he is your ally).

The target will be frozen for some turns, and then the viability of continued war will be evaluated by looking if there now are other targets that really should be dealt with instead. Otherwise, continue until target is dead, then repeat on next target. There might also be some code later to check if the war has degenerated into a stalemate, or if we are losing it (ooops!) by checking the relative development of our economic strength during the war.

(BTW, part of the patch will be the possibility to win as an alliance and share the score. This is not currently possible.)

Opinions/flames/criticism/ideas welcome

[CapTVK]

I voted nice in the sense that the "economic worth" is a good starting point but how are the future returns of a deal valued?

e.a Computer player Y can decide to (A) build a marketplace or (B) go to war and conquer city of neighbour Z. In Civ2MP I've realized wars are costly once you start losing units that must be replaced at all costs

-I mean in the sense that my neighbours continue to prosper while I sacrifice production/trade and science to win a conflict. All those resources could have gone to improving my own empire so I had massive opportunity costs. In theory it usually takes a 100 turns or more to recoup your investments from conquered territory (if you manage to capture some decent size 5> cities)-

Coming back to the decisions of Y: Unless player Z has a weak military and doesn't defend his cities at all, option (A) (improving your own civ) would always be the best choice. Computer players would need to have a bit of irrationality (like human players ) to go to war anyway.


There's something else about negotiation techniques, but I'll have to read up on that first...

[Per]

If you intend to win by waging war, you will have to attack sooner or later. If your enemy grows faster than you, then you will have greater chance of winning if you attack earlier rather than later. If you grow faster than everyone else, then I agree you shouldn't go to war unless it is absolutely necessary.

[CapTVK]

First this question...
How to alliances factor into this? If was allied to a friendly AI with a large military some of that strength would be factored in with my own strength, right?


Well back again, I had to look some references concerning game theory and multiplay PD game stategies. It seems that a relatively simple strategy called *** FOR TAT (TFT) - "you cheat me this turn?, I'll repay the favour next turn!"- scores with a high average in tournaments. It isn't perfect strategy however. A RANDOM strategy can beat TFT. On average TFT scores well and this model can be refined somewhat to include earlier results.

So, how does the AI handle negotiations and deal with betrayal?


Edit: *** means T-I-T ,in the other sense of course

2nd edit: doh!, removed obvious spelling mistake

[LDiCesare]

Having a single target when at war sounds good, but what if you end up against an alliance? Assessing the enemy allies' strength might be better than trying to give them all your gold for a cease fire when your enemy will try to get them back into the alliance.
I also think that you should have civs which go to war all the time and some which will pay for peace.
In target selection, you forgot to mention proximity. Better to attack a neighbour than a nation far away. That is also a way to know when to stop. If you are stretching too far, maybe you should stop, consolidate and select other targets or build yourself up.
Also, don't forget that there are actions like tech-stealing and bribing cities that are very useful against fast growing neighbours and far cheaper than war if you can get them done, and should be considered before throwing an army towards the opponent.

[Per]

Everything gets more complex when you have to factor in the actions of you allies. I won't do that to begin with. In target selection, it will factor in the military strength of a potential target's allies and our own allies unless they are already at war with someone else. So we might unilaterally pull out of a war that an ally started to pursue someone we think is a better enemy. This is probably not optimal, but it will get the job done in most cases. Optimalization (like proximity, which is hard to do right) can be done later when there is code that people can be banging on and testing out.

Eventually, to get this done right, we'd need some more diplomatic primitives for the diplomacy dialog, like "make peace with X" (where X is our ally) and "declare war on X" so that we can have this as part of a bargain for an alliance, cease-fire, peace or ally-to-ally requests.

CapTVK, do you have any URLs to TFT theory?

[CapTVK]

Originally posted by Per


CapTVK, do you have any URLs to TFT theory?

First up TFT is a strategy, not a theory. It's a simple but very effective negotiation strategy (actually just 4 lines of code in Fortran) used in gametheory simulations (Prisoners Dilemma etc..). The TFT strategy is older then gametheory itself but was first worked out for PD games by Axelrod R. in the seventies. The articles you would need to look out for are "Effective choices in the prisoner's dilemma" Journal of Conflict resolution 24 1980 p3-25 and "More effective choice in the prisoner's dilemma" idem 24 1980 p379-403


Game theory and the stated strategy are also explained in Axelrod's most famous work: "The Evolution of Cooperation" (1984, Basic Books, New York) It's been translated in a dozen languages (including German: Die Evolution Der Kooperation (Munich: Oldenbourg Verlag,
1987) )



Professor Axelrod is still active, these days his focus is on agent based models. You can contact him on his website (very informative btw! also has several online articles) here: http://www-personal.umich.edu/~axe/

[CapTVK]

For those who want a proper description of TFT here's a quote from an article by Axelrod:

To appear in
Routledge Encyclopedia of International Political Economy
Forthcoming June 2001.

***-for-tat Strategies

by Robert Axelrod

A ***-for-tat strategy plays the iterated prisoners' dilemma game by cooperating on the first move, and then making the same choice as the other player did on the previous move. This strategy has been shown to be a very robust in that it does well with a wide variety of other strategies, provided that there is a sufficiently large chance that the same players will meet again. The strategy can get started with a small cluster, can spread in a population, and then can resist invasion from strategies that refuse to cooperate (Axelrod, 1984). A problem with the ***-for-tat strategy is that it is overly sensitive to
misunderstanding or misimplementation. This can be effectively corrected by adding some generosity (occasionally cooperating after the other player defects), or contrition (cooperating after being punished for an unintended defection) (Wu and Axelrod, 1995). Strategies based on reciprocity, such as ***-for-tat strategies, are widely used by nations, bats, birds and monkeys (see Axelrod and Dion, 1988). Ongoing research programs in economics, political science, computer science, evolutionary biology, and other disciplines seek to understand the long term evolution of strategies in populations under various conditions of interaction, limited rationality and adaptation.

Don't blame me for ***, blame the autocensor!

[LDiCesare]

I think that not taking distance into account from the start is an error.
Imagine you have an Earth map, civs like America, China, Rome, Greece, Babylon, India. Taking your model, what happens is the following:
Rome starts, explores a bit, meets Greece. They attack Greece because it seems fun. Doing so, they suddenly meet a Babylonian city (out of a lucky hut near Greece maybe). They exchange diplomats and realize Babs are weak. They make peace with Greece and start attacking babs? Thus they split their army, have huge lines to move them through or around Greek territory and will get munched because it is not sound to attack a small far-away city. What is worse, they may lose their bab city to the Indians because in the meanwhile and will then try to attack India which is far far far away?
As a player, against this model, just trade maps. The AI will mob against the weaker civ, eliminate it, and you can pick the nearest enemy and make war with it while all its army was sent off far away.
At least include a notion of neighbour, like don't wage war/attack cities more than X distance from your own!

[Nightmare]

Proximity counts!

I'm with Cesare, Per, proximity has to be taken into account, from the beginning.

I mean, it can be considered as an additional weigh in the calculation or a multiplicative effect of the whole, thus reducing or increasing the value of the target/offer.

An example, on earth, Rome, Greece and Babylon.

We found Greece and they became our target, we need expansion! and they are military weaker but technologically at our level.

During this war we found Babylon, they are stronger than Greece but not so technologically advanced, why don't offer them alliance against Greece (they can easily be turned against us by Greek!) in any case, it is wiser to attack Greece that is near us instead of Babylon that we can take care of after Greece...

This has to be weighted, obviously, if Babylon is far better and is a threat to both Rome and Greece, perhaps it is wiser to stop war to Greece and perhaps make an alliance with them, helping them against Babylon (the war will proceed in their country! not in our...)

All of this can be difficult to balance and take into account, but I think that "distance" as a concept, can be calculated quite easily, the though part is to trasform this concept into a weight.

These are only my thoughts...

[salkin]

Just some general thoughs on AI.

When I play a game, I don't concentrate on preventing my opponent from winning. I play to win myself. I don't care if the other players are eliminated or just fall one move short. As long as I win.

Every AI I've ever played was designed to defeat me. It does not even consider winning itself. My winning becomes a simple matter once I learn what it takes to distract the particular AI (i.e. a single Rifleman on a fortified mountain in CivII). This would never work against a human opponent.

I guess what I mean is this.
To win a game:
I war as little as possible. It wastes a lot of resources. I attack easy targets then consolidate my gains. I try to get my opponents to war against each other. When I war, I defend my borders and strike key targets, sue for peace (with a profit) and again consolidate my winnings.
To defeat an opponent:
You spend the entire game looking for ways to attack your opponent. Expending all your resources in the effort.

When programming an AI ask the question:

What would I do in this situation to win the game? Then evaluate the logical steps you took to arrive at the answer. Program that process and you have an effective AI that wants to win.

[Mithrandir]

AFAIK, TFT can generally be suboptimal in games like Freeciv. The goal of TFT is not to make you do better than anyone else, but to make both you and your opponent do well. It tries to keep the trust between two players, if wise, in order so that both can gain from the mutual trust. It does not break the trust, even where there could be great gain for itself.

In games where you compete against many players at the same time, all this does is raise everyones' scores. In freeciv, the objective is generally considered to be to get higher scores than your opponents/get to Alpha Centauri first/conquer the world, with the secondary objective generally being to get the highest score.

There are other strategies that could be better than TFT (digs out Metamagical Themas). Unfortunately, I can't think of any right now.

[Straybow]

I say it is good to use gold value to measure the worth of offers, but there needs to be a way for the civ to make one fundamental decision: is peace/alliance intended to be permanent, or are they just temporary states between wars?

[Mark_Everson]

I agree too with LDiCesare that proximity is crucial. How about this, Per? Do the money evalulation approach you were going to, but weight all the military options as something like the inverse of the distance of power centers of the civs. That includes projection of power automatically into the equation. The distance effect would reduce somewhat as history marches on.

This approach would do for avoiding simple stupid things that the civ AI did, like allowing me to extort money from the AI when I"m half the world away. One other thing you might be able to throw in is a next-nearest-neighbor effect. I generally want to ally with not a neighbor, since they could be a target, but with my neighbor's neighbor.

Hope this is of some use. BTW I voted "nice". A few shades between nice and sucks would have been useful .

Good Luck!

[Per]

Thanks for some very useful comments.

The AI is not just meant to be there to win. It is also intended to be there for fun. It might be better if it didn't do war, but only built itself up in secret until it could blast off to Alpha Centauri... but damn, that would be boring.

Anyway, calculating the distance between nations is very hard. You can do some tricks like finding the "center" (point on map with least distance to all our cities) of nations and measure the distance between such "centers", but this can be very misleading too. The actual distance is dependent on such things as the movement of your transports, the prevalence of roads and railroads, oceans, the spread of cities, or just about anything that could mean that the enemy is on your doorstep next turn.

Peace is supposed to be temporary, while an alliance will always be regarded as permanent by the AI. There will be a possibility to end the game in "allied victory".

PS I only put up the poll to see how it was done, so don't complain about the options