# Are the Diplomacy rules Turing complete?

Tags:

Last response: in Video Games

Anonymous

May 6, 2004 7:17:36 AM

Archived from groups: rec.games.diplomacy (More info?)

Jim Burgess wrote:

>

> It is depressing to JUST see messages from the spammers and about

> the spamming. Anyone have any real comments or questions??

>

> I'm looking for articles for the next issue of Diplomacy World,

> just one more month to write them!! Contact me for editorial

> guidance or details.

I won't have the free time to spit and polish any formal essay for a Dip

publication in the next month, but I have been mulling over one highly

theoretical topic for the past few weeks. Perhaps others have discussed

this in other publications; I don't know. (If someone has seen detailed

discussions like this before, I'd be interested in a link or something.

The closest thing I've found is a brief mention of Godel's Theorem

applied to Diplomacy in a thread back in 2001.)

As you may be aware from my recent posts, I have found far too much

personal amusement in the various rule problems of this otherwise very

high-quality game. The rule paradoxes trouble me especially. One day I

got in an e-mail argument with a friend who believes that there really

are no paradoxes in the rules, merely ambiguities. His arguments seemed

spurious to me, though, and I tried to devise how I might prove to him

logically that there really are paradoxes in the rules.

It occurred to me that when you feed a paradoxical situation to a judge

program, it will loop infinitely, never rendering any resolution of the

given orders; whereas with orders that illustrate ambiguities, the judge

program will eventually produce an outcome according to programmer bias.

And then, my mind took a turn for the worse. I began to think of an

adjudicator as a logical reasoning engine, which I suppose is really

what it is, and played several thought experiments.

First, what would happen if the rule paradoxes were fixed? I suppose

that there would be no set of orders that would cause an adjudicator to

loop infinitely. Secondly, why exactly does an adjudicator loop like

that? Because of unresolved circular dependencies, such as "if A then

B; if B then A; if not A then not B; if not B then not A". And then, a

thought experiment I found truly fascinating: what other kinds of

logical problems could be represented as Diplomacy orders on a

particular map with particular units in particular places, and solved

using a judge program?

To get directly to the point, I wonder whether it is possible to encode

any Turing machine, including state diagram and initial "tape" (memory)

contents, as a single Diplomacy map, position, and set of orders;

resolve the orders; and then interpret the resultant position as the

final "tape" contents of the Turing machine. In other words, is the

Diplomacy order resolution process Turing-complete?

This question is quite relevant to the issue of paradoxes, and even

useful. If it were proven that the Diplomacy rules are Turing-complete,

then it must necessarily be true that the rules contain paradoxes, since

Turing machines can loop infinitely. And more importantly, fixing the

Diplomacy rules would render them non-Turing-complete! (Of course, even

if the rules are shown not to be Turing-complete, there still can be

paradoxes.)

I would like to present this problem as a challenge for the Computer

Science variety of Diplomacy players out there. To satisfy the

challenge, some kind of proof by contradiction could be offered that

shows the Diplomacy rules are not Turing-complete, or some algorithm

could be offered for translating the encoding of a Turing machine into a

complete Diplomacy order resolution problem, and for translating the

result back into the final tape contents.

In coming up with an encoding, it should be allowable to have a map of

arbitrary but finite size and structure (not even necessarily a planar

graph, but yet conforming to the rules of land/water adjacencies), and

an arbitrary but finite number of Powers and units (up to the number of

supply centers, of course), with each unit having an arbitrary but legal

location and an arbitrary but valid order.

Also, since all the paradoxes I've ever seen involve the convoy order in

conflict with either the beleaguered garrison rule or, more recently,

the rule that dislodged units do not affect provinces their attackers

come from, it seems natural that these situations would be important for

representing most kinds of iterative/recursive logical operations.

Perhaps it would be helpful to correlate Diplomacy orders resolution to

a known Turing-complete inference engine like Prolog. If any set of

Prolog "rules" can be expressed as a set of Diplomacy orders with map

and units, then Diplomacy is Turing complete.

Or perhaps a highly theoretical language like Unlambda

(http://www.eleves.ens.fr:8080/home/madore/programs/unla...) would

actually lend itself to this problem. Unlambda is Turing complete with

only 2 primitive functions and 1 operator, though it includes more

primitives for the pretense of convenience.

It may also be that Diplomacy orders resolution could be more easily

proven equivalent to logic circuits. One can build a Turing complete

system entirely out of 2-input NAND gates and a clock; if some corollary

to the NAND operation can be found within the Diplomacy rules, problem

solved.

Anybody else ever given this question some thought?

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Jim Burgess wrote:

>

> It is depressing to JUST see messages from the spammers and about

> the spamming. Anyone have any real comments or questions??

>

> I'm looking for articles for the next issue of Diplomacy World,

> just one more month to write them!! Contact me for editorial

> guidance or details.

I won't have the free time to spit and polish any formal essay for a Dip

publication in the next month, but I have been mulling over one highly

theoretical topic for the past few weeks. Perhaps others have discussed

this in other publications; I don't know. (If someone has seen detailed

discussions like this before, I'd be interested in a link or something.

The closest thing I've found is a brief mention of Godel's Theorem

applied to Diplomacy in a thread back in 2001.)

As you may be aware from my recent posts, I have found far too much

personal amusement in the various rule problems of this otherwise very

high-quality game. The rule paradoxes trouble me especially. One day I

got in an e-mail argument with a friend who believes that there really

are no paradoxes in the rules, merely ambiguities. His arguments seemed

spurious to me, though, and I tried to devise how I might prove to him

logically that there really are paradoxes in the rules.

It occurred to me that when you feed a paradoxical situation to a judge

program, it will loop infinitely, never rendering any resolution of the

given orders; whereas with orders that illustrate ambiguities, the judge

program will eventually produce an outcome according to programmer bias.

And then, my mind took a turn for the worse. I began to think of an

adjudicator as a logical reasoning engine, which I suppose is really

what it is, and played several thought experiments.

First, what would happen if the rule paradoxes were fixed? I suppose

that there would be no set of orders that would cause an adjudicator to

loop infinitely. Secondly, why exactly does an adjudicator loop like

that? Because of unresolved circular dependencies, such as "if A then

B; if B then A; if not A then not B; if not B then not A". And then, a

thought experiment I found truly fascinating: what other kinds of

logical problems could be represented as Diplomacy orders on a

particular map with particular units in particular places, and solved

using a judge program?

To get directly to the point, I wonder whether it is possible to encode

any Turing machine, including state diagram and initial "tape" (memory)

contents, as a single Diplomacy map, position, and set of orders;

resolve the orders; and then interpret the resultant position as the

final "tape" contents of the Turing machine. In other words, is the

Diplomacy order resolution process Turing-complete?

This question is quite relevant to the issue of paradoxes, and even

useful. If it were proven that the Diplomacy rules are Turing-complete,

then it must necessarily be true that the rules contain paradoxes, since

Turing machines can loop infinitely. And more importantly, fixing the

Diplomacy rules would render them non-Turing-complete! (Of course, even

if the rules are shown not to be Turing-complete, there still can be

paradoxes.)

I would like to present this problem as a challenge for the Computer

Science variety of Diplomacy players out there. To satisfy the

challenge, some kind of proof by contradiction could be offered that

shows the Diplomacy rules are not Turing-complete, or some algorithm

could be offered for translating the encoding of a Turing machine into a

complete Diplomacy order resolution problem, and for translating the

result back into the final tape contents.

In coming up with an encoding, it should be allowable to have a map of

arbitrary but finite size and structure (not even necessarily a planar

graph, but yet conforming to the rules of land/water adjacencies), and

an arbitrary but finite number of Powers and units (up to the number of

supply centers, of course), with each unit having an arbitrary but legal

location and an arbitrary but valid order.

Also, since all the paradoxes I've ever seen involve the convoy order in

conflict with either the beleaguered garrison rule or, more recently,

the rule that dislodged units do not affect provinces their attackers

come from, it seems natural that these situations would be important for

representing most kinds of iterative/recursive logical operations.

Perhaps it would be helpful to correlate Diplomacy orders resolution to

a known Turing-complete inference engine like Prolog. If any set of

Prolog "rules" can be expressed as a set of Diplomacy orders with map

and units, then Diplomacy is Turing complete.

Or perhaps a highly theoretical language like Unlambda

(http://www.eleves.ens.fr:8080/home/madore/programs/unla...) would

actually lend itself to this problem. Unlambda is Turing complete with

only 2 primitive functions and 1 operator, though it includes more

primitives for the pretense of convenience.

It may also be that Diplomacy orders resolution could be more easily

proven equivalent to logic circuits. One can build a Turing complete

system entirely out of 2-input NAND gates and a clock; if some corollary

to the NAND operation can be found within the Diplomacy rules, problem

solved.

Anybody else ever given this question some thought?

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

More about : diplomacy rules turing complete

Anonymous

May 7, 2004 2:01:19 AM

High Will,

I have to disappoint you, but the rules do not have much to do

with Turing or Godel.

The Turing Machine has an infinite memory, while the adjudication

of a finite map, can be calculated by a machine in linear memory

and in linear execution (in relation to the number of orders).

It isn't even NPC.

The mistake that people make is that they try to understand the

rules as an algorithm. With this you will end in something as

the DPTG (which contains still 3 bugs).

However, you should look to the rules as a set of equations.

Each move order and support order, is a variable with two

possible values. For the move order that is 'moves' or 'fails'

and for the support order that is 'cut' or 'given'. The principle

of equations is very close to the rules. The rules do not

define things in the form of an algorithm.

For each order, if you know the value of the surrounding orders,

you know the result of that order. So, for each order you can

write an equation.

Make for each order a equation. Take all those equations and find

a solution that fullfills these equations. Then you have your

adjudication.

A Diplomacy paradox, is a set of equations, where there is no

solution or more than one solutions.

You can deal with paradoxes in two ways. Adapt the rules for the

equations, such that there is always one solution for a set

(the 1982 rulebook approach). Or, do a paradox detection, and

introduce a special paradox rule. Examples of such rules are

the Szykman rule or the All Hold rule.

The new adjudicators, JDip, DipTool and Palmpolitik do paradox

detection and use the Szykman rule.

To make things easier, you can introduce 'derived decisions'.

Those are:

- HOLD STRENGTH (value equal or greater than 0)

- ATTACK STRENGTH (value equal or greater than 0)

- DEFEND STRENGTH (value equal or greater than 0)

- PREVENT STRENGTH (value equal or greater than 0)

- DISLODGED (yes/no)

- PATH (yes/no)

For each of these derived decisions you can give precise semantics

but also precisely how it depends on other decisions.

Note, that most people make no different between DEFEND STRENGTH

and PREVENT STRENGTH. The DEFEND STRENGTH is the strength of

a moving unit to defend in a head to head battle. While the

PREVENT STRENGTH is the strength to prevent another unit to

enter the same area as the moving unit. Those two strengths

are slightly different.

This is done in my DATC chapter 5:

http://web.inter.nl.net/users/L.B.Kruijswijk/#5

Although, the description of the decisions are a little bit mixed

with the algorithm (this will be corrected in the next version).

DipTool of Christian Hagenah, uses a different algorithm in finding

a solution of the equations.

> It occurred to me that when you feed a paradoxical situation to a judge

> program, it will loop infinitely, never rendering any resolution of the

> given orders;

RealPolitik uses the 1982 rule. JDip, DipTool and Palmpolitik, have

paradox detection and use the Szykman rule.

> And then, my mind took a turn for the worse. I began to think of an

> adjudicator as a logical reasoning engine, which I suppose is really

> what it is, and played several thought experiments.

You can see it like this. But it is closer to proposition logic

(first order logic, because the orders have binary result) and

not predicate logic (second order logic).

Regards,

Lucas

Anonymous

May 7, 2004 2:06:14 AM

> It may also be that Diplomacy orders resolution could be more easily

> proven equivalent to logic circuits. One can build a Turing complete

> system entirely out of 2-input NAND gates and a clock; if some corollary

> to the NAND operation can be found within the Diplomacy rules, problem

> solved.

>

> Anybody else ever given this question some thought?

I certainly haven't.

But if I did .... I think I might need one of your Second Brains to try and

comprehend the concepts involved.

> --

> Will Berry

> Co-founder, Second Brain website hosting

> http://www.secondbrainhosting.com/

Alastair

(now removing tongue from cheek).

PS One day soon I'll post something sensible to r.g.d. But I guess it'll

have to wait until after exam time ...

PPS Actually I just about managed to almost understand Lucas's response, so

maybe my First Brain isn't quite as addled as I thought.

Anonymous

May 7, 2004 8:19:26 AM

Lucas B. Kruijswijk wrote:

>

> It isn't even NPC.

I should hope not! We'd *never* get done playing!

> However, you should look to the rules as a set of equations.

> Each move order and support order, is a variable with two

> possible values. For the move order that is 'moves' or 'fails'

> and for the support order that is 'cut' or 'given'. The principle

> of equations is very close to the rules. The rules do not

> define things in the form of an algorithm.

Agreed, the rules themselves are not an algorithm. But they are

requirements for an algorithm, i.e. they describe the required output

(final state) for any given input (map, unit positions, orders). The

ambiguities in the rules of course mean that there is more than one

correct output for certain inputs; and the paradoxes mean that no output

is correct for certain inputs (i.e. those inputs cause the algorithm not

to provide output).

In this way I think it is meaningful to say "are the rules Turing

complete". But I suppose I should rephrase the problem statement as: Is

it true that *any* Diplomacy adjudicator algorithm that fully conforms

to the rules (not just adjudicators that follow some particular design)

is Turing complete?

> The Turing Machine has an infinite memory, while the adjudication

> of a finite map, can be calculated by a machine in linear memory

> and in linear execution (in relation to the number of orders).

I agree with this as well, with two caveats. First, "infinite memory"

need only mean "as much memory as you'll ever use + 1". After all, our

desktops and laptops are Turing complete, but their memories are quite

finite; consider also emulators and the Recursion Theorem. And besides,

if a Turing machine actually uses infinite memory, then it clearly loops

infinitely and never terminates. Secondly, who says the number of

provinces and adjacencies on a Diplomacy map, or even the number of

units on the board, has to be finite? It seems to me that a map/graph

that extends predictably forever, with units that occur infinitely in

expressible patterns, will still be compatible with the rules. The same

decisions can just be repeated for all units according to the patterns

given.

I am operating under the assumption that if any Diplomacy adjudicator is

Turing complete, any implementation of a Universal Turing Machine using

a Diplomacy adjudicator would construct a map having enough nodes

("provinces") and adjacencies as it needs to, in whatever arrangement

fits the problem, and populate it with as many units of whatever type as

it sees fit as well, and then issue orders to those units before

"calling" the adjudicator.

In other words, the initial tape contents and state diagram of the

Turing machine must be encoded as (map, unit positions, orders). The

initial tape contents, by the way, may be infinite if specified as a

deterministic pattern (i.e. "001" repeating forever) without breaking

the definition of a Turing machine; though there must always be a finite

number of states.

> You can deal with paradoxes in two ways. Adapt the rules for the

> equations, such that there is always one solution for a set

> (the 1982 rulebook approach). Or, do a paradox detection, and

> introduce a special paradox rule. Examples of such rules are

> the Szykman rule or the All Hold rule.

>

> The new adjudicators, JDip, DipTool and Palmpolitik do paradox

> detection and use the Szykman rule.

>

> ...

>

>>It occurred to me that when you feed a paradoxical situation to a judge

>>program, it will loop infinitely, never rendering any resolution of the

>>given orders;

>

> RealPolitik uses the 1982 rule. JDip, DipTool and Palmpolitik, have

> paradox detection and use the Szykman rule.

It seems to me that paradox detection is eerily like infinite loop

detection. The only way I can think of to implement paradox detection

is like this: Let U be the number of units on the map. If at any time

the adjudicator processes more than U dependencies without actually

deciding anything, then it is looping infinitely and it's time to apply

either the Szykman rule or the "three or more can trade places" rule,

however you can decide what the "culprits" are. Or something like that.

Another reasonable loop detection threshold would be the number of

provinces on the map times the number of adjacencies between provinces;

but the number of units is always smaller, and each unit can have only

one order, so U works better.

But what if the map extends infinitely in a deterministic pattern, and

has an infinite number of units placed in a deterministic pattern given

orders according to a deterministic pattern? Then the Szykman rule

(when implemented as above) breaks due to a count-to-infinity problem.

For example:

Map: An infinite set of supply center provinces P for all i >= 0,

with each P being adjacent by land to P[i+1] and vice versa

Units:

England: An army at P[2i] for all i >= 0

France: An army at P[2i+1] for all i >= 0

Orders:

England: A P[2i] -> P[2i+1] for each army P[2i]

France: A P[2i+1] hold for each army P[2i+1]

The final state of this map can be determined in a finite number of

steps with the proper reasoning; and I hold that this example is within

the rules of the game (neglecting, of course, departure from the

standard map and order writing conventions), even though I doubt any

judge program out there would accept it. (Victory conditions would be

that a player controlled more than half the supply centers; since the

number of supply centers is countable this is not a problem.)

However, when you allow the map and the number of units to become

deterministically infinite, you can detect paradox about as reliably as

you can detect an infinite loop in a Turing machine -- that is, never

perfectly. At least, this seems true to me, and if it can be shown that

any proper adjudicator is Turing complete, as I suspect, then I will

know that the Szykman rule and all other in-case-of-paradox rules are

broken in the general case (even though they may work perfectly on

finite, "normal" maps) by way of the Halting Problem.

On a personal note: if it seems like I'm abusing any of you, it's only

in the way that a chess player seeks out games versus more experienced

players than himself. That, and as one of my friends says, sometimes I

just have to find my inner troll and stroke it.

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 7, 2004 6:56:37 PM

"Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk> wrote in message

> PPS Actually I just about managed to almost understand Lucas's response,

so

> maybe my First Brain isn't quite as addled as I thought.

That's better than me. What the hell are they talking about?

What are the paradoxes in the rules anyway? I've never seen the infamous

convoy paradox come up in 10 years of playing Diplomacy.

Grant

Anonymous

May 7, 2004 7:06:26 PM

Grant Flowers wrote:

>

> What are the paradoxes in the rules anyway? I've never seen the infamous

> convoy paradox come up in 10 years of playing Diplomacy.

RUN! Run while you still have your precious little soul!

http://www.diplomacy-archive.com/diplomacy_rules.htm#Ru...

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 7, 2004 10:41:21 PM

"Will Berry" wrote:

> Agreed, the rules themselves are not an algorithm. But they are

> requirements for an algorithm, i.e. they describe the required output

> (final state) for any given input (map, unit positions, orders). The

> ambiguities in the rules of course mean that there is more than one

> correct output for certain inputs; and the paradoxes mean that no output

> is correct for certain inputs (i.e. those inputs cause the algorithm not

> to provide output).

This is true, but the point I wanted to make is that you have to transform

the rules in a more formal description as first step.

This formal description can be an algorithm or a more mathematical description.

What you see with the DPTG is that the distance between the English rules

and the DPTG is very large.

Large gap

English rules ------------------------ DPTG

In this way it is very hard to proof that the DPTG is correct. And indeed,

it is not correct, it contains 3 bugs.

What I promote is the following:

small

gap

English rules ---- Mathematical description

/ | \

Alg1 Alg2 Alg3

So, I am looking to a mathematical description that is very close to the

original English rules. So, that everyone agrees with this description.

From this mathematical description you can derive one or more algorithms.

But, since you are thinking in a more formal way, there is less risk on

bugs (and no dispute on how it should be interpreted).

I think I managed to do so in my DATC, although the description and the

algorithm is still intervened (will be corrected in next update).

However, if someone finds a better formal way that is closer to the

original rules, I am certainly interested.

One thing is clear, in this mathematical description you should not add

any sequence on how orders are adjudicated. This is not according to the

rules (so, your distance to the rules becomes larger) and the

correctness of your description starts to depend on this sequence.

Since, the sequence in how orders are adjudicated is very complex,

you run into trouble.

If you have this mathematical description (without sequence), you will

see that the best way is to let the computer determine the (very complex)

sequence at runtime (instead of hard coding) is the better approach.

Palmpolitik, JDip and DipTool are programmed this way. Although DipTool

has a different approach then Palmpolitik or JDip.

About infinity maps. In that moment you don't have computational Turing

problem anymore. A Turing machine has a infinite tape, but with a finite

part of the tape with initial values.

With an infinite map, you get at least one additional paradox. You can

create an order and unit chain to infinity. Such chain could be

adjudicated correctly in two ways.

Regards,

Lucas

Anonymous

May 7, 2004 10:41:22 PM

Lucas B. Kruijswijk wrote:

>

> About infinity maps. In that moment you don't have computational Turing

> problem anymore. A Turing machine has a infinite tape, but with a finite

> part of the tape with initial values.

I believe IBM OS/390 initializes all new memory to 0xDEADBEEF before

giving it to the program, to aid debugging in case of a crash. This is

basically equivalent to an infinite tape with an infinitely repeating

pattern of initial values.

> With an infinite map, you get at least one additional paradox. You can

> create an order and unit chain to infinity. Such chain could be

> adjudicated correctly in two ways.

I had never thought of that, but I can see how it could happen. But I'm

having trouble coming up with an example.

England:

Army P[2i] -> P[2i+1], i >= 0

France:

Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0

Army P[4i+3] -> P[4i+2], i >= 0

With these orders, all French moves fail because all supports are cut.

You can prove this inductively.

England:

Army P[2i] -> P[2i-1], i >= 1

France:

Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0

Army P[4i+3] -> P[4i+2], i >= 0

Here every other English unit is dislodged. This can likewise be proven

inductively.

England:

Army P[4i] support Army P[4i+2] -> P[4i+1], i >= 0

Army P[4i+2] -> P[4i+1], i >= 0

France:

Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0

Army P[4i+3] -> P[4i+2], i >= 0

Here France loses half its units.

England:

Army P[4i+2] support Army P[4i] -> P[4i+1], i >= 0

Army P[4i] -> P[4i+1], i >= 0

France:

Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0

Army P[4i+3] -> P[4i+2], i >= 0

Here all units standoff.

I can't think of a scenario where there are two equally valid outcomes,

but it seems possible. Such a situation might be useful in contructing

a TM emulator for Diplomacy. Iteration might be simulated as a chain of

similar attacks, that may or may not succeed, on units that affect other

parts of the action.

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 8, 2004 2:44:01 AM

"Grant Flowers" <darthvader@SPAMworldnet.att.net> wrote in message

news:FsNmc.29045$Ut1.834860@bgtnsc05-news.ops.worldnet.att.net...

>

> "Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk> wrote in

message

> > PPS Actually I just about managed to almost understand Lucas's response,

> so

> > maybe my First Brain isn't quite as addled as I thought.

> That's better than me. What the hell are they talking about?

It's OK. The subsequent conversation has totally lost me. Normal service is

resumed.

> What are the paradoxes in the rules anyway? I've never seen the infamous

> convoy paradox come up in 10 years of playing Diplomacy.

And I agree with Will. Run like the wind away from that particular thread of

discussion ....

Alastair

Anonymous

May 8, 2004 2:44:02 AM

Alastair Tomlinson wrote:

> "Grant Flowers" <darthvader@SPAMworldnet.att.net> wrote in message

> news:FsNmc.29045$Ut1.834860@bgtnsc05-news.ops.worldnet.att.net...

>

>>That's better than me. What the hell are they talking about?

>

> It's OK. The subsequent conversation has totally lost me. Normal service is

> resumed.

For the masochistic, here is a good definition of the Turing machine and

an applet that simulates one:

http://en.wikipedia.org/wiki/Turing_machine

http://www.igs.net/~tril/tm/

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 8, 2004 9:34:24 PM

"Will Berry" wrote:

> I can't think of a scenario where there are two equally valid outcomes,

> but it seems possible.

What about:

Army p -> p[i+1] for i >= 0

?

It is not a circular movement, but a movement into infinity.

It can all fail or all succeed.

The nice thing about these moves is, that if p[0] has supply center,

then you may build. However, you will still keep the same number of

armies :-))

Regards,

Lucas

Anonymous

May 9, 2004 6:23:13 AM

Lucas B. Kruijswijk wrote:

>

> Army p -> p[i+1] for i >= 0

>

> It is not a circular movement, but a movement into infinity.

>

> It can all fail or all succeed.

One could argue that this should have the same result as a circular

movement (i.e. all moves succeed), since it is necessary in both cases

to detect a loop in order to actually reach any decision. I prefer that

all moves succeed, but I wouldn't insist that the official rules are

sufficiently precise to justify such an opinion.

> The nice thing about these moves is, that if p[0] has supply center,

> then you may build. However, you will still keep the same number of

> armies :-))

However, it could give you the win when ordering all to hold would not,

depending on how you account for an infinite number of SCs. I would

personally prefer to say that <inf> + 1 = <inf> for the purpose of

counting centers, but 2 * <inf> would in fact be greater than <inf>.

This way, if a power were able to double his centers, that could give

him the win; but merely increasing his centers by a constant number

would not affect anything for that purpose.

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 9, 2004 6:28:33 AM

Lucas B. Kruijswijk wrote:

>

> This is true, but the point I wanted to make is that you have to transform

> the rules in a more formal description as first step.

I'm seeing your point here now. Since there are several logically

different ways of interpreting the English rules into an algorithm, only

some of those valid ways might be Turing complete. This actually

increases the usefulness of the problem, because it tells us which

interpretations of the rules definitely have paradoxes and which ones

may or may not.

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 10, 2004 6:49:01 AM

"Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk>

> > What are the paradoxes in the rules anyway? I've never seen the

infamous

> > convoy paradox come up in 10 years of playing Diplomacy.

>

> And I agree with Will. Run like the wind away from that particular thread

of

> discussion ....

Well, like the big Dipper I am, I'm not being totally honest. I kind of

know what the paradox is, but I can't believe the amount of bandwidth it has

devoured during the 10 years or so I've been reading RGD.

A few weeks ago I tried to launch a thread in which people might talk about

some of the comic anecdotes they've experienced in FTF games, but met with

little response. Why is it that the convoy paradox gets so much attention

from RGD posters but the play of the game itself achieves so little? If I

were a newbie coming across this newsgroup I'd think it was the most boring

game ever created.

Anyway, back to lurking...

Grant

Anonymous

May 10, 2004 5:12:49 PM

"Grant Flowers" <darthvader@SPAMworldnet.att.net> writes:

Hi Grant, I've always enjoyed both parts of this sort of

conversation, since I'm well trained in mathematical logic

techniques, Turing machines, Kurt Godel and the MISuses of

the Incompleteness Theorem, and non-cooperative game theory,

BUT I view the more fun way to deal with and play the game

is better informed by psychology and Zen philosophy. This

makes the Game of Diplomacy THE game, in my eyes, since it

really does "have it all". What you are supposed to do

(IMHO, wink, wink...) is to salute those of us who battle

down the mathematical logic highways and byways, even if

you don't want to follow along, since you plan to saw off

their branch and stab the hell out of them once they get

far enough off the edge...... but now to the question...

>"Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk>

>> > What are the paradoxes in the rules anyway? I've never seen the

>infamous

>> > convoy paradox come up in 10 years of playing Diplomacy.

>>

>> And I agree with Will. Run like the wind away from that particular thread

>of

>> discussion ....

>Well, like the big Dipper I am, I'm not being totally honest. I kind of

>know what the paradox is, but I can't believe the amount of bandwidth it has

>devoured during the 10 years or so I've been reading RGD.

The reason, quite simply is that there are the people that like these

aspects of trying to solve the game. The same people who like to

debate paradox completeness tend to like to study stalemate lines.

The neat thing about Diplomacy IS that it can attract that type of

debate while being a completely unsolvable game (i.e. it never will

be anywhere close to tic-tac-toe or even chess in its solvability).

That's why it absorbs bandwidth....

>A few weeks ago I tried to launch a thread in which people might talk about

>some of the comic anecdotes they've experienced in FTF games, but met with

>little response. Why is it that the convoy paradox gets so much attention

>from RGD posters but the play of the game itself achieves so little? If I

>were a newbie coming across this newsgroup I'd think it was the most boring

>game ever created.

Ideally, we would see both. I've told my BEST comic anecdotes here

before, but I'll tell two of them again. FTF is the BEST place for

really funny stuff and you HAVE to get the personalities involved

to really understand it, thus you only will "get" the second one

in all likelihood.

The first one happened at a PudgeCon in 1983, over 20 years ago

now. "Pudge" is Bob Olsen, who was a famous player of his time,

who lived in Wichita at the time and hosted large numbers of

players at his house for weekends of gaming. I was in a game

with the late Kathy Byrne Caruso and Eric Ozog (who still plays

FTF in the Pacific Northwest sometimes). I can't really remember

the details of the game, since they don't really matter. But

I had been elected 1982 Toady of the Year and Kathy was the Queen

Toad of the time, so I "should" have been doing her bidding.

I was playing Russia and stabbed her Germany. Of course, Kathy

came right back and worked up an alliance that CRUSHED me.

I forget what country Eric was playing, but at one point,

some really funny moves were played, as I desperately tried

to survive (Kathy, in her Queens accent you have to remember

was continually telling EVERYONE in earshot what a dirty rotten

toady I really was in a VERY loud voice), Eric did something

that kind of helped me, not very much, but a little bit.

And the two of us went out on the front step and fell down

laughing and almost missed the next turn..... ;-)

It was completely hilarious and totally stupid all at the same

time. And it had nothing to do with being Turing Complete.

The other one was at a Diplomatic Incident in Boston, where

I was playing with, among others, Dan Shoham. I pulled off

this massive stab of Dan (who really at heart WAS just a Carebear

who liked to win) that devastated his position and Dan was

just SO shocked. How could I lie to him like that? I got

an award at that Incident for that stab, that was about 10

years ago.... I had completely set him up (think non-cooperative

game theory to the next level....) and again I could hardly

keep playing I was giggling so hard. Dan's JDPR remains

eons ahead of where mine will never be..... ;-)

>Anyway, back to lurking...

>Grant

Yes, Grant, REAL r.g.d will have all of that....

Jim-Bob

Anonymous

May 14, 2004 12:54:47 AM

Would there be an issue if the Turing program always completed, but gave

different answers depending on the order in which it was given the

orders?

On Thu, 6 May 2004, Will Berry wrote:

> Jim Burgess wrote:

> >

> > It is depressing to JUST see messages from the spammers and about

> > the spamming. Anyone have any real comments or questions??

> >

> > I'm looking for articles for the next issue of Diplomacy World,

> > just one more month to write them!! Contact me for editorial

> > guidance or details.

>

> I won't have the free time to spit and polish any formal essay for a Dip

> publication in the next month, but I have been mulling over one highly

> theoretical topic for the past few weeks. Perhaps others have discussed

> this in other publications; I don't know. (If someone has seen detailed

> discussions like this before, I'd be interested in a link or something.

> The closest thing I've found is a brief mention of Godel's Theorem

> applied to Diplomacy in a thread back in 2001.)

>

> As you may be aware from my recent posts, I have found far too much

> personal amusement in the various rule problems of this otherwise very

> high-quality game. The rule paradoxes trouble me especially. One day I

> got in an e-mail argument with a friend who believes that there really

> are no paradoxes in the rules, merely ambiguities. His arguments seemed

> spurious to me, though, and I tried to devise how I might prove to him

> logically that there really are paradoxes in the rules.

>

> It occurred to me that when you feed a paradoxical situation to a judge

> program, it will loop infinitely, never rendering any resolution of the

> given orders; whereas with orders that illustrate ambiguities, the judge

> program will eventually produce an outcome according to programmer bias.

> And then, my mind took a turn for the worse. I began to think of an

> adjudicator as a logical reasoning engine, which I suppose is really

> what it is, and played several thought experiments.

>

> First, what would happen if the rule paradoxes were fixed? I suppose

> that there would be no set of orders that would cause an adjudicator to

> loop infinitely. Secondly, why exactly does an adjudicator loop like

> that? Because of unresolved circular dependencies, such as "if A then

> B; if B then A; if not A then not B; if not B then not A". And then, a

> thought experiment I found truly fascinating: what other kinds of

> logical problems could be represented as Diplomacy orders on a

> particular map with particular units in particular places, and solved

> using a judge program?

>

> To get directly to the point, I wonder whether it is possible to encode

> any Turing machine, including state diagram and initial "tape" (memory)

> contents, as a single Diplomacy map, position, and set of orders;

> resolve the orders; and then interpret the resultant position as the

> final "tape" contents of the Turing machine. In other words, is the

> Diplomacy order resolution process Turing-complete?

>

> This question is quite relevant to the issue of paradoxes, and even

> useful. If it were proven that the Diplomacy rules are Turing-complete,

> then it must necessarily be true that the rules contain paradoxes, since

> Turing machines can loop infinitely. And more importantly, fixing the

> Diplomacy rules would render them non-Turing-complete! (Of course, even

> if the rules are shown not to be Turing-complete, there still can be

> paradoxes.)

>

> I would like to present this problem as a challenge for the Computer

> Science variety of Diplomacy players out there. To satisfy the

> challenge, some kind of proof by contradiction could be offered that

> shows the Diplomacy rules are not Turing-complete, or some algorithm

> could be offered for translating the encoding of a Turing machine into a

> complete Diplomacy order resolution problem, and for translating the

> result back into the final tape contents.

>

> In coming up with an encoding, it should be allowable to have a map of

> arbitrary but finite size and structure (not even necessarily a planar

> graph, but yet conforming to the rules of land/water adjacencies), and

> an arbitrary but finite number of Powers and units (up to the number of

> supply centers, of course), with each unit having an arbitrary but legal

> location and an arbitrary but valid order.

>

> Also, since all the paradoxes I've ever seen involve the convoy order in

> conflict with either the beleaguered garrison rule or, more recently,

> the rule that dislodged units do not affect provinces their attackers

> come from, it seems natural that these situations would be important for

> representing most kinds of iterative/recursive logical operations.

>

> Perhaps it would be helpful to correlate Diplomacy orders resolution to

> a known Turing-complete inference engine like Prolog. If any set of

> Prolog "rules" can be expressed as a set of Diplomacy orders with map

> and units, then Diplomacy is Turing complete.

>

> Or perhaps a highly theoretical language like Unlambda

> (http://www.eleves.ens.fr:8080/home/madore/programs/unla...) would

> actually lend itself to this problem. Unlambda is Turing complete with

> only 2 primitive functions and 1 operator, though it includes more

> primitives for the pretense of convenience.

>

> It may also be that Diplomacy orders resolution could be more easily

> proven equivalent to logic circuits. One can build a Turing complete

> system entirely out of 2-input NAND gates and a clock; if some corollary

> to the NAND operation can be found within the Diplomacy rules, problem

> solved.

>

> Anybody else ever given this question some thought?

>

> --

> Will Berry

> Co-founder, Second Brain website hosting

> http://www.secondbrainhosting.com/

>

Anonymous

May 14, 2004 4:29:27 AM

George D. Phillies wrote:

> Would there be an issue if the Turing program always completed, but gave

> different answers depending on the order in which it was given the

> orders?

I suppose that would mean that the method of encoding the machine as

(map, state, orders), or of decoding the result into the final tape

contents, was flawed.

--

Will Berry

Co-founder, Second Brain website hosting

http://www.secondbrainhosting.com/

Anonymous

May 14, 2004 8:41:32 PM

"George D. Phillies" <phillies@WPI.EDU> writes:

That would be very bad... it's difficult to get computers

to consider things simultaneously, but the simultaneous

movement characteristic is critical.

Jim-Bob

>Would there be an issue if the Turing program always completed, but gave

>different answers depending on the order in which it was given the

>orders?

>On Thu, 6 May 2004, Will Berry wrote:

>> Jim Burgess wrote:

>> >

>> > It is depressing to JUST see messages from the spammers and about

>> > the spamming. Anyone have any real comments or questions??

>> >

>> > I'm looking for articles for the next issue of Diplomacy World,

>> > just one more month to write them!! Contact me for editorial

>> > guidance or details.

>>

>> I won't have the free time to spit and polish any formal essay for a Dip

>> publication in the next month, but I have been mulling over one highly

>> theoretical topic for the past few weeks. Perhaps others have discussed

>> this in other publications; I don't know. (If someone has seen detailed

>> discussions like this before, I'd be interested in a link or something.

>> The closest thing I've found is a brief mention of Godel's Theorem

>> applied to Diplomacy in a thread back in 2001.)

>>

>> As you may be aware from my recent posts, I have found far too much

>> personal amusement in the various rule problems of this otherwise very

>> high-quality game. The rule paradoxes trouble me especially. One day I

>> got in an e-mail argument with a friend who believes that there really

>> are no paradoxes in the rules, merely ambiguities. His arguments seemed

>> spurious to me, though, and I tried to devise how I might prove to him

>> logically that there really are paradoxes in the rules.

>>

>> It occurred to me that when you feed a paradoxical situation to a judge

>> program, it will loop infinitely, never rendering any resolution of the

>> given orders; whereas with orders that illustrate ambiguities, the judge

>> program will eventually produce an outcome according to programmer bias.

>> And then, my mind took a turn for the worse. I began to think of an

>> adjudicator as a logical reasoning engine, which I suppose is really

>> what it is, and played several thought experiments.

>>

>> First, what would happen if the rule paradoxes were fixed? I suppose

>> that there would be no set of orders that would cause an adjudicator to

>> loop infinitely. Secondly, why exactly does an adjudicator loop like

>> that? Because of unresolved circular dependencies, such as "if A then

>> B; if B then A; if not A then not B; if not B then not A". And then, a

>> thought experiment I found truly fascinating: what other kinds of

>> logical problems could be represented as Diplomacy orders on a

>> particular map with particular units in particular places, and solved

>> using a judge program?

>>

>> To get directly to the point, I wonder whether it is possible to encode

>> any Turing machine, including state diagram and initial "tape" (memory)

>> contents, as a single Diplomacy map, position, and set of orders;

>> resolve the orders; and then interpret the resultant position as the

>> final "tape" contents of the Turing machine. In other words, is the

>> Diplomacy order resolution process Turing-complete?

>>

>> This question is quite relevant to the issue of paradoxes, and even

>> useful. If it were proven that the Diplomacy rules are Turing-complete,

>> then it must necessarily be true that the rules contain paradoxes, since

>> Turing machines can loop infinitely. And more importantly, fixing the

>> Diplomacy rules would render them non-Turing-complete! (Of course, even

>> if the rules are shown not to be Turing-complete, there still can be

>> paradoxes.)

>>

>> I would like to present this problem as a challenge for the Computer

>> Science variety of Diplomacy players out there. To satisfy the

>> challenge, some kind of proof by contradiction could be offered that

>> shows the Diplomacy rules are not Turing-complete, or some algorithm

>> could be offered for translating the encoding of a Turing machine into a

>> complete Diplomacy order resolution problem, and for translating the

>> result back into the final tape contents.

>>

>> In coming up with an encoding, it should be allowable to have a map of

>> arbitrary but finite size and structure (not even necessarily a planar

>> graph, but yet conforming to the rules of land/water adjacencies), and

>> an arbitrary but finite number of Powers and units (up to the number of

>> supply centers, of course), with each unit having an arbitrary but legal

>> location and an arbitrary but valid order.

>>

>> Also, since all the paradoxes I've ever seen involve the convoy order in

>> conflict with either the beleaguered garrison rule or, more recently,

>> the rule that dislodged units do not affect provinces their attackers

>> come from, it seems natural that these situations would be important for

>> representing most kinds of iterative/recursive logical operations.

>>

>> Perhaps it would be helpful to correlate Diplomacy orders resolution to

>> a known Turing-complete inference engine like Prolog. If any set of

>> Prolog "rules" can be expressed as a set of Diplomacy orders with map

>> and units, then Diplomacy is Turing complete.

>>

>> Or perhaps a highly theoretical language like Unlambda

>> (http://www.eleves.ens.fr:8080/home/madore/programs/unla...) would

>> actually lend itself to this problem. Unlambda is Turing complete with

>> only 2 primitive functions and 1 operator, though it includes more

>> primitives for the pretense of convenience.

>>

>> It may also be that Diplomacy orders resolution could be more easily

>> proven equivalent to logic circuits. One can build a Turing complete

>> system entirely out of 2-input NAND gates and a clock; if some corollary

>> to the NAND operation can be found within the Diplomacy rules, problem

>> solved.

>>

>> Anybody else ever given this question some thought?

>>

>> --

>> Will Berry

>> Co-founder, Second Brain website hosting

>> http://www.secondbrainhosting.com/

>>

Read discussions in other Video Games categories

!