Are the Diplomacy rules Turing complete?

Toggle sidebar Toggle sidebar
G

Guest

Guest
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/unlambda/) 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/
 
G

Guest

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

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
 
G

Guest

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

> 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.
 
G

Guest

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

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/
 
G

Guest

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

"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
 
G

Guest

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

"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
 
G

Guest

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

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/
 
G

Guest

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

"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
 
G

Guest

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

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/
 
G

Guest

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

"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
 
G

Guest

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

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/
 
G

Guest

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

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/
 
G

Guest

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

"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
 
G

Guest

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

"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
 
G

Guest

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

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/unlambda/) 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/
>
 
G

Guest

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

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/
 
G

Guest

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

"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/unlambda/) 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/
>>
 
You must log in or register to reply here.

TRENDING THREADS

Latest posts

Moderators online

Share this page

COMPANY
RESOURCES
FOLLOW
Top Bottom